Fair Near Neighbor Search: Independent Range Sampling in High Dimensions. PODS

Martin Aumüller, Rasmus Pagh, Francesco Silvestri

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


Similarity search is a fundamental algorithmic primitive, widely used in many computer science disciplines. There are several variants of the similarity search problem, and one of the most relevant is the r-near neighbor (r-NN) problem: given a radius r>0 and a set of points S, construct a data structure that, for any given 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 fairness. We consider fairness in the sense of equal opportunity: 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. To address this, we propose efficient data structures for r-NN where all points in S that are near q have the same probability to be selected and returned by the query. Specifically, we first propose a black-box approach that, given any LSH scheme, constructs a data structure for uniformly sampling points in the neighborhood of a query. Then, we 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 (un)fairness in a recommendation setting on real-world datasets and discusses the inherent unfairness introduced by solving other variants of the problem.
Original languageEnglish
Title of host publicationPODS'20: Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
PublisherAssociation for Computing Machinery
Publication date2020
Publication statusPublished - 2020
EventSymposium on Principles of Database Systems -
Duration: 14 Jun 2020 → …


ConferenceSymposium on Principles of Database Systems
Period14/06/2020 → …


  • Similarity Search
  • r-Near Neighbor
  • Fairness
  • Locality Sensitive Hashing
  • Uniform Sampling


Dive into the research topics of 'Fair Near Neighbor Search: Independent Range Sampling in High Dimensions. PODS'. Together they form a unique fingerprint.

Cite this