document: LSH forest : self-tuning indexes for similarity search 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 .
doc_bio_tags: O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O