Graph-based compression of data records

Abstract

In general, examples of the present disclosure provide systems, methods and computer readable media for data record compression using graph-based techniques. For example, an example method includes retrieving a compound data record list that includes compound data records, identifying a unique second component value set that includes unique second component values, determining a data record position list based at least in part on at least one data record position within the compound data record list, and generating a data record encoding of the compound data records.

The invention claimed is: 
     
       1. An apparatus comprising a processor and a non-transitory memory storing program instructions, wherein the non-transitory memory and the program instructions are configured to, with the processor, cause the apparatus to:
 retrieve a compound data record list comprising a plurality of compound data records ordered based at least in part on an index component associated with each of the plurality of compound data records; 
 identify a unique second component value set comprising a plurality of unique second component values associated with a second component of each of the plurality of compound data records, wherein the second component is different from the index component; 
 determine a data record position list based at least in part on at least one data record position within the compound data record list corresponding to at least one compound data record that is associated with one of the plurality of unique second component values; and 
 generate a data record encoding of the plurality of compound data records based at least in part on associating the second component with the unique second component value set and the data record position list. 
 
     
     
       2. The apparatus of  claim 1 , wherein, prior to retrieving the compound data record list, the non-transitory memory and the program instructions are configured to, with the processor, cause the apparatus to:
 receive an impression data record set describing a user behavior instance sequence collected during a time window, wherein the impression data record set is associated with a user identifier, wherein the impression data record set comprises the plurality of compound data records. 
 
     
     
       3. The apparatus of  claim 2 , wherein the non-transitory memory and the program instructions are configured to, with the processor, cause the apparatus to:
 generate a directed link graph representing the user behavior instance sequence, wherein the directed link graph comprises graph nodes and graph edges, wherein each of the graph nodes represents a user behavior instance within the user behavior instance sequence, wherein each of the graph edges represents a hyperlink between a pair of graph nodes. 
 
     
     
       4. The apparatus of  claim 2 , wherein the non-transitory memory and the program instructions are configured to, with the processor, cause the apparatus to:
 determine that a first component of each of the plurality of compound data records is the index component; and 
 order the plurality of compound data records based at least in part on an index component value associated with the index component of each of the plurality of compound data records. 
 
     
     
       5. The apparatus of  claim 4 , wherein the non-transitory memory and the program instructions are configured to, with the processor, cause the apparatus to:
 identify a plurality of index component values within the compound data record list; and 
 generate an index component value set based at least in part on ordering the plurality of index component values. 
 
     
     
       6. The apparatus of  claim 5 , wherein the non-transitory memory and the program instructions are configured to, with the processor, cause the apparatus to:
 determine whether the index component value set comprises at least one duplicate of the index component value; and 
 in response to determining that the index component value set comprises the at least one duplicate of the index component value, determine a duplicate quantity of the at least one duplicate of the index component value. 
 
     
     
       7. The apparatus of  claim 6 , wherein the non-transitory memory and the program instructions are configured to, with the processor, cause the apparatus to:
 generate a second data record encoding based at least in part on the duplicate quantity and at least one index component value position within the index component value set that is associated with the at least one duplicate of the index component value; and 
 generate the compound data record list based at least in part on the index component value set and the second data record encoding. 
 
     
     
       8. A computer-implemented method comprising:
 retrieving a compound data record list comprising a plurality of compound data records ordered based at least in part on an index component associated with each of the plurality of compound data records; 
 identifying a unique second component value set comprising a plurality of unique second component values associated with a second component of each of the plurality of compound data records, wherein the second component is different from the index component; 
 determining a data record position list based at least in part on at least one data record position within the compound data record list corresponding to at least one compound data record that is associated with one of the plurality of unique second component values; and 
 generating a data record encoding of the plurality of compound data records based at least in part on associating the second component with the unique second component value set and the data record position list. 
 
     
     
       9. The computer-implemented method of  claim 8 , wherein, prior to retrieving the compound data record list, the computer-implemented method further comprising:
 receiving an impression data record set describing a user behavior instance sequence collected during a time window, wherein the impression data record set is associated with a user identifier, wherein the impression data record set comprises the plurality of compound data records. 
 
     
     
       10. The computer-implemented method of  claim 9 , further comprising:
 generating a directed link graph representing the user behavior instance sequence, wherein the directed link graph comprises graph nodes and graph edges, wherein each of the graph nodes represents a user behavior instance within the user behavior instance sequence, wherein each of the graph edges represents a hyperlink between a pair of graph nodes. 
 
     
     
       11. The computer-implemented method of  claim 9 , further comprising:
 determining that a first component of each of the plurality of compound data records is the index component; and 
 ordering the plurality of compound data records based at least in part on an index component value associated with the index component of each of the plurality of compound data records. 
 
     
     
       12. The computer-implemented method of  claim 11 , further comprising:
 identifying a plurality of index component values within the compound data record list; and 
 generating an index component value set based at least in part on ordering the plurality of index component values. 
 
     
     
       13. The computer-implemented method of  claim 12 , further comprising:
 determining whether the index component value set comprises at least one duplicate of the index component value; and 
 in response to determining that the index component value set comprises the at least one duplicate of the index component value, determining a duplicate quantity of the at least one duplicate of the index component value. 
 
     
     
       14. The computer-implemented method of  claim 13 , further comprising:
 generating a second data record encoding based at least in part on the duplicate quantity and at least one index component value position within the index component value set that is associated with the at least one duplicate of the index component value; and 
 generating the compound data record list based at least in part on the index component value set and the second data record encoding. 
 
     
     
       15. A computer program product comprising at least one non-transitory computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising an executable portion configured to:
 retrieve a compound data record list comprising a plurality of compound data records ordered based at least in part on an index component associated with each of the plurality of compound data records; 
 identify a unique second component value set comprising a plurality of unique second component values associated with a second component of each of the plurality of compound data records, wherein the second component is different from the index component; 
 determine a data record position list based at least in part on at least one data record position within the compound data record list corresponding to at least one compound data record that is associated with one of the plurality of unique second component values; and 
 generate a data record encoding of the plurality of compound data records based at least in part on associating the second component with the unique second component value set and the data record position list. 
 
     
     
       16. The computer program product of  claim 15 , wherein, prior to retrieving the compound data record list, the computer-readable program code portions comprises the executable portion configured to:
 receive an impression data record set describing a user behavior instance sequence collected during a time window, wherein the impression data record set is associated with a user identifier, wherein the impression data record set comprises the plurality of compound data records. 
 
     
     
       17. The computer program product of  claim 16 , wherein the computer-readable program code portions comprises the executable portion configured to:
 generate a directed link graph representing the user behavior instance sequence, wherein the directed link graph comprises graph nodes and graph edges, wherein each of the graph nodes represents a user behavior instance within the user behavior instance sequence, wherein each of the graph edges represents a hyperlink between a pair of graph nodes. 
 
     
     
       18. The computer program product of  claim 16 , wherein the computer-readable program code portions comprises the executable portion configured to:
 determine that a first component of each of the plurality of compound data records is the index component; and 
 order the plurality of compound data records based at least in part on an index component value associated with the index component of each of the plurality of compound data records. 
 
     
     
       19. The computer program product of  claim 18 , wherein the computer-readable program code portions comprises the executable portion configured to:
 identify a plurality of index component values within the compound data record list; and 
 generate an index component value set based at least in part on ordering the plurality of index component values. 
 
     
     
       20. The computer program product of  claim 19 , wherein the computer-readable program code portions comprises the executable portion configured to:
 determine whether the index component value set comprises at least one duplicate of the index component value; and 
 in response to determining that the index component value set comprises the at least one duplicate of the index component value, determine a duplicate quantity of the at least one duplicate of the index component value.