# Near Neighbor: Who is the Fairest of Them All?

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jun 2019.

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

- [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)
- [A Sociotechnical View of Algorithmic Fairness](https://mlsanity.com/paper/2110.09253/) (2021)
- [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023)
- [Toward Operationalizing Pipeline-aware ML Fairness: A Research Agenda for Developing Practical Guidelines and Tools](https://mlsanity.com/paper/2309.17337/) (2023)
- [Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of Them All?](https://mlsanity.com/paper/2101.10905/) (2021)
- [Querying in the Age of Graph Databases and Knowledge Graphs](https://mlsanity.com/paper/2106.11456/) (2021)

## Abstract (arXiv)

newcommandballmathbbBnewcommanddsQQnewcommanddsSSIn 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., ball(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 Obigl( dns(q.r) dsQ(n,c) bigr), and its space is O(dsS(n,c)), where dsQ(n,c) and dsS(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.