DBScholar

Back to papers

Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search

Summary: Multi-Probe LSH reduces LSH’s costly proliferation of hash tables by probing multiple promising buckets within each table. It preserves search quality and time efficiency while cutting space by an order of magnitude, outperforming entropy-based LSH. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
he148960fa9d0596b
Venue
VLDB
Year
2007
Pagerank
0.0002230467
Overall Rank
280 | 98.12%
DOI
10.14778/1325851.1325870

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{lv_vldb07,
        title = {{Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search}},
        author = {Lv, Qin and Josephson, William and Wang, Zhe and Charikar, Moses and Li, Kai},
        journal = {PVLDB},
        series = {{VLDB} '07},
        volume = {30},
        number = {2},
        pages = {950--961},
        doi = {10.14778/1325851.1325870},
        url = {https://doi.org/10.14778/1325851.1325870},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 48 of 48 citing papers.

Rank Citing Paper Year Venue Pagerank
338 Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting 2012 SIGMOD 0.00020585187
457 Distributed Representations of Tuples for Entity Resolution 2018 VLDB 0.00017907103
562 SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index 2015 VLDB 0.00016335405
576 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00016121388
650 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00015149775
927 SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00013025904
992 Bayesian Locality Sensitive Hashing for Fast Similarity Search 2012 VLDB 0.00012646771
1,328 VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning 2020 VLDB 0.00011003106
1,485 PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search 2020 VLDB 0.00010523759
1,530 LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index 2016 SIGMOD 0.00010344205
1,897 iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search 2020 VLDB 9.4092345e-05
1,957 SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search 2024 SIGMOD 9.3159589e-05
2,448 DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search 2020 VLDB 8.4494625e-05
2,505 DSH: Data Sensitive Hashing for High-Dimensional k-NN Search 2014 SIGMOD 8.3779738e-05
2,568 Locality-Sensitive Hashing for Earthquake Detection: A Case Study of Scaling Data-Driven Science 2018 VLDB 8.2870435e-05
2,969 Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring 2020 SIGMOD 7.8000797e-05
3,236 Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond 2017 VLDB 7.5020521e-05
3,290 Vexless: A Serverless Vector Data Management System Using Cloud Functions 2024 SIGMOD 7.4528093e-05
3,546 A General and Efficient Querying Method for Learning to Hash 2018 SIGMOD 7.2123214e-05
3,750 NET-FLi: On-the-fly Compression, Archiving and Indexing of Streaming Network Traffic 2010 VLDB 7.0527908e-05
4,050 Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search 2025 VLDB 6.8298981e-05
4,151 Inter-Media Hashing for Large-scale Retrieval from Heterogeneous Data Sources 2013 SIGMOD 6.776727e-05
4,688 Learned Cardinality Estimation for Similarity Queries 2021 SIGMOD 6.4697463e-05
4,856 Neighbor-Sensitive Hashing 2016 VLDB 6.3798143e-05
5,268 FARGO: Fast Maximum Inner Product Search via Global Multi-Probing 2023 VLDB 6.2015316e-05
5,444 Pigeonring: A Principle for Faster Thresholded Similarity Search 2019 VLDB 6.1268526e-05
5,796 Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search 2015 PODS 5.9910143e-05
5,920 ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph 2023 VLDB 5.9475097e-05
5,935 Continuously Adaptive Similarity Search 2020 SIGMOD 5.9419167e-05
5,987 SetSketch: Filling the Gap between MinHash and HyperLogLog 2021 VLDB 5.9259433e-05
6,646 Similarity Search and Locality Sensitive Hashing using Ternary Content Addressable Memories 2010 SIGMOD 5.7218669e-05
6,768 Dynamic Range-Filtering Approximate Nearest Neighbor Search 2025 VLDB 5.686858e-05
7,096 A New Sparse Data Clustering Method Based On Frequent Items 2023 SIGMOD 5.601767e-05
7,322 LIDER: An Efficient High-dimensional Learned Index for Large-scale Dense Passage Retrieval 2023 VLDB 5.5533524e-05
7,329 Randomized Algorithms Accelerated over CPU-GPU for Ultra-High Dimensional Similarity Search 2018 SIGMOD 5.5505604e-05
7,906 Near-Duplicate Text Alignment with One Permutation Hashing 2024 SIGMOD 5.428873e-05
8,998 ANN Softmax: Acceleration of Extreme Classification Training 2022 VLDB 5.2400492e-05
10,449 Enhancing Graph-based Approximate Maximum Inner Product Search via Norm-Adaptive Partitioning 2026 SIGMOD 4.9793485e-05
10,478 LSHAlign: All-Pair Near-Duplicate Text Alignment via LSH 2026 SIGMOD 4.9793485e-05
10,677 RAIRS: Optimizing Redundant Assignment and List Layout for IVF-Based ANN Search 2026 SIGMOD 4.9793485e-05
10,730 JHQ: Johnson-Lindenstrauss Enhanced Hierarchical Quantization for High-Dimensional Approximate Nearest Neighbor Search 2026 VLDB 4.9793485e-05
10,834 ConANN: Conformal Approximate Nearest Neighbor Search 2026 VLDB 4.9793485e-05
10,851 GAS: A Lightweight Framework for Filtered Search over Wide-table Vectors 2026 VLDB 4.9793485e-05
11,240 Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search 2025 VLDB 4.9793485e-05
11,918 ONe Index for All Kernels (ONIAK): A Zero Re-Indexing LSH Solution to ANNS-ALT (After Linear Transformation) 2022 VLDB 4.9793485e-05
12,035 MP-RW-LSH: An Efficient Multi-Probe LSH Solution to ANNS-L1 2021 VLDB 4.9793485e-05
12,150 Top-k Queries over Digital Traces 2019 SIGMOD 4.9793485e-05
12,662 Effective Data Co-Reduction for Multimedia Similarity Search 2011 SIGMOD 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.001992968
20 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00057568153
45 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.0004503446
279 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022308048
1,793 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.6235776e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,485 PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search 2020 VLDB
2 2,362 Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing 2013 VLDB
3 2,505 DSH: Data Sensitive Hashing for High-Dimensional k-NN Search 2014 SIGMOD
4 576 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD
5 20 Similarity Search in High Dimensions via Hashing 1999 VLDB
6 1,625 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB
7 1,530 LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index 2016 SIGMOD
8 12,035 MP-RW-LSH: An Efficient Multi-Probe LSH Solution to ANNS-L1 2021 VLDB
9 5,796 Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search 2015 PODS
10 3,236 Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond 2017 VLDB