Enriching Hierarchical Navigable Small World Searches with Result Diversification

Hierarchical Navigable Small World (HNSW) delivers state-of-the-art performances for approximate k-nearest neighbors ( \(k\) NN) queries in public benchmarks (e.g., ANN-Benchmarks). While it scales well for large datasets, characterizing the impact of the small-world construction strategy on the search quality is still an open issue. This paper investigates how result diversification can shed light on that question by adding a parameterless strategy to HNSW that explicitly uses local distance-based structures to produce diversified neighbors. Accordingly, we propose (i) a new heuristic for the small-world construction based on the Influence concept derived from ball partitioning, and (ii) an extension to HNSW \(k\) NN searching algorithm that supports Influence-driven result diversification ( \(k\textrm{N}_d\textrm{N}\) ). We evaluated our approach on ANN-Benchmarks, and results show that Influence-based partitioning of the search space can substantially enhance the \(k\textrm{N}_d\textrm{N}\) quality (Recall by proximity) with a throughput comparable to the standard HNSW construction strategy.