Method of ranking items using efficient queries

• US 20020165859A1
• Filed: 04/04/2001
• Published: 11/07/2002
• Est. Priority Date: 04/04/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lee, Jonathan, Iyengar, Vijay S.
• Granted Patent: US 6,721,737 B2
• Time in Patent Office: Days
• US Class Current: 707/5
• CPC Class Codes: G06F 16/2425 Iterative querying; Query formulation based on the results of a preceding query
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method is provided for ranking a plurality of items. The method comprises initializing a (D−1) dimensional weight space including a feasible region, where D is equal to a number of attributes and a point in the weight space corresponds to each attribute, determining an item pair, and querying a user to select an item from among the item pair. The method further includes reducing the feasible region based upon a user'"'"'s item selection, and ranking the items according a ranking point in a reduced feasible region. The ranking point is a center of the reduced feasible region, wherein the center is one of a vertex barycenter and center of gravity. The ranking point corresponds to a users item selection. The method includes the step of selecting a plurality of hyperplanes, each hyperplane corresponding to an item pair such that the hyperplane divides the feasible region into two substantially equal portions.

Claims

1. A method for ranking a plurality of items comprising the steps of:

initializing a (D−

1) dimensional weight space including a feasible region, where D is equal to a number of attributes and a point in the weight space corresponds to each attribute;

reducing the feasible region based upon an item selection; and

ranking the items according a ranking point in a reduced feasible region.

2. The method of claim 1, wherein the item selection is provided by historical data.

3. The method of claim 1, wherein the ranking point is a center of the reduced feasible region.

4. The method of claim 1, further comprising the steps of:

determining a k-member set of items; and

querying a user to select an item from among the k-member set.

5. The method of claim 4, further comprising the step of determining an additional query upon determining that the reduced feasible region includes at least one point.

6. The method of claim 4, further comprising the step of determining an additional query upon determining that a convergence is greater than a predefined minimum change, wherein the convergence is one of a change in the volume of the feasible region and the change in the position of the ranking point in the feasible region.

7. The method of claim 5, wherein a maximum number of queries is defined by a user.

8. The method of claim 5, wherein the step of querying the user to select an item further comprises:

determining at least two portions of the feasible space, the portions defined by at least one hyperplane, each hyperplane defined by two items; and

reducing the feasible region to the portion corresponding to the user selected item.

9. The method of claim 1, wherein the k-member item set is an item pair.

10. The method of claim 1, wherein the item selection is between at least three items.

11. The method of claim 10, further comprising the steps of:

determining a hyperplane for each item pair with each item set;

determining a volume for each portion of the feasible region as divided by each hyperplane; and

selecting an item set, the largest portion of the selected item set including the smallest volume among the plurality of largest portions of each item set.

12. The method of claim 11, wherein the volume for each portion is the volume of a bounding box enclosing the portion.

15. The method of claim 14, wherein the ranking point is a center of the reduced feasible region, wherein the center is one of a vertex barycenter and center of gravity.

16. The method of claim 14, further comprising the step of determining an additional query upon determining that a convergence is greater than a predefined minimum change, wherein the convergence is one of a change in the volume of the feasible region and the change in the position of the ranking point in the feasible region.

17. The method of claim 14, wherein a maximum number of queries is defined by a user.

18. The method of claim 14, wherein the step of determining the item pair further comprises the steps of:

determining a volume for each portion of the feasible region as divided by a hyperplane defined by an item pair, for each item pair respectively; and

selecting an item pair, the largest portion of the selected item pair including the smallest volume among the plurality of largest portions of each item pair.

19. The method of claim 18, wherein the volume for each portion is the volume of a bounding box enclosing the portion.

20. The method of claim 18, further comprising the step of selecting a plurality of hyperplanes proximate to the center of the feasible region.

21. The method of claim 20, wherein proximity is a function of a normal distance to the center of the feasible region.

13. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for ranking a plurality of items, the method steps comprising:

initializing a (D−

1) dimensional weight space including a feasible region, where D is equal to a number of attributes and a point in the weight space corresponds each attribute;

reducing the feasible region based upon an item selection; and

ranking the items according a ranking point in a reduced feasible region.

14. A method for ranking a plurality of items comprising the steps of:

initializing a (D−

1) dimensional weight space including a feasible region, where D is equal to a number of attributes and a point in the weight space corresponds to each attribute;

determining an item pair;

querying a user to select an item from among the item pair;

reducing the feasible region based upon a user'"'"'s item selection; and

ranking the items according a ranking point in a reduced feasible region.