Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-04-04
2004-04-13
Alam, Shahid (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C709S206000, C705S007380
Reexamination Certificate
active
06721737
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to ranking items and more particularly to a method for ranking items based on user preferences.
2. Discussion of the Prior Art
Ranking comparable items with multiple attributes based on user preferences is a task that is performed in various domains. For example, ranking bids received in response to a request for quotes in a marketplace. The ranking may be based on the user's notion of desirability for various attributes of goods or services. A value function may be formulated to combine the attributes of the goods or services.
Current proposed ranking methods describe user preferences in terms of values corresponding to attributes of an item. The proposed methods rank items based on comparisons of corresponding value functions. The choice of a value function may be done with or without interaction with the user. A choice may include a linear model for weighting the importance of a group of attributes. A ranking method then sums each attribute's weighted contribution to the value functions to compute an overall score for each item. The items are ranked based on the computed overall scores.
Another proposed method is provided by Perfect.com, embodied in the PerfectMarket (TM) product. A user is asked to specify weights for various item attributes in terms of relative importance. The system uses the explicitly specified weights to rank a group of items having the attributes. The method allowing the user to specify these weights explicitly is not easy or intuitive.
Active Research has a proposed method embodied in the Active Sales Assistant (TM) product. However, like other prior art methods, this method first queries the user about the desirability of various attributes. The method then iteratively queries the user to select a preferred item amongst a pair of synthetically generated items, the synthetic items including different subsets of the attributes. In the next step, the user is queried to provide other information about themselves before a final ranked list of items is determined. The multiple stages and types of queries in the method may be undesirable. The use of synthetic items in the pair wise ranking queries may not be desirable since it may give the user a false notion of what items are available. Displaying a small subset of the attributes with these synthetic items adds to the artificial ranking scenario used to gather the user preferences. In summary, this method is tedious and does not accurately capture user preferences.
Therefore, a need exists for a system and method of ranking items using efficient queries.
SUMMARY OF THE INVENTION
It is an object of this invention to provide a method of ranking items that uses intuitive queries to learn user preferences. It is an object of the present invention to be efficient with the queries while learning the user preferences accurately. It is an object of this invention to use actual items for comparisons so that accurate preferences may be determined by comparing item attributes simultaneously. It is an object of this invention to provide a ranking that is consistent with user responses to the queries; otherwise indicating to the user that a ranking not feasible.
According to an embodiment of the present invention, a method is provided for ranking a plurality of items. The method includes 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. The item selection can be provided by historical data. The ranking point is a center of the reduced feasible region.
The method includes determining a k-member set of items, and querying a user to select an item from among the k-member set. The method includes determining an additional query upon determining that the reduced feasible region includes at least one point. The method includes 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 within the feasible region. A maximum number of queries is defined by a user.
Querying the user to select an item includes 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.
The k-member item set is an item pair. The item selection is between at least three items.
The method includes determining a hyperplane for each item pair within 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. The volume for each portion is the volume of a bounding box enclosing the portion.
According to an embodiment of the present invention, a program storage device is provided, 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 includes 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.
According to an embodiment of the present invention, 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 method includes 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 within the feasible region. A maximum number of queries can be defined by a user.
The step of determining the item pair includes 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. The volume for each portion is the volume of a bounding box enclosing the portion.
The method includes selecting a plurality of hyperplanes proximate to the center of the feasible region. Proximity is a function of a normal distance to the center of the feasible region.
REFERENCES:
patent: 5930762 (1999-07-01), Masch
patent: 5933822 (1999-08-01), Braden-Harder et al.
patent: 6161130 (2000-12-01), Horvitz et al.
patent: 6173279 (2001-01-01), Levin et al.
patent: 6192360 (2001-02-01), Dumais et al.
patent: 6289353 (2001-09-01), Hazlehurst et al.
patent: 6408300 (2002-06-01), Bergman et al.
patent: 6453246 (2002-09-01), Agrafiotis et al.
Komei Fukuda & Alain Prodon, “Double Description Method Revisited”, pp. 1-22.
Benno Bueler, Andreas Enge & Komei Fukuda, “Exact Volume Computation For Polytopes”, Jan. 12, 1998 revised Aug. 7, 1998, pp. 1-18.
J.B. Lasserre, An Analytical Expression and a
Iyengar Vijay S.
Lee Jonathan
Alam Shahid
F. Chau & Associates LLC
LandOfFree
Method of ranking items using efficient queries does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of ranking items using efficient queries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of ranking items using efficient queries will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3244668