LARGE-SCALE ITEM AFFINITY DETERMINATION USING A MAP REDUCE PLATFORM

• US 20100205075A1
• Filed: 02/11/2009
• Published: 08/12/2010
• Est. Priority Date: 02/11/2009
• Status: Abandoned Application

• Current Assignee: Oath Inc. (Verizon Communications Inc.)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: ZHANG, Qiong
• Application Number:
  US12/369,160
• Publication Number:
  US 20100205075A1
• Time in Patent Office: Days
• US Class Current: 705/30
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 40/12 Accounting

Abstract

Pair-wise item affinity is based on transaction records. Each transaction record includes an indication of a bucket and an indication of an item transacted corresponding to that bucket. The method comprises a Phase 1 bucket filtering, Phase 2 item count, Phase 3 bucket materialization and Phase 4 pair count and affinity lift/calculation. The phases are ideally suited to be carried out by a computing system in a map-reduce configuration.

Claims

1. A computer-implemented method of determining pair-wise item affinity based on transaction records tangibly embodied in at least one computer-readable medium, each transaction record including an indication of a bucket and an indication of a item transacted corresponding to that bucket, the method comprising:

executing computer code by at least one computing device of a computing system to determine, for each partition, a total number of potential item pairs for that partition and a total count of unique items for that partition;

executing computer code by at least one computing device of the computing system to perform an item count, comprising;

determining, for each item, a count of the number of appearances of each item in all the buckets collectively;

for each item, encoding that item based at least in part on the determined item distribution across partitions;

executing computer code by at least one computing device of the computing system to perform a bucket materialization, comprising;

for each bucket, collecting into one record all item codes for items transacted in correspondence with that bucket;

for each bucket, processing the one record for that bucket to determine a number of item pairs that can be generated for that bucket and encoding that bucket based at least in part on the determined pair distribution across partitions;

executing computer code by at least one computing device of the computing system to perform a pair count and affinity/lift calculation, comprising;

generating pairs of item codes, and generating affinity statistics based on generated pairs of item codes; and

causing the generated pairs of item codes an affinity statistics to be stored in a tangible computer-readable medium.

2. The method of claim 1, wherein:

in the item count, the encoding is determined additionally based on, for each of a plurality of ranges of codes, that an approximately same number of pairs of items is encoded into each of the plurality of ranges.

3. The method of claim 1, further comprising:

executing computer code by at least one computing device of the computing system to perform a mapping of generated pairs of item codes back to the item pairs.

4. The method of claim 3, wherein determining, for each bucket, a total number of potential items pairs for that partition and a total count of unique items for that partition comprises:

in map processing of a computer system, executing computer code by at least one computing device of the computing system to receive a plurality of <

bucket, item>

indications and to provide, for each <

bucket, item>

indication, a first indication marked with a bucket key, and indicating the bucket and item of that <

bucket, item>

indication and a second indication marked with an item key and indicating the item of that <

bucket, item>

indication;

in partition processing of the computing system, for each <

bucket, item>

indication, executing computer code by at least one computing device of the computing system to determine a random indication for that <

bucket,item>

indication based on one of the bucket and the item and assigning each <

bucket, item>

indication to a partition based at least in part on the random indication; and

in reduce processing of the computing system,

for first indications, marked with a bucket key,

for each bucket, for each item corresponding to that bucket, executing computer code by at least one computing device of the computing system to filter out duplicate indications and indications for buckets having only one item; and

executing computer code by at least one computing device of the computing system to determine total number of potential item pairs per partition; and

executing computer code by at least one computing device of the computing system to process second indications, marked with an item key, to determine a total item count for the partition.

5. The method of claim 1, wherein the item count comprises:

in map processing of the computing system, executing computer code by at least one computing device of the computing system to receive <

bucket, item>

indications and outputting an indication, for each <

bucket, item>

indication, of a corresponding <

item, bucket>

indication;

in partition processing of the computing system, for each <

item, bucket>

indication, executing computer code by at least one computing device of the computing system to determine a random indication for that indication based on the item and assigning each <

item, bucket>

indication to a partition based at least in part on the random indication;

in reduce processing of the computing system,

executing computer code by at least one computing device of the computing system to encode each item based at least in part on the determined item distribution across partitions; and

executing computer code by at least one computing device of the computing system to provide, for each <

item, bucket>

, an indication of <

bucket, item code> and

to provide, for each item, an indication of <

item code, item, item count>

.

6. The method of claim 1, wherein the bucket materialization step comprises:

in map processing of the computing system, executing computer code by at least one computing device of the computing system to receive <

bucket, item code>

indications and outputting an identical <

bucket, item code>

;

in partition processing of the computing system, executing computer code by at least one computing device of the computing system to partition the <

bucket, item>

codes for reduce processing as a result of a determination of a random indication for each <

bucket,item>

indication based on the bucket and to assign each <

bucket, item>

indication to a partition based at least in part on the random indication;

in reduce processing of the computing system, for each bucket, executing computer code by at least one computing device of the computing system to provide an indication for that bucket, the indication including the code determined for that bucket and the codes for all the items transacted by that bucket.

7. The method of claim 1, wherein the pair count and affinity/lift calculation comprises:

in map processing of the computing system, executing computer code by at least one computing device of the computing system to, based on the indications from the reduce stage of the bucket materialization, for each bucket, generate an indication including a pair code for each item pair;

in partition processing of the computing system, executing computer code by at least one computing device of the computing system to determine a partition for each pair code based on ranges of the pair codes; and

in a reduce stage, executing computer code by at least one computing device of the computing system to perform pair count, affinity and lift calculations.

8. The method of claim 7, further comprising:

in customized split stage processing, executing computer code by at least one computing device of the computing system to distribute buckets to mappers of the map processing of the computing system such that each mapper generates a similar number of item pairs, executing computer code by at least one computing device of the computing system according to a greedy algorithm.

9. A computing system configured to determine pair-wise item affinity based on transaction records tangibly embodied in at least one computer-readable medium, each transaction record including an indication of a bucket and an indication of an item transacted corresponding to that bucket, the computing system configured to:

execute computer code by at least one computing device of the computing system to determine, for each partition, a total number of potential item pairs for that partition and a total count of unique items for that partition;

execute computer code by at least one computing device of the computing system to perform an item count, comprising;

determining, for each item, a count of the number of appearances of each item in all the buckets collectively;

for each item, encoding that item based at least in part on the determined item distribution across partitions;

execute computer code by at least one computing device of the computing system to perform a bucket materialization, comprising;

for each bucket, collecting into one record all item codes for items transacted in correspondence with that bucket;

for each bucket, processing the one record for that bucket to determine a number of item pairs that can be generated for that bucket and encoding that bucket based at least in part on the determined pair distribution across partitions; and

execute computer code by at least one computing device of the computing system to perform a pair count and affinity/lift calculation, comprising;

generating pairs of item codes, and generating affinity statistics based on generated pairs of item codes; and

causing the generated pairs of item codes an affinity statistics to be stored in a tangible computer-readable medium.

10. The computing system of claim 9, wherein:

in the item count, the encoding is determined additionally based on, for each of a plurality of ranges of codes, that an approximately same number of pairs of items is encoded into each of the plurality of ranges.

11. The computing system of claim 9, the computing system further configured to:

execute computer code by at least one computing device of the computing system to perform a mapping of generated pairs of item codes back to the item pairs.

12. The computing system of claim 11, wherein being configured to execute computer code to determine, for each partition, a total number of potential items pairs for that partition and a total count of unique items for that partition comprises:

in map processing of a computer system, being configured to execute computer code by at least one computing device of the computing system to receive a plurality of <

bucket, item>

indications and to provide, for each <

bucket, item>

indication, a first indication marked with a bucket key, and indicating the bucket and item of that <

bucket, item>

indication and a second indication marked with an item key and indicating the item of that <

bucket, item>

indication;

in partition processing of the computing system, for each <

bucket, item>

indication, being configured to execute computer code by at least one computing device of the computing system to determine a random indication for that <

bucket,item>

indication based on one of the bucket and the item and assigning each <

bucket, item>

indication to a partition based at least in part on the random indication; and

in reduce processing of the computing system,

for first indications, marked with a bucket key,

for each bucket, for each item corresponding to that bucket, being configured to execute computer code by at least one computing device of the computing system to filter out duplicate indications and indications for buckets having only one item; and

being configured to execute computer code by at least one computing device of the computing system to determine total number of potential item pairs per partition; and

executing computer code by at least one computing device of the computing system to process second indications, marked with an item key, to determine a total item count for the partition.

13. The computing system of claim 9, wherein being configured to execute computer code for the item count comprises:

in map processing of the computing system, being configured to execute computer code by at least one computing device of the computing system to receive <

bucket, item>

indications and outputting an indication, for each <

bucket, item>

indication, of a corresponding <

item, bucket>

indication;

in partition processing of the computing system, for each <

item, bucket>

indication, being configured to execute computer code by at least one computing device of the computing system to determine a random indication for that indication based on the item and assigning each <

item, bucket>

indication to a partition based at least in part on the random indication;

in reduce processing of the computing system,

being configured to execute computer code by at least one computing device of the computing system to encode each item based at least in part on the determined item distribution across partitions; and

being configured to execute computer code by at least one computing device of the computing system to provide, for each <

item, bucket>

, an indication of <

bucket, item code> and

to provide, for each item, an indication of <

item code, item, item count>

.

14. The computing system of claim 9, wherein being configured to execute computer code for bucket materialization comprises:

in map processing of the computing system, being configured to execute computer code by at least one computing device of the computing system to receive <

bucket, item code>

indications and outputting an identical <

bucket, item code>

;

in partition processing of the computing system, being configured to execute computer code by at least one computing device of the computing system to partition the <

bucket, item>

codes for reduce processing as a result of a determination of a random indication for each <

bucket,item>

indication based on one of the bucket and the item and to assign each <

bucket, item>

indication to a partition based at least in part on the random indication;

in reduce processing of the computing system, for each bucket, being configured to execute computer code by at least one computing device of the computing system to provide an indication for that bucket, the indication including the code determined for that bucket and the codes for all the items transacted by that bucket.

15. The computing system of claim 9, being configured to execute computer code for the pair count and affinity/lift calculation comprises:

in map processing of the computing system, being configured to execute computer code by at least one computing device of the computing system to, based on the indications from the reduce stage of the bucket materialization, for each bucket, generate an indication including a pair code for each for each item pair;

in partition processing of the computing system, being configured to execute computer code by at least one computing device of the computing system to determine a partition for each pair code based on ranges of the pair codes; and

in a reduce stage, being configured to execute computer code by at least one computing device of the computing system to perform affinity and lift calculations.

16. The computing system of claim 15, the computing system further configured to:

in customized split stage processing, execute computer code by at least one computing device of the computing system to distribute buckets to mappers of the map processing of the computing system such that each mapper generates a similar number of item pairs, executing computer code by at least one computing device of the computing system according to a greedy algorithm.

17. A computer-program product comprising at least one computer readable medium having computer-executable code tangibly embodied thereon, the computer-executable code to configure at least one computing device to:

determine, for each partition, a total number of potential item pairs for that partition and a total count of unique items for that partition;

perform an item count, comprising;

determining, for each item, a count of the number of appearances of each item in all the buckets collectively;

for each item, encoding that item based at least in part on the determined item distribution across partitions;

perform a bucket materialization, comprising;

for each bucket, collecting into one record all item codes for items transacted in correspondence with that bucket;

for each bucket, processing the one record for that bucket to determine a number of item pairs that can be generated for that bucket and encoding that bucket based at least in part on the determined pair distribution across partitions; and

perform a pair count and affinity/lift calculation, comprising;

generating pairs of item codes, and generating affinity statistics based on generated pairs of item codes; and

causing the generated pairs of item codes an affinity statistics to be stored in a tangible computer-readable medium.

18. The computer program product of claim 17, wherein:

in the item count, the encoding is determined additionally based on, for each of a plurality of ranges of codes, that an approximately same number of pairs of items is encoded into each of the plurality of ranges.

19. The computer program product of claim 17, the computer program instructions further to configure the at least one computing device to:

perform a mapping of generated pairs of item codes back to the item pairs.

20. The computer program product of claim 19, wherein being configured to determine, for each partition, a total number of potential items pairs for that partition and a total count of unique items for that partition comprises:

in map processing of a computer system, being configured to receive a plurality of <

bucket, item>

indications and to provide, for each <

bucket, item>

indication, a first indication marked with a bucket key, and indicating the bucket and item of that <

bucket, item>

indication and a second indication marked with an item key and indicating the item of that <

bucket, item>

indication;

in partition processing of the computing system, for each <

bucket, item>

indication, being configured to determine a random indication for that <

bucket,item>

indication based on one of the bucket and the item and assigning each <

bucket, item>

indication to a partition based at least in part on the random indication; and

in reduce processing of the computing system,

for first indications, marked with a bucket key,

for each bucket, for each item corresponding to that bucket, being configured to filter out duplicate indications and indications for buckets having only one item; and

being configured to determine total number of potential item pairs per partition; and

by at least one computing device of the computing system to process second indications, marked with an item key, to determine a total item count for the partition.

21. The computer program product of claim 17, wherein being configured to perform the item count comprises:

in map processing of the computing system, being configured to receive <

bucket, item>

indications and outputting an indication, for each <

bucket, item>

indication, of a corresponding <

item, bucket>

indication;

in partition processing of the computing system, for each <

item, bucket>

indication, being configured to determine a random indication for that indication based on the item and assigning each <

item, bucket>

indication to a partition based at least in part on the random indication;

in reduce processing of the computing system,

being configured to encode each item based at least in part on the determined partition; and

being configured to provide, for each <

item, bucket>

, an indication of <

bucket, item code> and

to provide, for each item, an indication of <

item code, item, item count>

.

22. The computer program product of claim 17, wherein being configured for bucket materialization comprises:

in map processing of the computing system, being configured to receive <

bucket, item code>

indications and outputting an identical <

bucket, item code>

;

in partition processing of the computing system, being configured to partition the <

bucket, item>

codes for reduce processing as a result of a determination of a random indication for each <

bucket,item>

indication based on the bucket and assign each <

bucket, item>

indication to a partition based at least in part on the random indication;

in reduce processing of the computing system, for each bucket, being configured to provide an indication for that bucket, the indication including the code determined for that bucket and the codes for all the items transacted by that bucket.

23. The computer program product of claim 17, wherein being configured for the pair count and affinity/lift calculation comprises:

in map processing of the computing system, being configured to, based on the indications from the reduce stage of the bucket materialization, for each bucket, generate an indication including a pair code for each for each item pair;

in partition processing of the computing system, being configured to determine a partition for each pair code based on ranges of the pair codes; and

in a reduce stage, being configured to perform affinity and lift calculations.

24. The computer program product of claim 23, the computer program instructions further configured to cause the at least one computing device:

in customized split stage processing, to distribute buckets to mappers of the map processing of the computing system such that each mapper generates a similar number of item pairs, according to a greedy algorithm.