$\mathbf{Steiner}$-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes

Zeyu Wang, Qitong Wang, Xiaoxing Cheng +3

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…