TOP-K SEARCH USING RANDOMLY OBTAINED PAIRWISE COMPARISONS

摘要

A method and apparatus for determining a pre-determined number of top ranked items are described including accepting a set of unranked items, the pre-determined number, and a random selection of pairwise comparisons, creating a graph structure using the set of unranked items and the random selection of pairwise comparisons, wherein the graph structure includes vertices corresponding to the items and edges corresponding to a pairwise ranking and performing a depth-first search for each item that is an element of the set of unranked items for paths along the edges through the graph that are not greater than a length equal to the pre-determined number.

主权项

1. A method for determining a pre-determined number of top ranked items, said method comprising:
accepting a set of unranked items, said pre-determined number, and a random selection of pairwise comparisons; creating a graph structure using said set of unranked items and said random selection of pairwise comparisons, wherein said graph structure includes vertices corresponding to said items and edges corresponding to a pairwise ranking; and performing a depth-first search for each item that is an element of said set of unranked items for paths along said edges through said graph that are not greater than a length equal to said pre-determined number.