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.