# US 10,311,471 B2 · Graph-based compression of data records > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,311,471 B2 - Document ID: US10311471B2 - Status: Granted - Kind: B2 - Application number: 16/050,986 - Filed: 2018-07-31 - Published: 2019-01-24 - Granted: 2019-06-04 - Earliest claimed: 2014-06-25 - Assignees: Groupon, Inc. - Applicants: Groupon, Inc. - Inventors: Ricardo A. Zilleruelo-Ramos; Hernan Enrique Arroyo Garcia; Joe Frisbie; Gaston L'Huillier; Francisco Jose Larrain - Web page: https://patentgrep.com/patent/US10311471B2 ## CPC - G06Q 30/0246: {Traffic} - G06F 16/1744: {using compression, e.g. sparse files} - G06F 16/2282: {Tablespace storage structures; Management thereof} - G06F 16/951: Indexing; Web crawling techniques - G06F 16/955: using information identifiers, e.g. uniform resource locators [URL] - H03M 7/30: Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction - H03M 7/70: {Type of the data to be coded, other than image and sound} - G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C) ## Abstract In general, embodiments of the present invention provide systems, methods and computer readable media for data record compression using graph-based techniques. ## Claims ### Claim 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. ### Claim 2 (depends on 1) The method of claim 1, wherein each impression data record of the set of impression data records comprises a plurality of data components. ### Claim 3 (depends on 2) 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. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 1) 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. ### Claim 6 (depends on 5) 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. ### Claim 7 (depends on 6) 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. ### Claim 8 (depends on 7) The method of claim 7, wherein the integer is 2. ### Claim 9 (depends on 7) The method of claim 7, further comprising compressing, by the processor, the encoded index value list. ### Claim 10 (depends on 9) The method of claim 9, wherein the encoded index value list is compressed using Elias delta encoding. ### Claim 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. ### Claim 12 (depends on 11) The system of claim 11, wherein each impression data record of the set of impression data records comprises a plurality of data components. ### Claim 13 (depends on 12) 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. ### Claim 14 (depends on 11) 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. ### Claim 15 (depends on 11) 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. ### Claim 16 (depends on 15) 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. ### Claim 17 (depends on 16) 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. ### Claim 18 (depends on 17) The system of claim 17, wherein the integer is 2. ### Claim 19 (depends on 17) The system of claim 17, further comprising compressing the encoded index value list using Elias delta encoding. ### Claim 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.