# US 2018/0025381 A1 · 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 2018/0025381 A1
- Document ID: US20180025381A1
- Status: Published application
- Kind: A1
- Application number: 15/449,687
- Filed: 2017-03-03
- Published: 2018-01-25
- Earliest claimed: 2014-06-25
- Assignees: Groupon, Inc.
- Applicants: Groupon, Inc.
- Inventors: Ricardo A. Zilleruelo-Ramos; Herman Enrique Arroyo Garcia; Joe Frisbie; Gaston L'Huillier; Francisco Jose Larrain
- Web page: https://patentgrep.com/patent/US20180025381A1

## 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 at position 1

1-30. (canceled)

### Claim 31

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; and
generating, by the processor, the compressed list of the impression data records based at least in part on properties of the directed link graph.

### Claim 32 (depends on 31)

The method of claim 31, wherein each impression data record of the set of impression data records comprises a plurality of data components.

### Claim 33 (depends on 31)

The method of claim 31, 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 34 (depends on 31)

The method of claim 31, further comprising:
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 35 (depends on 34)

The method of claim 34, 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 36 (depends on 35)

The method of claim 35, further comprising generating an encoded index value list by calculating an encoded index value for each element of the index value list.

### Claim 37 (depends on 36)

The method of claim 36, 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 38 (depends on 37)

The method of claim 37, wherein the integer is 2.

### Claim 39 (depends on 37)

The method of claim 37, further comprising compressing the encoded index value list.

### Claim 40 (depends on 39)

The method of claim 39, wherein the encoded index value list is compressed using Elias delta encoding.

### Claim 41 (depends on 32)

The method of claim 32, 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 42

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; and
generating the compressed list of the impression data records based at least in part on properties of the directed link graph.

### Claim 43 (depends on 42)

The system of claim 42, wherein each impression data record of the set of impression data records comprises a plurality of data components.

### Claim 44 (depends on 42)

The system of claim 42, 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 45 (depends on 43)

The system of claim 43, further comprising:
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 46 (depends on 45)

The system of claim 45, 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 47 (depends on 46)

The system of claim 46, further comprising generating an encoded index value list by calculating an encoded index value for each element of the index value list.

### Claim 48 (depends on 47)

The system of claim 47, 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 49 (depends on 48)

The system of claim 48, wherein the integer is 2.

### Claim 50 (depends on 48)

The system of claim 48, further comprising compressing the encoded index value list using Elias delta encoding.