Approximate Nearest Neighbor Search in ℓp

Huy L. NguyenarXiv 2013 · arXiv · OpenReview

Abstract: We present a new locality sensitive hashing (LSH) algorithm for $c$-approximate nearest neighbor search in $\ell_p$ with $1<p<2$. For a database of $n$ points in $\ell_p$, we achieve $O(dn^{\rho})$ query time and $O(dn+n^{1+\rho})$ space, where $\rho \le O((\ln c)^2/c^p)$. This improves upon the previous best upper bound $\rho\le 1/c$ by Datar et al. (SOCG 2004), and is close to the lower bound $\rho \ge 1/c^p$ by O'Donnell, Wu and Zhou (ITCS 2011). The proof is a simple generalization of the LSH scheme for $\ell_2$ by Andoni and Indyk (FOCS 2006).

Introduction

The Nearest Neighbor Search (NNS) problem is a cornerstone of computational geometry and data retrieval: given a database of $n$ points in a high-dimensional space, how can we efficiently identify the point closest to a new query point? In high dimensions, exact NNS often suffers from the "curse of dimensionality," where search algorithms become no more efficient than a linear scan of the entire database.

To circumvent this, researchers utilize Approximate Nearest Neighbor (ANN) search. In a $c$-approximate search, the algorithm returns a point whose distance from the query is at most $c$ times the distance to the true nearest neighbor. The standard framework for solving ANN is Locality Sensitive Hashing (LSH). The efficiency of an LSH algorithm is characterized by a parameter $\rho$, which determines the query time complexity $O(n^\rho)$ and space complexity $O(n^{1+\rho})$. For the $\ell_p$ norm where $1 < p < 2$, the long-standing upper bound for $\rho$ was $1/c$. However, theoretical lower bounds suggested a potential limit of $1/c^p$. This paper bridges that gap, providing a more efficient algorithm for large approximation factors $c$.

Methodology

The proposed algorithm generalizes the LSH framework originally developed for the $\ell_2$ norm (Euclidean distance) by Andoni and Indyk (2006). The approach consists of two primary stages:

1. Dimension Reduction via $p$-stable Distributions

The high-dimensional input points (dimension $d$) are projected into a lower-dimensional space (dimension $t$). This is achieved using $p$-stable distributions, which are mathematical tools that preserve the relative distances between points under the $\ell_p$ norm during the projection process. To ensure the integrity of this step, the paper introduces refined concentration bounds for $p$-stable variables, ensuring that the projection does not excessively distort distances.

2. Space Partitioning via Lattice of Balls

Once projected, the lower-dimensional space is partitioned using a lattice of balls. If two points fall within the same sphere in this lattice, they are assigned the same hash value and considered potential neighbors. The core innovation of this work lies in the rigorous analysis of how these balls overlap within $\ell_p$ space. By leveraging the geometric properties of uniform smoothness and uniform convexity, the author provides a tighter estimate of collision probabilities than was previously possible.

Theoretical Results

This work is purely theoretical, focusing on the mathematical proofs of algorithmic complexity. The primary contribution is the proof that $\rho = O((\ln c)^2 / c^p)$.

Complexity Summary:

  • Query Time: $O(dn^\rho)$
  • Space Requirements: $O(dn + n^{1+\rho})$
  • Performance Improvement: For $1 < p < 2$, this bound is a significant improvement over the previous $1/c$ standard. It moves the state-of-the-art much closer to the theoretical lower bound of $\rho \geq 1/c^p$ established by O’Donnell, Wu, and Zhou (2011).

Discussion and Future Work

The significance of this result lies in its "geometric generalization." It demonstrates that the sophisticated lattice-based hashing techniques used for Euclidean space are applicable to a broader range of $\ell_p$ norms by utilizing abstract geometric properties.

While the result is a major step forward, a logarithmic factor $(\ln c)^2$ remains in the bound, leaving a small gap before reaching the absolute theoretical lower bound. Furthermore, the reliance on uniform smoothness and convexity suggests that this LSH scheme could potentially be adapted to even more general classes of norms beyond the $\ell_p$ family. Finally, while the algorithm is described as "simple," future empirical studies are needed to evaluate the constant factors and practical performance in real-world database applications.

Summary updated

Abstract

We present a new locality sensitive hashing (LSH) algorithm for $c$-approximate nearest neighbor search in $\ell_p$ with $1<p<2$. For a database of $n$ points in $\ell_p$, we achieve $O(dn^{\rho})$ query time and $O(dn+n^{1+\rho})$ space, where $\rho \le O((\ln c)^2/c^p)$. This improves upon the previous best upper bound $\rho\le 1/c$ by Datar et al. (SOCG 2004), and is close to the lower bound $\rho \ge 1/c^p$ by O'Donnell, Wu and Zhou (ITCS 2011). The proof is a simple generalization of the LSH scheme for $\ell_2$ by Andoni and Indyk (FOCS 2006).
BibTeX
@misc{nguyen2013approximate,
  author = {Huy L. Nguyen},
  title = {{Approximate Nearest Neighbor Search in ℓp}},
  year = {2013},
  eprint = {1306.3601},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1306.3601},
}
Figure