Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search

Summary: Isolates and accelerates the Distance Comparison Operation (DCO) in high-dimensional AKNN by proposing DADE, a data-aware, unbiased lower-dimensional distance estimator with an optimized formulation. Adds a hypothesis-testing scheme to adaptively pick minimal projection dimensions and plugs into IVF/HNSW to cut DCO-dominated latency. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 14427
Venue: VLDB
Year: 2025
Pagerank: 5.9654376e-05
Overall Rank: 6,133 | 57.93%
DOI: 10.14778/3712221.3712244

Incoming Non-self Citations Over Time

Authors

1. Liwei Deng (University of Electronic Science and Technology of China)
2. Penghao Chen (University of Electronic Science and Technology of China)
3. Ximu Zeng (University of Electronic Science and Technology of China)
4. Tianfu Wang (University of Science and Technology Beijing)
5. Yan Zhao (Shenzhen University)
6. Kai Zheng (Shenzhen University)

BibTeX Citation

@article{deng_vldb25,
        title = {{Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search}},
        author = {Deng, Liwei and Chen, Penghao and Zeng, Ximu and Wang, Tianfu and Zhao, Yan and Zheng, Kai},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {3},
        pages = {812--821},
        doi = {10.14778/3712221.3712244},
        url = {https://doi.org/10.14778/3712221.3712244},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,889	SAQ: Pushing the Limits of Vector Quantization through Code Adjustment and Dimension Segmentation	2026	SIGMOD	5.1997534e-05
10,251	GPS: Revisiting the Data Layout for Disk-based High-Dimensional Vector Search	2026	SIGMOD	5.093636e-05
10,299	Through the Lens of Hubness: A Revisit on Graph-Based Approximate Nearest Neighbor Search: [Experiments & Analysis]	2026	SIGMOD	5.093636e-05
10,336	Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations	2026	SIGMOD	5.093636e-05
10,362	Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search	2026	SIGMOD	5.093636e-05
10,412	TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning	2026	SIGMOD	5.093636e-05
10,525	Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search	2026	VLDB	5.093636e-05
10,544	I/O Optimizations for Graph-Based Disk-Resident Approximate Nearest Neighbor Search: A Design Space Exploration	2026	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040719947
93	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034701237
369	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00019945234
398	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00019194947
580	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016157635
705	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014829964
926	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.00013181732
1,244	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	0.00011508159
1,357	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	0.00011043994
1,546	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	0.00010407159
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,534	ELPIS: Graph-Based Similarity Search for Scalable Data Science	2023	VLDB	8.4561875e-05
2,938	FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems	2017	SIGMOD	7.942728e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,454	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD
2	398	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB
3	1,612	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB
4	2,158	What is the nearest neighbor in high dimensional spaces?	2000	VLDB
5	705	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB
6	3,710	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD
7	9,165	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB
8	10,336	Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations	2026	SIGMOD
9	1,137	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS
10	1,735	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD