Fast Nearest Neighbor Search for ${\mathbf{\ell }}_{𝒑}$ Metrics

The Nearest Neighbor Search (NNS) problem asks to design a data structure (also called a scheme) that preprocesses an $n$-point dataset $X$ lying in a metric space $ℳ$, so that given a query point $q\in ℳ$, one can quickly return a point of $X$ minimizing the distance to $q$ (or approximately minimizing it in the approximate version). The efficiency of such a data structure is evaluated primarily by the amount of space it uses and the time required to answer a query. The preprocessing time is a secondary measure and is usually comparable to the space usage. Because of its central role in areas such as machine learning, data analysis, and information retrieval, NNS has been the subject of extensive research, both practical and theoretical (see, e.g., the surveys [1, 6]).

It is well known that approximate NNS can be reduced to solving $\mathrm{polylog}(n)$ instances of the approximate near neighbor problem [18]. For this reason, we restrict attention to the latter.

We focus on the fast query-time regime, which is crucial for modern large-scale applications where datasets are massive and queries must be processed online, and is often modeled by query time $\mathrm{poly}(d\log n)$ when $ℳ$ is a $d$-dimensional normed space. We study the metric spaces ${\mathrm{\ell }}_p^d$, which refer to ${ℝ}^d$ with distances defined by the ${\mathrm{\ell }}_p$ norm, and we may omit the dimension $d$ when it is clear from the context. In ${\mathrm{\ell }}_p$ spaces, ANN in this regime is well understood for $1\le p\le 2$ [19, 25, 18] and for $p=\mathrm{\infty }$ [20, 4, 21]. For , the situation is less clear: there exists a handful of data structures, each suitable for a different range of $p$, as detailed in Table 1. We present a new scheme for ANN in ${\mathrm{\ell }}_p$, $p>2$, with fast query time, that offers an improved tradeoff between approximation and space, as follows.

Studying ANN in ${\mathrm{\ell }}_p$, $p>2$, is important both practically and theoretically. Real-world data and applications may motivate norms that emphasize outliers, e.g., for anomaly detection, or alter the presence of “hubs”, e.g., to affect classification; such data structures were indeed used for time-series classification [28], see [14] for additional references. From a theoretical perspective, the geometry of ${\mathrm{\ell }}_p$ spaces undermines existing algorithmic techniques and requires developing new ones. A key challenge is to bridge between $p=2$ and $p=\mathrm{\infty }$. In the fast query-time regime, this means interpolating between the classical $(O(1),r)$-ANN in ${\mathrm{\ell }}_2$ [18] and the $(O(\log \log d),r)$-ANN in ${\mathrm{\ell }}_{\mathrm{\infty }}$ [20], which both use only $\mathrm{poly}(dn)$ space. It is natural to conjecture that exhibits an interpolation between these two guarantees, and since ${\mathrm{\ell }}_{\mathrm{\infty }}^d$ is $O(1)$-equivalent to ${\mathrm{\ell }}_{\log d}^d$ by Hölder’s inequality, this interpolated data structure is conjectured to achieve $O(\log p)$ approximation using $\mathrm{poly}(nd)$ space. The first step towards this conjecture, in [2, 3], devised a reduction from ${\mathrm{\ell }}_p$ to ${\mathrm{\ell }}_{\mathrm{\infty }}$, and obtained a data structure with $O({\log }^{1/p}n\log \log d)$-approximation, which is mainly suited for large values of $p$. A nontrivial reduction, devised in [14], reduced ${\mathrm{\ell }}_p$ to ${\mathrm{\ell }}_2$ and obtains $2^{O(p)}$-approximation, which is a major improvement for small values of $p$, although it is doubly-exponentially worse than the conjecture. A more sophisticated reduction, that was devised recently in [23], achieves approximation $\mathrm{poly}(p)$, which is an exponential improvement. However, it goes through multiple intermediate ${\mathrm{\ell }}_t$ spaces () via a recursive argument that increases the space to $n^{O(\log p)}$, much higher than conjectured. Our Theorem 1.2 essentially completes the improvement of [23], by decreasing the space complexity back to the conjectured $\mathrm{poly}(dn)$, albeit slightly increasing the approximation to $p^{\log \log p}$. In particular, it resolves a question posed in [23], of whether the recursion can avoid this higher space complexity.

The proof of Theorem 1.2 is based on a simple yet powerful enhancement of the known NNS schemes from [14, 23], which utilizes classical results from [11, 12] about sparse covers. We provide an overview of the algorithms of [14, 23] in Section 3, along with an intuitive explanation of our approach at the beginning of Section 4.

Given a metric space $ℳ=(X,d_{ℳ})$, we denote by $B_{d_{ℳ}}(x,r)≔\{y\in X:d_{ℳ}(x,y)\le r\}$ the ball of radius $r>0$ centered at a point $x\in ℳ$.

For every $p,q\in [1,\mathrm{\infty })$, the Mazur map $M_{p,q}:{\mathrm{\ell }}_p^d\to {\mathrm{\ell }}_q^d$ is computed by taking, in each coordinate, the absolute value raised to power $p/q$, but keeping the original sign. Our algorithm crucially relies on the following property of this map.

In this section, we review the algorithms of [14] and [23] for ANN in ${\mathrm{\ell }}_p$, $p>2$. For the rest of the section, fix a dataset $X\subset {\mathrm{\ell }}_p^d$ with $|X|=n$ for some $p>2$.

In this section, we give the proof of Theorem 1.2. We first explain the intuition, and for simplicity we restrict this discussion to reducing the space requirement of [14]; reducing the space requirements of [23] is similar in spirit, although more technical.

Revisiting Section 3.1, the final solution $x_k$ is obtained by finding iteratively a sequence of intermediate solutions $x_0,x_1,\mathrm{\dots },x_{k-1}$. Each iteration makes progress by finding a point $x_i$ and restricting the search region to $B_{{\mathrm{\ell }}_p}(x_i,{\widehat{c}}_{i}r)$, which has bounded diameter, and thus applying a Mazur map on this region has distortion guarantees. It follows that querying the data structure $A_{x_i,{\widehat{c}}_i}$ (computed over $B_{{\mathrm{\ell }}_p}(x_i,{\widehat{c}}_{i}r)\cap X$) finds a point $x_{i+1}$ and we can restrict the search region even further, to diameter ${\widehat{c}}_{i+1}r$.

The preprocessing phase prepares for the possibility that each point $x\in X$ will serve (at query time) the ${\widehat{c}}_i$-approximate solution, i.e., the search region will be restricted to $B_{{\mathrm{\ell }}_p}(x,{\widehat{c}}_{i}r)$. To make progress and restrict the search region even further, a data structure $A_{x,{\widehat{c}}_i}$ is constructed for (the points in) this region. Our key idea in Theorem 1.2 is that, rather than preparing a separate data structure for each search region, the algorithm constructs one global collection of data structures that together cover all the possible search regions. For every ${\widehat{c}}_i$, the algorithm constructs a set of ANN data structures computed on a collection of subsets $𝒮\subseteq 2^X$, such that for every point $x\in X$ there is some $S\in 𝒮$ that contains the search region $B_{{\mathrm{\ell }}_p}(x,{\widehat{c}}_{i}r)\cap X$. In addition, every $S\in 𝒮$ has diameter at most $\beta {\widehat{c}}_{i}r$ for some $\beta >1$. We also want the total number of points in $𝒮$ (counting repetitions) to be small. The preprocessing algorithm simply stores for every $x\in X$ a reference to a set $S_x\in 𝒮$ with $B_{{\mathrm{\ell }}_p}(x,{\widehat{c}}_{i}r)\cap X\subseteq S_x$, and at query time, if $x$ serves as a ${\widehat{c}}_i$-approximate solution, the algorithm queries the ANN data structure constructed for $S_x$. Since $S_x$ has a diameter at most $\beta {\widehat{c}}_{i}r$, this will still cause the search region’s diameter to shrink in the next iteration (although by a slightly smaller factor). Since the total number of points in $𝒮$ is small, the total memory used by all the ANN data structures will be small too.

It remains to show that the preprocessing phase can indeed find efficiently a collection of subsets of $X$ with the above properties. Fortunately, this was shown to be possible in [11, 12], and has become a fundamental algorithmic tool with numerous applications in distributed computing, network design, routing, graph algorithms, and metric embeddings.

We are now ready to prove Theorem 1.2, largely following the proof structure of [23, Theorem 1.8].