Kavli Affiliate: Cheng Peng
| First 5 Authors: Zeyu Wang, Qitong Wang, Xiaoxing Cheng, Peng Wang, Themis Palpanas
| Summary:
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 $Steiner$-hardness,
a novel connection-based graph-native query hardness measure. Specifically, we
first propose a theoretical framework to analyze the minimum query effort on
graph indexes and then define $Steiner$-hardness as the minimum effort on a
representative graph. Moreover, we prove that our $Steiner$-hardness is highly
relevant to the classical Directed $Steiner$ 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 $Steiner$-hardness efficiently.
Compared with LID and other similar measures, $Steiner$-hardness shows a
significantly better correlation with the actual query effort on various
datasets. Additionally, an unbiased evaluation designed based on
$Steiner$-hardness reveals new ranking results, indicating a meaningful
direction for enhancing the robustness of graph indexes. This paper is accepted
by PVLDB 2025.
| Search Query: ArXiv Query: search_query=au:”Cheng Peng”&id_list=&start=0&max_results=3