LSH forest: self-tuning indexes for similarity search
Explore this paper's citation graph
Summary
This index uses the well-known technique of locality-sensitive hashing (LSH), but improves upon previous designs by eliminating the different data-dependent parameters for which LSH must be constantly hand-tuned, and improving on LSH's performance guarantees for skewed data distributions while retaining the same storage and query overhead.
- Type
- article
- Published
- 2005-05-10
- Cited by
- 435
- References
- 39
- OpenAlex
- https://openalex.org/W2148781362
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:5771325
Keywords
Search engine indexing, Computer science, Locality-sensitive hashing, Similarity (geometry), Nearest neighbor search
References
- Scalable Data Access in Peer-to-Peer Systems Using Unbalanced Search Trees
- Similarity Search in High Dimensions via Hashing
- A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces
- Topical locality in the Web
- Authoritative sources in a hyperlinked environment
- Finding Related Pages in the World Wide Web
- Mirror, Mirror on the Web: A Study of Host Pairs with Replicated Content
- Building a scalable and accurate copy detection mechanism
- Computing Iceberg Queries Efficiently
- Automatic Resource Compilation by Analyzing Hyperlink Structure and Associated Text
- Copy detection mechanisms for digital documents
- Prefix B-trees
- Pagination of B*-trees with variable-length records
- Inferring Web communities from link topology
- Finding interesting associations without support pruning
- The K-D-B-tree: a search structure for large multidimensional dynamic indexes
- The string B-tree: a new data structure for string search in external memory and its applications
- The evolution of effective B-tree: page organization and techniques: a personal account
- R-trees: a dynamic index structure for spatial searching
- Measures of Distributional Similarity
Cited by
- OSRI: A Rotationally Invariant Binary Descriptor
- Classifications, Problems Identification and a New Approach
- Hashing-basierte Indizierung: Anwendungsszenarien, Theorie und Methoden
- Data De-duplication: A Review
- High-Dimensional Similarity Search for Large Datasets
- RIQ: Fast processing of SPARQL queries on RDF quadruples
- RankReduce - Processing K-Nearest Neighbor Queries on Top of MapReduce
- Distributed High-Dimensional Similarity Search with Music Information Retrieval Applications
- A study of gossip algorithms for Internet-scale cardinality estimation of distributed XML data
- Efficient Location-Aware Node and Object Discovery in Large-Scale Networks
- Pruning SIFT for Scalable Near-duplicate Image Matching
- Asymmetric Cyclical Hashing for Large Scale Image Retrieval
- Peer-to-Peer Similarity Search in Metric Spaces
- Enhancing Locality Sensitive Hashing with Peek Probing and Nearest Neighbor Links
- Event mining for system and service management
- An LSH Index for Computing Kendall's Tau over Top-k Lists
- Sharing of probabilistically correlated data in peer-to-peer networks
- Hashing for Similarity Search: A Survey
- Optimisation of correlation matrix memory prognostic and diagnostic systems
- Efficient k-Nearest Neighbors Search in High Dimensions Using MapReduce
Related papers
- Locality-sensitive hashing scheme based on dynamic collision counting
- Efficient protein structure search using indexing methods
- LSH vs Randomized Partition Trees: Which One to Use for Nearest Neighbor Search?
- Review on Locality Sensitive Hashing in Centralized Environment
- An Efficient Similarity Searching Scheme in Massive Databases
- Higher-dimensional Nearest Neighbor Search by Distributed Coding
- High-Dimensional Indexing
- Theoretical analysis on pruning nearest neighbor candidates by locality sensitive hashing
- A posteriori multi-probe locality sensitive hashing