Identifying information of interest based on user preferences

• US 9,092,516 B2
• Filed: 06/20/2012
• Issued: 07/28/2015
• Est. Priority Date: 06/20/2011
• Status: Active Grant

• Current Assignee: Primal Fusion Inc.
• Original Assignee: Primal Fusion Inc.
• Inventors: Ilyas, Ihab Francis, Soliman, Mohamed A.
• Primary Examiner(s): LE, DEBBIE M
• Application Number:
  US13/527,883
• Publication Number:
  US 20120323910A1
• Time in Patent Office: 1,133 Days
• Field of Search: 707732-734
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/36 Creation of semantic tools, e.g. ontology or thesauri
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9538 Presentation of query results

Abstract

Techniques for calculating a ranking of at least one item in a plurality of items. The techniques include receiving user preferences comprising a plurality of first-order user preferences indicative of a user'"'"'s preferences for items in the plurality of items, and at least one second-order user preference indicative of the user'"'"'s preferences among first-order user preferences in the plurality of first-order user preferences; calculating, with at least one processor, a ranking of the at least one item in the plurality of items based, at least in part on, at least one data structure encoding a preference graph that represents the received user preferences; and identifying and outputting at least a subset of the plurality of items to a user, in accordance with the ranking.

Claims

1. A computer-implemented method for calculating a ranking of at least one item in a plurality of items, the method comprising:

receiving user preferences comprising

a plurality of first-order user preferences indicative of a user'"'"'s preferences for items in the plurality of items, and

at least one second-order user preference indicative of the user'"'"'s preferences among first-order user preferences in the plurality of first-order user preferences;

wherein the at least one second-order user preference is indicative of the user'"'"'s preference among attributes of at least one item in the plurality of items;

calculating, with at least one processor, a ranking of the at least one item in the plurality of items based, at least in part on, at least one data structure encoding a preference graph that represents the received user preferences; and

identifying and outputting at least a subset of the plurality of items to a user, in accordance with the ranking.

2. The computer-implemented method of claim 1, wherein calculating the ranking comprises:

applying a pagerank-based algorithm to the at least one data structure encoding the preference graph to calculate the ranking.

3. The computer-implemented method of claim 2, wherein the preference graph comprises a plurality of nodes, wherein each node corresponds to an item in the plurality of items, and calculating the ranking comprises:

calculating a pagerank score of at least one node in the plurality of nodes.

4. The computer-implemented method of claim 1, wherein the preference graph comprises a plurality of nodes, wherein each node corresponds to an item in the plurality of items, and wherein calculating the ranking comprises:

computing a total order of nodes in a complete directed graph derived from the preference graph.

5. The computer-implemented method of claim 4, wherein computing the total order of nodes comprises calculating:

a Kendall score for at least one node in the complete directed graph.

6. The computer-implemented method of claim 1, wherein receiving user preferences comprises prompting the user to provide the at least one second-order user preference.

7. The computer-implemented method of claim 1, wherein the method further comprises constructing the preference graph based at least in part on the received user preferences, wherein the preference graph comprises a plurality of nodes, wherein each node in the plurality of nodes corresponds to an item in the plurality of items;

and wherein the preference graph further comprises a plurality of edges, wherein each edge corresponds to a first-order user preference in the plurality of first-order user preferences, the first-order user preference indicating a user preference for one of the two items represented by nodes terminating the each edge.

8. The computer-implemented method of claim 7, wherein the preference graph comprises a first node corresponding to a first item in the plurality of items, a second node corresponding to a second item in the plurality of items, and a directed edge from the first node directed to the second node, wherein the direction of the directed edge indicates that the second item is preferred to the first item as indicated by the first-order user preference associated with the directed edge.

9. The computer-implemented method of claim 7, wherein the preference graph comprises a first node corresponding to a first item, a second node corresponding to a second item, an edge between the first and second nodes, and a weight associated to the edge between the first node and the second node, the weight being indicative of a degree of preference for the first item over the second item.

10. A system comprising:

at least one memory configured to store

a plurality of tuples, each tuple in the plurality of tuples corresponding to an item in a plurality of items, and

at least one data structure encoding a preference graph to represent user preferences, wherein the user preferences comprise a plurality of first-order user preferences indicative of a user'"'"'s preferences among items in the plurality of items, and at least one second-order user preference indicative of the user'"'"'s preferences among first-order user preferences in the plurality of first-order user preferences;

wherein the at least one second-order user preference is indicative of the user'"'"'s preference among attributes of at least one item in the plurality of items; and

at least one processor coupled to the at least one memory, the at least one processor configured to;

calculate a ranking of at least one item in the plurality of items based, at least in part on, the at least one data structure encoding the preference graph that represents the user preferences; and

identify and output at least a subset of the plurality of items to a user, in accordance with the ranking.

11. The system of claim 10, wherein the at least one processor is configured to calculate the ranking at least by:

applying a pagerank-based algorithm to the at least one data structure encoding the preference graph to calculate the ranking.

12. The system of claim 10, wherein the preference graph comprises a plurality of nodes, wherein each node corresponds to an item in the plurality of items, and wherein the at least one processor is configured to calculate the ranking at least by:

computing a total order of nodes in a complete directed graph derived from the preference graph.

13. The system of claim 10, wherein the at least one processor is further configured to:

construct the preference graph based at least in part on the received user preferences,

wherein the preference graph comprises a plurality of nodes, wherein each node in the plurality of nodes corresponds to an item in the plurality of items; and

wherein the preference graph further comprises a plurality of edges, wherein each edge corresponds to a first-order user preference in the plurality of first-order user preferences, the first-order user preference indicating a user preference for one of the two items represented by nodes terminating the each edge.

14. The system of claim 13, wherein the preference graph comprises a first node corresponding to a first item, a second node corresponding to a second item, an edge between the first and second nodes, and a weight associated to the edge between the first node and the second node, the weight being indicative of a degree of preference for the first item over the second item.

15. At least one computer-readable storage medium article storing a plurality of processor-executable instructions that, when executed by at least one processor, cause the at least one processor to perform a method of calculating a ranking for at least one item in a plurality of items, the method comprising:

receiving user preferences comprising

a plurality of first-order user preferences indicative of a user'"'"'s preferences among items in the plurality of items, and

at least one second-order user preference indicative of the user'"'"'s preferences among first-order user preferences in the plurality of first-order user preferences;

wherein the at least one second-order user reference is indicative of the user'"'"'s preference among attributes of at least one item in the plurality of items;

calculating a ranking of the at least one item in the plurality of items based, at least in part on, at least one data structure encoding a preference graph that represents the received user preferences; and

identifying and outputting at least a subset of the plurality of items to a user, in accordance with the ranking.

16. The at least one computer-readable storage medium article of claim 15, wherein the at least one computer readable storage medium article further stores the at least one data structure encoding the preference graph.

17. The at least one computer-readable storage medium article of claim 15, wherein calculating the ranking comprises:

applying a pagerank-based algorithm to the at least one data structure encoding the preference graph to calculate the ranking.

18. The at least one computer-readable storage medium article of claim 15, wherein the preference graph comprises a plurality of nodes, wherein each node corresponds to an item in the plurality of items, and wherein calculating the ranking comprises:

computing a total order of nodes in a complete directed graph derived from the preference graph.

19. The at least one computer-readable storage medium article of claim 15,

wherein the method further comprises:

constructing the preference graph based at least in part on the received user preferences,

wherein the preference graph comprises a plurality of nodes, wherein each node in the plurality of nodes corresponds to an item in the plurality of items; and

wherein the preference graph further comprises a plurality of edges, wherein each edge corresponds to a first-order user preference in the plurality of first-order user preferences, the first-order user preference indicating a user preference for one of the two items represented by nodes terminating the each edge.

20. The at least one computer-readable storage medium article of claim 19, wherein the preference graph comprises a first node corresponding to a first item, a second node corresponding to a second item, an edge between the first and second nodes, and a weight associated to the edge between the first node and the second node, the weight being indicative of a degree of preference for the first item over the second item.

21. A computer-implemented method for constructing at least one data structure encoding a preference graph that represents user preferences, the method comprising:

receiving a plurality of first-order user preferences indicative of user preferences among values of attributes of items in a plurality of items;

receiving at least one second-order user preference indicative of user preferences among the attributes of items in the plurality of items, wherein the preference graph comprises a first node for a first item in the plurality of items and a second node for a second item in the plurality of items; and

computing, using at least one processor, a weight for an edge between the first node and the second node based at least in part on the plurality of first-order user preferences and the at least one second-order user preference, wherein the weight is indicative of a degree of preference for the first item over the second item.

22. The computer-implemented method of claim 21, wherein the preference graph comprises a third node for a third item in the plurality of items, a fourth node for a fourth item in the plurality of items, the method further comprising:

constructing the at least one data structure encoding the preference graph to include an edge between the third node and the fourth node when the plurality of first-order user preferences comprises a first-order user preference for the third item over the fourth item.

23. The computer-implemented method of claim 21, further comprising:

constructing the at least one data structure encoding the preference graph to include a node for each item in the plurality of items and an edge for every pair of nodes associated with items related by a first-order user preference in the plurality of first-order user preferences.

24. The computer-implemented method of claim 21, wherein computing the weight comprises:

computing a first number of first-order user preferences in the plurality of first-order user preferences indicating a user'"'"'s preference for the first item relative to the second item;

computing a second number of all first-order user preferences in the plurality of first-order user preferences indicating any preference associated with the first item; and

setting the weight based at least in part on the first number and the second number.

25. The computer-implemented method of claim 21, wherein items in the plurality of items are represented as tuples, each tuple comprising values of the attributes of the corresponding item, and wherein receiving the plurality of first-order preferences comprises:

receiving a first-order preference for the first item over the second item by receiving an indication of a user preference for a first value of a first attribute of a first tuple representing the first item over a second value of the second attribute of a second tuple representing the second item.

26. The computer-implemented method of claim 25, wherein the first attribute is a same attribute as the second attribute.

27. The computer-implemented method of claim 21, wherein the plurality of first-order user preferences comprises at least two types of first-order user preferences selected from the group consisting of score-based preferences, partial order preferences, skyline preferences, and conjoint analysis preferences.

28. The computer-implemented method of claim 21, wherein the at least one second-order user preference comprises a plurality of second-order user preference relations that comprises at least two types of second-order preferences selected from the group consisting of prioritized preference composition, partial order preferences, pairwise preferences, and Pareto preference composition.

29. A system for constructing at least one data structure encoding a preference graph that represents user preferences, the system comprising:

at least one processor configured to

receive a plurality of first-order user preferences indicative of user preferences among values of attributes of items in a plurality of items,

receive at least one second-order user preference indicative of user preferences among the attributes of items in the plurality of items, wherein the preference graph comprises a first node for a first item in the plurality of items and a second node for a second item in the plurality of items, and

compute a weight for an edge between the first node and the second node based at least in part on the plurality of first-order user preferences and the at least one second-order user preference, wherein the weight is indicative of a degree of preference for the first item over the second item.

30. The system of claim 29, wherein the preference graph comprises a third node for a third item in the plurality of items, a fourth node for a fourth item in the plurality of items, and wherein at least one processor is further configured to:

construct the at least one data structure encoding the preference graph to include an edge between the third node and the fourth node when the plurality of first-order user preferences comprises a first-order user preference for the third item over the fourth item.

31. The system of claim 29, wherein the at least one processor is further configured to:

constructing the at least one data structure encoding the preference graph to include a node for each item in the plurality of items and an edge for every pair of nodes associated with items related by a first-order user preference in the plurality of first-order user preferences.

32. The system of claim 29, wherein the at least one processor is configured to compute the weight at least by:

computing a first number of first-order user preferences in the plurality of first-order user preferences indicating a user'"'"'s preference for the first item relative to the second item;

computing a second number of all first-order user preferences in the plurality of first-order user preferences indicating any preference associated with the first item; and

setting the weight based at least in part on the first number and the second number.

33. The system of claim 29, wherein items in the plurality of items are represented as tuples, each tuple comprising values of the attributes of the corresponding item, and wherein the at least one processor is configured to receive the plurality of first-order preferences at least by:

receiving a first-order preference for the first item over the second item by receiving an indication of a user preference for a first value of a first attribute of a first tuple representing the first item over a second value of the second attribute of a second tuple representing the second item.

34. The system of claim 33, wherein the first attribute is a same attribute as the second attribute.

35. The system of claim 29, wherein the plurality of first-order user preferences comprises at least two types of first-order user preferences selected from the group consisting of score-based preferences, partial order preferences, skyline preferences, and conjoint analysis preferences.

36. The system of claim 29, wherein the at least one second-order user preference comprises a plurality of second-order user preference relations that comprises at least two types of second-order preferences selected from the group consisting of prioritized preference composition, partial order preferences, pairwise preferences, and Pareto preference composition.

37. At least one computer-readable storage medium article storing a plurality of processor-executable instructions that, when executed by at least one processor, cause the at least one processor to perform a method for constructing at least one data structure encoding a preference graph that represents user preferences, the method comprising:

receiving a plurality of first-order user preferences indicative of user preferences among values of attributes of items in a plurality of items;

receiving at least one second-order user preference indicative of user preferences among the attributes of items in the plurality of items, wherein the preference graph comprises a first node for a first item in the plurality of items and a second node for a second item in the plurality of items; and

computing a weight for an edge between the first node and the second node based at least in part on the plurality of first-order user preferences and the at least one second-order user preference, wherein the weight is indicative of a degree of preference for the first item over the second item.

38. The at least one computer-readable storage medium article of claim 37, wherein the preference graph comprises a third node for a third item in the plurality of items, a fourth node for a fourth item in the plurality of items, the method further comprising:

constructing the at least one data structure encoding the preference graph to include an edge between the third node and the fourth node when the plurality of first-order user preferences comprises a first-order user preference for the third item over the fourth item.

39. The at least one computer-readable storage medium article of claim 37, further comprising:

constructing the at least one data structure encoding the preference graph to include a node for each item in the plurality of items and an edge for every pair of nodes associated with items related by a first-order user preference in the plurality of first-order user preferences.

40. The at least one computer-readable storage medium article of claim 37, wherein computing the weight comprises:

computing a first number of first-order user preferences in the plurality of first-order user preferences indicating a user'"'"'s preference for the first item relative to the second item;

computing a second number of all first-order user preferences in the plurality of first-order user preferences indicating any preference associated with the first item; and

setting the weight based at least in part on the first number and the second number.

41. The at least one computer-readable storage medium article of claim 37, wherein items in the plurality of items are represented as tuples, each tuple comprising values of the attributes of the corresponding item, and wherein receiving the plurality of first-order preferences comprises:

receiving a first-order preference for the first item over the second item by receiving an indication of a user preference for a first value of a first attribute of a first tuple representing the first item over a second value of the second attribute of a second tuple representing the second item.

42. The at least one computer-readable storage medium article of claim 41, wherein the first attribute is a same attribute as the second attribute.

43. The at least one computer-readable storage medium article of claim 37, wherein the plurality of first-order user preferences comprises at least two types of first-order user preferences selected from the group consisting of score-based preferences, partial order preferences, skyline preferences, and conjoint analysis preferences.

44. The at least one computer-readable storage medium article of claim 37, wherein the at least one second-order user preference comprises a plurality of second-order user preference relations that comprises at least two types of second-order preferences selected from the group consisting of prioritized preference composition, partial order preferences, pairwise preferences, and Pareto preference composition.