Elastic Index Selection for Label-Hybrid AKNN Search

Summary: Introduces elastic index selection for label-hybrid AKNN, exploiting label containment so fewer indexes serve supersets with bounded cost inflation. Formulates NP-complete selection under space/efficiency constraints and gives greedy, index-agnostic algorithms yielding 10–800× speedups. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h54f471e2df6ab89a
Venue: VLDB
Year: 2026
Pagerank: 4.9793485e-05
Overall Rank: 11,048 | 25.72%
DOI: 10.14778/3785297.3785304

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Mingyu Yang (Hong Kong University of Science and Technology)
2. Wenxuan Xia (Hong Kong University of Science and Technology)
3. Wentao Li (University of Leicester)
4. Raymond Chi-Wing Wong (Hong Kong University of Science and Technology)
5. Wei Wang (Hong Kong University of Science and Technology)

BibTeX Citation

@article{yang_vldb26,
        title = {{Elastic Index Selection for Label-Hybrid AKNN Search}},
        author = {Yang, Mingyu and Xia, Wenxuan and Li, Wentao and Wong, Raymond Chi-Wing and Wang, Wei},
        journal = {PVLDB},
        series = {{VLDB} '26},
        volume = {19},
        number = {4},
        pages = {617--630},
        doi = {10.14778/3785297.3785304},
        url = {https://doi.org/10.14778/3785297.3785304},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 24 of 24 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
11	Implementing Data Cubes Efficiently	1996	SIGMOD	0.00071084324
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
164	Mining Frequent Patterns without Candidate Generation	2000	SIGMOD	0.00027412227
194	Milvus: A Purpose-Built Vector Data Management System	2021	SIGMOD	0.00025636725
341	AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data	2020	VLDB	0.00020539791
345	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00020445545
713	Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan	2016	VLDB	0.00014571977
804	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	0.00013832333
1,170	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	0.0001171991
1,225	ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data	2024	SIGMOD	0.00011444398
1,485	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	0.00010523759
1,536	Cardinality Estimation: An Experimental Survey	2018	VLDB	0.00010327422
1,601	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	0.00010103316
1,613	Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment	2024	SIGMOD	0.00010072237
1,684	HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search	2022	VLDB	9.8801753e-05
1,957	SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search	2024	SIGMOD	9.3159589e-05
2,448	DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search	2020	VLDB	8.4494625e-05
2,726	iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search	2024	SIGMOD	8.0904995e-05
2,783	Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search	2024	SIGMOD	8.0242863e-05
2,821	Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search	2025	SIGMOD	7.9711961e-05
3,385	SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search	2025	SIGMOD	7.3548612e-05
7,593	DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph	2025	SIGMOD	5.4880197e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,027	Answering Top-k Representative Queries on Graph Databases	2014	SIGMOD
2	10,827	Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization	2026	VLDB
3	10,078	Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts	2025	VLDB
4	5,920	ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph	2023	VLDB
5	12,754	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB
6	1,625	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB
7	3,774	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD
8	10,443	Efficient Index Layout and Search Strategy for Large-scale High-dimensional Vector Similarity Search	2026	SIGMOD
9	2,783	Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search	2024	SIGMOD
10	6,459	Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search	2025	SIGMOD