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: h63035b739110eb73
Venue: VLDB
Year: 2023
Pagerank: 5.9475097e-05
Overall Rank: 5,920 | 60.20%
DOI: 10.14778/3603581.3603601
PDF: Download (CC BY-NC-ND 4.0)

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 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,957	SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search	2024	SIGMOD	9.3159589e-05
4,346	UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search	2025	VLDB	6.6488514e-05
6,768	Dynamic Range-Filtering Approximate Nearest Neighbor Search	2025	VLDB	5.686858e-05
6,895	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	5.6536466e-05
8,671	Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries	2024	VLDB	5.2917782e-05
9,551	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	5.1591583e-05
10,325	WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search	2026	SIGMOD	5.0346745e-05
10,457	FAVOR: Efficient Filter-Agnostic Vector ANNS Based on Selectivity-Aware Exclusion Distances	2026	SIGMOD	4.9793485e-05
10,628	Curator: Efficient Vector Search with Low-Selectivity Filters	2026	SIGMOD	4.9793485e-05
10,769	Harmonizing Efficiency and Accuracy in Filtered Vector Search	2026	VLDB	4.9793485e-05
10,813	X-Wim: Massive Parallelization of Weighted Matching in Bipartite Graphs	2026	VLDB	4.9793485e-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.001992968
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00057568153
74	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00037091678
90	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00034860244
194	Milvus: A Purpose-Built Vector Data Management System	2021	SIGMOD	0.00025636725
280	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.0002230467
298	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00021833987
338	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00020585187
341	AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data	2020	VLDB	0.00020539791
562	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016335405
576	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016121388
713	Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan	2016	VLDB	0.00014571977

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,662	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
2	10,827	Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization	2026	VLDB
3	4,050	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB
4	1,170	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD
5	11,048	Elastic Index Selection for Label-Hybrid AKNN Search	2026	VLDB
6	1,957	SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search	2024	SIGMOD
7	6,459	Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search	2025	SIGMOD
8	10,326	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD
9	10,829	RNSG: A Range-Aware Graph Index for Efficient Range-Filtered Approximate Nearest Neighbor Search	2026	VLDB
10	2,726	iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search	2024	SIGMOD