Given a set of points S and a query point q, the k-nearest neighbour (k-NN) problem is to find the k points in S that are closest to q. This geometric problem is ubiquitous in (web) information retrieval and efficient algorithms are hard to come by, in spite of much work done in the area. In this talk we will introduce a very simple random clustering (RC) technique and show that: (1) RC can be analyzed mathematically and strong, useful properties can be proven about it; (2) with real data, RC outperforms well-known solutions for k-NN such as p-spheres and rank aggregation. Our experiments show that RC is superior to these well-known methods for a variety of applications, including text retrieval and image processing. Our theorems explain why.
Joint work with: Flavio Chierichetti, Prabakhar Raghavan, Mauro Sozio, Alessandro Tiberi, and Eli Upfal