Sampling Near Neighbors in Search for Fairness.
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 fr...
| Publicado en: | Communications of the ACM Vol. 65; no. 8; pp. 83 - 91 |
|---|---|
| Autores principales: | , , , , |
| Formato: | Artículo |
| Publicado: |
Association for Computing Machinery
Aug2022
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=158128820&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 158128820 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00010782 ACM jtl: Communications of the ACM issn: 00010782 maglogo: N pubinfo: dt: Aug2022 vid: 65 iid: 8 pid: 68 pub: Association for Computing Machinery artinfo: ui: 158128820 10.1145/3543667 ppf: 83 ppct: 8 formats: tig: atl: Sampling Near Neighbors in Search for Fairness. aug: au: Aumüller, Martin Har-Peled, Sariel Mahabadi, Sepideh Pagh, Rasmus Silvestri, Francesco affil: University of Copenhagen, Denmark University of Illinois at Urbana-Champaign, IL, USA Toyota Technological Institute at Chicago, IL, USA BARC and University of Copenhagen, Denmark University of Padova, Italy su: Data Fairness Database searching Search algorithms Algorithms Computer science Computer programming sug: subj: Data Fairness Database searching Search algorithms Algorithms Computer science Computer programming 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 subcollection 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. pubtype: Periodical doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2022 holdings: @attributes: islocal: N |
|---|