Approximation Algorithms for Diversity-Aware $K$-Nearest Neighbor Search

As a fundamental computational primitive, Nearest Neighbor Search (NNS) retrieves the $K$ most relevant objects for a given query, underpinning a vast array of applications like image search, retrieval-augmented generation (RAG), and recommendation systems. However, traditional NNS schemes neglect diversity awareness, thereby suffering from severe redundancy and near-duplicate results. To tackle this limitation, diversity-aware $K$-nearest neighbor search (D$K$NNS) has been extensively studied. Despite these efforts, state-of-the-art D$K$NNS methods still struggle with compromised result quality, efficiency bottlenecks, or inflexible trade-offs between relevance and diversity. To address these limitations, we study a D$K$NNS formulation that linearly combines the relevance and diversity terms in a unified objective function, with a controllable parameter $\lambda$ to adjust their relative importance. We prove that the problem is NP-hard and that, unless $\mathrm{P}=\mathrm{NP}$, no polynomial-time algorithm can approximate it with a factor of $(4/3-\zeta )$ for any $\zeta >0$. Then, we propose a linear scan-based algorithm, threshold-greedy scan (TGS), for D$K$NNS with a $(4/3+ϵ)$-approximation for any fixed $ϵ>0$. Furthermore, we integrate the threshold-greedy principle with graph-based indexes for NNS and propose multi-threshold graph search (MTGS), which achieves a $(2+ϵ)$-approximation under a shortcut-reachability assumption on the graph. Finally, we conduct extensive experiments on four real-world datasets. The results demonstrate that TGS achieves the best result quality for D$K$NNS in almost all cases. Meanwhile, MTGS runs over two orders of magnitude faster than TGS and improves upon state-of-the-art D$K$NNS baselines in both result quality and search efficiency.