Abstract
In this work we study a fair variant of the near neighbor problem. Namely, given a set of $n$ points $P$ and a parameter $r$, the goal is to preprocess the points, such that given a query point $q$, any point in the $r$-neighborhood of the query, i.e., $\mathbb{B}(q,r)$, have the same probability of being reported as the near neighbor. We show that LSH based algorithms can be made fair, without a significant loss in efficiency. Specifically, we show an algorithm that reports a point in the $r$-neighborhood of a query $q$ with almost uniform probability. The query time is proportional to $O\bigl( \mathrm{dns}(q,r) \mathcal{Q}(n,c) \bigr)$, and its space is $O(\mathcal{S}(n,c))$, where $\mathcal{Q}(n,c)$ and $\mathcal{S}(n,c)$ are the query time and space of an LSH algorithm for $c$-approximate near neighbor, and $\mathrm{dns}(q,r)$ is a function of the local density around $q$. Our approach works more generally for sampling uniformly from a sub-collection of sets of a given collection and can be used in a few other applications. Finally, we run experiments to show performance of our approach on real data.
Introduction
In many modern machine learning applications—ranging from recommendation systems to density estimation—the core task involves finding points "near" a specific query. The industry standard for performing this efficiently in high-dimensional spaces is Locality Sensitive Hashing (LSH). LSH works by hashing points such that nearby items are more likely to collide in the same bucket than distant ones.
However, LSH has an inherent structural bias: points closer to the query have a significantly higher probability of colliding in a hash bucket than points further away, even if both points fall within the desired radius $r$. While this bias is often considered a feature for finding the nearest neighbor, it becomes a bug when "individual fairness" is required. In a fair context, all items within the $r$-neighborhood $\mathbb{B}(q,r)$ should be treated equally and have an equal probability of being reported.
This paper introduces Fair Near Neighbor (FANN) algorithms, which ensure that every point within a specified radius has a nearly uniform probability of being reported, achieving this with minimal computational overhead.
The Need for Fair Sampling
The authors identify several scenarios where returning a "random nearby" neighbor is superior to returning the "absolute nearest" neighbor:
- Noise Robustness: The absolute nearest neighbor may be an unrepresentative outlier or noise; sampling from the neighborhood provides a more robust view of the local data distribution.
- Anonymization: In privacy-sensitive contexts, returning a random neighbor makes it significantly harder for an adversary to reverse-engineer the original query compared to returning a deterministic nearest neighbor.
- Density Estimation: Accurate estimation of the number of items in a neighborhood requires uniform sampling to avoid over-representing dense clusters.
- Graph Simulations: Simulating random walks on proximity graphs (e.g., for manifold learning) requires picking neighbors uniformly to maintain the integrity of the stochastic process.
Methodology: Rejection Sampling from Union of Sets
The technical challenge lies in sampling uniformly from the union of sets—specifically, the collection of LSH buckets that contain the query $q$. Because a single point $x$ might appear in multiple buckets, it is naturally over-represented in the search results.
The proposed framework utilizes a rejection sampling technique. The basic algorithm follows three steps:
- Pick a bucket $X$ containing the query $q$ with probability proportional to the bucket's size.
- Pick a point $x$ from that bucket uniformly at random.
- Accept $x$ with probability $1/d(x)$, where $d(x)$ is the "degree" of the point (the number of buckets containing the query that also contain $x$).
Efficient Degree Handling
Computing the exact degree $d(x)$ for every candidate is computationally expensive. The paper introduces three ways to manage this:
- Exact Degree: A baseline method that counts every occurrence, which is slow ($O(g^2)$ where $g$ is the number of buckets).
- Degree Approximation: Uses statistical estimation to approximate the degree, significantly reducing runtime.
- Simulation-based Sampling: This is the most novel contribution. Instead of calculating the degree, the algorithm probes buckets at random. If it finds the point $x$ again quickly, it indicates a high degree (over-representation), and the algorithm uses the iteration count to decide whether to accept the sample. This effectively "shortcuts" the counting process.
Experimental Results
The authors evaluated the FANN approach on three high-dimensional benchmarks: MNIST (784-D images), SIFT10K (128-D descriptors), and GloVe (100-D word embeddings). Performance was measured using Total Variation Distance (TVD) to a perfectly uniform distribution.
- Superior Fairness: On the MNIST dataset, the "Degree Approximation" algorithm was 2.4x closer to the optimal fair distribution than standard LSH sampling. Standard LSH methods were found to be 6.6x to 10x further from the optimal distribution than the proposed fair methods.
- Efficiency: For standard LSH parameters (e.g., $L=100$ buckets), the fair sampling approach was twice as fast as the "Optimal" (but slow) exact degree counter.
- Trade-offs: The results demonstrate a clear trade-off: by allowing the algorithm to perform a few more queries for degree approximation, the statistical distance to a "perfect" fair distribution drops rapidly toward zero.
Insights and Limitations
The fundamental insight of this work is that the bias in LSH is exactly captured by the "degree" of a point across buckets. By treating the search as a sampling problem from a union of sets, the authors mathematically "undo" the LSH bias. Crucially, they prove that fairness is nearly free; uniform sampling can be achieved with a query time only a polylogarithmic factor slower than standard LSH.
However, some limitations remain:
- The "Outlier" Tax: Query time depends on the ratio of the "approximate neighborhood" (points within distance $cr$) to the "exact neighborhood" (points within distance $r$). If a query is surrounded by many points that are "almost-near" but few that are "actually-near," the algorithm will spend significant time rejecting outliers.
- Dynamic Data: The current framework focuses on static datasets. Extending these fair sampling techniques to dynamic structures where points are frequently inserted or deleted remains an open area for future research.
Summary updated