Near Neighbor: Who is the Fairest of Them All?

Sariel Har-Peled, Sepideh Mahabadi

Executive Summary

In the discourse surrounding algorithmic fairness, the vast majority of research focuses on training datasets or model optimization objectives. However, the underlying data structures used to retrieve information can also introduce significant, hidden biases. This paper investigates a "fair" variant of the near neighbor problem. Standard search algorithms like Locality Sensitive Hashing (LSH) inherently favor points closest to a query over others in the same neighborhood. To resolve this, the authors introduce a mathematically rigorous framework for "Fair Near Neighbor" search, enabling uniform sampling from a query's neighborhood with minimal impact on computational efficiency.

Given a query point $q$, the Near Neighbor (NN) problem seeks to find data points within a specified radius $r$, denoted as $B(q,r)$. The industry standard for executing this in high-dimensional spaces is Locality Sensitive Hashing (LSH).

LSH operates by hashing points into buckets such that "close" points are more likely to collide. However, this creates a structural selection bias: points that are very close to the query collide in significantly more buckets than points near the outer edge of the radius $r$. Consequently, if an algorithm picks a random bucket and a random point within it, it is far more likely to retrieve the absolute nearest neighbor than a "typical" neighbor within the valid radius.

This "closer is more likely" bias is highly problematic for several real-world applications:

  • Anonymization: Systems often need to return a "typical" representative from a neighborhood rather than a specific, identifiable outlier.
  • Density Estimation: Accurate statistical estimations require unbiased, uniform samples from a given neighborhood.
  • Fairness in Recommendations: It is crucial to ensure that all qualified candidates or items within a similarity threshold have an equal probability of being surfaced by the algorithm.

The "Fair Near Neighbor" Framework

To counteract this bias, the authors propose a novel framework based on sampling from the union of sets. In the context of LSH, the "sets" are the hash buckets containing the query point, and their "union" is the complete set of candidate neighbors.

Rejection Sampling and Degree Approximation

Explicitly computing the entire union of buckets is computationally prohibitive. Instead, the authors utilize a highly efficient filter approach:

  1. Select a bucket from the LSH data structure with a probability proportional to its size.
  2. Select a random point $x$ from that chosen bucket.
  3. Compute the "degree" $d(x)$, defined as the number of buckets that contain point $x$.
  4. Accept or Reject: Accept the point with probability $1/d(x)$. If rejected, repeat the process.

By applying this $1/d(x)$ probability filter, the algorithm mathematically cancels out the collision bias introduced by the hashing process.

The primary algorithmic innovation lies in degree approximation. Calculating the exact degree $d(x)$ for every sample is expensive. The authors demonstrate that approximating this degree achieves an "almost uniform" distribution while maintaining sub-linear query time. The time to report a fair point is proportional to $O(\text{dns}(q,r) Q(n,c))$, where $Q(n,c)$ is the standard LSH query time and $\text{dns}(q,r)$ is a function of the local density around $q$. They also introduce dynamic bucket weight adjustments to seamlessly handle outliers—points that fall into a bucket but reside outside the desired radius $r$.

Experimental Validation

The authors evaluated their approach on three standard high-dimensional benchmarks: MNIST (784 dimensions), SIFT10K (128 dimensions), and GloVe (100 dimensions).

Key Results: * Dramatically Improved Uniformity: On the MNIST dataset, the proposed Degree Approximation algorithm performed significantly better than standard LSH. While standard LSH distributions skewed 6.6x to 10x "further" from a uniform distribution than an optimal sampler, the authors' method reduced this discrepancy to just 2.4x. * High Efficiency: While an "Optimal" sampler (using exact degrees) achieves perfect fairness, it suffers from slow query times. The authors' approximation approach proved 2x to 4.3x faster than the optimal version while maintaining nearly identical fairness metrics. * Tunable Accuracy: The framework offers a clear operational trade-off. By allowing the algorithm to run slightly longer (processing more queries), the resulting distribution becomes virtually indistinguishable from a perfectly uniform sample.

Limitations and Future Directions

While the proposed method proves that algorithmic fairness is "almost free" in terms of computational overhead, it does have limitations. The query time is inherently sensitive to local density ($\text{dns}(q,r)$); in extremely dense regions of the feature space, the number of rejections increases, which can slow down performance. Furthermore, the method's efficacy is tied to the underlying LSH parameters—if the radius $r$ is tuned too small to capture any points, the fairness of the sampler becomes moot.

Ultimately, this research successfully shifts the fairness conversation from "what models learn" to "how data structures retrieve," proving that unbiased data retrieval is both mathematically possible and practically scalable.

Summary updated

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., $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 $p$ in the $r$-neighborhood of a query $q$ with almost uniform probability. The time to report such a point is proportional to $O(\dns(q.r) Q(n,c))$, and its space is $O(S(n,c))$, where $Q(n,c)$ and $S(n,c)$ are the query time and space of an LSH algorithm for $c$-approximate near neighbor, and $\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.
BibTeX
@inproceedings{harpeled2019near,
  author = {Sariel Har-Peled and Sepideh Mahabadi},
  title = {{Near Neighbor: Who is the Fairest of Them All?}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=WjLti7tMGR},
}
Figure