IP Library › Granted Patent US 12,284,261
Granted Patent B2
US 12,284,261 · App. 18/623,625 · Granted Apr 22, 2025

Systems and methods for compressing digital data

Inventors: Kirti Agarwal (Wood Ridge, CA); Behrooz Badii (Westport, CT); Nathaniel Joseph Oorloff (Brooklyn, NY); Jeffrey Tsvi Pinner (Tiburon, CA); Yann Thomas Ramin (Folsom, CA)
Assignee: Bitdrift, Inc.
H04L69/04H04L47/38H04L51/06
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,284,261
App. No.
18/623,625
Granted
Apr 22, 2025
Kind
B2
Abstract

A computing system configured to (i) obtain a set of key-value pairs, wherein each key-value pair corresponds to a respective timestamp in a period of time, (ii) for at least one timestamp in the given period of time: (a) identify a first subset of the key-value pairs corresponding to the timestamp, (b) sort the first subset, and (c) generate a subset of compression values for the sorted first subset, (iii) for at least one key: (a) identify a second subset of the key-value pairs corresponding to the key, (b) sort the second subset, and (c) generate a subset of compression values for the sorted second subset, and (iv) store a set of compression values comprising (a) the subset of compression values that is generated for each of the at least one timestamp and (b) the subset of compression values that is generated for each of the at least one key.

Claims (55)

1. A computing system comprising:

at least one processor;

at least one non-transitory computer-readable medium; and

program instructions stored on the non-transitory computer-readable medium that are executable by the at least one processor such that the computing system is configured to:

obtain a set of key-value pairs for a given period of time, wherein each key-value pair of the set of key-value pairs corresponds to a respective timestamp in the given period of time;

for at least one respective timestamp in the given period of time:

identify a first subset of the set of key-value pairs that corresponds to the respective timestamp;

sort the first subset of key-value pairs according to value; and

generate a respective subset of compression values for the sorted first subset of key-value pairs;

for at least one respective key:

identify a second subset of the set of key-value pairs that corresponds to the respective key;

sort the second subset of key-value pairs according to timestamp; and

generate a respective subset of compression values for the sorted second subset of key-value pairs; and

store a set of compression values comprising (i) the respective subset of compression values that is generated for each of the at least one respective timestamp and (ii) the respective subset of compression values that is generated for each of the at least one respective key.

2. The computing system of claim 1 , wherein the program instructions that are executable by the at least one processor such that the computing system is configured to obtain the set of key-value pairs comprise program instructions that are executable by the at least one processor such that the computing system is configured to (i) retrieve the set of key-value pairs from a data storage repository that is accessible by the computing system, (ii) receive the set of key-value pairs from one or more other computing systems, or both.

3. The computing system of claim 1 , wherein the computing system comprises a first computing system, the first computing system further comprising program instructions stored on the at least one non-transitory computer-readable medium that are executable by the at least one processor such that the first computing system is configured to:

transmit the set of compression values to a second computing system.

4. The computing system of claim 3 , wherein the first computing system comprises a server computing system, and wherein the second computing system comprises a client device.

5. The computing system of claim 1 , wherein key-value pairs of the set of key-value pairs correspond to digital metrics, with keys of the key-value pairs comprising metric names and values of the key-value pairs comprising metric values.

6. The computing system of claim 1 , wherein the respective subset of compression values for the sorted first subset of key-value pairs comprises compression values determined based on respective differences between respective adjacent values in the sorted first subset of key-value pairs.

7. The computing system of claim 6 , wherein at least one of the respective adjacent values in the sorted first subset of key-value pairs comprises a compression value.

8. The computing system of claim 1 , wherein compression values of the respective subset of compression values for the sorted second subset of key-value pairs comprise delta compression values determined based on respective differences between respective adjacent values in the sorted second subset of key-value pairs.

9. The computing system of claim 8 , wherein at least one of the respective adjacent values in the sorted second subset of key-value pairs comprises a compression value.

10. A method implemented by a computing system, the method comprising:

obtaining a set of key-value pairs for a given period of time, wherein each key-value pair of the set of key-value pairs corresponds to a respective timestamp in the given period of time;

for at least one respective timestamp in the given period of time:

identifying a first subset of the set of key-value pairs that corresponds to the respective timestamp;

sorting the first subset of key-value pairs according to value; and

generating a respective subset of compression values for the sorted first subset of key-value pairs;

for at least one respective key:

identifying a second subset of the set of key-value pairs that corresponds to the respective key;

sorting the second subset of key-value pairs according to timestamp; and

generating a respective subset of compression values for the sorted second subset of key-value pairs; and

storing a set of compression values comprising (i) the respective subset of compression values that is generated for each of the at least one respective timestamp and (ii) the respective subset of compression values that is generated for each of the at least one respective key.

11. The method of claim 10 , wherein obtaining the set of key-value pairs comprises (i) retrieving the set of key-value pairs from a data storage repository that is accessible by the computing system, (ii) receiving the set of key-value pairs from one or more other computing systems, or both.

12. The method of claim 10 , wherein the computing system comprises a first computing system, the method further comprising:

transmitting the set of compression values to a second computing system.

13. The method of claim 12 , wherein the first computing system comprises a server computing system, and wherein the second computing system comprises a client device.

14. The method of claim 10 , wherein key-value pairs of the set of key-value pairs correspond to digital metrics, with keys of the key-value pairs comprising metric names and values of the key-value pairs comprising metric values.

15. The method of claim 10 , wherein the respective subset of compression values for the sorted first subset of key-value pairs comprises compression values determined based on respective differences between respective adjacent values in the sorted first subset of key-value pairs.

16. The method of claim 15 , wherein at least one of the respective adjacent values in the sorted first subset of key-value pairs comprises a compression value.

17. The method of claim 10 , wherein compression values of the respective subset of compression values for the sorted second subset of key-value pairs comprise delta compression values determined based on respective differences between respective adjacent values in the sorted second subset of key-value pairs.

18. The method of claim 17 , wherein at least one of the respective adjacent values in the sorted second subset of key-value pairs comprises a compression value.

19. A non-transitory computer-readable medium, wherein the non-transitory computer-readable medium is provisioned with program instructions that, when executed by at least one processor, cause a computing system to:

obtain a set of key-value pairs for a given period of time, wherein each key-value pair of the set of key-value pairs corresponds to a respective timestamp in the given period of time;

for at least one respective timestamp in the given period of time:

identify a first subset of the set of key-value pairs that corresponds to the respective timestamp;

sort the first subset of key-value pairs according to value; and

generate a respective subset of compression values for the sorted first subset of key-value pairs;

for at least one respective key:

identify a second subset of the set of key-value pairs that corresponds to the respective key;

sort the second subset of key-value pairs according to timestamp; and

generate a respective subset of compression values for the sorted second subset of key-value pairs; and

store a set of compression values comprising (i) the respective subset of compression values that is generated for each of the at least one respective timestamp and (ii) the respective subset of compression values that is generated for each of the at least one respective key.

20. The non-transitory computer-readable medium of claim 19 , wherein the program instructions that, when executed by the at least one processor, cause the computing system to obtain the set of key-value pairs comprise program instructions that, when executed by the at least one processor, cause the computing system to (i) retrieve the set of key-value pairs from a data storage repository that is accessible by the computing system, (ii) receive the set of key-value pairs from one or more other computing systems, or both.

Assignments (3)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Apr 2, 2024
From: AGARWAL, KIRTI; BADII, BEHROOZ; OORLOFF, NATHANIEL JOSEPH; PINNER, JEFFREY TSVI; RAMIN, YANN THOMAS
To: LYFT, INC.
Reel/Frame 066974/0030 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Apr 2, 2024
From: LYFT, INC.
To: CONTRAST LABS, INC.
Reel/Frame 066974/0095 →
CHANGE OF NAME Recorded Apr 2, 2024
From: CONTRAST LABS, INC.
To: BITDRIFT, INC.
Reel/Frame 066974/0136 →
Continuity (4)
Continuation 18047880 · Oct 19, 2022
Continuation 17932882 · Sep 16, 2022
Continuation 17410921 · Aug 24, 2021
Related Publication 20240244121A1 · Jul 18, 2024
References Cited (82)
US 8018866B1 · Kasturi et al. · 2011 [cited by applicant]
US 9143393B1 · Bird et al. · 2015 [cited by applicant]
US 20050232504A1 · Suzuki et al. · 2005 [cited by applicant]
US 20080077607A1 · Gatawood et al. · 2008 [cited by applicant]
US 20080240226A1 · Okmianski et al. · 2008 [cited by applicant]
US 20090157712A1 · De Peuter et al. · 2009 [cited by applicant]
US 20110310051A1 · Souchkov · 2011 [cited by examiner]
US 20110313980A1 · Faerber et al. · 2011 [cited by applicant]
US 20120150877A1 · Ramamurthy et al. · 2012 [cited by applicant]
US 20120191670A1 · Kennedy et al. · 2012 [cited by applicant]
US 20120265723A1 · Arndt et al. · 2012 [cited by applicant]
US 20130018889A1 · Jagmohan et al. · 2013 [cited by applicant]
US 20130254197A1 · Hay et al. · 2013 [cited by applicant]
US 20140149605A1 · Annamalaisami et al. · 2014 [cited by applicant]
US 20150032757A1 · Barykin et al. · 2015 [cited by applicant]
US 20150178305A1 · Mueller et al. · 2015 [cited by applicant]
US 20150347426A1 · Dickie et al. · 2015 [cited by applicant]
US 20160204799A1 · Ackerman et al. · 2016 [cited by applicant]
US 20160210332A1 · Milton · 2016 [cited by examiner]
US 20160246811A1 · Ackerman et al. · 2016 [cited by applicant]
US 20160381188A1 · Fekri et al. · 2016 [cited by applicant]
US 20170004158A1 · Faerber et al. · 2017 [cited by applicant]
US 20170031944A1 · Faerber et al. · 2017 [cited by applicant]
US 20170279932A1 · Schurman et al. · 2017 [cited by applicant]
US 20180039902A1 · Jeffries · 2018 [cited by applicant]
US 20180131516A1 · Meng · 2018 [cited by examiner]
US 20180139458A1 · Wang et al. · 2018 [cited by applicant]
US 20180173372A1 · Greenspan et al. · 2018 [cited by applicant]
US 20190057120A1 · D'Halluin · 2019 [cited by examiner]
US 20190138927A1 · Jeffries · 2019 [cited by applicant]
US 20190155925A1 · Giannikis et al. · 2019 [cited by applicant]
US 20200073868A1 · Delamare et al. · 2020 [cited by applicant]
US 20200250193A1 · Pham et al. · 2020 [cited by applicant]
US 20200274550A1 · St. John · 2020 [cited by applicant]
US 20200311029A1 · Demoor · 2020 [cited by examiner]
US 20200311132A1 · Demoor · 2020 [cited by examiner]
US 20200409566A1 · Demoor · 2020 [cited by examiner]
US 20210034598A1 · Arye et al. · 2021 [cited by applicant]
US 20210064585A1 · Chen · 2021 [cited by examiner]
US 20210119641A1 · Alligand · 2021 [cited by applicant]
US 20210152364A1 · Beecham · 2021 [cited by examiner]
US 20210160080A1 · Struttmann et al. · 2021 [cited by applicant]
US 20210342323A1 · Valaguru · 2021 [cited by examiner]
US 20210373777A1 · Dubucq · 2021 [cited by examiner]
US 20210373983A1 · Dubucq · 2021 [cited by examiner]
US 20210373998A1 · Dhuse · 2021 [cited by examiner]
US 20210373999A1 · Dhuse · 2021 [cited by examiner]
US 20220043585A1 · Senyuk · 2022 [cited by examiner]
CN 101311930A · 2008 [cited by applicant]
CN 101311930B · 2012 [cited by applicant]
CN 111782660A · 2020 [cited by applicant]
WO 2019152346A1 · 2019 [cited by applicant]
Graphite—Scalable Realtime Graphing. http://graphite.wikidot.com/. Accessed Mar. 20, 2015. [cited by applicant]
Influxdb.com: InfluxDB—Open Source Time Series, Metrics, and Analytics Database. http://influxdb.com/. Accessed Mar. 20, 2015. [cited by applicant]
L. Abraham, J. Allen, 0. Barykin, V. R. Borkar, B. Chopra, C. Gerea, D. Merl, J. Metzler, D. Reiss, S. Subramanian, J. L. Wiener, and 0. Zed. Scuba: Diving into Data at Facebook. PVLDB, 6(11):1057-1067, 2013. [cited by applicant]
E. B. Boyer, M. C. Broomfield, and T. A. Perrotti. GlusterFS One Storage Server to Rule Them All. Technical report, Los Alamos National Laboratory (LANL), 2012. [cited by applicant]
N. Bronson, T. Lento, and J. L. Wiener. Open Data Challenges at Facebook. In Workshops Proceedings of the 31st International Conference on Data Engineering Workshops, ICDE Seoul, Korea. IEEE, 2015. [cited by applicant]
T. D. Chandra, R. Griesemer, and J. Redstone. Paxos Made Live: An Engineering Perspective. In Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, pp. 398-407. ACM, 2007. [cited by applicant]
H. Chen, J. Li, and P. Mahapatra. RACE: Time Series Compression with Rate Adaptivity and Error Bound for Sensor Networks. In Mobile Ad-hoc and Sensor Systems, 2004 IEEE International Conference on, pp. 124-133. IEEE, 20… [cited by applicant]
B. Hu, Y. Chen, and E. J. Keogh. Time Series Classification under More Realistic Assumptions. In SOM, pp. 578-586, 2013. [cited by applicant]
E. Keogh, K. Chakrabarti, M. Pazzani, and S. Mehrotra. Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases. ACM SIGMOD Record, 30(2):151-162, 2001. [cited by applicant]
E. Keogh, S. Lonardi, and B. Chiu. Finding Surprising Patterns in a Time Series Database in Linear Time and Space. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining,… [cited by applicant]
E. Keogh, S. Lonardi, and C. A. Ratanamahatana. Towards Parameter-Free Data Mining. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 206-215. ACM, 2004. [cited by applicant]
E. Keogh and C. A. Ratanamahatana. Exact Indexing of Dynamic Time Warping. Knowledge and information systems, 7(3):358-386, 2005. [cited by applicant]
I. Lazaridis and S. Mehrotra. Capturing Sensor-Generated Time Series with Quality Guarantees. In Data Engineering, 2003. Proceedings. 19th International Conference on, pp. 429-440. IEEE, 2003. [cited by applicant]
L. Lamport. Paxos Made Simple. SIGACT News, 32(4):51-58, Dec. 2001. [cited by applicant]
J. Lin, E. Keogh, S. Lonardi, and B. Chiu. A Symbolic Representation of Time Series, with Implications for Streaming Algorithms. In Proceedings of the 8th ACM SIG MOD workshop on Research issues in data mining and knowl… [cited by applicant]
J. Lin, E. Keogh, S. Lonardi, J. P. Lankford, and D. M. Nystrom. Visually Mining and Monitoring Massive Time Series. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining… [cited by applicant]
P. Lindstrom and M. Isenburg. Fast and Efficient Compression of Floating-Point Data. Visualization and Computer Graphics, IEEE Transactions on, 12(5):1245-1250, 2006. [cited by applicant]
A. Mueen, S. Nath, and J. Liu. Fast Approximate Correlation for Massive Time-Series Data. In Proceedings of the 2010 ACM SIG MOD International Conference on Management of data, pp. 171-182. ACM, 2010. [cited by applicant]
R. Nishtala. Learning from Mistakes and Outages at Facebook. Presented at SREcon16, Santa Clara, CA, Mar. 2015. [cited by applicant]
R. Nishtala, H. Fugal, S. Grimm, M. Kwiatkowski,H. Lee, H. C. Li, R. McElroy, M. Paleczny, D. Peek, P. Saab, et al. Scaling Memcache at Facebook. In nsdi, vol. 13, pp. 385-398, 2013. [cited by applicant]
J. Parikh. Keynote speech. Presented at @Scale Conference, San Francisco, CA, Sep. 2014. [cited by applicant]
K. Pearson. Note on regression and inheritance in the case of two parents. Proceedings of the Royal Society of London, 58(347-352):240-242, 1895. [cited by applicant]
F. Petitjean, G. Forestier, G. Webb, A. Nicholson, Y. Chen, and E. Keogh. Dynamic Time Warping Averaging of Time Series Allows Faster and More Accurate Classification. In IEEE International Conference on Data Mining, 20… [cited by applicant]
T. Rakthanmanon, B. Campana, A. Mueen, G. Batista, B. Westover, Q. Zhu, J. Zakaria, and E. Keogh. Searching and Mining Trillions of Time Series Subsequences Under Dynamic Time Warping. In Proceedings of the 18th ACM SIG… [cited by applicant]
P. Ratanaworabhan, J. Ke, and M. Burtscher. Fast Lossless Compression of Scientific Floating-Point Data. In DCC, pp. 133-142. IEEE Computer Society, 2006. [cited by applicant]
A. Thusoo, J. S. Sarma, N. Jain, Z. Shao, P. Chakka, S. Anthony, H. Liu, P. Wyckoff, and R. Murthy. Hive: A Warehousing Solution Over a Map-ReduceFramework. PVLDB, 2(2):1626-1629, 2009. [cited by applicant]
T. W. Wlodarczyk. Overview of Time Series Storage and Processing in a Cloud Environment. In Proceedings of the 2012 IEEE 4th International Conference on Cloud Computing Technology and Science (CloudCom), pp. 625-628. IE… [cited by applicant]
Wikipedia: The Free Encyclopedia; “Finite-state transducer”; Date downloaded Oct. 12, 2021. [cited by applicant]
2-Dimensional Line Graph Examples: SIMS Sensory Quality Panel Software Cloud Systems—Evaluation Testing Software Systems; Date downloaded Oct. 12, 2021. [cited by applicant]
International Search Report & Written Opinion as received in PCT /US2022/075201 dated Dec. 21, 2022. [cited by applicant]