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.
The Hidden Bias in Standard Search
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:
- Select a bucket from the LSH data structure with a probability proportional to its size.
- Select a random point $x$ from that chosen bucket.
- Compute the "degree" $d(x)$, defined as the number of buckets that contain point $x$.
- 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