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.

Lay Summary:

Nearest neighbor search (NNS) is a fundamental problem to model the search task. Its goal is to quickly find data points (like images, documents, or user profiles) that are most similar to a given query point, and is widely used in applications like search, recommendations, and machine learning. A known issue with traditional NNS is that the results it returns can be very redundant — the top matches might all be nearly identical. To fix this, most systems use a two-stage approach:In the first stage, the algorithm retrieves a large number (say, hundreds or thousands) of the nearest points to the query, while in the second stage, the algorithm post-processes that list to select a smaller, more diverse subset. While effective, this method can be inefficient because it processes many more points than it actually needs to return.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 existing efficient implementations. These are the first graph-based algorithms for nearest neighbor search with diversity constraints. The theoretical guarantees of our algorithm are qualitatively similar to the best known bounds for standard (non-diverse) graph-based algorithms. We further run experiments showing that the search time of our algorithms is substantially lower than that of using the standard two-stage approach.