Abstract We consider the problem of indexing high-dimensional data for answering (approximate) similarity search queries. Similarity indexes prove to be important in a wide variety of settings: Web search engines desire fast, parallel, main-memory based indexes for similarity search on text data; database systems desire disk-based similarity indexes for a variety of high-dimensional data, including text and images; peer-to-peer systems desire distributed similarity indexes that can index data with low communication cost. We propose an indexing scheme called LSH Forest which is applicable in all the above contexts. Our index uses the well-known technique of locality-sensitive hashing (LSH), but improves upon previous designs by (a) eliminating the different data-dependent parameters for which LSH must be constantly hand-tuned, and (b) improving on LSH's performance guarantees for skewed data distributions while retaining the same storage and query overhead. We show how to construct this index in main memory, on disk, in parallel systems, and in peer-to-peer systems. We evaluate the design with experiments on multiple text corpora and demonstrate both the self-tuning nature and the superior performance of LSH Forest.
bawa@cs.stanford.edu
01-28-2005