Graph-based compression of data records
View Patent ↗In general, embodiments of the present invention provide systems, methods and computer readable media for data record compression using graph-based techniques.
1. A computer-implemented method for generating a compressed list of impression data records, the method comprising:
receiving, by a processor, a set of impression data records describing a sequence of consumer behavior instances collected during a time window, wherein the set of impression data records is associated with a particular consumer;
generating, by the processor, a directed link graph representing the consumer behavior instances;
generating, by the processor, the compressed list of the impression data records based at least in part on properties of the directed link graph;
determining, by the processor, a first component of the set of impression data records to be an index component;
generating, by the processor, a sorted list of the set of impression data records by ordering the set of impression data records using a respective value of the index component within each impression data record;
identifying, by the processor, a set of unique index component values within the sorted list of the set of impression data records; and
generating, by the processor, an ordered list of the set of unique index component values using the sorted list of the set of impression data records.
2. The method of claim 1 , wherein each impression data record of the set of impression data records comprises a plurality of data components.
3. The method of claim 2 , wherein the plurality of data components includes one or more of an identifier of the promotion, a date on which the interaction occurred, and a position of the promotion within the impression display layout.
4. The method of claim 1 , wherein the graph nodes respectively represent the consumer behavior instances and each of the graph edges connecting a pair of the nodes represents a hyperlink between the nodes.
5. The method of claim 1 , further comprising generating, by the processor, an index value list by replacing each impression data record of the set of impression data records with its respective position in the ordered list of the set of unique index component values.
6. The method of claim 5 , further comprising generating, by the processor, an encoded index value list by calculating an encoded index value for each element of the index value list.
7. The method of claim 6 , wherein calculating the encoded index value for each element of the index value list comprises subtracting, by the processor, a value from a previous value in the index value list to produce a difference value; and
in instances where the difference value is positive, multiplying, by the processor, the difference by an integer;
in instances where the difference value is negative, multiplying, by the processor, a mod of the difference by the integer and subtracting the integer.
8. The method of claim 7 , wherein the integer is 2.
9. The method of claim 7 , further comprising compressing, by the processor, the encoded index value list.
10. The method of claim 9 , wherein the encoded index value list is compressed using Elias delta encoding.
11. A system comprising:
one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations implementing generating a compressed list of impression data records, the operations comprising:
receiving a set of impression data records describing a sequence of consumer behavior instances collected during a time window, wherein the set of impression data records is associated with a particular consumer;
generating a directed link graph representing the consumer behavior instances;
generating the compressed list of the impression data records based at least in part on properties of the directed link graph;
determining a first component of the set of impression data records to be an index component;
generating a sorted list of the set of impression data records by ordering the set of impression data records using a respective value of the index component within each impression data record;
identifying a set of unique index component values within the sorted list of the set of impression data records; and
generating an ordered list of the set of unique index component values using the sorted list of the set of impression data records.
12. The system of claim 11 , wherein each impression data record of the set of impression data records comprises a plurality of data components.
13. The system of claim 12 , wherein the plurality of data components includes one or more of an identifier of the promotion, a date on which the interaction occurred, and a position of the promotion within the impression display layout.
14. The system of claim 11 , wherein the graph nodes respectively represent the consumer behavior instances and each of the graph edges connecting a pair of the nodes represents a hyperlink between the nodes.
15. The system of claim 11 , further comprising generating an index value list by replacing each impression data record of the set of impression data records with its respective position in the ordered list of the set of unique index component values.
16. The system of claim 15 , further comprising generating an encoded index value list by calculating an encoded index value for each element of the index value list.
17. The system of claim 16 , wherein calculating the encoded index value for each element of the index value list comprises subtracting a value from a previous value in the index value list to produce a difference value; and
in instances where the difference value is positive, multiplying the difference by an integer;
in instances where the difference value is negative, multiplying a mod of the difference by the integer and subtracting the integer.
18. The system of claim 17 , wherein the integer is 2.
19. The system of claim 17 , further comprising compressing the encoded index value list using Elias delta encoding.
20. A computer program product, stored on a computer readable medium, comprising instructions that when executed on one or more computers cause the one or more computers to perform operations implementing generating a compressed list of impression data records, the operations comprising:
receiving a set of impression data records describing a sequence of consumer behavior instances collected during a time window, wherein the set of impression data records is associated with a particular consumer;
generating a directed link graph representing the consumer behavior instances;
generating the compressed list of the impression data records based at least in part on properties of the directed link graph;
determining a first component of the set of impression data records to be an index component;
generating a sorted list of the set of impression data records by ordering the set of impression data records using a respective value of the index component within each impression data record;
identifying a set of unique index component values within the sorted list of the set of impression data records; and
generating an ordered list of the set of unique index component values using the sorted list of the set of impression data records.