- Rating
- 4
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
In this paper, the authors propose the new solution for the diversity-aware kNN search problem, which is a fundamental research problem in vector database (or AI infra). The authors prove that this problem does not have the polynomial-time approximation algorithm with the approximation ratio of , given that . Moreover, they have proposed two solutions, namely (i) threshold-greedy scan (TGS) and (ii) multi-threshold graph search (MTGS), which can solve this problem (i) using a polynomial-time algorithm with approximation ratio and (ii) using a faster algorithm with approximation ratio.
Critical strengths
S1: The technical novelty/contribution of this work is very solid. The authors propose two approximation methods that can handle this problem with a non-trivial approximation guarantee.
S2: Solid theoretical analysis has been provided in this paper. For example, they have also proved that the hardness of this problem.
S3: Their methods can achieve the near-optimal performance with respect to the approximation guarantee.
S4: Finding diversity-aware kNN for each query is very important in many applications, especially for recommendation (because it may not be good to recommend the same movie for the users).
Critical weaknesses
W1: The datasets that are adopted in this paper are small-scale. In Table 1, the largest one is only with 1,183,514 objects. Nowadays, vector DB normally stores billion-scale/trillion-scale vectors. Therefore, algorithms that work for million-scale vectors may not be very meaningful in practice. The authors should better show that their algorithms can handle billion-scale vectors.
W2: I believe that the diversity-aware kNN search problem may not be new. Many research studies should have already shown that this problem is NP-hard. Therefore, is it necessary to provide a long proof for showing that this problem is NP-hard in Appendix C2. Is this problem different from those papers that have been published in the literature?
W3: I think the authors should also consider combining those parallel/distributed techniques for boosting the performance of their proposed algorithms. The main reason is that vector DB is normally very large nowadays. Only considering a single machine setting may not be very meaningful.
Questions for authors
Q1: Can the authors should the performance of their methods and competitor methods using large-scale datasets?
Q2: Is this problem different from those diversity-aware kNN search problem proposed from the literature?
Q3: Following Q2, why do we need to prove the NP-hardness again for this problem?
Q4: Can the authors comment how the parallel/distributed techniques can be combined with their methods to further improve efficiency?
2 comments
Reply to the Comment
I have read the rebuttal from the authors and think that they have adequately addressed my comments.
We sincerely appreciate your insightful questions and respond to each of them below.
For Q1/W1: Given the available computing resources, as the implementation of our algorithms and all baselines is memory-based, we additionally evaluated the SIFT-100M dataset, the largest dataset affordable for the memory space of the server we use (see Appendix D.6). TGS achieved the lowest mean objective at 109.29 s/query. Our graph-based MTGS averaged 61.85 ms/query, only 1.03% higher objective than TGS. Compared with LotusFilter, MTGS was 2.90× faster and achieved a 3.85% lower objective. PSS averaged 16.21 s/query with the highest objective among all diversity-oriented methods. Beam Search was fastest at 6.70 ms/query, but its mean minimum pairwise distance was 118.26, compared with 186.56 for MTGS and 190.36 for TGS. The added baseline, Anand-M, failed to complete the graph construction on SIFT-100M after 24 hours. On the large-scale dataset, MTGS still achieved the best trade-off between diversity and relevance.
For Q2/Q3/W2: We note that closely related works on diversity-aware kNN adopt different formulations from ours. They either impose diversity constraints, e.g., Zhao et al. (2026) and Anand et al. (2025)'s extension, or define diversity through categorical attributes, e.g., Barman et al. (2026) and Anand et al. (2025). After checking all the proofs of NP-hardness in these works, we confirm that none of their reduction procedures is directly applicable to our problem due to their formulation distinctions. We thus believe that establishing a new reduction procedure for the NP-hardness of our problem is necessary.
For Q4/W3: In the current experiments, we focus on a single-machine setting primarily to compare the solution quality and query overhead of different search algorithms in a fair and unified environment. Nevertheless, we think our approaches are extendable to the parallel/distributed setting along the following levels. 1) Inter-query parallelism: Different queries can execute TGS or MTGS independently, improving throughput through multi-core or multi-node concurrency. 2) Intra-query parallelism: Our threshold selection mechanism is naturally suited to parallelization and can be parallelized across queries without additional synchronization. For each candidate visited during graph traversal, feasibility checks and candidate-set updates for different thresholds can be performed in parallel without affecting one another. 3)Sharded retrieval and global selection: Each shard could perform local retrieval in parallel, followed by global diversity-aware selection over the merged candidates. We will consider extending to parallel/distributed settings for future work.