# Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of Them All?

arXiv: https://arxiv.org/abs/2101.10905 · HTML: https://mlsanity.com/paper/2101.10905/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 88 references that are in the map.
- First posted on arXiv 26 Jan 2021.

## Builds on (most cited first, 28 of 28)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [On Fairness and Calibration](https://mlsanity.com/paper/1709.02012/) (2017)
- [Fairness Beyond Disparate Treatment & Disparate Impact: Learning Classification without Disparate Mistreatment](https://mlsanity.com/paper/1610.08452/) (2016)
- [Empirical Risk Minimization under Fairness Constraints](https://mlsanity.com/paper/1802.08626/) (2018)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [Guarantees for Spectral Clustering with Fairness Constraints](https://mlsanity.com/paper/1901.08668/) (2019)
- [Downstream Effects of Affirmative Action](https://mlsanity.com/paper/1808.09004/) (2018)
- [Hashing-Based-Estimators for Kernel Density in High Dimensions](https://mlsanity.com/paper/1808.10530/) (2018)
- [Fair Algorithms for Learning in Allocation Problems](https://mlsanity.com/paper/1808.10549/) (2018)
- [User Fairness in Recommender Systems](https://mlsanity.com/paper/1807.06349/) (2018)
- [Convex Formulations for Fair Principal Component Analysis](https://mlsanity.com/paper/1802.03765/) (2018)
- [Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors](https://mlsanity.com/paper/1608.03580/) (2016)
- [Solving the Problem of the K Parameter in the KNN Classifier Using an Ensemble Learning Approach](https://mlsanity.com/paper/1409.0919/) (2014)
- [Near Neighbor: Who is the Fairest of Them All?](https://mlsanity.com/paper/1906.02640/) (2019)
- [Fair Near Neighbor Search: Independent Range Sampling in High Dimensions](https://mlsanity.com/paper/1906.01859/) (2019)
- [Probabilistic Polynomials and Hamming Nearest Neighbors](https://mlsanity.com/paper/1507.05106/) (2015)
- [A Framework for Similarity Search with Space-Time Tradeoffs using Locality-Sensitive Filtering](https://mlsanity.com/paper/1605.02687/) (2016)
- [Edge Estimation with Independent Set Oracles](https://mlsanity.com/paper/1711.07567/) (2017)
- [Parameter-free Locality Sensitive Hashing for Spherical Range Reporting](https://mlsanity.com/paper/1605.02673/) (2016)
- [Proximity in the Age of Distraction: Robust Approximate Nearest Neighbor Search](https://mlsanity.com/paper/1511.07357/) (2015)
- [Sub-Linear Privacy-Preserving Near-Neighbor Search](https://mlsanity.com/paper/1612.01835/) (2016)
- [Distance-Sensitive hashing](https://mlsanity.com/paper/1703.07867/) (2017)
- [Independent Range Sampling, Revisited Again](https://mlsanity.com/paper/1903.08014/) (2019)

## Built on by (most cited first, 3 of 3)

- [Improved Approximation Algorithms for Individually Fair Clustering](https://mlsanity.com/paper/2106.14043/) (2021)
- [Approximation Algorithms for Socially Fair Clustering](https://mlsanity.com/paper/2103.02512/) (2021)
- [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023)

## Abstract (arXiv)

Similarity search is a fundamental algorithmic primitive, widely used in many computer science disciplines. Given a set of points S and a radius parameter r>0, the r-near neighbor (r-NN) problem asks for a data structure that, given any query point q, returns a point p within distance at most r from q. In this paper, we study the r-NN problem in the light of individual fairness and providing equal opportunities: all points that are within distance r from the query should have the same probability to be returned. In the low-dimensional case, this problem was first studied by Hu, Qiao, and Tao (PODS 2014). Locality sensitive hashing (LSH), the theoretically strongest approach to similarity search in high dimensions, does not provide such a fairness guarantee. In this work, we show that LSH based algorithms can be made fair, without a significant loss in efficiency. We propose several efficient data structures for the exact and approximate variants of the fair NN problem. 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. We also develop a data structure for fair similarity search under inner product that requires nearly-linear space and exploits locality sensitive filters. The paper concludes with an experimental evaluation that highlights the inherent unfairness of NN data structures and shows the performance of our algorithms on real-world datasets.