VLDB Endowment Logo

go back

Volume 17, No. 13

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

Authors:
Zeyu Wang, Qitong Wang, Xiaoxing Cheng, Peng Wang, Themis Palpanas, Wei Wang
Download PDF

Abstract

Graph-based indexes have been widely employed to accelerate approximate similarity search of high-dimensional vectors. However, the performance of graph indexes to answer different queries varies vastly, leading to an unstable quality of service for downstream applications. This necessitates an effective measure to test query hardness on graph indexes. Nonetheless, popular distance-based hardness measures like LID lose their effects due to the ignorance of the graph structure. In this paper, we propose π‘†π‘‘π‘’π‘–π‘›π‘’π‘Ÿ-hardness, a novel connection-based graph-native query hardness measure. Specifically, we first propose a theoretical framework to analyze theminimumqueryeffortongraphindexesandthendefineπ‘†π‘‘π‘’π‘–π‘›π‘’π‘Ÿ-hardness as the minimum effort on a representative graph. Moreover, we prove that our π‘†π‘‘π‘’π‘–π‘›π‘’π‘Ÿ-hardness is highly relevant to the classical Directed π‘†π‘‘π‘’π‘–π‘›π‘’π‘Ÿ Tree (DST) problems. In this case, we design a novel algorithm to reduce our problem to DST problems and then leverage their solvers to help calculate π‘†π‘‘π‘’π‘–π‘›π‘’π‘Ÿ-hardness efficiently. Compared with LID and other similar measures, π‘†π‘‘π‘’π‘–π‘›π‘’π‘Ÿ-hardness shows a significantly better correlation with the actual query effort on various datasets. Additionally, an unbiased evaluation designed based on π‘†π‘‘π‘’π‘–π‘›π‘’π‘Ÿ-hardness reveals new ranking results, indicating a meaningful direction for enhancing the robustness of graph indexes.

PVLDB is part of the VLDB Endowment Inc.

Privacy Policy