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: 13712
Venue: VLDB
Year: 2024
Pagerank: 4.7623207e-05
Overall Rank: 7,307 | 49.22%
DOI: 10.14778/3704965.3704974

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,028	Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search	2024	SIGMOD	5.7447815e-05
7,848	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	4.6323445e-05
9,296	DARTH: Declarative Recall Through Early Termination for Approximate Nearest Neighbor Search	2026	SIGMOD	4.3577746e-05
10,071	Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search	2026	SIGMOD	4.1905499e-05
10,129	WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search	2026	SIGMOD	4.1905499e-05
10,154	Distribution-Aware Exploration for Adaptive HNSW Search	2026	SIGMOD	4.1905499e-05
10,767	SIEVE: Effective Filtered Vector Search with Collection of Indexes	2025	VLDB	4.1905499e-05

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
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076824554
210	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034086264
494	Milvus: A Purpose-Built Vector Data Management System	2021	SIGMOD	0.00021769407
579	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.0001982328
596	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00019455943
730	AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data	2020	VLDB	0.00017443615
763	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00016963981
1,013	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014632051
1,157	A Data-adaptive and Dynamic Segmentation Index for Whole Matching on Time Series	2013	VLDB	0.00013600695
1,347	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.00012463441
2,002	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	9.8258191e-05
2,160	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	9.4037759e-05
2,264	Manu: A Cloud Native Vector Database Management System	2022	VLDB	9.1587362e-05
2,287	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	9.1004806e-05
2,687	HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search	2022	VLDB	8.3079951e-05
2,772	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	8.1491893e-05
2,969	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	7.7955562e-05
3,199	Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search	2020	VLDB	7.3999833e-05
3,403	ELPIS: Graph-Based Similarity Search for Scalable Data Science	2023	VLDB	7.1338786e-05
3,544	Scalable, Variable-Length Similarity Search in Data Series: The ULISSE Approach	2018	VLDB	6.98759e-05
3,629	The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art	2019	VLDB	6.8997167e-05
5,086	Pivot-based Metric Indexing	2017	VLDB	5.7036022e-05
5,559	LANNS: A Web-Scale Approximate Nearest Neighbor Lookup System	2022	VLDB	5.437026e-05
5,747	Hercules Against Data Series Similarity Search	2022	VLDB	5.3427166e-05
6,375	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	5.0868008e-05
7,090	Dumpy: A Compact and Adaptive Index for Large Data Series Collections	2023	SIGMOD	4.8318862e-05
9,208	Odyssey: A Journey in the Land of Distributed Data Series Similarity Search	2023	VLDB	4.3693005e-05
11,025	CIVET: Exploring Compact Index for Variable-Length Subsequence Matching on Time Series	2024	VLDB	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,843	GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces	2025	VLDB	4.6335219e-05
210	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034086264
10,165	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD	4.1905499e-05
763	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00016963981
3,857	Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity	2015	SIGMOD	6.6924202e-05
10,158	Efficient and Robust Out-Of-Distribution Vector Similarity Search with Cross-Distribution Monotonic Graph	2026	SIGMOD	4.1905499e-05
2,969	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	7.7955562e-05
2,002	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	9.8258191e-05
10,691	Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts	2025	VLDB	4.1905499e-05
10,071	Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search	2026	SIGMOD	4.1905499e-05