ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph

Summary: Introduces ARKGraph, an index for approximate KNN graphs over vectors within arbitrary numeric-key ranges. Grouping stable KNNs across nearby ranges reduces average space from O(Kn³) to O(Kn log n), enabling direct construction and fast neighbor restoration. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 13297
Venue: VLDB
Year: 2023
Pagerank: 5.8859287e-05
Overall Rank: 6,404 | 56.07%
DOI: 10.14778/3603581.3603601

Incoming Non-self Citations Over Time

Authors

1. Chaoji Zuo (Rutgers University)
2. Dong Deng (Rutgers University)

BibTeX Citation

@article{zuo_vldb23,
        title = {{ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph}},
        author = {Zuo, Chaoji and Deng, Dong},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {10},
        pages = {2645--2658},
        doi = {10.14778/3603581.3603601},
        url = {https://doi.org/10.14778/3603581.3603601},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,303	SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search	2024	SIGMOD	8.7783079e-05
5,653	UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search	2025	VLDB	6.1332953e-05
6,995	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	5.7301567e-05
7,426	Dynamic Range-Filtering Approximate Nearest Neighbor Search	2025	VLDB	5.6211019e-05
8,504	Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries	2024	VLDB	5.4132367e-05
9,776	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	5.2209769e-05
10,242	FAVOR: Efficient Filter-Agnostic Vector ANNS Based on Selectivity-Aware Exclusion Distances	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,439	Curator: Efficient Vector Search with Low-Selectivity Filters	2026	SIGMOD	5.093636e-05

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
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0020210012
21	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00056760516
85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035405879
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
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
406	AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data	2020	VLDB	0.00019054532
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
805	Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan	2016	VLDB	0.00013891999

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,934	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB
2	7,426	Dynamic Range-Filtering Approximate Nearest Neighbor Search	2025	VLDB
3	8,493	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
4	1,244	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD
5	4,712	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB
6	10,601	Elastic Index Selection for Label-Hybrid AKNN Search	2026	VLDB
7	2,303	SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search	2024	SIGMOD
8	7,259	Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search	2025	SIGMOD
9	10,454	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD
10	3,286	iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search	2024	SIGMOD