Through the Lens of Hubness: A Revisit on Graph-Based Approximate Nearest Neighbor Search: [Experiments & Analysis]

Graph-based Approximate Nearest Neighbor Search (ANNS) is a cornerstone of modern AI systems; however, its practical utility is undermined by a severe long-tail latency problem in which outlier queries jeopardize Service-Level Objectives (SLOs). This paper presents the first systematic study to establish the hubness phenomenon, an intrinsic property of high-dimensional data, as the fundamental cause of this performance instability. Our theoretical analysis reveals that hubness induces topologically skewed proximity graphs, characterized by overly centralized hubs and isolated anti-hubs. This topological imbalance invalidates the greedy traversal heuristic underpinning graph-based search, explaining why queries targeting anti-hubs become performance outliers. We propose a unified framework that deconstructs mainstream ANNS algorithms, reinterpreting their designs as a taxonomy of distinct hubness-mitigation strategies. Extensive experiments on datasets scaling up to 100 million vectors validate this framework, linking an algorithm's mitigation strategy to its effectiveness in balancing graph topology and optimizing outlier performance. Furthermore, our analysis uncovers critical design challenges, specifically the inherent trade-off between suppressing hubs and ensuring the reachability of anti-hubs. Building on these insights, we introduce a hubness-aware pruning optimization that efficiently refines graph topology. This approach yields performance improvements with negligible processing overhead, validating the potential of designing robust graph-based ANNS indexes by integrating hubness information.