Database Paper Browser

Back to papers

HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces

Summary: HD-Index proposes RDB-trees built on Hilbert keys for scalable, approximate kNN in massive high-dimensional data. Leaves store distances to reference objects, enabling distance-filter pruning; by applying triangular and Ptolemaic inequalities, it tightens lower bounds for billion-scale, 1000+‑dimensional workloads. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
11794
Venue
VLDB
Year
2018
Pagerank
0.00014632051
Overall Rank
1,013 | 92.97%
DOI
10.14778/3204028.3204034

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 35 of 35 citing papers.

Rank Citing Paper Year Venue Pagerank
210 Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph 2019 VLDB 0.00034086264
763 A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search 2021 VLDB 0.00016963981
1,934 VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning 2020 VLDB 0.00010047294
2,434 iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search 2020 VLDB 8.8225986e-05
2,657 Detecting Logic Bugs of Join Optimizations in DBMS 2023 SIGMOD 8.3636172e-05
3,182 DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search 2020 VLDB 7.4280768e-05
3,199 Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search 2020 VLDB 7.3999833e-05
3,403 ELPIS: Graph-Based Similarity Search for Scalable Data Science 2023 VLDB 7.1338786e-05
4,622 Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art 2025 SIGMOD 6.0356382e-05
5,559 LANNS: A Web-Scale Approximate Nearest Neighbor Lookup System 2022 VLDB 5.437026e-05
6,970 AquaPipe: A Quality-Aware Pipeline for Knowledge Retrieval and Large Language Models 2025 SIGMOD 4.8740302e-05
7,090 Dumpy: A Compact and Adaptive Index for Large Data Series Collections 2023 SIGMOD 4.8318862e-05
7,235 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB 4.7882389e-05
7,307 Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes 2024 VLDB 4.7623207e-05
7,612 UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search 2025 VLDB 4.6919232e-05
7,654 LiteHST: A Tree Embedding based Method for Similarity Search 2023 SIGMOD 4.6831082e-05
7,843 GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces 2025 VLDB 4.6335219e-05
8,430 Accelerating Graph Indexing for ANNS on Modern CPUs 2025 SIGMOD 4.508568e-05
8,495 DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph 2025 SIGMOD 4.4938255e-05
8,709 ANN Softmax: Acceleration of Extreme Classification Training 2022 VLDB 4.4584416e-05
9,399 BigVectorBench: Heterogeneous Data Embedding and Compound Queries are Essential in Evaluating Vector Databases 2025 VLDB 4.3399748e-05
9,684 How to Design Robust Algorithms using Noisy Comparison Oracle 2021 VLDB 4.3006524e-05
9,821 DIDS: Double Indices and Double Summarizations for Fast Similarity Search 2024 VLDB 4.2716118e-05
9,913 RWalks: Random Walks as Attribute Diffusers for Filtered Vector Search 2025 SIGMOD 4.2520778e-05
10,052 Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study 2026 SIGMOD 4.1905499e-05
10,071 Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search 2026 SIGMOD 4.1905499e-05
10,086 High-Throughput, Cost-Effective Billion-Scale Vector Search with a Single GPU 2026 SIGMOD 4.1905499e-05
10,154 Distribution-Aware Exploration for Adaptive HNSW Search 2026 SIGMOD 4.1905499e-05
10,187 On Efficient Approximate Aggregate Nearest Neighbor Queries over Learned Representations 2026 SIGMOD 4.1905499e-05
10,256 I/O Optimizations for Graph-Based Disk-Resident Approximate Nearest Neighbor Search: A Design Space Exploration 2026 VLDB 4.1905499e-05
10,260 JHQ: Johnson-Lindenstrauss Enhanced Hierarchical Quantization for High-Dimensional Approximate Nearest Neighbor Search 2026 VLDB 4.1905499e-05
10,420 MicroNN: An On-device Disk-resident Updatable Vector Database 2025 SIGMOD 4.1905499e-05
10,610 Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-based ANN Index Updates 2025 VLDB 4.1905499e-05
10,744 Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-based ANN Search 2025 VLDB 4.1905499e-05
11,342 Scalable Time Series Compound Infrastructure 2022 SIGMOD 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 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.0032118946
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016113151
78 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00056385781
91 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00051785122
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00044255276
301 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00028396714
399 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.00024359304
579 Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting 2012 SIGMOD 0.0001982328
596 Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search 2016 VLDB 0.00019455943
675 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00018304179
710 Efficient Similarity Search and Classification via Rank Aggregation 2003 SIGMOD 0.00017727016
858 SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index 2015 VLDB 0.00015833075
929 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.0001523035
1,225 SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00013182109
1,923 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 0.00010079134
3,301 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.2450912e-05
7,006 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS 4.8606861e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
574 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.0001987713
9,026 Dimensional Testing for Reverse k-Nearest Neighbor Search 2017 VLDB 4.4030177e-05
2,969 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB 7.7955562e-05
3,574 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 6.9520978e-05
2,099 What is the nearest neighbor in high dimensional spaces? 2000 VLDB 9.5429949e-05
675 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00018304179
858 SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index 2015 VLDB 0.00015833075
1,180 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00013455619
8,559 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD 4.4893996e-05
34 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00076824554