GENERALIZED GRAPH, RULE, AND SPATIAL STRUCTURE BASED RECOMMENDATION ENGINE

• US 20150142785A1
• Filed: 11/18/2013
• Published: 05/21/2015
• Est. Priority Date: 11/18/2013
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Roberts, Michael, Ahern, Shane P.
• Granted Patent: US 9,582,547 B2
• Time in Patent Office: Days
• US Class Current: 707/723
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: G06F 16/337 Profile generation, learning or modification
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06Q 30/06 Buying, selling or leasing transactions

Abstract

One embodiment of the present invention provides a recommendation system. During operation, the system receives context information associated with the user, updates a plurality of user models based on the received context information, and identifies at least one spatial data structure that stores a plurality of items. A respective item is stored within the spatial data structure based on a vector value associated with the item. The system then queries the spatial data structure to obtain a first set of recommendable items that have vector values within a predetermined range, calculates a score for each item within the set of recommendable items based on the plurality of the user models and a characterization vector associated with each item, ranks the items within the set of recommendable items based on calculated scores, and recommends one or more top-ranked items to the user.

Claims

1. A method for providing a recommendation to a user, comprising:

receiving context information associated with the user;

updating a plurality of user models based on the received context information;

identifying a spatial data structure that stores a plurality of items, wherein the spatial data structure corresponds to a vector space, and wherein a respective item is stored within the spatial data structure based on a vector value associated with the item;

querying the spatial data structure to obtain a first set of recommendable items that have vector values within a predetermined range;

calculating a score for each item within the set of recommendable items based on the plurality of the user models and a characterization vector associated with each item;

ranking the items within the set of recommendable items based on calculated scores; and

recommending one or more top-ranked items to the user.

2. The method of claim 1, wherein calculating the score involves:

calculating a model-specific output for each user model; and

calculating a weighted sum of model-specific outputs over the plurality of user models.

3. The method of claim 2, wherein calculating the model-specific output involves:

identifying elements in the characterization vector that correspond to parameters of the user model; and

calculating the model-specific output as a function of the identified elements and the corresponding parameters of the user model.

4. The method of claim 1, further comprising:

identifying an additional spatial data structure that corresponds to a different vector space;

querying the additional spatial data structure to obtain a second set of recommendable items; and

generating a combined set of recommendable items using the first and the second sets of recommendable items.

5. The method of claim 1, wherein the plurality of items includes one or more of:

a web page;

a consumer item;

an activity;

a venue; and

a location.

6. The method of claim 1, further comprising updating a context graph associated with the user based on the received context information.

7. The method of claim 1, wherein the spatial data structure is segmented into cells, and wherein a respective cell stores items having vector values within boundaries of the cell.

8. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for providing a recommendation to a user, the method comprising:

receiving context information associated with the user;

updating a plurality of user models based on the received context information;

identifying a spatial data structure that stores a plurality of items, wherein the spatial data structure corresponds to a vector space, and wherein a respective item is stored within the spatial data structure based on a vector value associated with the item;

querying the spatial data structure to obtain a first set of recommendable items that have vector values within a predetermined range;

calculating a score for each item within the set of recommendable items based on the plurality of the user models and a characterization vector associated with each item;

ranking the items within the set of recommendable items based on calculated scores; and

recommending one or more top-ranked items to the user.

9. The computer-readable storage medium of claim 8, wherein calculating the score involves:

calculating a model-specific output for each user model; and

calculating a weighted sum of model-specific outputs over the plurality of user models.

10. The computer-readable storage medium of claim 9, wherein calculating the model-specific output involves:

identifying elements in the characterization vector that correspond to parameters of the user model; and

calculating the model-specific output as a function of the identified elements and the corresponding parameters of the user model.

11. The computer-readable storage medium of claim 8, wherein the method further comprises:

identifying an additional spatial data structure that corresponds to a different vector space;

querying the additional spatial data structure to obtain a second set of recommendable items; and

generating a combined set of recommendable items using the first and the second sets of recommendable items.

12. The computer-readable storage medium of claim 8, wherein the plurality of items includes one or more of:

a web page;

a consumer item;

an activity;

a venue; and

a location.

13. The computer-readable storage medium of claim 8, wherein the method further comprises updating a context graph associated with the user based on the received context information.

14. The computer-readable storage medium of claim 8, wherein the spatial data structure is segmented into cells, and wherein a respective cell stores items having vector values within boundaries of the cell.

15. A recommendation system for providing a recommendation to a user, comprising:

an activity-detection module configured to detect user activities and/or interests based on context information associated with the user;

a model-updating mechanism configured to update a plurality of user models based on an output of the activity-detection module;

a spatial data structure configured to store a plurality of items, wherein the spatial data structure corresponds to a vector space, and wherein a respective item is stored within the spatial data structure based on a vector value associated with the item;

a querying mechanism configured to query the spatial data structure to obtain a first set of recommendable items that have vector values within a predetermined range; and

a mixed-model recommender configured to;

calculate a score for each item within the set of recommendable items based on the plurality of the user models and a characterization vector associated with each item;

rank the items within the set of recommendable items based on calculated scores; and

recommend one or more top-ranked items to the user.

16. The recommendation system of claim 15, wherein while calculating the score, the mixed-model recommender is further configured to:

calculate a model-specific output for each user model; and

calculate a weighted sum of model-specific outputs over the plurality of user models.

17. The recommendation system of claim 16, wherein while calculating the model-specific output, the mixed-model recommender is further configured to:

identify elements in the characterization vector that correspond to parameters of the user model; and

calculate the model-specific output as a function of the identified elements and the corresponding parameters of the user model.

18. The recommendation system of claim 15, further comprising:

an additional spatial data structure that corresponds to a different vector space;

wherein the querying mechanism is further configured to;

query the additional spatial data structure to obtain a second set of recommendable items; and

generate a combined set of recommendable items using the first and the second sets of recommendable items.

19. The recommendation system of claim 15, wherein the plurality of items includes one or more of:

a web page;

a consumer item;

an activity;

a venue; and

a location.

20. The recommendation system of claim 15, further comprising a context graph updating mechanism configured to update a context graph based on the output of the activity-detection module.

21. The recommendation system of claim 15, wherein the spatial data structure is segmented into cells, and wherein a respective cell stores items having vector values within boundaries of the cell.

22. The recommendation system of claim 15, further comprising an item-characterization module configured to generate a characterization vector for an item.