Graph-Based Algorithms for Diverse Similarity Search
Authors: Piyush Anand
Piotr Indyk
Ravishankar Krishnaswamy
Sepideh Mahabadi
Vikas C. Raykar
Kirankumar Shiragur
Haike Xu
Venue: ICML 2025 poster (2025)
Keywords: nearest neighbor search; diversity; algorithms
Primary area: theory->optimization
TL;DR: This paper presents provably efficient algorithms for incorporating diversity into the results of graph-based similarity search algorithms.

Abstract: Nearest neighbor search is a fundamental data structure problem with many applications. Although the main objective of the data structure is to quickly report data points that are closest to a given query, it has long been noted that without additional constraints the reported answers can be redundant and/or duplicative. This issue is typically addressed in two stages: in the first stage, the algorithm retrieves a (large) number $r$ of points closest to the query, while in the second stage, the $r$ points are post-processed and a small subset is selected to maximize the desired diversity objective. Although popular, this method suffers from a fundamental efficiency bottleneck, as the set of points retrieved in the first stage often needs to be much larger than the final output. In this paper we present provably efficient algorithms for approximate nearest neighbor search with diversity constraints that bypass this two stage process. Our algorithms are based on popular graph-based methods, which allows us to ``piggy-back'' on the existing efficient implementations.  These are the first graph-based algorithms for nearest neighbor search with diversity constraints.   For data sets with low intrinsic dimension, our data structures report a diverse set of $k$ points approximately closest to the query, in time that only depends on $k$ and $\log \Delta$, where $\Delta$ is the ratio of the diameter to the closest pair distance in the data set. This bound is qualitatively similar to the best known bounds for standard (non-diverse) graph-based algorithms. Our experiments show that the search time of our algorithms is substantially lower than that using the standard two-stage approach.

Graph-Based Algorithms for Diverse Similarity Search
Piyush Anand
Piotr Indyk" "2 Ravishankar Krishnaswamy" *3 Sepideh Mahabadi Vikas C. Raykar
Kirankumar Shiragur's *3 Haike Xu
Abstract
1. Introduction
Nearest neighbor search is fuuddaeental data structure problem with many applications. Al- though the main objective of the data structure is to quickly report data points that are closest to a given query, it has long been noted (Car- bonell & Goldstein, 1998) that without additional constraints the reported answers can be redun- dant and/or duplicative. This issue is typically addressed in two stages: in the first stage, the algorithm retrieves (large) number of points closest to the query, while in the second stage, the points are post-processed and a small sub- set is selected to maximize the desired diversity objective. Although popular, this method suffers from a fundamental efficiency bottleneck, as the set of points retrieved in the first stage often needs to be much larger than the final output. In this paper we present provably efficient algorithms for approximate nearest neighbor search with diver- sity constraints that bypass this two stage process. Our algorithms are based on popular graph-bac based methods, which allows us to "piggy-back" on the existing efficient implementations. These are the first graph-based algorithms for nearest neighbor search with diversity constraints. For data sets with low intrinsic dimension, our data structures report a diverse set of & points approximately clos- est to the query, in time that only depends on k and log A, where A the ratio of the diameter to the closest pair distance in the data set. This bound is qualitatively similar the best known bounds for standard (non-diverse) graph-based al- gorithms (Indyk& & Xu, 2023). Our experiments show that the search time of our algorithms is substantially lower than that using the standard two-stage approach.
Nearest neighbor search is a classic data structure prob- lem with many applications in machine learning, com- puter vision, recommendation systems and other areas (Shakhnarovich et al., 2006). It is defined as follows: given set P of n2 points from some space X equipped with a distance function ().,)) :), build a data structure that, given any query point & E X, returns a point p E P that mini- mizes D(g.P) p)- In a more general version of the problem we are given parameter and the goal is to report k points in P that are closest q. In typical scenario, the metric space (X, D) is the d-dimensional space, and D(p, 4) is the Euclidean distance between points p and q.
Since for high- digh-dimensionll point sets the known exact near- est neighbor search data structures are not efficient, several approximate versions of this problem have been formu- lated. A popular theoretical formulation relaxes the require- ment that the query algorithm must return the exact closest point p. and instead allows it to output any point p' E P that is a c-approximate nearest neighbor of in P, i.e. D(g.1') I cD p). In empirical studies, the quality of the set of points reported by an approximate data structure is measured by its recall, i.e., the average fraction of the true k nearest neighbors returned by the data structure.
Although minimizing the distance of the reported points to the query is often the main objective, it has long been noted (Carbonell & Goldstein, 1998) that, without addi- tional constraints, the reported answers are often redundant and/or duplicative. This is particularly important in appli- cations such as recommendation systems or information retrieval', where many similar variants of the same product, product seller, or document exist. For example, update to the search results listing algorithm implemented by Google in 2019 ensures that "no more than two pages from the same site" are listed (Liaison, 2019). Such constraints can be formulated by assuming that each point assigned a "color" (e.g., site id or product seller) and requiring the data
Equal contribution 'Microsoft "MIT 'Microsoft Re- search. Correspondence to: Sepideh Mahabadi <sma- habadi mwwrosoft.com.. Haike Xu <haikcxu@ mit.edu>.
Mooee recent applications include Retrieval Augmented Gener- ation (RAG) systems. For example, (Chen & Choi, 2025) argues that retrieved items need to be diverse with respect perspective to excel in RAG queries. Similarly (Rezaei & Dieng, 2025) argues for diverse retrieval using Vendi scores.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Graph-Based Algorithms for Diverse Similarity Search
structure to output set S of k points containing most K' points of each color, whose distances to & are (approx- imately) optimal. A more general formulation allows arbitrary diversity metric p (typically different from D), and requires the data structure to report a set S of k points such that for any distinct p, p' E S. p(p.p') 2 C, for some required diversity parameter C > O.
dimension d, and that its aspect ratio (the ratio of the di- ameter to the closest pair distance) is at most A. Under this assumption, we show that the query time of our data structures is polynomial in k, log n and log A.
Formally, our result is as follows. (Here we state the result in the simplest setting, where the diversity is induced by point colors and K' 1. (See Theorem A.5 for the general result statement.)
The aforementioned paper of (Carbonell & Goldstein, 1998) stimulated the development of the rich area of diversity- based reranking, which became the dominant approach to this problem. The approach proceeds in two stages. In the first stage, the data structure retrieves r points closest to the query, where r can be much larger than the desired output k. In the second stage, the points are post-processed to maximize the diversity objective of the reported & points.
Theorem 1.1. Consider the data structure constructed by Algorithm 1. Given a query q, let R be the radius of the smallest ball around q (w.r.. the metric D) which contains k points of different colors. Then the search Algorithm 2 returns a set S of k points of different colors such that, for all p E S,
D(g.P) p) S (a-1+e) ) R.
(a+l
Though popular, the reranking approach to diversifying near- est neighbor search suffers from fundamental efficiency bottleneck, as the algorithm needs to retrieve a large enough set to ensure that it contains the k diverse points. In many scenarios, the number r of points that need to be retrieved can be much larger than (see e.g., Figure 1 and the discus- sion in the experimental section). In the worst case, it might be necessary to set (2(2) to ensure that the optimal set is found. This leads to the following algorithmic question:
The search algorithms takes O (k: (o0. 2) steps, where each step takes Ô (k(a)) log A) time. The data structure uses space ((nk(80)* log A).
We note that the approximation factor with respect to D, as well as the running time bounds, are essentially the same as the bounds obtained in (Indyk & Xu, 2023) for the non- diverse approximate nearest neighbor problem. The main difference is that the bound in (Indyk & Xu, 2023) does not depend on k, as they consider only the case of k = 1.
Is it possible bypass the standard reranking pipeline by directly reporting the k diverse points, in time that depends on k and not r?
As mentioned earlier, Theorem 1.1 generalizes arbitrary k and general diversity metric p. as discussed later.
In this paper, we aim to solve this problem both in the- ory and in practice. Because of these dual goals, we focus on designing efficient graph-based algorithms for diverse similarity search. In graph-based algorithms, the data struc- ture consists of graph between the points in P. and the query procedure performs greedy search over this graph to find points close to the query. Graph-based algorithms such HNSW (Malkov& & Yashunin, 2018), NGT (Iwasaki & Miyazaki, 2018) 8), and DiskANN (Jayaram Subramanya et al., 2019) have become popular tools in practice, often topping Approximate Nearest Neighbor benchmarks (Au- mueller et al., 2024). In addition, they are highly versatile, as they do not put any restrictions on the distance function D. Although most of the work in this area is purely empiri- cal, recent paper (Indyk& & Xu, 2023) gives approximation and running time guarantees for some of those algorithms.
Experimental results. We adapt our theoretical algorithms to devise fast heuristics based on them, and show the effi- ciency of our algorithms on several realistic scenarios. In one of them, we consider the task of showing ads to user based on their search queries. Given a number k, say 100, of available slots, the goal is to choose ads from a large corpus, such that the sellers (i.c., colors) of those ads are all different. A more relaxed constraint requires that the num- ber of ads shown from a single seller be bounded by at most k', say 10. To achieve 95% recall@100 on this real-world scenario, the prevailing baseline approach of retrieving a much larger number of candidates using a regular ANN in- dex and then choosing the best prreeeriy- k-sized subset of them has latency upwards of 8ms; our algorithm, on the other hand achieves a similar recall at latency of around 1.5ms, resulting in an improvement upwards of 5X! A production-quality implementation of our algorithm is cur- rently under development for serving large-scale workloads at one of the major technology companies.
1.1. Our Results
We give positive answer to the aforementioned question, by designing a variant of the DiskANN algorithm that re- ports approximate nearest neighbors of a given query satis- fying diversity constraints. Our theoretical analysis assumes the same setup as in (Indyk& & Xu, 2023). Specifically, we assume that the input point set P has bounded doubling
The key idea in work- modifying graph construction to encourage diversity is conceptually simple and broadly
Doubling dimension is measure of the intrinsic dimensional- ity of the pointset see Preliminaries for the formal definition.
2

---

Graph-Based Algorithms for Diverse Similarity Search
applicable. In principle, it can be integrated into any graph- based ANN algorithm that uses greedy search, such as HNSW, as it does not rely on DiscAfN- internals. We chose to apply our ideas within the DiskANN frame- work because it is, to our knowledge, the only real-world graph-based ANN algorithm that comes with worst-case theoretical guarantees. This allows us to ground our contri- butions in a rigorous yet practically relevant setting.
1.2. Related Work
Diverse nearest neighbor: Nearest Neighbor Search with diversity requirement has been previously studied in the work of (Abbar et al., 2013a:b), where they presented "di- versified version" of the Locality-Sensitive Hashing (LSH) approach due to (Indyk & Motwani, 1998). However, their diversification approach does not carry over to the graph- based methods. Moreover, they provide bi-criteria approx- imation only for the dual formulation of the problem, and do not consider the primal formulation. Finally, the distance functions D that they consider are limited to Hamming distance or its variants like the Jaccard similarity (Abbar et al., 2013a). Although it is plausible that the result could be extended to other distances that are supported by LSH functions, not all distance functions satisfy this constraint.
Generalizations. On the theoretical side, we extend our results in several directions listed below. These are shown and proved in Section A.
Relaxing the diversity requirement. First, in some ap- plications, the requirement that all reported results have different colors is too strong. (For example, the aforemen- tioned application to search (Liaison, 2019) allows for two points having the same color.) Therefore, we consider more general constraint, requiring that no color should appear more than k' times. We show how our results can be generalized to any 1 S k S k.
Graph-Based algorithms for similarity search: This work focuses on algorithms that employ graph- bash- data struc- tures for (approximate) nearest neighbor search. These ap- proaches are applicable to general metric spaces, where, dur- ing preprocessing, the metric is approximated by construct- ing a carefully designed graph. Given a query point, the al algorithm performs a greedy traversal of the graph to locate nearby points. Graph- based methods have received signifi- cant attention in both theoretical (Krauthgamer & Lee, 2004; Beygelzimer et al., 2006) and practical contexts (Malkov & Yashunin, 2018; Fu et al., 2019; Jayaram Subramanya et al., 2019). Further improvements can be obtained by optimiz- ing the graph traversal during greedy search by either ruling out expensive distance calculations of candidates which will not improve the priority queue (by cleverly using esti- mates (Chen al., 2023), and probabilistically excluding bad candidates using probabilistic partitioning methods (Lu et al., 2024)). For broader surveys of this area, see (Clarkson et al., 2006; Wang et al., 2021).
Generic metric p. Second, we generalize our results to the case where diversity is defined according to a given metric P (also defined over X but potentially different from D). Here, given required diversity parameter C, the goal is to report a set S of k closest points the query such that PrEss
P2) 2 C. We say that such a set S is C-diverse. Note that the color version is the special case where p(P1,P2) is defined to be 0 if p1 and P2 are of the same color, and 1 otherwise.
Unifying the two generalizations. In order to unify the above two results, and incorporate the notion of k' into the generic metric p. we allow for each point in the reported set S to be "similar" to at most k' 1 other points in S. More formally, for any p S there should be at most K'' 1 other points p' E S such that p(p.p') < C. We say that such set S is (K' C)-diverse". We show how our algorithms can be modified to this most general formulation of the problem.
A related but different line of research studies nearest neigh- bor search with local attribute constraints (Wang et al., 2023). In (Wang et al., 2023), the goal to obtain results with similar metadata as the query metadata (say color=RED or brand=NIKE as specified by the user query in shopping scenario). In contrast, in our setting, there is no user spec- ified constraint and the goal is to output relevant vectors with sufficiently dissimilar metadata. This crucial differ- ence extends to both the problem formulation as well as the indexing and search strategies.
Primal vs Dual formulations. Finally, instead of asking for the closest k points to the query satisfying a diversity requirement parameterized by C, which we refer to as the primal variant of the problem, one can ask the dual question: Given radius R, find a set of k points within radius R of the query, while maximizing the diversity. We show algorithms for both the primal and dual variants of the most general formulation of the problem.
2. Preliminaries
Problem definition. Let (X, D) be the underlying metric space, with distance function D. Let P be our colored point set. For p E P, we use collp) p] to denote its color.
IIn fact algorithms work for P being any pseudo-metie allowing p()1,p))
for two different points pl, P. but for simplicity we refer to it as metric, throughout the paper.
"We note that the notion of (K', C')-iverre set is new notion of diversity that strictly generalizes the widely used minimum- pairvise-distance notion for diversity.
Definition 2.1 (colorful). A set S is colorful if no two points in S have the same color.
3

---

Graph-Based Algorithms for Diverse Similarity Search
Definition 2.2 coloorff,,,,, A set S is k--oolorful, if within the multi-set {col [pi], coll [px]), no color appears more than k' times.
following intuition when pruning the graph: If a and v are "much closer" to each other than to another point p. then it is not necessary to connect p to both and v. This makes it possible to track the progress of the search procedure as it identifies points closer to the query point and use the doubling dimension to bound the degree of the graph and the total space. Our algorithm retains these insights, but also requires several new ones, as now we need to show that the search algorithms can progress while maintaining colorful solution. On high-level, this is established using the following two intuitions. First, if the colors of u. and v are the same, then again there is no need to connect to both of them, and we can use the same pruning as before. Second, if p is already connected to k points v Uks all of which are much closer u compared to p. and that they all have different colors, then again there is no need to connect p u. This is roughly because solution would need more than k points of different colors in relatively small neighborhood. The main challenge in converting these intuitions into a formal argument is in showing that such a graph keeps enough edges for greedy search algorithm to converge to an approximately optimal solution for the colorful NN problem.
Note that for k'ccoloruul for k' is equivalent the colorful notion.
Definition 2.3. Given a subset S C P of size k, and query q. for each i S k, we use Si(g) to denote the distance of the ith closest point in S to q. When is clear from the context, we drop and simply use S,.
Definition 2.4 (Colorful NN), Given a colored point set P. the goal of colorful NN is to preprocess P and create a data structure such that given query point q, one can quickly return a colorful subset S c P of size lo such that Sy is minimized.
Note that, when k= 1, our Colorful NN degenerates to the standard nearest neighbor search problem.
Definition 2.5 (k'- -Coooflll NN). Given colored point set P. the goal of k' -'-colorful NN is to preprocess P and create a data structure such that given a query point one can quickly return a k' k'-colorful subset S c P of size k such that S minimized.
Balls, doubling dimension, and aspect ratio. We use (p) to denote ball centered at p with radius r, i..., rD(p,r) = {u= E X D(u, p) < r). We will drop the subscript D if the metric is clear from the context.
3.1. The Preprocessing Algorithm
The indexing algorithm is shown in Algorithm 1. order to decide on the vertices that p should be connected to, we sort all vertices based on their distance from p in the list L and start connecting p to them. If we have already connected p to a close-by vertex u that has the same color as then we do not connect to v anymore. The same holds if we have already connected p to l near-by vertices all with different colors. We keep track of this using the array rep(u).
We say a point set P has doubling dimension d if for any point p and radius r, the set B(p, 2r) n P can be covered by at most 2d balls of radius r.
Lemma 2.6. Consider any point set P C X with doubling dimension d.
For any ball r) centered at some point p E P with radius r and a constant o, we can cover B(p, r) n P using at most m S ((a)) balls with radius smaller than r r/ox, i.e. B(p, r) n P C Um_ 3(p,.r/a) for some .I... Pm E X.
Lemma 3.1. The graph constructed by Algorithm I has degree limit (kk(Sa)) log A).
Proof. Let's first bound the number of points not removed by others, then according to Line 10 in Algorithm 1, the degree bound will be that times k:
We define A = Dmne to be the aspect ratio of the point DDim
set where Dmaz resp.) represents the maximal (minimal, resp.) distance between any two points in the point set P.
We use Ring(p: ri, r2) to denote the points whose distance from p is larger than T1 but smaller than T2. For each i [log2 AJ, we consider the Ring(p, Dmez/ /2i, Dmnn/ /i-1) separately. According to Lemma 2.6, Ring(p. Dmaz/2', (max/22111 n P using at most m. S Dmaz, Ac- (((a))) small balls of radius D(p, u)/(4a) > 2 cording to the pruning criteria in Line 9, within each small ball, there will be at most one such point u remaining. This establishes the degree bound of (1(a))) log A).
3. Algorithm for Colorful NN
can cover
In this section, for the sake of simplicity of presentation, we focus on the simplest setting where k' = 1, and p is the binary metric. The binary setting corresponds to our main application of seller diversity, and the case of k' = focuses on retrieving & closest points from the data set such that all of them have different colors/sellers. The algorithm that handles the general setting is presented in Section A.
3.2. The Search Algorithm
Intuition behind the algorithm. At high level, the "slow pre- pre-processing" algorithm of (Indyk& & Xu, 2023) uses the
Algorithm 2 shows the search algorithm for the colorful nearest neighbor search problem. The algorithm is greedy
4

---

Graph-Based Algorithms for Diverse Similarity Search
Algorithm 1 Indexing algorithm for colorful NN
Algorithm 2 Search algorithm for colorful NN
1: Input: set of n points P = {pi, .... Pn J: k the size
1: Input: A graph G EV, with Now being the out edges of p: query q; number of optimization steps T.
of the output; a is the parameter used for pruning.
2: Output: A directed graph G = (V, E) where V
(1....,f} are associated with the point set P.
2: Output: A set of k points ALG.
3: for each point E Pd do
3: Initialize ALG = {PI....,PH to be any set of ls points with different colors.
4: Sort all points u E P based on their distance from p
and put them in a list L in that order.
4: for i = 1 to do
5: while is not empty do
Pk <- the furthest point in ALG from q.
6: 6 argmin (u.
U + (ps)(ps) and sort U based on their distance
NCC 7: Initialize rep m)] <- {u}
from
7: for each point E U do
8:
for each point E C in order do
8: if ALG \ P& U u is colorful then
9:
if D(,, S D(p u) (2a) then
9: ALG + ALG Ph Uu
10:
if col[u] not shown in replu] and |repfu]] < 1 then
10:
Break
11: end if
11:
rep[u] + rep w| Uv
12: end for
12:
end if
13:
end for
13:
remove e from C end if
14:
Return ALG
14:
15:
end for
16: add edges from p to rep[u]
the distance upper bound above.
17:
Remove u from L
18:
end while
Otherwise, we let be the point where p" removed when processing u on line 9 in Algorithm 1. Because pd was not connected from Pk. either there exists a point in rep(u, with the same color, or rep(u) has already got k points with different colors. In the first case, we can set p' to be the point in rep [u] with the same color. In the latter case, by pigeon hole principle, there always exists color in rep [u] not shown in ALG Pk- Therefore, we can find desired y' E rep[u] and it is connected to pk-
19:
end for
algorithm where at each step, the neighbors of the furthest point from the query are additionally considered as candi- dates and a greedy solution is constructed among the points in the current solution and these neighbors. Next, we ana- lyze the search algorithm and finally prove Theorem 1.1.
Proposition 3.2. Let OPT {PIi...., be a colorful solution with minimized OPTk (see Definition 2.3), and ALG {Pi,..., pk) be the current solution (both ordered by distance from q). If Pk & OPT, there exists point p" E OPT \ ALG such that ALG \ Pke Up" is colorful.
We have proved that the p' we found satisfies the colorful criteria. Now we will bound its distance upper bound.
D .) s D(p", ,0) + D(p'.p") DDpp", q) + D(p', + D(p", u)
S &D(p', q) + D(p.. u)/ + D(pe, /)/(2)))
Proof. Observe that throughout the search algorithm, we maintain the property that AL colorful. Note that ALG
(Line 9 in Algorithm 1)
< D(p" q) + D(p:: w)/a S D(p", 9) + P(pk.p))/a (Because u is ordered earlier than p" in Algorithm 1)
P& has k 15-1 different colors, and OPT has & different colors. Thus there should be point p" OPT whose color is different from all points in ALG \ ps- Note that such p² cannot belong to ALG and thus belongs to OPT \ ALG. n
S D(p" q) + D(p.. g)/a a + D(p", .4)/a
S D(pr, 4) a (1
Lemma 3.3. There always exists a point p' E Nouc(pk) (for pk as defined in Line 5) such that (i) ALG \ P& Up' is colorful; and (ii) D(p's .4 S D(p 9)/a (1++((1)/))
Proof of Theorem 1.1. Regarding the running time, the to- tal number of edges connected from any point in ALG is bounded by |0| s O(K(8a)" log A). In each step, the algorithm first sorts all these edges connected from pk E ALG and then checks whether each of them can be added to the new ALG set. The total time spent per step is bounded by O(UU) log Ul). The overall time complexity is Ô (k((aa) log A) per step.
Proof. According to Proposition 3.2, for any current so- lution ALG with ps & OPT, there exists a point p* E OPT \ ALG such that ALG \ Ps Up" is colorful. If there exists an edge from pa to p", replacing pa with p" is a poten- tial update, We set p' = p" and D(p q) S OPT, satisfies
5

---

Graph-Based Algorithms for Diverse Similarity Search
To analyze the approximation ratio, at time step 4, we use ALG {pi:....P' } to denote the current unordered so- lution. We denote A = max D(y). q). According to {E[M]
Dfrf .)) < D at OPT,P S can happen only if S log S
D(pj.9) +
Duii This
In conclusion, O log, ) steps suffice to achieve the de- sired approximation ratio in Theorem 1.1.
Algorithm 2 and Lemma 3.3, if p. is updated at time step t, we have D(v(.9) g) < D(p .9)/a + OPTx(1 + 1/0)- By an induction argument, if a point Pr is updated by times at the end of time step T, we have D(pf q) x
We remark that it is easy to verify that for k1 2 k2, the data structure built for the value k = 1 can be used to search with respect to value k = kg. Thus in applications, it suffices to only have an upper bound on the value of k at the data structure construction time.
D a OPT
D(p We now prove that ALG S max a7
+ a-1 OP
Let E [k] be the index achieving the maximal distance upper bound. For the sake of contradiction, if ALG.
3.3. High-level Intuition about the Generalizations
D(p..9) + a K this means that pf" was updated for at most T/k - times. By a counting argument, there exists another index j which was updated for at least T/k k + times. However, at the time 1. when p/ was already updated
a7/$
Given our results colorful NN, it is relatively simple to extend them to the k' k'cooloruul NN version with the same bounds. One key contribution is to demonstrate that, in the graph degree bound, the overhead factor k. can be reduced to k/k' while preserving the approximation quality. This reduces both the query time bound and the overall space used by the algorithm. This improvement is tight, in the following sense: When K' 1, we recover the bound for colorful NN problem, and when k' = k. we recover the standard K-NN bound, where no additional factor is needed.
for T/k times, D(p), < D(p),a) - ALG. < a=74
ALG so the algorithm wouldn't 't have chosen P/ to optimize because it couldn't 't have had the maximal distance at that time, leading to contradiction. Therefore, we prove that D(pP.g) a+1 ++1 OPT
A S max T// +
Now we consider the following three cases depending on the value of the maximal D(p.. q). This case analysis is similar to the proof Theorem 3.4 from (Indyk & Xu, 2023).
For our algorithm to work with a generic diversity metric p. we use an intuition similar to that in colorful case. However, instead of pruning an edge from the point p to the point u when p is already connected to representative vectors 01,..., ..... T2 of different colors, now choose the represen- tatives based on the diversity metric p. We find diverse subset of points in the neighborhood of u (c.g., using the greedy Gonzales algorithm for the k-center problem) and connect p only to those selected points U1..... Up. Again, the main challenge to demonstrate that a greedy search al- gorithm can converge an approximately optimal solution, given the set of edges retain. The difficulty lies in the fact that we can only maintain an approximately diverse sub- set ALG, in contrast to the colorful version, where we only needed ALG to contain k different colors. As the algorithm proceeds with further iterations, the technical difficulty lies in ensuring that the approximation factor does not grow depending on the number of iterations.
Case 1: D( 2Dmaz.
Let Pk be the point having the maximal distance from q in an optimal solution OPT. We know that for any p!, we have D(pk q) 2 D(P..)) g) - D(r.. pk) 2 D(p 4) D maxx& 2 D)p..))/2. Therefore, the approximation ratio ALG. after T optimization steps upper bounded by D(r S
Dop + a+1 S T/N + a+1, A simple calculation D/p a-1
a-1" shows that we can get a (a=1 + c) approximate solution in OKklog, 2) steps.
Case 2: D(p..g) S 2az and OPT >
a-1 Dmnn- 1(a+1)
To satisfy
D) at! OPT, < ( OPT we need 777
D(p.-g)
< <OPT.. Applying the lower bound OPTr >
a=7E
a-1
D Dynns we can get that T 2 log M(++1A (a-1)e
suffices.
([+1)
4. Experimental Evaluation
Case 3: D(pf,g) q) 2Dmaz and OPTr a-1
1la41yDmin Dmin-
In this section we provide an empirical evaluation of our m To this end, we first devise a heuristic adaptation based on our provable algorithms for the k'cclorfull NN problem as in Definition 2.5. As we note below, this problem itself captures several real-world notions of diversity.
In this case, we must have k- 1, because otherwise D(pi. pi) < 2D q) < Dminn violating the definition of Dmin- Suppose to = 1 and the problem degenerates to the standard nearest neighbor search problem. After T optimiza- tion steps, if of is still not the exact nearest neighbor, we have D(pf q) Z D(p :i) - OPT, Z Duss, Applying the upper bound of D(pT' 9) and OPT1, we have Pmnin <
At high level, the difference between our heuristics
2
'The code is available https://github.com mi microsoft/Diss http:////Disttatteeee//eeeeeeeee
6

---

Graph-Based Algorithms for Diverse Similarity Search
Seller
3.0%
Seller
5. 0%
Oonuate The cerigge
Seller 54.3%
8%
Seller
11 M%
by 18%k coert dk
20
Seller 2
Ueiters Dusiibutee
100
Figure I: Seller distribution in a real-world dataset with 20 million base vectors, where the top 7 sellers constitute more than 90% of the data.
Piccstage
Figure 2: Brand cumulative distribution for Amazon dataset, showing the coverage of the vectors by the brands in sorted order. The top 10% of brands cover 86% of the vectors.
and our theoretical algorithms is similar to the difference between the fast- and slowpprepoccessing algorithms in DiskANN (Jayaram Subramanya et al., 2019; Indyk & Xu, 2023)). Indeed, we deploy the same construction as in the fast-preprocessing variant of DiskANN, but modify the pruning procedure to insist that any node u has sufficiently many colorful out-neighbors before an edge (u, v) can get pruned, in addition to the geometric condition for pruning as in the original algorithm (Jayaram Subramanya et al., 2023). The number of colorful edges that needed before pruning can occur is given by tunable parameter in our algorithm, and indeed this is the direct heuristic analog of step 10 in Algorithm 1. This is very high-level description, and we refer the interested reader to Appendix B for the complete pscudo-code of our heuristic algorithms.
comprises of 64 o4-dimensional vector embeddings of differ- ent products from a large advertisement corpus. Each prod- uct/vector is additionally associated with a seller, which becomes its color in our setting. There are 20 million base vectors, around 2500 sellers, and 5000 query vectors. This distribution is highly skewed, with an extremely small num- ber (around 7) of sellers constituting more than 90% of the data. hence naturally motivating the need for enfore- ing diversity in the search results. The fraction of products corresponding to the top 20 sellers is shown in Figure 1.
Amazon Automotive Dataset: Our second real-world dataset is derived from the recently released Amazon dataset (Simhadri et al., 2024). It comprises of 384- dimensional vector embeddings of product descriptions listed on Amazon under the Automotive category. Each product/vector is additionally associated with a brand, which becomes the color. There are around 2 million base vectors and around 85000 brands. The distribution, while skewed, is far more balanced than the above seller dataset, with around 1 10% of the brands accounting for 80% of the vectors as summarized in Figure 2.
Second, we rum experiments using our heuristies on sev- eral different datasets, both real-world well as synthet- ically generated. We show how our heuristic consistently delivers superior recall for fixed latency budget, across datasets when compared to a natural baseline of using a vanilla DiskANN algorithm and enforcing diversity only via a final post-proe pros-processing. We stress that both our real-world datasets are motivated from important shopping scenarios: the data points represent products and color of vector corresponds to either the seller or the brand of the product. It is then desirable to output results from diverse set of sell- ers/brands (Liaison, 2019). Intuitively, displaying diverse results would lead to increased competition between the sellers, and also simultaneously higher click probabilities, thereby leading to an increase in revenue of the exchange,
We also consider the pub- licly available real-world Arxiv dataset (Embeddings, 2024) which contains OpenAI embeddings of around 2 million paper abstracts into 1536 dimensional vectors and the clas- sical SIFT dataset of 1M vectors in 128 dimensions. These datasets do not contain any color information, so we syn- thetically add this information into the data set. Specifically, for the Arxiv dataset, we generate the color information as follows: for each vector, with probability 0.9, we assign a color selected from the set (1,2, uniformly at random, and with 0.1 probability we assign a color selected uni- formly at random from the set {4, {4.... 1000}. Therefore the number of distinct colors is at most 1000 in this data set. For the SIFT dataset, we sampled one dominant colors with probability 0.8 and had a uniform distribution over 999 other colors with probability 0.2.
"Skewed" Semi-syuthetic Datasets:
4.1. Experiment Setup
All experiments were run on a Linux Machine with AMD Ryzen Threadripper 3960X 24-Core Processor CPU's @ 2.3GHz with 48 vCPUs and 250 GB RAM. All query throughput and latency measurements are reported for runs with 48 threads.
Datasets. We consider two real-world and three semi- synthetic datasets for evaluation.
"Balanced" semi-synthetic Dataset: Finally, we also consider another distribution which is globally uniform, but locally
woal-world Seller Dataset: Our first real-world seller dataset
7

---

Graph-Based Algorithms for Diverse Similarity Search
skewed. Indeed, we use the same SIFT dataset for the vector data. For colors, we randomly partition the space into one thousand buckets, using a random hyperplane scheme. We then assign a unique primary color for each bucket. Now, each vector within any specific bucket is assigned its primary color with a high probability of 0.8, and a uniformly random non-primary color with the remaining probability. It is then easy to see that the distribution is roughly balanced across colors from global perspective, but quite skewed in any small local neighborhood.
Standard DiskANN Build + Diverse Search: In this improve- ment, we use our piverssty-preserving search Algorithm 7 discussed in the Appendix B, but the index construction remains the standard DisKANN algorithm.
Diverse DiskANN Build + Diverse Search: For our complete algorithm, we additionally use our diversity-aware index construction Algorithm (Appendix B) which ensures sufficient edges are present to nodes of different colors in any neighborhood.
Parameter setup. For all of the above algorithms, we use fairly standard parameters of list-size L = 200 and graph- degree 64 when building the graphs. During search, we vary the list-size L. at search time to get varying quality search results and plot the recall@ 100 vs average query latency.
Tasks. For all of the above datasets, we seek to retrieve k = 100 nearest neighbors. In one extreme scenario, we set K' = 1, i.e., all hundred of the returned results need to be of distinct colors. This type of setting would be relevant in retrieval augmented generation setting where documents are typically chunked into several parts and each part is vectorized; when the user utters a query, we might want to retrieve the most relevant set of documents (as opposed to the most relevant chunks, which might all be from the same document) to a given query. before passing on these contents to a large-language model which then answers the user query. A natural way to enforce this document-level diversity during retrieval is treat the document-id of any vector its color, and using our diverse search routine.
4.2. Results
Our results are shown in plots of Figures 3, 4, and addition- ally in Figures 5, and 6 in Appendix C. As one can see, both of our algorithmic innovations play crucial role in the over- all search quality on the real-world dataset. For example, to achieve 95% recall @ 100 in the real-world seller dataset, the baseline approach has latencies upwards of 8ms, while the improved search algorithm brings it down to zs 4.5ms. Making both build and search diverse further brings it down to around R 1.5ms, resulting in an improvement of 5X.
In another scenario which might have more appeal in shop- ping or advertisement display, we seek to retrieve k- = 100 nearest neighbors, while having k' = 10, i.c., no more than ten of the k results may belong to any single color. This will promote the retrieval to display a diverse set of sellers/ brands in such scenarios, thereby hopefully increasing user satisfaction and engagement, This can also capture intent diversity in regular web-search (when we can use a simple classifier to represent the intent behind the data point as ad- ditional meta-data, which becomes the color in our setting- e.g., car or animal for different images of jaguar, ML or EE concept for transformer, etc.).
The plot in Figure 4 reveals an interesting phenomenon: for high recalls (say 90%) on the semi-synthetic arXiv dataset, the post-processing approach has latency of around 90ms, while the diverse search algorithm when run on the stan- dard graph has a latency of around 135ms. This is perhaps because the standard graph construction might not have sufficiently many edges between nodes of different colors to ensure that the diverse search algorithm converges to a good local optimum. On the other hand, running the diverse search on the graph constructed keeping diversity in mind during index construction fares the best, with a latency of only around 25ms. A similar phenomenon occurs in the SIFT semi-synthetic dataset (shown in Appendix C) as well.
Algorithms. Since our algorithms are enhancements of the DiskANN algorithm, we use that as a natural baseline to compare against.
Standard DisKANN Build+ + Post-Processing (Baseline): In this baseline, we build a regular DiskANN graph without any diversity constraints. To answer query, we first invoke the regular DiskANN search algorithm to retrieve r >>> k candidates, again without any diversity constraints. Then we iterate over the retrieved elements in sorted order of distances to the query, and greedily include the ones which do not violate the k' diversity constraint, until we have k total elements. The parameter r is tunable at search time, and higher yields more candidates, meaning more diverse candidates can be obtained using the post-processing step. However, higher also consumes more search complexity.
4.3. Build Diversity Parameter Ablation
In our heuristic graph construction algorithm (see Algo- rithms 8 and 9), the graph edges are added by considering both the geometry of the vectors and the corresponding colors. Loosely, the a-pruning rule of DiskANN dictates
'Recall @ 100 is the size of the intersection of the algorithm's 's 100 returned results with the true 100 closest diverse candidates, averaged over all queries. The ground -tuth set of top 100 diverse NNs for any query can be computed by iterating over all the vectors in sorted order of distances to the query, and greedily including the ones which do not violate the & diversity constraint, until we have accumulated & total elements.
8

---

Graph-Based Algorithms for Diverse Similarity Search
Real Dataset, Max Per Color
Amazon Dataset, Max Per Seller
ARXIV Dataset, Max Per Color
100
110
90
50-
Recalighodd
Recaliigtoo
30
Diverse Build Diverse Search
-0- Diverse Buld e Diverse Search
-e- Diverse Build + Diverse Search Stancard Build Divense Sea Stancard Bulld Post Processing
Standard Build Diverse Search Standard Processing
Standard Build Post Processing
Standard Build Diverse Search
20
10
15
20
5000
10000
15000
20000 25000
30000
20
40
60
100 Mean Labency (ms)
BC
120
140
Moan Latercy (ma)
Mean Latency Jus)
Figure 3: Recall vs Latency for real-world, Amazon, and ArXiv datasets with k' = 1.
Real Dataset, Max Per Color 10
Amazon Dataset, Max Per Seller 10
ARXIV Dataset, Max Per Color 10
100
100
95
90-
90
nec.alginm
80
Recwigrmm mm
Recatggoo
80-
60-
60
Diverse Build Diverse Search
Diverse Diverse Search
Biverse Civerse Search
Standard build + Diverse Search
Standard build + Diverse Search
Stanciand build Diverse Search
btandard build Posteroccssiigg
Standard Build rost-rrocassing
- Stanicard build host-Mocessing
5000
10000
15000
20006 25000
30000
20
40
80 Mean Latency Ims)
60
100
120
Meen Latency (ms)
Mean Latency (ps)
Figure 4: Recall vs Latency for real-world, Amazon, and ArXiv datasets with k' 10.
m Parameter
Build Time (s)
a distance threshold, the goal is to retrieve a maximally diverse set of results within that threshold. Our algorithm can further allow more relaxed diversity requirement pa- rameterized using k allowing limited number of similar items in the output. All our algorithms come with provable guarantees, and we further present heuristic adaptations that integrate easily with existing DiskANN implementations. We expect that similar strategies can be applied to other graph
1
50
2
53
10
55
Table 1: Build Times w.r.t Parameter
that an edge (u, v) is blocked by an existing edge (u, w) if d(w, v) S d(u, v) aa. In the original DiskANN algorithm, any edge (u, v) which is blocked is not added. In our setting, we additionally enforce that an edge needs to be blocked by edges of m different colors to not be added to the graph, where m is a tuneable parameter. We now perform an ab- lation capturing the role of m in the graph quality using the skewed SIFT dataset. Table shows table with build times for various indices by varying only the parameter, and Figure 7 in Appendix C shows the search quality of these different indices.
search methods, such as HNSW, to enhance result diversity. Finally, we demonstrated the practical effec- tiveness of our approach through experiments focusing on the binary diversity case across several application domains.
5. Conclusion
In this work, we introduced methods to incorporate diver- sity into the DiskANN graph-based similarity search algo- rithm. We proposed algorithms that address both binary diversity measures (the colorful case), as well as the more general case where an arbitrary metric is used to measure the diversity. Our algorithm can handle both the primal ver- sion- where the goal is to find nearest neighbors that meet a diversity requirement- and the dual version-aee wwhre, given
9

---

Graph-Based Algorithms for Diverse Similarity Search
Acknowledgements
Embeddings, A. O. Openai embeddings
of arxiv abstracts, 2024. URL https:
Piotr Indyk was supported in part by the NSF TRIPODS program (award RMS-20224433 Haike Xu was supported by the Mathworks Fellowship. This work was conducted in part while Piotr Indyk and Sepideh Mahabadi were visitors at the Simons Institute for the Theory of Computing as part of the Sublinear Algorithms program.
//github.bb/// wwwttoooaaa simhadri bllg-amm-beecchaarks/ccoomm @fle53aa3cd9cd222 ddaaa4aaaaf224cc weefff2eec2222222 fedd..
Fu, C., Xiang, C., Wang, C.,, and Cai. D. Fast approximate nearest neighbor search with the navigating spreading- out graph. Proceedings of the VLDB Endowment, 12(5):
Impact Statement
461-474, 2019.
Gonzalez, T. F. Clustering minimize the maximum in- tercluster distance. Theoretical computer science, 38: 293-306, 1985.
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Indyk, P. and Motwani, R. Approximate nearest neigh- bors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 603-613, 1998.
References
Abbar, S., Amer- Yahia, S., Indyk, P., and Mahabadi, S. Real- time recommendation of diverse related articles. In Pro- ceedings of the 22nd international conference on World Wide Web, pp. 1-1 2013a.
Indyk, P. and Xu, H. Worst-case performance of popular approximate nearest neighbor search implementations: Guarantees and limitations. Advances in Neural Infor- mation Processing Systems, volume 36, pp. 66239-66256, 2023.
Abbar, S., Amer- Yahia, S., Indyk, P., Mahabadi, S., and Varadarajan, K. R. Diverse near neighbor problem. In Proceedings of the twenty-ninth annual symposium on Computational geometry, pp. 207-214, 2013b.
Iwasaki, M. and Miyazaki, D. Optimization of indexing based on k-nearest neighbor graph for proximity search in high-dimensional data, arXiv preprint XXIv:1810007355 2018.
Aumueller, M., Bernhardsson, E., and Faitfull, A. Ann benchmarks. benchmarks. https: https:https:///e banca//aasaa....a.aaa...... com, 2024.
Jayaram Subramanya, S., Devvrit, F., Simhadri, H. V., Kr- ishnawamy, R., and Kadekodi, R. Diskann: Fast accurate billion-poin nearest neighbor search on a single node. Advances in Neural Information Processing Systems, 32, 2019.
Beygelzimer, A., Kakade, S., and Langford, J. Cover trees for nearest neighbor. In Proceedings of the 23rd inter- national conference Machine learning, pp. 97-104, 2006.
Jayaram Subramanya, S., Devvrit, F., Simhadri, H. V., Kr- ishnawamy, R., and Kadekodi, R. Diskann. https: 2023.
Carbonell, J. and Goldstein, J. The use of mmr, diversity- based reranking for reordering documents and producing summaries. Proceedings of the 21st annual interna- tional ACM SIGIR conference on Research and develop- ment in information retrieval, pp. 335-336, 1998.
/ //github. /mi http://....ommmccoooooo/t////
Krauthgamer, R. and Lee, J. R. Navigating nets: sim- ple algorithms for proximity search. In Munro, I. (ed.), Proceedings of the Fifteenth Annual ACM-SIAM Symposium Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004, pp. 798-807. SIAM, 2004. URL /tptt:::/dde.. org/ citation. cfm? id= 98279992722222 982913.
Chen, H.-T. and Choi, E. Open-world evaluation for re- trieving diverse perspectives. In Proceedings of the 2025 Conference of the North American Chapter of the Associ- ation for Computational Linguistics: Human Language Technologies (NAACL), Long Pupers, 2025.
Liaison, S. Google announces site diver- sity change to search results, 2019. URL
Chen, P., Chang, W.-C., Jiang, Y., Yu, H.-F., Dhillon, I., and Hsieh, C.-J. Finger: Fast inference for graph- approximate nearest neighbor search. In Proceedings of the ACM Web Conference 2023, pp. -235,, 2023.
http://wwwwreccegggneoooraaaaaaa google site wwwe-ssteeeeeaitttyaaeaeeeeeeeee whwnge//11anna../////// 1
Lu, K., Xiao, C., and Ishikawa, Y. Probabilistic routing for graph-based approximate nearest neighbor search. In Pro- ceedings of the 41st International Conference on Machine Learning, pp. 33177-33195, 2024.
Clarkson, K. L. et al. Nearest-neighhor searching and metric space dimensions. Nearest- neighbor methods for learning and vision: theory and practice, pp. 15-59, 2006.
10

---

Graph-Based Algorithms for Diverse Similarity Search
Malkov, Y. A. and Yashunin, D. A. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions pattern analysis and machine intelligence, 42(4))824- 836, 2018
Rezaei, M. R. and Dieng, A. B. Vendi-rag: Adaptively trading-off diversity and quality significantly improves retrieval augmented generation with llms. arXiv preprint 122,,, 2025.
Shakhnarovich, G., Darrell, T., and Indyk, P. Nearest- neighbor methods in learning and vision. MIT press, 2006.
Simhadri, H. V., Aumüller, M. Ingber, A.. Douze, M., Williams, G., Manohar, M. D., Baranchuk, D., Liberty, E., Liu, F, Landrum, B., Karjikar, M., Dhulipala, I.., Chen, M., Chen, Y., Ma, R., Zhang, K., Cai, Y., Shi, J. Chen, Y., Zheng, W., Wan, Z., Yin, J., and Huang, B. Big ann benchmarks. https: //gthub..bh////gg wwwp//aarsaa-iimaaaeeaa httpekk//ppplll11 2024.
Wang, M., Xu, X., Yue, Q. and Wang. Y. A comprehen- sive survey and experimental comparison of graph-based approximate nearest neighbor search. arXiv preprint arXiv:2101. /2631, 2021.
Wang, M. Lv, L., Xu, X., Wang, Y., Yue, Q., and Ni, J. An efficient and robust framework for approximate near- est neighbor search with attribute constraint. Advances in Neural Information Processing Systems, 36:15738- 15751, 2023.

---

Graph-Based Algorithms for Diverse Similarity Search
A. Algorithms for the General Case
In this section we describe our algorithms for the most general case where can take any value between and k; and the diversity metric p an arbitrary diversity metric. First we start with definitions, additional preliminaries, and our main theorem statements A.5 and A.6.
A.1. Additional Preliminaries, Problem Formulation, and the Main Theorems
As before, we let (X, D) be the underlying metric space, where D measures the distance between the points. In this section, we assume that we are given second metric space (X. which measures the diversity between the points. As before P subset of n points in X. So for two points P1. E P. p(P1.22) measures their pairwise diversity.
Again, we use (p r) (or just r(p,r) for simplicity of exposition) to denote ball centered at p with radius i.e. Bp(,, = {u E X D(u,p) < r). Similarly, we define the ball (p,),r) = {u E X p(u, p) < r).
The following definitions recap the discussion in the introduction.
Definition A.1 (C-diverse). Let be a set of points in X. We say S C-diverse if for any two points pr P2 E S, we have p2) 2 C.
Note that the colorful setting, corresponds to the diversity metric p being uniform. That is, we can set p(p:. P2) = 0 when col[p;] = [p)] and set p(P.. = otherwise. Then, we retrieve the colorful notion of diversity: a set S of size is colorful iff it is 1-diverse. We further generalize this notion to allow the set to contain at most k' > 1 points that are similar to each other.
Definition A.2 ((K', C))diverse). Let S be set of points in X. We say S is (K', C'--iverse if for any point p S, we have [p C) n S S k'. Note that being (1, C') diverse is equivalent to the notion of C-diverse.
We consider two dual variants of the diverse nearest neighbor search problem, both of which use two approximation factors: e > 1 is the "dissimilarity" approximation factor with respect to D, and a > 1 is the "diversity" approximation factor with respect to p.
Definition A.3 (Primal Diverse NN). Given a point set P. diversity value C, and the value k' S k. the goal of Primal Diverse NN is to preprocess P and create data structure such that given query point g. one can quickly return the closest set S C P of size l that is (k', C')-iverse. Here closeness of set S is measured by S₃ (See Definition 2.3).
In the approximate variant, for any q E XX if OPT is a (K, C'-diverse set of k points which minimizes OPTK. then the data structure outputs ALG that is (K', C/a)-diverse such that ALG, S c OPT
Definition A.4 (Dual Diverse NN). Given a point set P, a radius R. and the value k' < k. the goal of Dual Diverse NN is to preprocess P and create data structure such that given a query point q, one can quickly return a set S P of size k that lie within the radius R, while maximizing the diversity.
Formally, for any q E X, let Bp(g, It) be the set of points in P within distance R from g, and let OPT be a (k', C)-diverse set of k- = min(k: (k. (g, R))) points from Bp R) that maximizes C. Then the data structure outputs ALG of size k* that is (k', diveeee such that ALG S cR.
As described in the introduction, the problem addressed in the prior work (Abbar et al., 2013b) is the dual diverse NN problem, where the only consider k' 1.
Our main theoretical result is captured by the following theorems, which specifies the approximation and running time guarantees for our algorithms solving the primal and dual versions of the diverse nearest neighbor problem.
Results.
Theorem A.5 (Primal Diverse ANN). Ler OPT = {pi,...pii> be a (K', C'-diverse solution that minimizes OPT Given the graph constructed by Algorithm 3, the search Algorithm 4 finds a (W',
solution ALG with ALG S
(et) + OPT in O (kloga 2) steps, where each step takes O / (Ba)())) log A) time. The data structure uses space (n(kk/))(8))) log A).
Theorem A.6 (Dual Diverse ANN). Given the graph constructed by Algorithm 3, the search Algorithm 5 finds (K', CC/24- diverse NN solution ALG satisfying ALGi < a=1 +o) R in Ô ((K//k) (8a)) log? A) time, if there exists a (K' C)- diverse solution OPT with OPT₁ & R.
12

---

Graph-Based Algorithms for Diverse Similarity Search
A.2. Algorithm
The preprocessing algorithm. The indexing algorithm, which is the same for both the primal and dual versions of the problem, is shown in Algorithm 3. Line 12 of the algorithm uses the greedy algorithm of (Gonzalez, 1985), defined below.
Algorithm 3 Indexing algorithm for diverse NN
1: Input: A set of n points P {Pi...., ... P. k is the size of the output; k' is the parameter in the diversity definition; is the parameter used for pruning.
2: Output: A directed graph G = (V, E)) where V = {I,..., n are associated with the point set P.
3: for each point E P do
4: Sort all points u E P based on their distance from p and put them list C in that order
5: while C not empty do
6: 6 argmin (u, p)
NEC 7: Initialize bag (x] {4}
8: for each point E C in order do
9:
if D(u, v (pp, (2a) then
10:
bag[u] < bag[u) u U
11:
remove e from C end end for
12:
14:
rep[u] the greedy algorithm of Gonzales choose k/W/ points in bag[u] to approximately maximize the minimum pairwise diversity.
15:
add edges from p to rep in]
16:
Remove from C
17:
end while
18:
end for
Gonzales' greedy algorithm. Given set of n points and parameter m, the algorithm picks points follows. The first point is chosen arbitrarily. Then, in each of the next m-1 steps, the algorithm picks the point whose minimum distance w.r.f. to the currently chosen points is maximized. It is known (Gonzalez, 1985) that this algorithm provides a 2-approximation for the problem of picking a subset of size m which maximizes the minimum pairwise diversity distance between the picked points. Moreover, the picked set has an anti-cover property which we will discuss Proposition A.10.
Primal Search Algorithm. Algorithm 4 shows the search algorithm for the primal version of diverse nearest neighbor. The algorithm is analyzed in Section A.3. The initialization step of line can be done using the following algorithm.
The initialization step. Given set P of points equipped with metric distance p. and parameters h'' and k, and lower bound diversity C, the goal is to pick a subset S C P of size k which is (k', C/4) diverse or otherwise output that no (K', -'-diverse subset 5 exists. We use the following algorithm
Initialize SOL =0
While there exists point E P such that the ball B = (p C/4) has ke' points in it, (i.e., |Bn k'),
Add an arbitrary subset of B n P of size k to SOL.
Remove all points in 2B Bp C/2) from P.
Add all remaining points in SOL.
If |SOL| > k. return an arbitrary subset of it of size ki otherwise return 'no solution'.
Lemma A.7 (Initialization). If has a subset OPT of size k that is (K', C)-diverse, our initialization algorithm finds a (k', C/4)-diverse subset of size
Proof. Note that is straightforward to see why the set SOL that we get at the end is (k', C/4)-diverse. This is because first of all, each time we pick k' points in ball and add them SOL, we make sure that no additional point will ever be
13

---

Graph-Based Algorithms for Diverse Similarity Search
Algorithm 4 Search algorithm for primal diverse NN
Input: A graph G E) with Nout(p) denoting the out edges of p: query q, number of optimization steps T; diversity lower bound C.
2: Output: A set of k points ALG.
3: Initialize ALG
(P.)... to be set of k points that are (k', C/12)- using the initialization step proved in
Lemma A.7.
4: for = 1 to T do
5: + U (p) Up, and sort based on their distance from !
PEALG
6:
ALG + the closest k - 1 points in ALG
7:
for each point u E U in order do ALG u (K', C/ve)-diverse then
8:
9:
ALG u
10:
end if
11:
if |LL = k then
12:
Break
13:
end if
14:
end for
15:
end for
Return ALG
picked in 2B and thus within distance C/4 4 of the points we pick there will be at most k'' points in the end. Second, the end, every remaining ball of radius C/4 has less than equal to K' points in it. Therefore, can pick all such points in the solution and everything we picked will be (k', C/4) diverse.
Next we argue that we are in fact able to pick at least l points in total which completes the argument. We do it by following the procedure of our algorithm and comparing it with OPT. At each iteration of the while loop that we remove P n 2B, we add exactly k' points from P 2 2B to our solution SOL. Now note that the optimal solution OPT cannot have more than k' points in 2B because by triangle inequality any pair of points in 2B have distance at most C, and picking more than k' points in this ball contradicts the fact that OPT is (k', C) diverse. Thus we can have an one-to-one mapping from each point in OPT n 2B to the k' points in P n 2B added to SOL. At the end of the while iteration, we know any unmapped point in OPT still exists in P. so we just map it to itself. By doing this, we can have an one-to-one mapping from OPT to SOL, which means that [SOL| 2 |OPT| =
Dual Search Algorithm. Algorithm 5 shows the search algorithm for the dual version of the diverse nearest neighbor problem. We provide the analysis in Section A.4.
A.3. Analysis of the Primal Diverse NN Algorithm
In this section, we prove Theorem A.5 that gives the approximation and running time guarantees for Algorithm 3 and Algorithm 4.
Lemma A.8. The graph constructed by Algorithm has degree limit (((+/K)(8a)) log A).
Proof. Let's first bound the number of points not removed by others, then according to Line 14-15 in Algorithm 3, the degree bound will be that times k/k'.
We use Ring(p, P1, 12) to denote the points whose distance from p is larger than rı but smaller than 72- For each i llog, A). consider the Ring(p, Dmaz/ /2, Fmax//2-11 separately. According to Lemma 2.6, we can cover Ring(p, Dmaz/2*. D Dmax/2i-11 n P using at most m & O((a))) small balls with radius Dmaz pruning criteria in Line 9, within each small ball, there will be at most one point remaining. This establishes the degree bound of ((k/k)))Sad log A).
According to the
2:+20
Lemma A.9. Suppose OPT = {pi,...,P?. is (K' -iviiers solution with minimized OPT k. and let ALG = {pI,..., Pa be the current solution (ordered by distance from q). If pa & OPT. there exists a point p" E OPT ALG such that BD(P", C/2) n (ALG)) \pp) k' and ALG Ap Up" n is (K', (,,CC44-da -ivvedieerse.
14

---

Graph-Based Algorithms for Diverse Similarity Search
Proof. Recall that we use Bp(p," r) denote the ball in the p) metric space. Because phe & OPT, have OPT OPT ALG # Ø. We repeatedly perform the following operation until OPT gets empty: select point p from OPT, and let (p(p, C*) n OPT, and remove from OPT. By doing this, we can get list of points {pi and partition of OPT ALG 21 U 22... U 2m. By definition, we have the following properties:
(pi.-.,Pm)) ALG =
2, = for j
E1 = OPT \ ALGI = ALG OPT]
Now let my B
(ALG)) \ pk OPT). Because all the Bp(r), C/2) balls are disjoint, E; Iwxl < |ALG \ Pk OPT < |OPT \ ALGG| = E |zi|, there must exist such that |ma]| < [z:]. For that i, we have that [B,(P] C/2) n
(ALG) \ pa) is equal to
= [B,(P; (ALG Bp(r.. (/2) Pk OPT)
(Because py & OPT)
= =|Bp(p,, (ALL)G))O)))) wel
<IB,let, (AL))(AG)))))))) |za]
<IBple,, (/LG(((A))OPT)) Bp () { ALG))
< (BADE, (ALGANNOPP))) (B (OPT (ALG)
= (B,(P,,))
Sk'
Therefore, we get (p) C/2) n (ALG), p&) < W. Now, for any point p E Bp(p,, [B,(, (ALG) / pk:] S [B,(%, C
n (ALG pa)l < K, so we know that ALG \ pa Upt is (K' c/4)ddeeee
The following is the well-known anti-cover property of the greedy algorithm of Gonzales whose proof we include for the sake of completeness.
Proposition A.10. In Line 14 of Algorithm 3, let rep[u] be the output of greedily choosing k/K points in bag(u) maximizing p(U1,
minimum pairwise diversity. If a point p E bag[u] \ rep[u], we have min p(p, v) S min
vErep(u]
V1,v2Erep(u]
Proof. For the sake of contradiction, suppose min p(p, v) min Erepp[) achieved by min p(11, v2) = p(x,y). Without loss of generality, we assume rr added to rep[u] before y. At the EreepErep(u"
p(u1, U2), and the pairwise diversity minimizer
vErep[u]
time step & when y was added to rep:[u]. min p(y,v) - p( v) and min p(p, v) min p(p,v) > p(3; v), so y nEropi[N]
verep, (u] wouldn't 't have been chosen by the greedy algorithm. Therefore, we have derived contradiction.
#Erep[un]
Lemma A.11. There always exists point p' connected from some point ALG such that
1. ALG \ Pe Up' is (K' C/12)-diverse
2. D(p' S D(p.: g)/a + OPTx(1+1/0)
Proof. According Lemma A.9, for any current solution ALG with Pk & OPT, there exists point p" E OPT ALG such that ALG \ P& U p" is (K', d/ve--ee Let E ALG be the closest point to p". If there exists edge from to p". replacing Pk with p" is potential update. We set p' p² and D(p', g) < OPT, satisfies the distance upper bound above.
Otherwise, we let be the point where p' E bag[u] but not selected into rep/u]. For any point p' bag[u], D(p', u) < D(w, (2x), so D(p', pp)) < D(w,u)/a < D(w, p²). This means that all points in bag(u) are closer to p* than w, so they can't belong to ALG. In the following, we consider two cases depending on whether min p(p", v) 2 C/3, In each vErepju]
case, we will find desired y/ E rep(u) and connected to w.
15

---

Graph-Based Algorithms for Diverse Similarity Search
1. min p(p",)) C/3: In this case, there exists another point p' rep[u] with D(p", S D(p", + D', S vEreplu]
D(w,u)/a and p(p", ,/) < C/3. Because |BA(", C/2) ( p&)] < K', we have BB' C/6) \pa)l S
[Bplu", C/2) p&)l < k', so the addition of such p' satisfies that ALG \ pa Up' is (K', C/12)-diverse
2. min p(p",v) 2 C/3: In this case, according to Proposition A.10, we have rep[u] = { Fx/k C
vErep[u]
B(u, D(u, (2a)) all with diversity distance at least C/3 from each other. Therefore, for any P. E ALG \ pk there can't exist two 2j and 2y s.t. p(pe, 2z) < C/6 and p(p;; 2yr) < C/6. By a counting argument, we can find at least one 24 s.t. [2, C/6) O (ALG \p4) k'. Finally, we let p' = 2; where ALG \ Pke Up' is (K' (41.)/22)ddveer)
We have proved that the p' we found satisfies the (K', C/122) criteria. Now we will bound its distance upper bound.
D 9) s D(p", D(y', - D(p" 9) + D(p', u) + D(p",
s D(p", ,4) D(w, (2a) + u2(a)
(Line 9 in Algorithm 3)
I D(p", ,4) + D(w, u) aa/a
I D(p", ,4) +
(Because u is ordered earlier than p²)
s D(r",0) .4) + D(w, g) a + ///a S D(pk, 0)/a + + (1 1/aa
Proof of Theorem A.5. Regarding the running time, the total number of edges connected from any point in ALG is bounded by [0] O((k)/K)(aa)
log A). In each step, the algorithm first sorts all these edges and then checks whether each of them can be added to the new ALG set. The total time spent per step is O(k]U + |0| log (U]). Usually, we assume log (U and we can have the overall time complexity to be O ((K3) (k/))))()) (8a) log A) per step.
k >>>>>
To analyze the approximation ratio, at time step 4, we use ALG = [pi,-.. ...... p&} to denote the current unordered solution. We denote ALG; = max D(p..g) q). According to Algorithm 4 and Lemma 1,, if p3 is updated at time step t, we have sE[k
D(p g) < D(p .9//a (1 + 1/a). By an induction argument, if a point is updated by t times at the end of time step T, we have Dip 9) < Dipl.9)
+ a+ع OPT.
a²
D(pi.g) We now prove that ALG. < max T7
a+ OPT Let i [k] be the index achieving the maximal distance upper
bound. For the sake of contradiction, if ALGT times. By counting argument, there exists another index which was updated for at least T/k: times. However, at the time f when D was already updated for T/k times, D(p) S
D( /= + at OPT this means that pf was updated for at most T/k 1
a-1 I
D(p),4) /= + a @+1 < ALG. s ALG so the algorithm wouldn't 't have chosen P to optimize cause it couldn't 't have had the maximal distance at that time, leading to a contradiction. Therefore, we prove that ALG. < max
D(r:.a) 27 + OPT
Now we consider the following three cases depending on the value of the maximal D(pl,)) g). The case analysis here is similar to the proof in Theorem 3.4 from (Indyk& & Xu, 2023).
Case 1: D(p.: g) > 2azz Let PK be the point having the maximal distance from q in an optimal solution OPT. We know that for any p.. we have D(p 4) Z D(pl. q) - D(p.. Z D(p 4) - Dman 2 D(p 4)/2. Therefore, the approximation ratio after T optimization steps is upper bounded by Dipi.9]
ALG. S D(pt + g+1 < 2 + a+1
Dipi
a- A
simple calculation shows that we can get (o+1 + e) approximate solution in O loga 2) steps.
Case 2: D(p. g) s 2Dmaz and OPTr >
e 1 D Dmin- To satisfy D(p J3te
attOPT < (at) + <)oP,, we need + a-
1(++1)
p) < <0PT.. Applying the lower bound OPT 2 3(a+1) 077E
2)+ a-1 Dmins we can get that T 2 & log. (a-1)e suffices.
Case 3: D(vl.g) 2Dmaz and OPT, 10+41 Dmin- In this case, we must have i = because otherwise
D(pi.pi) pi) < 2D(pi: g) < Dmmn. violaaiig the definition of Dmin- Suppose = 1 and the problem degenerates to the standard nearest neighbor search problem. After T optimization steps, pf is still not the exact nearest neighbor, we have
16

---

Graph-Based Algorithms for Diverse Similarity Search
D(p 9) Div pii OPT1 2 Puin,
Applying the upper bound of D(v 9) and OPT1, have Puin S D(ff 5 a Dmi This can happen only if T S log, g
D(gfa0) + a+1 OPT1 v a-1
D(rf
A.4. Analysis for the Dual Diverse NN Algorithm
In this section we analyze Algorithm 5.
Algorithm 5 Search algorithm for dual diverse NN
1: Input: A graph G = (V, F)) with (p) denoting the out edges of p; query q; distance bound Rt distance approxima-
tion error e.
2: Output: A set of l points ALG.
3: Use binary search to find maximal such that the initialization step proved Lemma A.7 outputs (K', diveree
set ALG (P1, (P.,
4: C'
5: while max ((p,g) PEALG
(at) + e) R do
6: C+ C+1/2
7:
i 1100 k loga A do
8:
U + U (Nout (p) U) and sort U' based on their distance from g
PEALG
9:
ALG f the closest k points in ALG for each point E U in order do
10:
11:
if' ALG u is (K,C/ C/11)-1122000 (C12)-diverse then
12:
ALG + ALG U u
13:
Break
14:
end
15:
end for
16:
end for
17:
end while
18:
Return ALG
Proof of Theorem A.6. After applying the binary search to the initialization algorithm in Lemma A.7, we get initial (k', -'-diverre solution and we know there doesn't It exist (k', -dvvere solution. Therefore, set T 4C' to be the upper bound on the maximal diversity we can achieve.
Then our Algorithm 5 is basically adding a binary search to Algorithm 4. Invoking the analysis from Theorem A.5, there exists a (k', C'v-iierse solution OPT = {pi,..., pp.} with OPT < R, we can find a (k', Ci12)-d solution ALG = {pI...., } with ALG, < (=# +) in O(k log, )) steps where each step takes Ō((}²) (a((3//))((a))) log A) time. As a result, each time when the algorithm enters the while loop on Line 5 in Algorithm 5, we know that there doesn't exist a (k', Ci-diverse solution with maximal distance smaller than Rt. When exit the while loop, the current C value is at least 1/2 of the optimal C' value, and the current ALG solution we get is at least (k', -iiversee
B. Algorithm Implementation
To conduct our experiments, we provide the heuristic algorithm that we designed for the k-ccoloruul nearest neighbor problem, based on the provable algorithms provided in the main paper. The provable indexing algorithm (3) has runtime which is quadratic in the size of the data set and is slow in practice. This situation mimics the original DiskANN algorithm (Jayaram Subramanya et al., 2019), where the "slow preprocessing" algorithm has provable guarantees (Indyk & Xu, 2023) but quadratic running time, and was replaced by heuristic "fast preprocessing" algorithm used in the actual implementation (Jayaram Subramanya et al., 2023). Here, Algorithm 9 offers a fast method tailored for the colooful case, using several heuristics to improve the runtime. In the following section, we present the pseudocode for the procedures: search, index build, and the pruning procedure required for the index build.
17

---

Graph-Based Algorithms for Diverse Similarity Search
Diverse Search. Our diverse search procedure, greedy graph-based local search method. In our search method, in each step, we maintain list of best and diverse nodes, ensuring that at most k' points selected in the list per color. In each iteration of our search algorithm, we choose the best unexplored node and examine its out neighbors. From the union of our current list and the out neighbors, we select the best diverse set of nodes while satisfying the k' k'cooloful diversity constriint-meaning no color can have more than k' points the updated list. To identify the optimal diverse set from the union, we use priority queue designed to accommodate the diversity constraint. Below, we present the pseudocode for this diverse priority queue.
Algorithm 6 Insert (p. d, c) into DiversePriorityQuen (Q, L, k)
Input: Current queue Q, tuple (p, d, of (point, distance, color) for new insertion, maximum size L of the queue, maximum size k' per color.
2: Output: Updated queue Q after inserting (p, d, c) which maintains the best set of at most I. points and at most k' points of each color.
3: Let count(c) < number of elements in Q with the color c.
4: Let maxDist(c) < maximum distance an element in Q with color c.
5: if cc) < k or d < maxDist(c) then
6: Insert (p, d into Q
7: if (c)un(c)= k' then
8: Remove the element with the maximum distance in Q having color
9: end if
10: end if
11:
if [QQ > then
12: Remove the element with the maximum distance in Q.
end if
Building on the previous explanation of the diverse priority queue, we outline the description of our diverse search procedure as follows.
Algorithm 7 DiverseSearcchGsssg.....
Input: directed graph G, start node s, query q, max per color parameter i', search list size L.
2: Output: A set of k points such that there are most k' points from any color.
3: Initialize DiversePriorits Queue f. <- {(s, D(s, 2), col(s)) with color parameter k' and size parameter T.,
4: Initialize set of expanded nodes V 0
5: while L \ V + ( do
6: Let pr + argmin D(p,0 q)
PELAV
7: V- V- {p}}
8: Insert [(p, D(p. 4), col(p)) p E Now((p") to L
9:
end while
10: Return [top & NNs from L; V]
Diverse Prune. A key subroutine in our index- building algorithm is the prune procedure. Given a node p and set of potential outgoing edges V, the standard prune procedure removes an edge to a vertex if there exists vertex such that an edge p - u exists and the condition D(u, w) < Dip.") is satisfied. Intuitively, this means that to reach w, we would first reach u. thus making multiplicative progress and eliminating the need for the edge p + w, which contributes the sparsity of the graph.
However, to account for diversity, the outgoing edges from the node must also be diverse and enable access multiple colors. To address this requirement, we modify the standard prune procedure to incorporate the diversity constraint. The details of our revised algorithm are provided next.
Diverse Index. Our indexing algorithm follows the same approach as the DiskANN "fast preprocessing" heuristic implementation (Jayaram Subramanya et al., 2023), but we replace the search and prune procedures in their implementation
18

---

Graph-Based Algorithms for Diverse Similarity Search
Algorithm 8 DiversePrune(p, v. R.m.
1: Input: point p, V. prune parameter a, degree parameter R, and diversity parameter
2: Output: subset V
cardinality at most R to which edges are added. 3: Sort all points u E V based on their distances from and add them to list C in that order.
4: Initialize sets blockers[u] <- 0 for each E V.
5: while is not empty do
6: u < argmin ((u,)) p)
NEC
7: V + U-V and L + L }
8:
if IV R then
9:
break end if
11:
for each point u E L do
12:
if w), S D(p w// then
13:
blockers w] t blockers [n] U {eol(u))
blockers[w]] m or col(u) col(w) then L L {w}
15:
16:
end if
17:
end if
18:
end for
end while
20:
Return V"
with our diverse search and diverse prune procedures. The details of our index-building procedure provided below.
Algorithm 9 DiverscIndex(P.co a, L, R, m)
1: Input: A set of points P (PI...... ). prune parameter at, search list size L, degree parameter R, and diversity parameter m.
2: Output: A directed graph G over P with out-degree most
Let denote the estimated medoid of
4: Initialize G with start node s.
5: for each E P do
6: Let [C; V] t DiverseSearch (G, Pi, K L/m, L)
7: Let V DiversePrune (p,, V. m).
8: Add node p, to and set (p.(p.) = V (out-going edges from p; V*).
9:
for Noue do
10:
Update (p)(p) <- -No((p) U [p.}. if [No((p) Ri then
11:
Run DiversePrunc(p. Non(p), ax R. m) to update out-neighbors p.
13: end if
14:
end for
15:
end for
C. Additional Plots
In this section we include the plots that were removed from the main body due to the space constraint.
C.1. Remaining Plots from Section 4.2
Here include the results plots for the two datasets SIFT-Skewed and SIFT-Balanced with N and k' 10 in Figures 5 and 6.
C.2. Plots from Parameter Ablation Section 4.3
Here we include the plots for Recall versus Latency, for various diversity parameter
D. DiskANN Overview
In this section we give an overview of the DiskANN procedures. For the full description the reader is referred to the original paper (Jayaram Subramanya et al., 2019).
19

---

Graph-Based Algorithms for Diverse Similarity Search
SIFT Dataset, Max Per Color
SIFT-Balanced Dataset, Max Per Color
100
100
90
80
80
R 100
70-
1ecall@1100
70-
60
50
50
40
Diverse Build Diverse Search
Diverse Build Diverse Search
10
30
Standard Build Diverse Search
Standard Build Diverse Search
Standard Build + Post-Pracessing
Standard Build Post-Processing
20
10 Miaa I atenry (ms)
14
16
Mean antency (ms)
Figure 5: Recall vs Latency for SIFT-Skewed (left) and SIFT-Balanced (right) datasets with k' 1.
SIFT Dataset, Max Per Color 10
SIFT-Balanced Dataset, Max Per Color = 10
100
100
90
95
R0
90
Recaili:110
70-
85
60
80
50
Diverse Build
40
Standard Diverse Search
Standard Build Diverse
30
Standard Build Post-Processing
70
Standard Build Post-Processing
2
3
2
10 12
Mean Latency (ms)
Mean Latency (ms)
Figure Recall vs Latency for SIFT-Skewed (left) and SIFT-Balanced (right) datasets with kv' 10.
The DiskANN data structure utilizes directed graph with vertices V corresponding to a set of points Once the graph constructed, the search procedure begins from specific vertex s to answer given query q. In the following, we provide description of the search and insertion process.
The search procedure (Algorithm 11), GreedySearch(s, (s. q, L), takes the following parameters: the starting vertex the query point q, and the queue size L. It executes a best-first search using a queue of bounded length L, continuing until the 7. vertices v with the smallest values D(v, q) seen so far are all scanned. Upon completion, it returns a list of vertices ordered by increasing distance from g, where the first vertex (or the first & vertices) are answers for the query. Note that the procedure will always run for at least L steps, as long as the graph is connected. The total running time of the procedure bounded by the number of steps multiplied by the out-degree bound of the graph G.
The construction of the graph G (V, E) is carried out through repeated calls to procedure named RobusttPunine (Algorithm 10). Given a vertex v, a set of vertices U (to be defined later), and parameters a >> 1 and R, the procedure Robust U, a, R) operates as follows. First, the set U is sorted in ascending order of distance to The algorithm then iterates through this sorted list. Upon processing a new vertex u, it removes all other vertices w from for which D(u, w) a < Dvv w). Finally, the vertex is connected to all remaining vertices in that have not been removed.
The starting point of the DiskANN data structure construction algorithm is the following simple procedure: for each vertex v. execute Robust Pruning(e (v, U, a, R) with U V and R In other words, robust pruning is performed every vertex in the graph. We call this approach slow preprocessing (Algorithm 13), as naive implementation incurs a time complexity of (n²3). Despite the high construction cost, (Indyk & Xu, 2023) demonstrate that this method reliably produces a graph whose degree grows only logarithmically with the graph's 's aspect ratio (under the assumption of constant doubling dimension), while ensuring that the greedy search procedure executes in polylogarithmic time.
Since the slow-preprooe wwwpprocessingalggrrittt is too slow in practice, the authors of (Jayaram Subramanya et al., 2019) propose a
20

---

Graph-Based Algorithms for Diverse Similarity Search
SIFT Dataset, Max Per Color 10
SIFT Dataset, Max Per Color
100
100
98
96
R
94
10c
92
88
m= 10
m=10
86
--- m-2
- m=2
m=1
mm1
Mean intency (ms)
Mraa atenry (ms)
Figure 7: Recall vs Latency for SIFT-Skewed dataset with k'' 10 (left) and k' (right) by varying the diversity parameter during index construction. Higher m implies more diversity.
faster heuristic method construct the graph G, which we call fast preprocessing method (Algorithm 12). Initially, the graph G is set random R-regular graph. Then, the construction of the graph G (V, F.) proceeds incrementally. The algorithm makes two passes over the point set in a random order. For each vertex encountered, it computes candidate set U = GreedySearch Lo, L) (starting from some vertex 8), and applies the pruning procedure on U rather than the entire vertex set V, i.e., it executes
U, a, RR.. Once pruning is complete, the algorithm inserts edges (v. u) and (u, v) for all u E U retained by the pruning step. If the degree of any vertex u E U exceeds the threshold R, its outgoing neighbors are also pruned via Robust Pruning(ww (u, (w), ar R). This heuristic method implemented and empirically evaluated in (Jayaram Subramanya et al., 2019).
Algorithm 10 RobustPruning(,.U U,,
1: Input Vertex candidate neighbor set U, pruning parameter a, degree limit R(default R is n if not given)
2: Result Update (i). the set of out-neigh of
3: U <- UNNt (i)
4: (one(i) + Ø
5: while U # Ø and (N)u < R do
6: v +- argminn,eu (1)
7: Nont < (ou Uv
8: U+U
9:
E D(z,, aa >>>>>0 D(2,,
10: end while
21

---

Graph-Based Algorithms for Diverse Similarity Search
Algorithm 11 GreedySearch(s. q, L)
1: Input Graph = (V, F)), seed 8, query point queue length limit I.
2: Output visited vertex list
3: A -- {s}
4: U V-@ Ø
5: while A do
6:
e argini g)
7:
A AU (v)
8:
U UU
9:
|A| > then
4 -op I closest vertices to y in
end if
12: end while
13: sort U in increasing distance from
14:
return U
Algorithm 12 DiskANN indexing algorithm (with fast preprocessing)
Input Point set P {.1 f.. J. degree limit R, queue length
2: Output A proximity graph G (V, E) where V = {1.... associated with point sets P.
3: G' < randomly sample R-regular graph vertex set V {1.m}
4: +- vertex for the point closest to the centroid of P
5: for k to do
6: a f- a random permutation of [1...n]
7: for i = to n do
8:
GreedySSerch(ss. (())) L)
9: Robust Pruning( a (i), U,a; R)
for vertex in Nout (a do [jue(j) & Nout (j) U aii) if [ouu(j)) > R then RobustPruningle Woue(j), a, R) 14: end
10:
11:
12:
13:
end for
end for
17: end for
Algorithm 13 DiskANN indexing algorithm (with slow preprocessing)
1: Input Vertex set {xI...... parameters: degree limit R
2: Output A proximity graph G = (V, E) where V = {L.m) are associated with point sets
3: t- vertex for the point closest the centroid of P
4: for 1 to n do
5: (i) < RobustPruninggh V,a,R R)
6: end for
22


Reviews:
[{"review_id": "xRJuUCzyJ4", "reviewer": "Reviewer_JqK5", "summary": "This paper addresses an important problem of graph-based nearest neighbor search (NNS) with diversity constraints. The new algorithm is proposed that is supported by theoretical analysis and also shows promising experimental results.\n\n## update after rebuttal\n\nI appreciate the authors' rebuttal and will keep my original score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback!\n\nResponse for W1: Thank you for the suggestions.  We will include preliminaries on the DiskANN algorithm in the appendix. We have included intuition on the new algorithms, but for completeness we will add informal descriptions of them too. We will also include a conclusion to the paper\n\nResponse for W2: We note that, to obtain theoretical guarantees, it suffices to know an “upper bound” on the value of k. (It is easy to see that building a graph on a larger value of k works for searching on smaller values of k. We are happy to include this remark in the paper.)\nOn the practical side, we use the tunable parameter ‘m’ which determines the number of colorful neighbors a candidate needs to have (defined in Section 4, line 325). Empirically,  we find that m can be set much smaller than k while retaining good results. In fact, in our experiments, we studied the performance of the algorithm even with m=1, i.e., where the graph construction method is the same as in the vanilla DiskANN but the search retrieves k>1 diverse candidates. Please see Figure 7 for this ablation study\nWe also want to emphasize that in the worst case, the index must account for the number of retrieved elements (k) in the colorful nearest neighbor (NN) problem. Consider an extreme scenario where we color a dataset using $k^*$ colors, $k^*-1$ of which are uniformly and evenly assigned across the dataset, and the last color is randomly assigned to only one point. For the colorful NN query with $k \\leq k^*-1$, we can ignore the last color, and a diverse search applied to the standard index should work. However, for $k = k^*$, the data structure needs to find a set of $k−1$ close points, plus the unique point with the $k$-th color. Without appropriate preprocessing, identifying a point with a unique color in the data set can take linear time. Therefore, the index-building algorithm should account for this and add more edges toward the point with the unique color. This justifies the need of knowing the value of $k$ during the preprocessing.\n\nResponse for W3: Please note that diverse-build+diverse-search is never outperformed by the baseline except in a tiny fraction of cases, and that too only by a small amount. Moreover, this occurs only in the very high latency regimes. A possible explanation for when and why this occurs could be the following: in datasets where there is more balance in the colors, the naive search itself organically retrieves diverse items which makes it easier for the baseline algorithm without the overheads of our slightly expensive diverse priority queue data structure. In a majority of cases (including on the real-world dataset), our approach is significantly superior to the baseline. Finally, real-world use-cases often deal with the lower latency regimes as long as the desired recall is achieved.\n\nResponse for Q1: Please see Definition 2.3 for $OPT_k$. We will add a reference to the definition in line 195\n\nResponse for Q2: The number of categories can be very large. In our seller data set, this number is roughly 2500, and in the Amazon Automotive dataset, this number is roughly 85000. Therefore, in practice, it can be quite inefficient to enumerate the prepared data structure for each color.\n\nResponse for Q3: In the Standard DiskANN algorithm, there is one search time parameter, L, which is the size of the priority queue the algorithm maintains till the search converges. Indeed, upon convergence, the algorithm knows the local optimal set of L potential candidates. We merely set ‘r = L’, and select the most diverse subset of these L candidates as a post-processing step. Therefore, in this baseline, we can think of r = L and sweep over the values of L as is usually done. There is an overloaded priority queue size parameter L during index construction, which we fix to be 200, which is within the range of commonly chosen values (typically around 2 to 3 times the graph degree). We apologize for this notational mistake and can disambiguate to Ls and Lb to denote search-time vs build-time parameters.\n\nResponse for Q4: We have suggested possible explanations for the reason why the baseline is marginally outperforming our approach. As for heuristics to improve, if there are scenarios where the baseline is significantly superior, one could then potentially have a pre-determined cut-off for the list-size ‘L’ parameter at search time, such that we implement our diverse search + diverse build algorithm for values of L below the cut-off, and we perform a post-processing approach on the diverse index built for values of L above the cut-off, which we have empirically validated to be superior to the baseline algorithm reported in the paper. As for the last question of whether Figure 7 holds for larger values too, we have tried much larger values as well, and it indeed holds that increasing ‘m’ yields better performance, but with diminishing returns as observed in the figure with values of m=2 and m=10.", "claims_and_evidence": "Claims made in the submission are supported by convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation are reasonable.", "theoretical_claims": "I’ve only partially checked the proofs and haven’t found any issues.", "experimental_designs_or_analyses": "I haven’t found any major problems with experimental design.", "relation_to_broader_scientific_literature": "The paper addresses an important problem in graph-based NNS that, to the best of my knowledge, has not been previously addressed.", "essential_references_not_discussed": "There are other papers on graph-based NNS with theoretical analysis that can be mentioned for completeness, e.g., (Laarhoven, 2018; Fu et al., 2019; Prokhorenkova & Shekhovtsov, 2020; Lu et al., 2024; Diwan et al., 2024).", "other_strengths_and_weaknesses": "The paper addresses an important problem in graph-based NNS. Importantly, it theoretically analyzes graphs constructed with neighbor pruning, which is known to be critical for effective graph-based NNS.\n\n\nThe weaknesses of the paper are the following:\n1. Some presentation issues. For example, the paper is significantly based on the DiskANN algorithm, but the algorithm is not described which makes it more difficult to follow the paper. Informal descriptions of Algorithms 1 and 2 (in addition to the pseudocode) would also be helpful. There is no conclusion section in the paper.\n2. Algorithm limitation: one disadvantage of the proposed algorithm is that one needs to know the number of retrieved elements ($k$) before constructing the graph.\n3. Also, in some cases the simplest baseline outperforms other approaches (see, e.g., Figures 5 and 6).", "other_comments_or_suggestions": "L83 (left): I suggest using “best-first search” instead of “greedy search” since usually several best candidates are maintained to reduce the probability of getting stuck in a local optimum.\n\n$\\alpha$ is not defined before first mentioned in line 66.\n\nSome typos:\n- There are multiple uses of \\citep instead of \\citet.\n- L128 (left): footnotes are typically placed after punctuation marks.\n- L121 (right): “note that for” -> “note that”\n- L203 (left): “let’s” -> “let us”\n- L414 (left): “Figures 5, and 6” ->  “Figures 5 and 6”\n- L459 (left): typo in the url.", "questions_for_authors": "Q1. Line 195 (right): what is OPT_k?\n\n\nQ2. Can there be other simple baselines, e.g., having separate indices for some categories?\n\n\nQ3. In Standard DiskANN Build + Post-Processing, how is $r$ chosen? As I understand, both $r$ and $L$ affect the time-accuracy trade-off.\n\n\nQ4. In some cases, the simplest baseline outperforms other approaches (see, e.g., Figures 5 and 6). What can be the reason for that? Can some heuristics be used to improve the performance of the proposed approach in such scenarios?\nQ5. From Figure 7 it seems that higher values of diversity parameters are better.  Does this hold for larger values too?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SJckvJ5wkK", "reviewer": "Reviewer_qrKi", "summary": "In this paper, the authors present provably efficient algorithms for approximate nearest neighbor search with diversity constraints. They propose several problem formulations, such as Colorful NN and k'-Colorful NN, and further generalize them into more general problems. To solve these problems, the authors propose related indexing and search algorithms, providing a theoretical analysis of query results under the assumption of bounded doubling dimension. In experiments, they demonstrate that the proposed algorithm outperforms straightforward vector search followed by attribute filtering.\n\n---\n\n## Update After Rebuttal\n\nThe authors' rebuttal and the follow-up discussion addressed my questions. I will raise my score from 2 to 3.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback!\n\n**Response to W1:** Since we cite HNSW, NGT and DiskANN earlier in the introduction, we did not want to repeat the discussion later.. However, given the feedback, we will expand the discussion and provide a comprehensive overview of graph-based NN algorithms.\n\n**Response to W2:** Diversity-based retrieval has found many applications since the influential paper of (Carbonell & Goldstein, 1998). To the best of our knowledge, the predominant algorithmic approach to this problem relied on re-ranking/filtering as proposed in that paper.\n \nAs mentioned in our paper, Google emphasized the importance of “diversity” w.r.t intent during search to capture multiple intents. E.g., searching for “transformers” without other context should ideally return results related to the movie, the electrical engineering concept and the ML concept. We can capture this in our framework by using some classification algorithm to assign a color to each vector based on its underlying “intent”.  \n\nSimilarly, there is a recent body of literature which highlights the importance of diverse retrievals in Retrieval Augmented Generation (RAG) systems. For example, the paper https://arxiv.org/pdf/2409.18110 argues that retrievals need to be diverse w.r.t perspective to excel in RAG queries. Similarly, the work https://arxiv.org/pdf/2502.11228v1 also argues for diverse retrieval using Vendi scores. Conceptually speaking, both these works seek to ensure diversity during retrieval, which is exactly what our work is targeting, albeit with slightly different modeling. We therefore believe that our work, which studies the problem of efficient diverse retrievals, will prove to be important in furthering this line of inquiry.\n\nRegarding the specific formulation of colorful nearest neighbor, here are two specific real-world applications:\n1. Seller diversity, which we include in the paper (please refer to e.g. line 295-right for the description). \n2. Typically in RAG systems, documents are divided into chunks/passages and each passage is embedded as a vector. Therefore each vector in the data set is associated with a document (and has a docID which we see as a color). It has been noted in practice that when we retrieve top k vectors to the query, many vectors retrieved correspond to passages from the same document, making them redundant as the eventual goal is to pass the complete documents corresponding to the docIDs retrieved through the vector search. In such scenarios, retrieving vectors corresponding to diverse set of docIDs, would help improve the efficiency and accuracy of the RAG pipelines.\n\n**Response to W3.1:** It is indeed possible that integrating faster methods for selecting promising nodes to expand [1,2] into DiskANN could improve its performance. Our strategy was instead to start from the existing DiskANN code and make as minimal changes to it as possible, in order to retain optimizations that have been already developed for that code. In addition to retaining the efficiency benefits of those optimizations, this also allows us to make “apples to apples” comparisons, as we use the same code base for both re-ranking and our algorithm. It is plausible, although not guaranteed, that further optimizations along the lines of [1] and [2] would equally benefit both our algorithm and the re-ranking baseline.\n \n**Response to W3.2:** Thank you for mentioning reference [3], and it is an important distinction to make  - it appears that their framework is indeed substantially different from ours. Most notably, attribute constraints in [3] are “local”: they specify a relation (or filter constraint) between the query q and a data point p which must be satisfied if p is to be included in the output. In contrast, diversity constraints are “global”, as they specify the overall constraint on the whole output  (e.g., at most k’ out of k points can have the same color). This difference is reflected in the indexing procedures. In particular, the approach of [3] augments the distance function so that close points with similar attributes are linked in the graph. In contrast, the main goal of our indexing procedure is to connect each node to close points with dissimilar attributes (colors). We will include this discussion in the paper.\n\n**Response to W3.3:** The number of categories can be very large. In our seller data set, this number is roughly 2500, and in the Amazon Automotive dataset, this number is roughly 85000. Therefore, in practice, it can be quite inefficient to enumerate the prepared data structure for each color.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes, but some related methods are missing, see my comments below.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "Yes, I believe the experimental results are reasonable.", "relation_to_broader_scientific_literature": "The contribution may be limited, as the problem studied in the paper is essentially ANNS with attribute constraints, which has been explored in previous research.", "essential_references_not_discussed": "W1. The literature survey is insufficient. In the related work section, the authors mention only a few LSH papers while omitting similarity-graph (a.k.a. proximity-graph) papers. Given that this paper focuses on graph-based search, a more detailed introduction to graph-based methods is important.", "other_strengths_and_weaknesses": "### **Strength**\n\nS1. This paper researched a new task in the category of ANNS with attribute constraints. \n\nS2. The theoretical analysis of proposed algorithms is thorough and sound.\n\n### **Weakness**\n\nW2. I wonder whether the problem setting is sufficiently useful. Given that there are almost no baseline methods specifically designed for this task, could the authors provide more evidence on the usefulness of the central problem, namely, colorful NN?\n\nW3. The baseline algorithms are insufficient. The reasons are summarized as follows.\n\n- W3.1. The authors claimed that the first stage of retrieving a large number of points closest to the query is time-consuming, and I agree with this. However, some research has shown significant improvements in the efficiency of original similarity graphs [1][2]. Since these methods are orthogonal to vanilla DiskANN, combining them with the original DiskANN build and diverse search might yield better performance than the diverse build + diverse search approach. \n\n- W3.2 The color is essentially an attribute, so this work falls into the category of ANNS with constrained attributes. Several research papers have addressed this problem, with a representative one being [3]. Could the authors compare diverse search with the approach in [3]? Although the attribute constraints are different, I wonder if the graph construction in [3] could be easily modified to solve the colourful NN tasks.  \n\n- W3.3 In the current design of baseline algorithms in the experiments, only the strategy of vector search followed by attribute filtering is considered. It is also recommended to consider the alternative strategy of attribute filtering followed by vector search. In fact, we can divide the original set into multiple subsets based on their colors, then use vector quantization to index points in small subsets and use similarity graphs to index points in large subsets. During the query phase, we can combine the search results from different subsets to obtain the final results. I wonder if the proposed method in this paper can outperform such a straightforward strategy.\n\n[1] Patrick H. Chen, Wei-Cheng Chang, Jyun-Yu Jiang, Hsiang-Fu Yu, Inderjit S. Dhillon, Cho-Jui Hsieh: FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search. WWW 2023.\n\n[2] Kejing Lu, Chuan Xiao, Yoshiharu Ishikawa: Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search. ICML 2024.\n\n[3] Mengzhao Wang, Lingwei Lv, Xiaoliang Xu, Yuxiang Wang, Qiang Yue, Jiongkang Ni. An Efficient and Robust Framework for Approximate Nearest Neighbor Search with Attribute Constraint. NeurIPS 2023.", "other_comments_or_suggestions": "I recommend that the authors add sufficient literature on similarity graphs. See W1.", "questions_for_authors": "Please answer the questions or provide your comments to address the concerns raised in W1-W3.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "grJiyWWVXJ", "reviewer": "Reviewer_iY1E", "summary": "This paper considers the nearest-neighbor search problem with diversity constraints. It builds on existing graph-based algorithms for similarity search and proposes a new indexing algorithm which can more efficiently answer queries with diversity constraints.\n\nThrough experimentation on several large datasets, the effectiveness of the new algorithm is demonstrated when compared with existing methods for diverse similarity search.\n\n## Update after Rebuttal\n\nI have nothing further to add following the rebuttal by the authors.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback!\n\n> W1: In my view, the experimental section could be more extensive by comparing against additional baseline methods for ANN and post-processing, such as HNSW.\n\n**Response:** It is indeed possible that using different graph-based methods could improve the performance. However, this could hold for both for the baseline re-ranking and for the diversity-aware algorithm - we believe that other graph-based algorithms like HNSW should be amenable to the modifications we applied to DiskANN. Our strategy was instead to start from the existing DiskANN code and make as minimal changes to it as possible, in order to retain optimizations that have been already developed for that code. This allows us to make “apples to apples” comparisons, as we use the same code base for both re-ranking and our algorithm. \n\n> W2: Finally, one possible downside of this approach is the need to build the index for a specific diversity requirement: that is, for returning k neighbors with at most k′ of the same color. The proposed algorithm could be even more general if a flexible index could support queries with varying diversity constraints.\n\n**Response:** We note that, to obtain theoretical guarantees, it suffices to know an “upper bound” on the value of k. (It is easy to see that building a graph on a larger value of k works for searching on smaller values of k. We are happy to include this remark in the paper.)\nOn the practical side, we use the tunable parameter ‘m’ which determines the number of colorful neighbors a candidate needs to have (defined in Section 4, line 325). Empirically,  we find that m can be set much smaller than k while retaining good results. In fact, in our experiments, we studied the performance of the algorithm even with m=1, i.e., where the graph construction method is the same as in the vanilla DiskANN but the search retrieves k>1 diverse candidates. Please see Figure 7 for this ablation study\n\nWe also want to emphasize that in the worst case, the index must account for the number of retrieved elements (k) in the colorful nearest neighbor (NN) problem. Consider an extreme scenario where we color a dataset using $k^*$ colors, $k^*-1$ of which are uniformly and evenly assigned across the dataset, and the last color is randomly assigned to only one point. For the colorful NN query with $k \\leq k^*-1$, we can ignore the last color, and a diverse search applied to the standard index should work. However, for $k = k^*$, the data structure needs to find a set of $k−1$ close points, plus the unique point with the $k$-th color. Without appropriate preprocessing, identifying a point with a unique color in the data set can take linear time. Therefore, the index-building algorithm should account for this and add more edges toward the point with the unique color. This justifies the need to know the value of $k$ during the preprocessing.\n\n> Q1: The index is built based on the values of k and  k′ and so they need to be known in advance. On the other hand, in the experimental section, you compare with using the 'diverse query' on the standard index. Is there some kind of intuitive interpolation between these cases, such a 'balanced index' which is effective at responding to non-diverse queries, and diverse queries whose parameters are not known in advance?\n\n**Response:** We believe that the ideal index should take into account how restrictive the diversity constraint is e.g. for the colorful case, the larger k is, the more restrictive the constraint is, so our index should keep more edges between different colors. Please see the intuitive analysis above. Our experiment shows that the diverse search algorithm also helps find more diverse answers even when applied to the standard index. In conclusion, both the diverse index and the diverse search help solve this problem.", "claims_and_evidence": "The claimed theoretical and empirical results are well backed up in the paper.", "methods_and_evaluation_criteria": "The experimental evaluation methodology seems reasonable. It may be interesting to also compare with other nearest-neighbor algorithms beyond DiskANN.", "theoretical_claims": "The paper proves a bound on the running time complexity of the query algorithm, and gives an approximation guarantee for the returned near-neighbors. The theoretical claims appear sound.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "Approximate nearest neighbour search is a hugely important and active area of research, into which this work fits naturally. The diverse ANNS problem is well motivated in this paper, which puts it into the context of the literature.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "The paper addresses a natural problem, and proposes an effective algorithm.\n\nIn my view, the experimental section could be more extensive by comparing against additional baseline methods for ANN and post-processing, such as HNSW.\n\nFinally, one possible downside of this approach is the need to build the index for a specific diversity requirement: that is, for returning $k$ neighbors with at most $k'$ of the same color. The proposed algorithm could be even more general if a flexible index could support queries with varying diversity constraints.", "other_comments_or_suggestions": "None.", "questions_for_authors": "1. The index is built based on the values of $k$ and $k'$, and so they need to be known in advance. On the other hand, in the experimental section, you compare with using the 'diverse query' on the standard index. Is there some kind of intuitive interpolation between these cases, such a 'balanced index' which is effective at responding to non-diverse queries, and diverse queries whose parameters are not known in advance?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hfhH4hGiZY", "reviewer": "Reviewer_NUeQ", "summary": "This paper studies the problem of diversifying the results of approximate nearest search (ANNS) for vectors. It adapts the state-of-the-art proximity graph algorithm for ANNS and modifies both the graph construction and query processing algorithm to consider diversity. It also conducts theoretical analysis to show the query processing complexity of the proposed algorithms and extends the algorithms to general definitions of diversity. The empirical results show that the proposed algorithms significantly improves the performance compared with the original proximity graph algorithm.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback!\n\n**Response for W1/Q1:** Thanks for your suggestion! For the colorful NN definition, the current algorithm 2 always optimizes the furthest point, which only provides approximation guarantees on the maximal distance but not the total distance. For the total (average) distance, we have developed a modified search algorithm (not included in the paper)  that optimizes the k points together in a single step. For that algorithm we obtain a “uniform” guarantee $ALG_i\\le (\\frac{\\alpha+1}{\\alpha-1}+\\epsilon)OPT_i$ for all $ i<k$ where $ALG_i$ and $OPT_i$ are the distance from the i-th point in our solution ALG and the optimal solution OPT. Note that the point-wise guarantee implies a bound on the total distance. \n\n**Response for W2/Q2:** Thanks for proposing this idea! This setting fits in our (k’,C)-diverse NN formulation in Definition A.3, so our algorithm can handle this setting, at least from a theoretical perspective. However, our codebase is optimized for the colorful NN problem (see Appendix B) because of the concrete application we targeted. Performing experiments under the general diversity setting requires a separately optimized algorithm implementation tailored to that case, which is possible but needs significant work.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes. The theorems are correct to my understanding.", "experimental_designs_or_analyses": "Yes. The experiment is sound.", "relation_to_broader_scientific_literature": "This paper studies diversified ANNS and may benefit applications that require result diversification.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Thank for the interesting paper!\n\nStrength\n\n(1) Diversified ANNS is an important problem of practical significance.\n\n(2) The proposed algorithms make sense, i.e., by considering diversity when adding the edges and staring search from a diverse set.\n\n(3) Extensive theoretical analysis is conducted.\n\n(4) More general cases of diversified search are disused and extended. \n\nWeakness\n\n(1) The relation w.r.t. alternative result quality definitions is not discussed.\n\n(2) Some experiment results for general cases should be provided.", "other_comments_or_suggestions": "Following the weakness, I have two suggestions that may enhance the paper.\n\n(1) In this paper, the goal is to minimize S_k, i.e., the kth nearest neighbor. [1] requires to maximizes the total similarity score of the k results (or equivalently, minimize the total distances). What are the relations of the two results requirements? \n[1] Diversifying TopK Results\n\n(2) One interesting instance of the diversified search problem is that the diversity measure is also the distance itself. For example, when handling image embeddings without labels, we may want the returned results to differ by a distance threshold to impose semantic distinctiveness. Could you add an experiment for this instance with the proposed algorithms?", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes an efficient graph-based approach for nearest neighbor search. The reviewers appreciated that the paper addresses an important problem and that the proposed method is theoretically sound. Given the positive evaluations from the reviewers, I recommend acceptance.
Decision: Accept (poster)