Sampling near neighbors in search for fairness
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
Sampling near neighbors in search for fairness. / Aumüller, Martin; Har-Peled, Sariel; Mahabadi, Sepideh; Pagh, Rasmus; Silvestri, Francesco.
I: Communications of the ACM, Bind 65, Nr. 8, 2022, s. 83-90.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Sampling near neighbors in search for fairness
AU - Aumüller, Martin
AU - Har-Peled, Sariel
AU - Mahabadi, Sepideh
AU - Pagh, Rasmus
AU - Silvestri, Francesco
N1 - Publisher Copyright: © 2022 ACM.
PY - 2022
Y1 - 2022
N2 - 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. The problem is of special interest in high dimensions, where Locality Sensitive Hashing (LSH), the theoretically leading approach to similarity search, does not provide any 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 carried out an experimental evaluation that highlights the inherent unfairness of existing NN data structures.
AB - 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. The problem is of special interest in high dimensions, where Locality Sensitive Hashing (LSH), the theoretically leading approach to similarity search, does not provide any 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 carried out an experimental evaluation that highlights the inherent unfairness of existing NN data structures.
UR - http://www.scopus.com/inward/record.url?scp=85135707549&partnerID=8YFLogxK
U2 - 10.1145/3543667
DO - 10.1145/3543667
M3 - Journal article
AN - SCOPUS:85135707549
VL - 65
SP - 83
EP - 90
JO - Communications of the A C M
JF - Communications of the A C M
SN - 0001-0782
IS - 8
ER -
ID: 340693159