DB-LSH: Locality-Sensitive Hashing with Query-based Dynamic Bucketing
Authors:
- 1 May 2022
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2250-2262
Abstract
Among many solutions to the high-dimensional approximate nearest neighbor (ANN) search problem, locality sensitive hashing (LSH) is known for its sub-linear query time and robust theoretical guarantee on query accuracy. Traditional LSH methods can generate a small number of candidates quickly from hash tables but suffer from large index sizes and hash boundary problems. Recent studies to address these issues often incur extra overhead to identify eligible candidates or remove false positives, making query time no longer sub-linear. To address this dilemma, in this paper we propose a novel LSH scheme called DB-LSH which supports efficient ANN search for large high-dimensional datasets. It organizes the projected spaces with multi-dimensional indexes rather than using fixed-width hash buckets. Our approach can significantly reduce the space cost by avoiding the need to maintain many hash tables for different bucket sizes. During the query phase of DB-LSH, a small number of high-quality candidates can be generated efficiently by dynamically constructing query-based hypercubic buckets with the required widths through index-based window queries. For a dataset of $n$ d-dimensional points with approximation ratio $c$, our rigorous theoretical analysis shows that DB-LSH achieves a smaller query cost $O(n^{\rho}d\log n)$, where $\rho^{\ast}$ is bounded by $1/c^{\alpha}$ versus a bound of $1/c$ in the existing work. An extensive range of experiments on real-world data demonstrate the superiority of DB-LSH over state-of-the-art methods on both efficiency and accuracy.
Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- R2LSH: A Nearest Neighbor Search Scheme Based on Two-dimensional Projected Spaces2020
- Approximate Nearest Neighbor Search on High Dimensional Data — Experiments, Analyses, and ImprovementIEEE Transactions on Knowledge and Data Engineering, 2019
- I-LSH: I/O Efficient c-Approximate Nearest Neighbor Search in High-Dimensional Space2019
- Use of locality sensitive hashing (LSH) algorithm to match Web of Science and ScopusScientometrics, 2017
- DSH2014
- Locality-sensitive hashing scheme based on dynamic collision counting2012
- Quality and efficiency in high dimensional nearest neighbor search2009
- Entropy based nearest neighbor search in high dimensions2006
- LSH forest2005
- Performance Evaluation of Main-Memory R-tree Variants2003