DBScholar

Back to papers

VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning

Summary: VHP bounds LSH candidate search with a query-centered virtual hypersphere, emulated by coordinated physical hyperspheres across projections. Independent B+-trees and principled radius growth provide probabilistic c-ANN guarantees and up to 2× speedups on billion-scale data. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
12242
Venue
VLDB
Year
2020
Pagerank
0.0001080902
Overall Rank
1,430 | 90.20%
DOI
10.14778/3397230.3397240

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{lu_vldb20,
        title = {{VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning}},
        author = {Lu, Kejing and Wang, Hongya and Wang, Wei and Kudo, Mineichi},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {9},
        pages = {1443--1455},
        doi = {10.14778/3397230.3397240},
        url = {https://doi.org/10.14778/3397230.3397240},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 26 of 26 citing papers.

Rank Citing Paper Year Venue Pagerank
286 Milvus: A Purpose-Built Vector Data Management System 2021 SIGMOD 0.00022357911
1,357 RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search 2024 SIGMOD 0.00011043994
1,515 ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data 2024 SIGMOD 0.00010521317
1,589 Manu: A Cloud Native Vector Database Management System 2022 VLDB 0.00010264469
1,735 High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations 2023 SIGMOD 9.9004924e-05
1,760 Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment 2024 SIGMOD 9.8157819e-05
1,802 HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search 2022 VLDB 9.7284341e-05
1,934 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB 9.4561907e-05
2,920 SingleStore-V: An Integrated Vector Database System in SingleStore 2024 VLDB 7.9628307e-05
3,310 Similarity Query Processing for High-Dimensional Data 2020 VLDB 7.5363562e-05
3,364 Vexless: A Serverless Vector Data Management System Using Cloud Functions 2024 SIGMOD 7.4796687e-05
4,965 LANNS: A Web-Scale Approximate Nearest Neighbor Lookup System 2022 VLDB 6.4241124e-05
5,121 Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere 2021 SIGMOD 6.3577317e-05
5,800 DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search 2024 VLDB 6.0850924e-05
6,956 A New Sparse Data Clustering Method Based On Frequent Items 2023 SIGMOD 5.7303405e-05
7,124 GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces 2025 VLDB 5.6961208e-05
7,145 Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search 2025 SIGMOD 5.6908957e-05
7,166 Accelerating Graph Indexing for ANNS on Modern CPUs 2025 SIGMOD 5.6846045e-05
7,761 DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph 2025 SIGMOD 5.550467e-05
9,493 MQH: Locality Sensitive Hashing on Multi-level Quantization Errors for Point-to-Hyperplane Distances 2023 VLDB 5.2621754e-05
10,242 FAVOR: Efficient Filter-Agnostic Vector ANNS Based on Selectivity-Aware Exclusion Distances 2026 SIGMOD 5.093636e-05
10,247 GEM: A Native Graph-based Index for Multi-Vector Retrieval 2026 SIGMOD 5.093636e-05
10,400 Scalable Graph Indexing using GPUs for Approximate Nearest Neighbor Search 2026 SIGMOD 5.093636e-05
10,443 Distribution-Aware Exploration for Adaptive HNSW Search 2026 SIGMOD 5.093636e-05
10,454 Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search 2026 SIGMOD 5.093636e-05
11,738 Fast Algorithm for Anchor Graph Hashing 2021 VLDB 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank Cited Paper Year Venue Pagerank
46 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00044853085
287 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.00022323585
332 Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search 2016 VLDB 0.00020920444
369 Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting 2012 SIGMOD 0.00019945234
580 SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index 2015 VLDB 0.00016157635
581 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00016153395
690 Efficient Similarity Search and Classification via Rank Aggregation 2003 SIGMOD 0.0001492934
705 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014829964
990 SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00012796562
1,546 PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search 2020 VLDB 0.00010407159
2,673 DSH: Data Sensitive Hashing for High-Dimensional k-NN Search 2014 SIGMOD 8.2730112e-05
2,734 Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search 2020 VLDB 8.190416e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 581 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD
2 369 Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting 2012 SIGMOD
3 3,279 Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring 2020 SIGMOD
4 9,493 MQH: Locality Sensitive Hashing on Multi-level Quantization Errors for Point-to-Hyperplane Distances 2023 VLDB
5 580 SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index 2015 VLDB
6 990 SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB
7 1,546 PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search 2020 VLDB
8 5,121 Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere 2021 SIGMOD
9 1,934 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB
10 332 Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search 2016 VLDB