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:
- 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.
- 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.
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