Efficient similarity search and classification via rank aggregation

摘要

A system, method, and computer program product for automatically performing similarity search, classification, and other nearest-neighbor search-based applications using rank aggregation. The invention reduces the &egr;-approximate Euclidean nearest neighbor problem to the problem of finding the candidate with the best median rank in an election with n candidates and O(&egr;^−2logn) voters. ;Database elements and a query are points projected in a multidimensional Euclidean space, and coordinates in the space serve as independent “voters” that rank database elements by their closeness to the query coordinate. The rankings are aggregated and the winners are the database elements with the highest aggregated ranks. ;Combined with dimensionality reduction, the invention is a simple, efficient, database-friendly scheme for generating a &egr;-approximate nearest neighbor answer. ;The invention also enables searching of categorical vs. mere numerical features by sorting the database according to each feature and aggregating the resulting rankings.