IP Library › Granted Patent US 12,413,243
Granted Patent B2
US 12,413,243 · App. 17/677,989 · Granted Sep 9, 2025

Systems, methods, and apparatus for dividing and compressing data

Inventors: Yang Seok Ki (Palo Alto, CA); Sungwook Ryu (Palo Alto, CA)
Assignee: SAMSUNG ELECTRONICS CO., LTD.
H03M7/40G06F16/217
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,413,243
App. No.
17/677,989
Granted
Sep 9, 2025
Kind
B2
Abstract

A method for data compression may include scanning input data, performing, based on the scanning, a compression operation to generate compressed data using the input data, finding, based on the scanning, a delimiter in the input data, and generating, based on a position of the delimiter in the input data, a portion of data using the compressed data. The input data may include a record, the delimiter indicates a boundary of the record, and the portion of data may include the record. The generating may include generating the portion of data based on a portion size. The portion size may be a default portion size. The portion size may be based on a default portion size and a length of a match in the input data.

Claims (44)

1. A method for data compression, the method comprising:

receiving input data in a first buffer;

finding a delimiter in the input data;

generating, based on a position of the delimiter in the input data, a first portion of data using a part of the input data, wherein a size of the first portion of data is determined based on the position of the delimiter in the input data, the size of the first portion of data is used to determine a size of a second portion of data in a second buffer; and

compressing the second portion of data.

2. The method of claim 1 , wherein:

the input data comprises a record;

the delimiter indicates a boundary of the record; and

the first portion of data comprises the record.

3. The method of claim 1 , wherein the position of the delimiter is in the part of the input data.

4. The method of claim 3 , wherein the generating the first portion of data comprises generating the first portion of data based on a subset of the part of the input data.

5. The method of claim 1 , wherein:

the part of the input data is a first part of the input data; and

the position of the delimiter is in a second part of the input data.

6. The method of claim 5 , wherein the generating the portion of data comprises generating the first portion of data based on the first part of the input data and the second part of the input data.

7. The method of claim 1 , wherein a size of the part of input data is based on a default portion size.

8. The method of claim 1 , wherein the second buffer is a window.

9. A method for data compression, the method comprising:

scanning input data;

performing, based on the scanning, a compression operation to generate compressed data using the input data;

finding, based on the scanning, a delimiter in the input data, wherein a size of a first portion of data is determined based on a position of the delimiter in the input data, the size of the first portion of data is used to determine a size of a second portion of data in a second buffer; and

generating, based on the position of the delimiter in the input data, the first portion of data using the compressed data.

10. The method of claim 9 , wherein

the input data comprises a record;

the delimiter indicates a boundary of the record; and

the portion of data comprises the record.

11. The method of claim 9 , wherein the generating comprises generating the first portion of data based on a portion size.

12. The method of claim 11 , wherein the portion size is a default portion size.

13. The method of claim 11 , wherein the portion size is based on a default portion size and a length of a delimiter in the input data.

14. The method of claim 9 , further comprising setting an indication based on a size of the compressed data.

15. The method of claim 14 , wherein the generating comprises generating the first portion of data based on the indication and the delimiter.

16. The method of claim 14 , wherein the scanning comprises scanning the input data based on the indication.

17. The method of claim 9 , wherein the scanning comprises scanning the input data based on the delimiter.

18. The method of claim 9 , wherein the performing comprises performing the compression operation based on the delimiter.

19. A system comprising:

a host comprising a memory for storing instructions; and

a processor configured to execute the instructions to:

perform a scanning operation on input data;

perform, based on the scanning operation, a data compression operation to generate compressed data using the input data;

find, based on the scanning operation, a delimiter in the input data; and

generate, based on the delimiter, a first portion of data using the compressed data, wherein a size of the first portion of data is determined based on a position of the delimiter in the input data, the size of the first portion of data is used to determine a size of a second portion of data in a second buffer.

20. The system of claim 19 , further comprising a device configured to receive the first portion of data from the host, the device comprising device logic configured to:

decompress the first portion of data to generate a decompressed portion of data; and

perform an operation on the decompressed portion of data.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Aug 17, 2023
From: KI, YANG SEOK; RYU, SUNGWOOK
To: SAMSUNG ELECTRONICS CO., LTD.
Reel/Frame 064628/0651 →
Continuity (5)
Provisional Application 63231710 · Aug 10, 2021
Provisional Application 63231715 · Aug 10, 2021
Provisional Application 63231709 · Aug 10, 2021
Provisional Application 63231711 · Aug 10, 2021
Related Publication 20230055535A1 · Feb 23, 2023
References Cited (155)
US 5396595A · Standley · 1995 [cited by examiner]
US 6351776B1 · O'Brien et al. · 2002 [cited by applicant]
US 6938204B1 · Hind · 2005 [cited by examiner]
US 7065618B1 · Ghemawat et al. · 2006 [cited by applicant]
US 7315923B2 · Retnamma et al. · 2008 [cited by applicant]
US 7447865B2 · Uppala · 2008 [cited by applicant]
US 7464247B2 · Uppala · 2008 [cited by applicant]
US 7571346B2 · Illowsky et al. · 2009 [cited by applicant]
US 7587569B2 · Uppala · 2009 [cited by applicant]
US 7640363B2 · Teodosiu et al. · 2009 [cited by applicant]
US 7681240B2 · Maheshwari et al. · 2010 [cited by applicant]
US 7716180B2 · Vermeulen et al. · 2010 [cited by applicant]
US 7921087B2 · Uppala · 2011 [cited by applicant]
US 8028106B2 · Bondurant et al. · 2011 [cited by applicant]
US 8195978B2 · Flynn et al. · 2012 [cited by applicant]
US 8214517B2 · Dubnicki et al. · 2012 [cited by applicant]
US 8380681B2 · Oltean et al. · 2013 [cited by applicant]
US 8468345B2 · Auradkar et al. · 2013 [cited by applicant]
US 8509315B1 · Petranovich · 2013 [cited by applicant]
US 8533231B2 · Aizman et al. · 2013 [cited by applicant]
US 8645335B2 · Gupta et al. · 2014 [cited by applicant]
US 8689279B2 · Basmov et al. · 2014 [cited by applicant]
US 8712978B1 · Shilane et al. · 2014 [cited by applicant]
US 8762743B2 · Cannon et al. · 2014 [cited by applicant]
US 8799238B2 · Eshghi et al. · 2014 [cited by applicant]
US 8799746B2 · Baker et al. · 2014 [cited by applicant]
US 8832043B2 · Koifman et al. · 2014 [cited by applicant]
US 8838541B2 · Camble et al. · 2014 [cited by applicant]
US 8886914B2 · Huang · 2014 [cited by applicant]
US 8909657B2 · Mensch et al. · 2014 [cited by applicant]
US 8954654B2 · Yu et al. · 2015 [cited by applicant]
US 8972672B1 · Wallace et al. · 2015 [cited by applicant]
US 9002907B2 · Martin et al. · 2015 [cited by applicant]
US 9110936B2 · Li et al. · 2015 [cited by applicant]
US 9165154B2 · Auradkar et al. · 2015 [cited by applicant]
US 9195851B1 · Chandra · 2015 [cited by applicant]
US 9201800B2 · Bolla et al. · 2015 [cited by applicant]
US 9253166B2 · Gauda · 2016 [cited by applicant]
US 9298951B2 · Barney et al. · 2016 [cited by applicant]
US 9400610B1 · Wallace et al. · 2016 [cited by applicant]
US 9426219B1 · Keyser · 2016 [cited by examiner]
US 9537650B2 · Auradkar et al. · 2017 [cited by applicant]
US 9823981B2 · Kalach et al. · 2017 [cited by applicant]
US 10187358B2 · Fahey et al. · 2019 [cited by applicant]
US 10296494B2 · Davis et al. · 2019 [cited by applicant]
US 10310765B1 · Laurence · 2019 [cited by applicant]
US 10318389B2 · Arslan et al. · 2019 [cited by applicant]
US 10346066B2 · Danilov et al. · 2019 [cited by applicant]
US 10348693B2 · Auradkar et al. · 2019 [cited by applicant]
US 10387673B2 · Surla et al. · 2019 [cited by applicant]
US 10394757B2 · Cheung et al. · 2019 [cited by applicant]
US 10552062B2 · Ki · 2020 [cited by applicant]
US 10572161B2 · Subramanian et al. · 2020 [cited by applicant]
US 10608784B2 · Yanovsky et al. · 2020 [cited by applicant]
US 10664165B1 · Faibish et al. · 2020 [cited by applicant]
US 10776321B1 · Balcha et al. · 2020 [cited by applicant]
US 10809945B2 · Patwardhan et al. · 2020 [cited by applicant]
US 10838990B1 · Shilane et al. · 2020 [cited by applicant]
US 10852989B1 · Patel et al. · 2020 [cited by applicant]
US 10949303B2 · Kohli · 2021 [cited by applicant]
US 10977136B2 · Patel et al. · 2021 [cited by applicant]
US 11017127B2 · Secatch et al. · 2021 [cited by applicant]
US 11023318B1 · Volkov et al. · 2021 [cited by applicant]
US 11177012B1 · Avraham et al. · 2021 [cited by applicant]
US 12106455B2 · Chiyoda et al. · 2024 [cited by applicant]
US 20030088783A1 · DiPierro · 2003 [cited by applicant]
US 20040049700A1 · Yoshida · 2004 [cited by applicant]
US 20060020605A1 · Chan et al. · 2006 [cited by applicant]
US 20060182274A1 · Nicolai et al. · 2006 [cited by applicant]
US 20090132760A1 · Flynn et al. · 2009 [cited by applicant]
US 20120089775A1 · Ranade et al. · 2012 [cited by applicant]
US 20120159098A1 · Cheung et al. · 2012 [cited by applicant]
US 20120254689A1 · Resch · 2012 [cited by applicant]
US 20140250119A1 · Bhattiprolu et al. · 2014 [cited by applicant]
US 20140281146A1 · Horn · 2014 [cited by applicant]
US 20150378616A1 · Khadiwala et al. · 2015 [cited by applicant]
US 20150379072A1 · Dirac et al. · 2015 [cited by applicant]
US 20150379425A1 · Dirac · 2015 [cited by examiner]
US 20170185625A1 · Cheru et al. · 2017 [cited by applicant]
US 20180024746A1 · Jagadeesh et al. · 2018 [cited by applicant]
US 20180026655A1 · Gopal et al. · 2018 [cited by applicant]
US 20180152733A1 · Karaje et al. · 2018 [cited by applicant]
US 20180267856A1 · Hayasaka et al. · 2018 [cited by applicant]
US 20180285014A1 · Li et al. · 2018 [cited by applicant]
US 20180314710A1 · Peloski · 2018 [cited by applicant]
US 20180365102A1 · Li et al. · 2018 [cited by applicant]
US 20190005262A1 · Surla et al. · 2019 [cited by applicant]
US 20190007493A1 · Gray et al. · 2019 [cited by applicant]
US 20190196907A1 · Khan et al. · 2019 [cited by applicant]
US 20200042500A1 · Li et al. · 2020 [cited by applicant]
US 20200117362A1 · McCarthy et al. · 2020 [cited by applicant]
US 20200117518A1 · Costa et al. · 2020 [cited by applicant]
US 20200134049A1 · Bassov et al. · 2020 [cited by applicant]
US 20200162101A1 · Beckman · 2020 [cited by examiner]
US 20200201789A1 · Durham et al. · 2020 [cited by applicant]
US 20200241960A1 · Yanovsky et al. · 2020 [cited by applicant]
US 20200274855A1 · Xin · 2020 [cited by applicant]
US 20200296100A1 · Prahlad et al. · 2020 [cited by applicant]
US 20200341690A1 · Saad et al. · 2020 [cited by applicant]
US 20200372163A1 · Chung · 2020 [cited by applicant]
US 20210004166A1 · Luo et al. · 2021 [cited by applicant]
US 20210011799A1 · Chen et al. · 2021 [cited by applicant]
US 20210019067A1 · Miller et al. · 2021 [cited by applicant]
US 20210064477A1 · Patel et al. · 2021 [cited by applicant]
US 20210064582A1 · Wang et al. · 2021 [cited by applicant]
US 20210072899A1 · Furuta et al. · 2021 [cited by applicant]
US 20210096962A1 · Yang et al. · 2021 [cited by applicant]
US 20210200469A1 · Kim et al. · 2021 [cited by applicant]
US 20210232310A1 · Pitchumani et al. · 2021 [cited by applicant]
US 20220188028A1 · Mesnier et al. · 2022 [cited by applicant]
US 20220276785A1 · Deguchi et al. · 2022 [cited by applicant]
US 20230011742A1 · Merritt · 2023 [cited by applicant]
CN 105242879A · 2016 [cited by applicant]
WO 2013136584A1 · 2013 [cited by applicant]
WO 2020186081A1 · 2020 [cited by applicant]
WO 2020189081A1 · 2020 [cited by applicant]
Adams, lan F. et al., “Respecting the Block Interface-Computational Storage Using Virtual Objects,” USENIX Association, 11th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 19), (https://www.usenix… [cited by applicant]
Chen, Shengbo, et al., “When Queueing Meets Coding: Optimal-Latency Data Retrieving Scheme in Storage Clouds”, IEEE INFOCOM 2014—IEEE Conference on Computer Communications, 2014, pp. 1042-1050. [cited by applicant]
European Extended Search Report for Application No. 22186187.5, mailed Dec. 15, 2022. [cited by applicant]
European Extended Search Report for Application No. 22187681.6, mailed Dec. 19, 2022. [cited by applicant]
European Extended Search Report for Application No. 22187683.2, mailed Dec. 19, 2022. [cited by applicant]
European Extended Search Report for Application No. 22189731.7, mailed Jan. 3, 2023. [cited by applicant]
Liang, Guanfeng et al., “Fast Cloud: Pushing the Envelope on Delay Performance of Cloud Storage With Coding” IEEE/ACM Transactions on Networking, vol. 22, No. 6, 2014, pp. 2012-2025. [cited by applicant]
Liang, Guanfeng et al., “TOFEC: Achieving Optimal Throughput-Delay Trade-Off of Cloud Storage Using Erasure Codes”, IEEE Infocom 2014—IEEE Conference on Computer Communications, 2014, pp. 826-834. [cited by applicant]
Mukhopadhyay, Sinjoni et al., “Efficient Reconstruction Techniques for Disaster Recovery in Secret-Split Datastores”, 2018 IEEE 26th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecomm… [cited by applicant]
Pritchard, Stephen, “Computational Storage: What is it and What are Its Key Use Cases?”, (https://www.computerweekly.com/feature/Computational-storage-What-is-it-and-what-are-its-key-use-cases), 2020, retrieved 2022, 7 … [cited by applicant]
Wikipedia, “Block Cipher”, (https://en.wikipedia.org/w/index.php?title=Block_ciphe%20&oldid=1036074863), retrieved 2022, 17 pages. [cited by applicant]
Wikipedia, “Data Deduplication”, (https:/en.wikipedia.org/w/index.php?title=Data_deduplication&oldid=1025113325), retrieved 2022, 7 pages. [cited by applicant]
Wu, Xingbo, “Supporting Efficient Large-Scale Key-Value Systems with an Optimized Storage Hierarchy”, Dissertation, The University of Texas at Arlington, 2018, 123 pages. [cited by applicant]
Zhang, Xingyu et al., “Data Deduplication Cluster Based on Similarity-Locality Approach”, 2013 IEEE International Conference on Green Computing and Communications and IEEE Internet of Things and IEEE Cyber, Physical and… [cited by applicant]
Zuo, Chunxue et al., “PFCG: Improving the Restore Performance of Package Datasets in Deduplication Systems”, 2018 IEEE 36th International Conference on Computer Design (ICCD), 2018, pp. 553-560. [cited by applicant]
Zuo, Chunxue et al., “RepEC-Duet: Ensure High Reliability and Performance for Deduplicated and Delta-Compressed Storage Systems”, 2019 IEEE 37th International Conference on Computer Design (ICCD), 2019, pp. 190-198. [cited by applicant]
Office Action for U.S. Appl. No. 17/572,621, mailed May 4, 2023. [cited by applicant]
Office Action for U.S. Appl. No. 17/591,597, mailed May 25, 2023. [cited by applicant]
Office Action for U.S. Appl. No. 17/666,548, mailed Jul. 19, 2023. [cited by applicant]
Final Office Action for U.S. Appl. No. 17/572,621, mailed Oct. 10, 2023. [cited by applicant]
Final Office Action for U.S. Appl. No. 17/666,548, mailed Dec. 19, 2023. [cited by applicant]
Office Action for U.S. Appl. No. 17/677,991, mailed Sep. 27, 2023. [cited by applicant]
Advisory Action for U.S. Appl. No. 17/572,621, mailed Dec. 28, 2023. [cited by applicant]
Anisimov, Anatoly V. et al., “Variable-Length Prefix Codes With Multiple Delimiters,” IEEE Transactions on Information Theory, vol. 63, No. 5, May 2017, pp. 2885-2895. [cited by applicant]
Corrected Notice of Allowability for U.S. Appl. No. 17/677,991, mailed Apr. 10, 2024. [cited by applicant]
Final Office Action for U.S. Appl. No. 17/591,597, mailed Feb. 23, 2024. [cited by applicant]
Notice of Allowance for U.S. Appl. No. 17/677,991, mailed Mar. 5, 2024. [cited by applicant]
Corrected Notice of Allowability for U.S. Appl. No. 17/677,991, mailed Jun. 13, 2024. [cited by applicant]
Office Action for U.S. Appl. No. 17/572,621, mailed Jun. 12, 2024. [cited by applicant]
Office Action for U.S. Appl. No. 17/591,597, mailed Jun. 18, 2024. [cited by applicant]
Corrected Notice of Allowability for U.S. Appl. No. 17/677,991, mailed May 8, 2024. [cited by applicant]
Office Action for U.S. Appl. No. 17/666,548, mailed May 17, 2024. [cited by applicant]
European Office Action for Application No. 22189257.3, mailed Sep. 25, 2024. [cited by applicant]
Final Office Action for U.S. Appl. No. 17/572,621, mailed Oct. 31, 2024. [cited by applicant]
Final Office Action for U.S. Appl. No. 17/591,597, mailed Jan. 13, 2025. [cited by applicant]
Corrected Notice of Allowability for U.S. Appl. No. 17/677,991, mailed Jul. 22, 2024. [cited by applicant]
Notice of Allowance for U.S. Appl. No. 17/666,548, mailed Apr. 8, 2025. [cited by applicant]
Office Action for U.S. Appl. No. 17/591,597, mailed Jun. 26, 2025. [cited by applicant]
Office Action for U.S. Appl. No. 17/572,621, mailed Aug. 6, 2025. [cited by applicant]