mlsanityData to 14 Oct 2026

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

arXiv 2101.10905 ↗First posted 26 Jan 2021cs.DS cs.DB cs.LGcited by 3

Not on the map. Why?

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.

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

28 of 88 references.

References · 28

  1. 2016Equality of Opportunity in Supervised Learningcited by 2,007
  2. 2016Fair prediction with disparate impact: A study of bias in recidivism prediction instrumentscited by 672
  3. 2018A Reductions Approach to Fair Classificationcited by 587
  4. 2017On Fairness and Calibrationcited by 406
  5. 2016Fairness Beyond Disparate Treatment & Disparate Impact: Learning Classification without Disparate Mistreatmentcited by 369
  6. 2018Empirical Risk Minimization under Fairness Constraintscited by 226
  7. 2018Fair Clustering Through Fairletscited by 176
  8. 2018ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithmscited by 130
  9. 2019Fair Algorithms for Clusteringcited by 98
  10. 2019Scalable Fair Clusteringcited by 78
  11. 2019Guarantees for Spectral Clustering with Fairness Constraintscited by 72
  12. 2018Downstream Effects of Affirmative Actioncited by 34
16 more
  1. 2018Hashing-Based-Estimators for Kernel Density in High Dimensionscited by 33
  2. 2018Fair Algorithms for Learning in Allocation Problemscited by 29
  3. 2018User Fairness in Recommender Systemscited by 21
  4. 2018Convex Formulations for Fair Principal Component Analysiscited by 20
  5. 2016Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighborscited by 18
  6. 2014Solving the Problem of the K Parameter in the KNN Classifier Using an Ensemble Learning Approachcited by 7
  7. 2019Near Neighbor: Who is the Fairest of Them All?cited by 7
  8. 2019Fair Near Neighbor Search: Independent Range Sampling in High Dimensionscited by 5
  9. 2015Probabilistic Polynomials and Hamming Nearest Neighborscited by 3
  10. 2016A Framework for Similarity Search with Space-Time Tradeoffs using Locality-Sensitive Filteringcited by 3
  11. 2017Edge Estimation with Independent Set Oraclescited by 3
  12. 2016Parameter-free Locality Sensitive Hashing for Spherical Range Reportingcited by 2
  13. 2015Proximity in the Age of Distraction: Robust Approximate Nearest Neighbor Searchcited by 1
  14. 2016Sub-Linear Privacy-Preserving Near-Neighbor Searchcited by 1
  15. 2017Distance-Sensitive hashingcited by 1
  16. 2019Independent Range Sampling, Revisited Againcited by 1

Built on by

Cited by year

Citing papers per year: 2021: 2; 2022: 0; 2023: 1.

3 papers.

  1. 2021Improved Approximation Algorithms for Individually Fair Clusteringcited by 33
  2. 2021Approximation Algorithms for Socially Fair Clusteringcited by 25
  3. 2023Approximation Algorithms for Fair Range Clusteringcited by 10