Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases

Summary: tau-monotonic graph (tau-MG) for ANN in multi-dimensional databases; exploits a tau-monotonic property to guarantee exact NN when dist(q,NN) ≤ tau and to beat existing PG-based search times. Approximate tau-monotonic neighborhood graph (tau-MNG) lowers construction cost by restricting monotonicity to neighborhoods and adds a distance-reduction optimization; experiments on real datasets show gains over prior PG-based ANN methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hde821a969747bbf0
Venue: SIGMOD
Year: 2023
Pagerank: 0.00011708765
Overall Rank: 1,165 | 92.20%
DOI: 10.1145/3588908

Incoming Non-self Citations Over Time

Authors

1. Yun Peng (Guangdong University of Technology; Hong Kong Baptist University)
2. Byron Choi (Hong Kong Baptist University)
3. Tsz Nam Chan (Hong Kong Baptist University)
4. Jianye Yang (Guangdong University of Technology)
5. Jianliang Xu (Hong Kong Baptist University)

BibTeX Citation

@inproceedings{peng_sigmod23,
        title = {{Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases}},
        author = {Peng, Yun and Choi, Byron and Chan, Tsz Nam and Yang, Jianye and Xu, Jianliang},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3588908},
        url = {https://dl.acm.org/doi/10.1145/3588908},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 47 of 47 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
802	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	0.00013822222
2,791	Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search	2024	SIGMOD	7.9939669e-05
3,389	SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search	2025	SIGMOD	7.329962e-05
3,876	RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search	2024	VLDB	6.9349247e-05
4,077	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB	6.8040917e-05
4,157	Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes	2024	VLDB	6.7596305e-05
5,142	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	6.2420637e-05
5,526	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	6.0804398e-05
6,256	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB	5.8162066e-05
6,941	GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces	2025	VLDB	5.6229105e-05
7,023	Accelerating Graph Indexing for ANNS on Modern CPUs	2025	SIGMOD	5.6026129e-05
7,286	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	5.5493084e-05
7,358	Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-based ANN Index Updates	2025	VLDB	5.5288758e-05
7,610	Scalable Graph Indexing using GPUs for Approximate Nearest Neighbor Search	2026	SIGMOD	5.4683985e-05
7,719	VSAG: An Optimized Search Framework for Graph-based Approximate Nearest Neighbor Search	2025	VLDB	5.4543461e-05
8,087	Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs	2025	SIGMOD	5.3746995e-05
8,364	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	5.3304544e-05
8,434	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD	5.3165535e-05
10,128	Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-based ANN Search	2025	VLDB	5.0615166e-05
10,261	CoTra: Towards Efficient and Scalable Distributed Vector Search with RDMA	2026	SIGMOD	5.0380426e-05
10,354	PGTuner: An Efficient Framework for Automatic and Transferable Configuration Tuning of Proximity Graphs	2026	SIGMOD	5.0156513e-05
10,356	Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search	2026	SIGMOD	5.0156513e-05
10,357	TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning	2026	SIGMOD	5.0156513e-05
10,358	WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search	2026	SIGMOD	5.0156513e-05
10,359	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD	5.0156513e-05
10,473	Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation	2026	PODS	4.9605343e-05
10,495	Balancing Global and Local: Representative Sampling for Large-Scale Vector Data	2026	SIGMOD	4.9605343e-05
10,534	FAVOR: Efficient Filter-Agnostic Vector ANNS Based on Selectivity-Aware Exclusion Distances	2026	SIGMOD	4.9605343e-05
10,568	PathSeer: Adaptive Neighbor Handling for Efficient Filtered ANN Search	2026	SIGMOD	4.9605343e-05
10,588	Through the Lens of Hubness: A Revisit on Graph-Based Approximate Nearest Neighbor Search: [Experiments & Analysis]	2026	SIGMOD	4.9605343e-05
10,616	Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations	2026	SIGMOD	4.9605343e-05
10,623	Beyond Vector Search: Querying With and Without Predicates	2026	SIGMOD	4.9605343e-05
10,637	Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph	2026	SIGMOD	4.9605343e-05
10,707	Efficient and Robust Out-Of-Distribution Vector Similarity Search with Cross-Distribution Monotonic Graph	2026	SIGMOD	4.9605343e-05
10,714	FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search	2026	SIGMOD	4.9605343e-05
10,749	RAIRS: Optimizing Redundant Assignment and List Layout for IVF-Based ANN Search	2026	SIGMOD	4.9605343e-05
10,752	Reveal Hidden Pitfalls and Navigate Next Generation of Vector Similarity Search from Task-Centric Views: [Experiments & Analysis]	2026	SIGMOD	4.9605343e-05
10,780	Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search	2026	VLDB	4.9605343e-05
10,797	I/O Optimizations for Graph-Based Disk-Resident Approximate Nearest Neighbor Search: A Design Space Exploration	2026	VLDB	4.9605343e-05
10,816	Balancing the Blend: An Experimental Analysis of Trade-offs in Hybrid Search	2026	VLDB	4.9605343e-05
10,905	ConANN: Conformal Approximate Nearest Neighbor Search	2026	VLDB	4.9605343e-05
10,938	CONDA: A Connectivity-Aware Dynamic Index for Approximate Nearest Neighbor Search over Evolving Data	2026	VLDB	4.9605343e-05
10,980	TEngineDB-V: An OLAP-Native Vector Search System for Large-k Workloads at Tencent	2026	VLDB	4.9605343e-05
10,983	RED-ANNS: An RDMA-Enabled Distributed Framework for Graph-Based Approximate Nearest Neighbor Search	2026	VLDB	4.9605343e-05
11,098	Advances of Query Processing in Vector Databases	2026	VLDB	4.9605343e-05
11,118	Elastic Index Selection for Label-Hybrid AKNN Search	2026	VLDB	4.9605343e-05
11,647	DARKER: Efficient Transformer with Data-driven Attention Mechanism for Time Series	2024	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
75	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00037163157
335	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.0002067515
837	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.00013530806
1,524	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD	0.0001033427

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,473	Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation	2026	PODS
2	10,900	RNSG: A Range-Aware Graph Index for Efficient Range-Filtered Approximate Nearest Neighbor Search	2026	VLDB
3	10,117	Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts	2025	VLDB
4	1,618	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB
5	10,898	Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization	2026	VLDB
6	10,637	Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph	2026	SIGMOD
7	4,077	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB
8	335	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB
9	75	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB
10	10,359	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD