Fast collaborative filtering through sketch function based approximations

• US 7,624,095 B2
• Filed: 11/15/2005
• Issued: 11/24/2009
• Est. Priority Date: 11/15/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Majumder, Rangan
• Primary Examiner(s): Vital; Pierre M
• Assistant Examiner(s): LIAO, JASON G
• Application Number:
  US11/273,944
• Publication Number:
  US 20070124698A1
• Time in Patent Office: 1,470 Days
• Field of Search: 707/2, 707/3, 707/5, 705/10, 705/14, 705/26
• US Class Current: N/A
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data

Abstract

The claimed subject matter provides systems and/or methods that enable scalable collaborative filtering. A collaborative filtering component can receive data associated with a plurality of user sessions and data associated with at least one of a user and an item. Additionally, the collaborative filtering component can generate a recommendation based on a similarity. Further, an approximation component can approximate the similarity between at least one of the item and disparate items and the user and disparate users.

Claims

1. A system that enables scalable collaborative filtering, the system comprising:

a processor;

system memory; and

one or more computer storage media having stored thereon;

a collaborative filtering component configured to receive data associated with a plurality of user sessions and to generate a recommendation based on one or more similarities among the user sessions, the data associated with the user sessions including;

first data indicating a plurality of users;

second data indicating a plurality of items; and

third data indicating ratings of the items by the users;

an approximation component configured to approximate the one or more similarities that the collaborative filtering component uses to generate the recommendation, the approximation component comprising;

an adjustable accuracy component configured to receive input indicating a number of sketching functions;

a sketch component configured to generate sketching functions according to the number indicated by the input received by the adjustable accuracy component, the generated sketching functions including a first sketching function in a form f(x)=mx+b mod P, wherein m is a first randomly generated integer, b is a second randomly generated integer, and P is a randomly generated prime number, the sketch component configured to randomly generate the first integer, the second integer, and the prime number;

a mapping component configured to individually map the users to unique integers and to generate individual data sets linked to each of the items, each data set including one or more of the unique integers to indicate that the one or more users which are mapped to the one or more unique integers rated the linked item above a threshold rating;

a min-hashing component configured to;

generate hash values by selecting each data set and applying the generated sketching functions to the one or more unique integers in the selected data set;

for each sketching function applied to the selected data set, identify a min-hash value from among the hash values generated using the applied sketching function and the selected data set; and

associate each identified min-hash value with the item linked to the selected data set;

a matching component configured to;

compare the min-hash values associated with the items;

based on the comparison, calculate a total of min-hash value matches for pairs of items; and

generate an approximate Jaccard coefficient for each pair of items by dividing the total of min-hash value matches for the pair of items by the number of sketching functions generated and applied to the data sets linked to the items; and

a component configured to determine whether the data associated with a plurality of user sessions is sufficiently large as to warrant approximating the one or more similarities that the collaborative filtering component uses to generate the recommendation rather than calculating the one or more similarities.

2. The system of claim 1, wherein the collaborative filtering component further comprises a user-based collaborative filtering component that utilizes the data associated with the user to identify a disparate user that is similar to generate the recommendation.

3. The system of claim 1, wherein the collaborative filtering component further comprises an item-based collaborative filtering component that utilizes the data associated with the item to identify a disparate item that is similar to generate the recommendation.

4. By a computing system including a processor and system memory, a method that facilitates utilizing approximations in connection with collaborative filtering, the method comprising:

collecting data associated with a plurality of user sessions, the data associated with the user sessions including;

first data indicating a plurality of users;

second data indicating a plurality of items; and

third data indicating interactions with the items by the users;

receiving first input indicating a number of sketching functions;

generating a plurality of sketching functions according to the number indicated by the first input, the generated sketching functions including a first randomly generated sketching function in a form f(x)=mx+b mod P, wherein m is a first randomly generated integer, b is a second randomly generated integer, and P is a randomly generated prime number;

individually mapping the users to unique integers;

generating individual data sets linked to each of the items, each data set for each item including one or more of the unique integers to indicate that the one or more users which are mapped to the one or more unique integers interacted with the item;

generate hash values by selecting each data set and applying the generated sketching functions to the one or more unique integers in the data set;

for each sketching function applied to a selected data set, identify a min-hash value from among the hash values generated using the applied sketching function and the selected data set, and associate the identified min-hash value with the item linked to the selected data set;

compare the min-hash values associated with the items;

based on the comparison, calculate a total of min-hash value matches for pairs of items;

generate an approximate Jaccard coefficient for each pair of items by dividing the total of min-hash value matches for the pair of items by the number of sketching functions generated and applied to the data sets linked to the pair of items; and

generating a recommendation based on at least one approximate Jaccard coefficient generated for a pair of items.

5. The method of claim 4, wherein each data set for each item includes one or more of the unique integers to indicate that the one or more users which are mapped to the one or more unique integers rated the item above a threshold.

6. The method of claim 4, wherein each data set for each item includes one or more of the unique integers to indicate that the one or more users which are mapped to the one or more unique integers bought the item.

7. The method of claim 4, wherein each data set for each item includes one or more of the unique integers to indicate that the one or more users which are mapped to the one or more unique integers viewed the item.

8. A system that enables scalable collaborative filtering using data associated with a plurality of user sessions, the data associated with the user sessions including first data indicating a plurality of users, second data indicating a plurality of items, and third data indicating interactions with the items by the users, the users being individually mapped to unique identifiers, the system comprising:

one or more processors;

system memory; and

one or more computer storage media having stored thereon computer-executable instructions for performing a method, the method including;

receiving first input indicating a number of hashing functions;

generating a plurality of hashing functions according to the number indicated by the first input, including randomly generating at least one hashing function in a form f(x) =mx+b mod P, wherein m is a first randomly generated integer, b is a second randomly generated integer, and P is a randomly generated prime number;

generating individual data sets linked to each of the items, each data set for each item including one or more of the unique identifiers to indicate that the one or more users which are mapped to the one or more unique identifiers interacted with the item;

generate hash values by selecting each data set and applying the generated hashing functions to the one or more unique identifiers in the data set;

for each hashing function applied to a selected data set, identify a min-hash value from among the hash values generated using the applied hashing function and the selected data set, and associate the identified min-hash value with the item linked to the selected data set;

compare the min-hash values associated with the items;

based on the comparison, calculate a total of min-hash value matches for pairs of items;

generate an approximate Jaccard coefficient for each pair of items by dividing the total of min-hash value matches for the pair of items by the number of hashing functions generated and applied to the data sets linked to the pair of items; and

generating a recommendation based on at least one approximate Jaccard coefficient generated for a pair of items.

9. The system of claim 8, wherein each data set for each item includes one or more of the unique integers to indicate that the one or more users which are mapped to the one or more unique integers rated the item above a threshold.

10. The system of claim 8, wherein each data set for each item includes one or more of the unique integers to indicate that the one or more users which are mapped to the one or more unique integers bought the item.

11. The system of claim 8, wherein each data set for each item includes one or more of the unique integers to indicate that the one or more users which are mapped to the one or more unique integers viewed the item.