High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations

Summary: Proposes ADSampling, a randomized DCO-sampling technique that reduces high-dimensional AKNN distance comparisons from linear to logarithmic time with high probability. It serves as a generic plugin and as algorithm-specific accelerators, offering negligible accuracy loss and measurable speedups. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6702
Venue: SIGMOD
Year: 2023
Pagerank: 9.9004924e-05
Overall Rank: 1,735 | 88.10%
DOI: 10.1145/3589282

Incoming Non-self Citations Over Time

Authors

1. Jianyang Gao (Nanyang Technological University)
2. Cheng Long (Nanyang Technological University)

BibTeX Citation

@inproceedings{gao_sigmod23,
        title = {{High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations}},
        author = {Gao, Jianyang and Long, Cheng},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3589282},
        url = {https://dl.acm.org/doi/10.1145/3589282},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 39 of 39 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,357	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	0.00011043994
3,108	Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search	2025	SIGMOD	7.7499741e-05
3,286	iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search	2024	SIGMOD	7.5596483e-05
3,799	SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search	2025	SIGMOD	7.114484e-05
4,116	RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search	2024	VLDB	6.892012e-05
6,133	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB	5.9654376e-05
6,148	Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes	2024	VLDB	5.9593368e-05
6,334	MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search	2025	SIGMOD	5.9093559e-05
6,650	Tribase: A Vector Data Query Engine for Reliable and Lossless Pruning Compression using Triangle Inequalities	2025	SIGMOD	5.8146324e-05
6,995	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	5.7301567e-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,720	PDX: A Data Layout for Vector Similarity Search	2025	SIGMOD	5.559007e-05
8,205	VSAG: An Optimized Search Framework for Graph-based Approximate Nearest Neighbor Search	2025	VLDB	5.4666548e-05
9,145	SIEVE: Effective Filtered Vector Search with Collection of Indexes	2025	VLDB	5.3150984e-05
9,776	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	5.2209769e-05
9,889	SAQ: Pushing the Limits of Vector Quantization through Code Adjustment and Dimension Segmentation	2026	SIGMOD	5.1997534e-05
9,918	HAKES: Scalable Vector Database for Embedding Search Service	2025	VLDB	5.1955087e-05
10,034	HARMONY: A Scalable Distributed Vector Database for High-Throughput Approximate Nearest Neighbor Search	2026	SIGMOD	5.173224e-05
10,179	Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation	2026	PODS	5.093636e-05
10,227	Efficient Index Layout and Search Strategy for Large-scale High-dimensional Vector Similarity Search	2026	SIGMOD	5.093636e-05
10,251	GPS: Revisiting the Data Layout for Disk-based High-Dimensional Vector Search	2026	SIGMOD	5.093636e-05
10,279	PathSeer: Adaptive Neighbor Handling for Efficient Filtered ANN 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,400	Scalable Graph Indexing using GPUs for 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,417	WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search	2026	SIGMOD	5.093636e-05
10,435	CANDOR-Bench: Benchmarking In-Memory Continuous ANNS under Dynamic Open-World Streams [Experiments & Analysis]	2026	SIGMOD	5.093636e-05
10,447	Efficient and Robust Out-Of-Distribution Vector Similarity Search with Cross-Distribution Monotonic Graph	2026	SIGMOD	5.093636e-05
10,454	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD	5.093636e-05
10,490	RAIRS: Optimizing Redundant Assignment and List Layout for IVF-Based ANN Search	2026	SIGMOD	5.093636e-05
10,512	SVFusion: A CPU-GPU Co-Processing Architecture for Large-Scale Real-Time Vector Search	2026	VLDB	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
10,563	Balancing the Blend: An Experimental Analysis of Trade-offs in Hybrid Search	2026	VLDB	5.093636e-05
10,578	ConANN: Conformal Approximate Nearest Neighbor Search	2026	VLDB	5.093636e-05
10,601	Elastic Index Selection for Label-Hybrid AKNN Search	2026	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
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
286	Milvus: A Purpose-Built Vector Data Management System	2021	SIGMOD	0.00022357911
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
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
926	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.00013181732
991	Bayesian Locality Sensitive Hashing for Fast Similarity Search	2012	VLDB	0.00012793339
1,065	PASE: PostgreSQL Ultra-High-Dimensional Approximate Nearest Neighbor Search Extension	2020	SIGMOD	0.00012335063
1,430	VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning	2020	VLDB	0.0001080902
1,546	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	0.00010407159
1,802	HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search	2022	VLDB	9.7284341e-05
3,265	New Trends in High-D Vector Similarity Search: AI-driven, Progressive, and Distributed	2021	VLDB	7.5834255e-05
3,310	Similarity Query Processing for High-Dimensional Data	2020	VLDB	7.5363562e-05
3,858	A General and Efficient Querying Method for Learning to Hash	2018	SIGMOD	7.067591e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,259	Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search	2025	SIGMOD
2	580	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB
3	10,454	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD
4	690	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD
5	9,165	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB
6	3,710	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD
7	1,137	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS
8	10,336	Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations	2026	SIGMOD
9	2,158	What is the nearest neighbor in high dimensional spaces?	2000	VLDB
10	6,133	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB