Back to results
US 10,311,471 B2Granted
Graph-based compression of data records
AssigneeGroupon, Inc.
InventorsRicardo A. Zilleruelo-Ramos, Hernan Enrique Arroyo Garcia, Joe Frisbie, Gaston L'Huillier, Francisco Jose Larrain
Life of this patent
Estimating the term…
Abstract
In general, embodiments of the present invention provide systems, methods and computer readable media for data record compression using graph-based techniques.
Claims20
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.
5 more elements
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.
6 more elements
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.
5 more elements
Dependencies are inferred from the claim text.