Approximate Furthest Neighbor with Application to Annulus Query

Rasmus Pagh, Francesco Silvestri, Johan Sivertsen, Matthew Skala

Abstract

This paper addresses the challenge of finding "far" neighbors in high-dimensional spaces, a task crucial for diversity in recommender systems. We introduce a sublinear-time approach for the $c$-Approximate Furthest Neighbor ($c$-AFN) problem using random projections. Furthermore, we demonstrate how this technique can be integrated with Locality Sensitive Hashing (LSH) to solve annulus queries—identifying points within a specific distance range from a query. Empirical evaluations on synthetic and real-world datasets, including MovieLens 20M, validate the efficiency and accuracy of the proposed methods.

Introduction

In the domain of big data, Nearest Neighbor Search (NNS) is the standard for finding similar items. However, in many applications, particularly recommender systems, finding the absolute closest item is not always optimal. Recommending a nearly identical item to one a user already likes adds little value. Instead, many systems require items in an "annulus": a ring-shaped region that is close enough to be relevant but far enough away to provide diversity.

Finding the Furthest Neighbor (FN) is computationally more demanding than finding the nearest one due to the "curse of dimensionality," which often necessitates a full database scan. This paper tackles the $c$-Approximate Furthest Neighbor ($c$-AFN) problem: finding a point whose distance to the query is at least $1/c$ times the distance to the true furthest neighbor, where $c > 1$.

Proposed Algorithms

The core of the proposed approach relies on Random Projections. The underlying intuition is that if two points are far apart on a random 1D line, they are likely far apart in the original high-dimensional space. The paper introduces two primary data structures:

  1. Query-Dependent AFN (Algorithm 1): This method projects all data points onto several random 1D lines and stores them in sorted lists. At query time, it utilizes a priority queue to examine points that appear furthest across these projections. This improves upon previous work by removing a logarithmic factor in running time.
  2. Query-Independent AFN (Algorithm 2): This simpler variation identifies a fixed set of "extreme" points (outliers near the convex hull) during preprocessing. At query time, it only checks this small, fixed candidate set, which often contains the furthest neighbors for a wide variety of queries.

Annulus Query Integration

A key contribution of this work is the first sublinear-time solution for the approximate annulus query problem in Euclidean space. By combining the AFN technique with Locality Sensitive Hashing (LSH), the system can effectively filter for "near" points and then identify the furthest points within that subset to satisfy the annulus constraints.

The annulus query region defined by the area between two concentric balls.

As illustrated in the figure above, an annulus query seeks points $p$ that reside within an outer ball $B(q, rw)$ but outside an inner ball $B(q, r/w)$, effectively capturing items that are similar but not too similar to the query $q$.

Theoretical and Empirical Insights

The $\sqrt{2}$ Barrier

The authors establish a theoretical lower bound: achieving an approximation factor $c < \sqrt{2} \approx 1.41$ requires space that grows either exponentially with the dimension or linearly with the number of points. This explains the fundamental difficulty of the AFN problem.

Experimental Results

The algorithms were evaluated on synthetic datasets and real-world benchmarks like the MovieLens 20M dataset (treated as a sparse 138,493-dimensional space). Key findings include:

  • Efficiency: The query-dependent algorithm achieves a 0.72 success probability with $O(n^{1/c^2})$ query time, examining only a tiny fraction of the database.
  • Outlier Dominance: In real-world data like MovieLens, a few extreme items tend to be the furthest neighbors for almost any query. Consequently, the simpler Query-Independent method performed nearly as well as the complex version.
  • Practical Accuracy: Even with a small number of projections (e.g., 30), the empirical approximation factor $c$ often remained below 1.1, significantly better than the worst-case theoretical bounds.

Conclusion

This research provides a practical framework for finding approximate furthest neighbors and solving annulus queries in sublinear time. While the current work is optimized for Euclidean space, future research may extend these techniques to general metric spaces using random pivots and seek to close the theoretical gap between space complexity upper and lower bounds.

Summary updated

Abstract

Much recent work has been devoted to approximate nearest neighbor queries. Motivated by applications in recommender systems, we consider approximate furthest neighbor (AFN) queries and present a simple, fast, and highly practical data structure for answering AFN queries in high- dimensional Euclidean space. The method builds on the technique of In- dyk (SODA 2003), storing random projections to provide sublinear query time for AFN. However, we introduce a different query algorithm, improving on Indyk's approximation factor and reducing the running time by a logarithmic factor. We also present a variation based on a query- independent ordering of the database points; while this does not have the provable approximation factor of the query-dependent data structure, it offers significant improvement in time and space complexity. We give a theoretical analysis, and experimental results. As an application, the query-dependent approach is used for deriving a data structure for the approximate annulus query problem, which is defined as follows: given an input set S and two parameters r > 0 and w >= 1, construct a data structure that returns for each query point q a point p in S such that the distance between p and q is at least r/w and at most wr.
BibTeX
@inproceedings{pagh2016approximate,
  author = {Rasmus Pagh and Francesco Silvestri and Johan Sivertsen and Matthew Skala},
  title = {{Approximate Furthest Neighbor with Application to Annulus Query}},
  booktitle = {Inf. Syst},
  year = {2016},
  url = {https://openreview.net/forum?id=Bj2gIT4qHDk},
}
Figure