Fair near neighbor search via sampling

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

Fair near neighbor search via sampling. / Aumuller, Martin; Har-Peled, Sariel; Mahabadi, Sepideh; Pagh, Rasmus; Silvestri, Francesco.

In: SIGMOD Record, Vol. 50, No. 1, 2021, p. 42-49.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Aumuller, M, Har-Peled, S, Mahabadi, S, Pagh, R & Silvestri, F 2021, 'Fair near neighbor search via sampling', SIGMOD Record, vol. 50, no. 1, pp. 42-49. https://doi.org/10.1145/3471485.3471496

APA

Aumuller, M., Har-Peled, S., Mahabadi, S., Pagh, R., & Silvestri, F. (2021). Fair near neighbor search via sampling. SIGMOD Record, 50(1), 42-49. https://doi.org/10.1145/3471485.3471496

Vancouver

Aumuller M, Har-Peled S, Mahabadi S, Pagh R, Silvestri F. Fair near neighbor search via sampling. SIGMOD Record. 2021;50(1):42-49. https://doi.org/10.1145/3471485.3471496

Author

Aumuller, Martin ; Har-Peled, Sariel ; Mahabadi, Sepideh ; Pagh, Rasmus ; Silvestri, Francesco. / Fair near neighbor search via sampling. In: SIGMOD Record. 2021 ; Vol. 50, No. 1. pp. 42-49.

Bibtex

@article{c7dcd8c9636947568eb3b777838d1527,
title = "Fair near neighbor search via sampling",
abstract = "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 rnear 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.",
author = "Martin Aumuller and Sariel Har-Peled and Sepideh Mahabadi and Rasmus Pagh and Francesco Silvestri",
year = "2021",
doi = "10.1145/3471485.3471496",
language = "English",
volume = "50",
pages = "42--49",
journal = "S I G M O D Record",
issn = "0163-5808",
publisher = "Association for Computing Machinery, Inc.",
number = "1",

}

RIS

TY - JOUR

T1 - Fair near neighbor search via sampling

AU - Aumuller, Martin

AU - Har-Peled, Sariel

AU - Mahabadi, Sepideh

AU - Pagh, Rasmus

AU - Silvestri, Francesco

PY - 2021

Y1 - 2021

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 rnear 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.

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 rnear 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.

UR - http://www.scopus.com/inward/record.url?scp=85108234781&partnerID=8YFLogxK

U2 - 10.1145/3471485.3471496

DO - 10.1145/3471485.3471496

M3 - Journal article

AN - SCOPUS:85108234781

VL - 50

SP - 42

EP - 49

JO - S I G M O D Record

JF - S I G M O D Record

SN - 0163-5808

IS - 1

ER -

ID: 300923551