DBScholar

Back to papers

Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes

Summary: Steiner-hardness: a graph-native, connection-based measure of query difficulty for graph-based ANN, modeling minimal query effort on a representative graph. Reducible to Directed Steiner Tree so DST solvers compute it efficiently; outperforms LID in predicting actual query effort and yields unbiased index rankings. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
hcf470df0682517d1
Venue
VLDB
Year
2024
Pagerank
6.7596305e-05
Overall Rank
4,157 | 72.14%
DOI
10.14778/3704965.3704974
PDF
Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{wang_vldb24,
        title = {{Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes}},
        author = {Wang, Zeyu and Wang, Qitong and Cheng, Xiaoxing and Wang, Peng and Palpanas, Themis and Wang, Wei},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {13},
        pages = {4668--4682},
        doi = {10.14778/3704965.3704974},
        url = {https://doi.org/10.14778/3704965.3704974},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank Citing Paper Year Venue Pagerank
2,791 Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search 2024 SIGMOD 7.9939669e-05
7,286 Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search 2025 SIGMOD 5.5493084e-05
7,585 SIEVE: Effective Filtered Vector Search with Collection of Indexes 2025 VLDB 5.4747603e-05
9,168 DARTH: Declarative Recall Through Early Termination for Approximate Nearest Neighbor Search 2026 SIGMOD 5.2026953e-05
9,593 Distribution-Aware Exploration for Adaptive HNSW Search 2026 SIGMOD 5.1376962e-05
10,356 Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search 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,396 Exploiting Structural Properties for Efficient Constraint-Aware HNSW Hyperparameter Tuning 2027 SIGMOD 4.9605343e-05
10,487 An In-Depth Study of Filter-Agnostic Vector Search on a PostgreSQL Database System: [Experiments & Analysis] 2026 SIGMOD 4.9605343e-05
10,586 TaCo: Data-adaptive and Query-aware Subspace Collision for High-dimensional Approximate Nearest Neighbor 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,894 Revisiting Filtered ANN Benchmarks: A Hardness-Controlled Benchmark Generator for Realistic Evaluation 2026 VLDB 4.9605343e-05
10,918 QBAT: Model-based Query Budget Autotuner for Clustering-based Approximate Nearest Neighbor Search 2026 VLDB 4.9605343e-05
10,970 ANNiE: A Learned Query Cost Estimator 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
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 28 of 28 cited papers.

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

Rank Cited Paper Year Venue Pagerank
20 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00057610161
75 Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph 2019 VLDB 0.00037163157
181 Milvus: A Purpose-Built Vector Data Management System 2021 SIGMOD 0.00026425782
286 Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search 2016 VLDB 0.00022090962
325 AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data 2020 VLDB 0.00020930941
335 A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search 2021 VLDB 0.0002067515
339 Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting 2012 SIGMOD 0.00020558018
650 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00015142453
802 RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search 2024 SIGMOD 0.00013822222
837 Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination 2020 SIGMOD 0.00013530806
1,098 A Data-adaptive and Dynamic Segmentation Index for Whole Matching on Time Series 2013 VLDB 0.00012016918
1,165 Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases 2023 SIGMOD 0.00011708765
1,280 Manu: A Cloud Native Vector Database Management System 2022 VLDB 0.00011199537
1,460 PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search 2020 VLDB 0.00010558941
1,601 High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations 2023 SIGMOD 0.00010092977
1,618 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB 0.00010045437
1,684 HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search 2022 VLDB 9.8770749e-05
2,268 ELPIS: Graph-Based Similarity Search for Scalable Data Science 2023 VLDB 8.7144632e-05
2,733 Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search 2020 VLDB 8.0653682e-05
2,879 The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art 2019 VLDB 7.8951769e-05
3,521 Scalable, Variable-Length Similarity Search in Data Series: The ULISSE Approach 2018 VLDB 7.2177846e-05
4,643 Pivot-based Metric Indexing 2017 VLDB 6.4734189e-05
4,995 LANNS: A Web-Scale Approximate Nearest Neighbor Lookup System 2022 VLDB 6.30976e-05
5,335 Hercules Against Data Series Similarity Search 2022 VLDB 6.1613957e-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,621 Dumpy: A Compact and Adaptive Index for Large Data Series Collections 2023 SIGMOD 5.7145251e-05
9,478 Odyssey: A Journey in the Land of Distributed Data Series Similarity Search 2023 VLDB 5.1576017e-05
11,624 CIVET: Exploring Compact Index for Variable-Length Subsequence Matching on Time Series 2024 VLDB 4.9605343e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 335 A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search 2021 VLDB
2 3,145 Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity 2015 SIGMOD
3 10,521 Efficient Index Layout and Search Strategy for Large-scale High-dimensional Vector Similarity Search 2026 SIGMOD
4 10,707 Efficient and Robust Out-Of-Distribution Vector Similarity Search with Cross-Distribution Monotonic Graph 2026 SIGMOD
5 1,618 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB
6 10,898 Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization 2026 VLDB
7 1,165 Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases 2023 SIGMOD
8 10,117 Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts 2025 VLDB
9 10,894 Revisiting Filtered ANN Benchmarks: A Hardness-Controlled Benchmark Generator for Realistic Evaluation 2026 VLDB
10 10,356 Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search 2026 SIGMOD