Compressing digital metrics for transmission across a network utilizing a graph-based compression dictionary and time slice delta compression

Patent metadata

Field	Value
Publication number	US-11463559-B1
Application number	US-202117410921-A
Country	US
Kind code	B1
Filing date	Aug 24, 2021
Priority date	Aug 24, 2021
Publication date	Oct 4, 2022
Grant date	Oct 4, 2022

Abstract

The present disclosure relates to systems, methods, and non-transitory computer-readable media that generate compressed metric data for digital metrics utilizing a graph-based compression dictionary and time slice compression. For instance, the disclosed systems can utilize a dynamically modifiable graph-based compression dictionary to generate compressed metric label identifiers for metric labels of digital metrics. The graph-based compression dictionary can include nodes and edges corresponding to metric label segments and metric label identifier values, respectively. The disclosed systems can traverse the graph-based compression dictionary using a metric label to determine the corresponding compressed metric label identifier. The disclosed systems can further generate delta compression values for the metric values of the digital metrics. For instance, the disclosed systems can compare metric values within a single time slice (e.g., a time stamp) to generate corresponding delta compression values. In some cases, the disclosed systems further compare the metric values across a time window.

First claim

What is claimed is:

1. A computer-implemented method comprising:
generating a set of compressed metric data from a set of digital metrics comprising a plurality of metric values and a plurality of metric labels by:
generating, utilizing a graph-based compression dictionary shared between a first computing device and a second computing device, compressed metric label identifiers based on the plurality of metric labels;
sorting the set of digital metrics in a sequence based on the plurality of metric values; and
generating delta compression values according to the sequence using the sorted plurality of metric values; and

transmitting the set of compressed metric data comprising the compressed metric label identifiers and the delta compression values from the first computing device to the second computing device across a network.

2. The computer-implemented method of claim 1 , wherein the graph-based compression dictionary comprises a plurality of nodes corresponding to metric label segments and a plurality of edges corresponding to metric label identifier values.

3. The computer-implemented method of claim 2 , further comprising:
receiving, at the first computing device, a dictionary update indicating at least one of a node or an edge to modify within the graph-based compression dictionary; and
modifying, at the first computing device, the graph-based compression dictionary in accordance with the dictionary update.

4. The computer-implemented method of claim 2 , further comprising:
determining, at the first computing device, one or more metric labels currently unrepresented within the graph-based compression dictionary;
generating, at the first computing device, a dictionary update indicating one or more nodes and one or more edges to add to the graph-based compression dictionary to represent the one or more metric labels; and
transmitting the dictionary update to the second computing device.

5. The computer-implemented method of claim 2 , wherein generating the compressed metric label identifiers based on the plurality of metric labels and utilizing the graph-based compression dictionary comprises, for a metric label:
traversing the plurality of nodes of the graph-based compression dictionary using segments of the metric label;
determining one or more metric label identifier values corresponding to one or more edges between traversed nodes; and
generating a compressed metric label identifier for the metric label using the one or more metric label identifier values.

6. The computer-implemented method of claim 1 , wherein generating the delta compression values according to the sequence using the sorted plurality of metric values comprises:
determining that a metric value and a preceding metric value from the sorted plurality of metric values include a same value; and
generating a delta compression value for the metric value using a single bit of data to indicate that the metric value and the preceding metric value include the same value.

7. The computer-implemented method of claim 1 , wherein generating the delta compression values according to the sequence using the sorted plurality of metric values comprises:
determining a value difference between a metric value and a preceding metric value from the sorted plurality of metric values; and
generating a delta compression value for the metric value to include a set of bits representing the value difference.

8. The computer-implemented method of claim 1 , wherein generating the compressed metric label identifiers based on the plurality of metric labels utilizing the graph-based compression dictionary comprises generating the compressed metric label identifiers based on the plurality of metric labels utilizing a finite-state transducer.

9. The computer-implemented method of claim 1 , further comprising:
generating, at the first computing device, a metric blocklist indicating a plurality of digital metrics that are to be withheld from transmission across the network;
generating, at the first computing device, a compressed metric blocklist that includes a plurality of compressed metric label identifiers corresponding to the plurality of digital metrics; and
transmitting the compressed metric blocklist from the first computing device to another computing device across the network.

10. The computer-implemented method of claim 1 , further comprising generating an additional set of compressed metric data from an additional set of digital metrics comprising a set of metric values and a set of metric labels that span a window of time by:
determining, utilizing the graph-based compression dictionary, additional compressed metric label identifiers based on the set of metric labels;
generating a first set of delta compression values for the additional set of digital metrics by determining, for each digital metric, a value difference between pairs of metric values across the window of time; and
generating a second set of delta compression values for the additional set of digital metrics by determining differences between pairs of delta compression values from the first set of delta compression values.

11. A non-transitory computer-readable medium storing instructions thereon that, when executed by at least one processor, cause a computing device to:
generating a set of compressed metric data from a set of digital metrics comprising a plurality of metric values and a plurality of metric labels by:
generating, utilizing a graph-based compression dictionary shared between a first computing device and a second computing device, compressed metric label identifiers based on the plurality of metric labels;
sorting the set of digital metrics in a sequence based on the plurality of metric values; and
generating delta compression values according to the sequence using the sorted plurality of metric values; and

transmitting the set of compressed metric data comprising the compressed metric label identifiers and the delta compression values from the first computing device to the second computing device across a network.

12. The non-transitory computer-readable medium of claim 11 , wherein the graph-based compression dictionary comprises a plurality of nodes corresponding to metric label segments and a plurality of edges corresponding to metric label identifier values.

13. The non-transitory computer-readable medium of claim 12 , further comprising instructions that, when executed by the at least one processor, cause the computing device to:
receive, at the first computing device, a dictionary update indicating at least one of a node or an edge to modify within the graph-based compression dictionary; and
modify, at the first computing device, the graph-based compression dictionary in accordance with the dictionary update.

14. The non-transitory computer-readable medium of claim 12 , further comprising instructions that, when executed by the at least one processor, cause the computing device to:
determine, at the first computing device, one or more metric labels currently unrepresented within the graph-based compression dictionary;
generate, at the first computing device, a dictionary update indicating one or more nodes and one or more edges to add to the graph-based compression dictionary to represent the one or more metric labels; and
transmit the dictionary update to the second computing device.

15. The non-transitory computer-readable medium of claim 12 , wherein generating the compressed metric label identifiers based on the plurality of metric labels and utilizing the graph-based compression dictionary comprises, for a metric label:
traversing

Assignees

• Lyft Inc

Inventors

• Agarwal Kirti
• Badii Behrooz
• Oorloff Nathaniel Joseph
• Pinner Jeffrey Tsvi
• Ramin Yann Thomas

Classifications

• H04L67/5651 Primary

  Reducing the amount or size of exchanged application data · CPC title

• H04L47/38

  by adapting coding or compression rate · CPC title

• H04L69/04 Primary

  Protocols for data compression, e.g. ROHC · CPC title

• H04L51/06

  Message adaptation to terminal or network requirements · CPC title

• H03M7/6052

  Synchronisation of encoder and decoder · CPC title