Exact and/or Fast Nearest Neighbors

Matthew Francis-Landau, Benjamin Van DurmearXiv 2019 · OpenReview

TL;DR

This paper introduces Certified Cosine (C2), a novel method for finding nearest neighbors in high-dimensional data. C2 offers a way to guarantee the correctness of the nearest neighbor result, potentially avoiding slow exhaustive searches, and outperforms existing exact methods on high-dimensional datasets.

What Problem Does This Paper Address?

Finding the nearest neighbor to a query point in a large dataset is a fundamental problem in many fields, including information retrieval, image search, and language modeling. The challenge lies in the trade-off between speed and accuracy. Traditional "exact" methods, like KD-trees or VP-trees, guarantee finding the true nearest neighbor but become prohibitively slow in high-dimensional spaces (often referred to as the "curse of dimensionality"). On the other hand, "approximate" nearest neighbor (ANN) methods are much faster but only provide probabilistic guarantees, meaning they might miss the true nearest neighbor. This leaves a gap for applications that require guaranteed correctness without the extreme computational cost of exhaustive search in high dimensions.

Methods

The core innovation of Certified Cosine (C2) is its ability to generate a "certificate" that proves the correctness of the found nearest neighbor. C2 builds upon existing K-Nearest Neighbor Graph (KNNG) based ANN techniques.

Here's a breakdown of the key methods:

  • KNNG as a Foundation: C2 uses an exact KNNG as its underlying search structure. This graph connects each data point to its k nearest neighbors.
  • Certificates: The central idea is to define a region of "unchecked" space where a better neighbor could exist. If this region can be proven to be empty, then the current best guess is guaranteed to be the true nearest neighbor.
  • Tracking the Unchecked Region (St): C2 maintains a set St representing the space that still needs to be checked. The goal is to shrink St until it's empty.
  • Convex Relaxation: To efficiently check if St is empty, C2 employs convex relaxation techniques. This involves transforming the non-convex problem into a series of convex feasibility problems.
  • Projection Operator Relaxation: This method uses alternating projections to find a point within the intersection of convex sets that define the relaxed St.
  • Linear Programming Relaxation: This approach relaxes the problem further by removing the unit norm constraint and using linear programming to find a potential counterexample.
  • Finding Counterexamples: If St is not empty, C2 uses the results from the convex relaxations to find a potential counterexample point. This point can then be used to refine the search and target unexplored regions, effectively guiding the search towards areas where a certificate might be more easily constructed.
  • Lookup Procedure: C2 integrates the certificate construction process directly into its search procedure. It uses a priority queue to explore promising neighbors and updates constraints as regions are explored. The search continues until a certificate is successfully constructed or a predefined budget is met.

Datasets

The paper evaluates C2 on the following datasets:

  • GloVe: A dataset of word embeddings, 200-dimensional, with 1,183,514 entries.
  • NYTimes: A dataset of document embeddings, 256-dimensional, with 290,000 entries.

These datasets are standard benchmarks used in the ANN community.

Key Insights and Ideas

  • Bridging the Exact/Approximate Gap: The most significant insight is the development of a method that can provide guaranteed correctness in high dimensions without resorting to slow exhaustive searches. This is achieved by intelligently using certificates.
  • Certificates as a Proof: The concept of a certificate is powerful. Instead of just finding a "good enough" neighbor, C2 proves that the found neighbor is the nearest neighbor, which is crucial for many applications.
  • Leveraging Structure for Guarantees: C2 effectively exploits the structure of the cosine similarity metric and KNNGs to define and shrink the unchecked region, making the certification process tractable.
  • Convex Relaxation for Tractability: The use of convex relaxation techniques (alternating projections and linear programming) is key to making the complex geometric problem of checking St computationally feasible.
  • Guiding the Search with Counterexamples: Using potential counterexamples found during relaxation to guide the search is an elegant way to improve efficiency and avoid getting stuck in local optima.

Key Results

  • Performance on High-Dimensional Data: C2 significantly outperforms previous exact nearest neighbor methods on high-dimensional datasets.
  • Speedup: C2 achieves query runtimes comparable to state-of-the-art approximate nearest neighbor methods, especially when high recall is required.
  • Comparison to NGT: C2 is about 14% slower than NGT (a strong ANN method) at high recall (>99%), likely because NGT's heuristic stopping allows it to terminate earlier. However, C2 provides a guarantee that NGT does not.
  • Impact of Query Distribution: The performance of C2 is sensitive to the distribution of queries. For "lower entropy" queries (where the nearest neighbor is very close), C2's certification ability allows it to stop earlier and outperform other ANN methods.

Limitations and Future Work

  • Certificate Construction Not Always Feasible: The paper acknowledges that constructing a certificate is not always efficient or possible within a given budget. In such cases, C2 falls back to returning the best guess found so far, similar to ANN methods.
  • Future Work: The authors suggest adapting C2's certificate construction process to design better heuristics for ANN methods. This implies that the insights gained from C2 could inform the development of even more efficient approximate methods. They also note that their approach could be generalized to certify top-k nearest neighbors.

Summary updated

Abstract

Prior methods for retrieval of nearest neighbors in high dimensions are fast and approximate--providing probabilistic guarantees of returning the correct answer--or slow and exact performing an exhaustive search. We present Certified Cosine, a novel approach to nearest-neighbors which takes advantage of structure present in the cosine similarity distance metric to offer certificates. When a certificate is constructed, it guarantees that the nearest neighbor set is correct, possibly avoiding an exhaustive search. Certified Cosine's certificates work with high dimensional data and outperform previous exact nearest neighbor methods on these datasets.
BibTeX
@misc{francislandau2019exact,
  author = {Matthew Francis-Landau and Benjamin Van Durme},
  title = {{Exact and/or Fast Nearest Neighbors}},
  year = {2019},
  eprint = {1910.02478},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1910.02478},
}
Figure