Stanford InfoLab Publication Server

LSH Forest: Self-Tuning Indexes for Similarity Search

Bawa, Mayank and Condie, Tyson and Ganesan, Prasanna (2005) LSH Forest: Self-Tuning Indexes for Similarity Search. In: Fourteenth International World Wide Web Conference (WWW 2005), May 10-14, 2005, Chiba, Japan.




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 high-dimensional data, including text and images; peer-to-peer systems desire distributed similarity indexes 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.

Item Type:Conference or Workshop Item (Paper)
Subjects:Computer Science > Databases and the Web
Computer Science > Distributed Systems
Computer Science > Query Processing
Related URLs:Project Homepage
ID Code:678
Deposited By:Import Account
Deposited On:15 May 2005 17:00
Last Modified:22 Dec 2008 17:52

Download statistics

Repository Staff Only: item control page