Approximate Diverse k-Nearest Neighbor Search in Vector Database

Approximate k-nearest neighbor search (Ak-NNS) is a core operation in vector databases, underpinning applications such as retrieval-augmented generation (RAG) and image retrieval. In these scenarios, users often prefer diverse result sets to minimize redundancy and enhance information value. However, existing greedy-based diverse methods frequently yield suboptimal results, failing to adequately approximate the optimal similarity score under certain diversification level. Furthermore, there is a need for flexible algorithms that can adapt to varying user-defined result sizes and diversity requirements.

To address these challenges, we propose a novel approach that seamlessly integrates result diversification into state-ofthe-art (SOTA) Ak-NNS methods. Our approach introduces a progressive search framework, consisting of iterative searching, diversification, and verification phases. Carefully designed diversification and verification steps enable our approach to efficiently approximate the optimal diverse result set according to user-specified diversification levels without additional indexing overhead.

We evaluate our method on three million-scale benchmark datasets, LAION-art, Deep1M, and Txt2img, using latency, similarity, and recall as performance metrics across a range of k values and diversification thresholds. Experimental results demonstrate that our approach consistently retrieves nearoptimal diverse results with minimal latency overhead, particularly under medium and high diversity settings.

• Diversification condition: ∀r i , r j ∈ R, i ̸ = j, such that sim(r i , r j ) < ϵ