{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T14:24:15Z","timestamp":1785594255733,"version":"3.56.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2021,6,15]]},"abstract":"<jats:p>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 &gt; 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.<\/jats:p>","DOI":"10.1145\/3471485.3471496","type":"journal-article","created":{"date-parts":[[2021,6,18]],"date-time":"2021-06-18T05:22:06Z","timestamp":1623993726000},"page":"42-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Fair near neighbor search via sampling"],"prefix":"10.1145","volume":"50","author":[{"given":"Martin","family":"Aumuller","sequence":"first","affiliation":[{"name":"IT University of Copenhagen, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sariel","family":"Har-Peled","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign (UIUC), Champaign, IL, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sepideh","family":"Mahabadi","sequence":"additional","affiliation":[{"name":"Toyota Technological Institute at Chicago (TTIC), Chicago, IL, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rasmus","family":"Pagh","sequence":"additional","affiliation":[{"name":"BARC and University of Copenhagen, Copenhagen, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Francesco","family":"Silvestri","sequence":"additional","affiliation":[{"name":"University of Padova, Padova, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2013.0570"},{"key":"e_1_2_1_2_1","first-page":"1","volume-title":"Proc. 35th Int. Symposium on Computational Geometry (SoCG)","volume":"129","author":"Afshani P.","year":"2019","unstructured":"P. Afshani and J. M. Phillips . Independent range sampling, revisited again. In G. Barequet and Y. Wang, editors , Proc. 35th Int. Symposium on Computational Geometry (SoCG) , volume 129 of LIPIcs, pages 4: 1 -- 4 :13, 2019 . P. Afshani and J. M. Phillips. Independent range sampling, revisited again. In G. Barequet and Y. Wang, editors, Proc. 35th Int. Symposium on Computational Geometry (SoCG), volume 129 of LIPIcs, pages 4:1--4:13, 2019."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039702"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.18"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327494"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196976"},{"key":"e_1_2_1_7_1","volume-title":"Sampling a near neighbor in high dimensions - Who is the fairest of them all? CoRR, 2101.10905","author":"Aum\u00a8uller M.","year":"2021","unstructured":"M. Aum\u00a8uller , S. Har-Peled , S. Mahabadi , R. Pagh , and F. Silvestri . Sampling a near neighbor in high dimensions - Who is the fairest of them all? CoRR, 2101.10905 , 2021 . M. Aum\u00a8uller, S. Har-Peled, S. Mahabadi, R. Pagh, and F. Silvestri. Sampling a near neighbor in high dimensions - Who is the fairest of them all? CoRR, 2101.10905, 2021."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387648"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/829502.830043"},{"key":"e_1_2_1_10_1","first-page":"1032","volume-title":"Proc. 58th IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Charikar M.","year":"2017","unstructured":"M. Charikar and P. Siminelakis . Hashing-based-estimators for kernel density in high dimensions. In C. Umans, editor , Proc. 58th IEEE Symposium on Foundations of Computer Science (FOCS) , pages 1032 -- 1043 , 2017 . M. Charikar and P. Siminelakis. Hashing-based-estimators for kernel density in high dimensions. In C. Umans, editor, Proc. 58th IEEE Symposium on Foundations of Computer Science (FOCS), pages 1032--1043, 2017."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1089\/big.2016.0047"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090255"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1538772"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a014"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/3454287.3455468"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3157382.3157469"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594545"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.35"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1098\/rsif.2005.0051"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.spl.2012.05.017"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00140665"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2008.79"},{"key":"e_1_2_1_25_1","volume-title":"Sub-Linear Privacy-Preserving Near-Neighbor Search with Untrusted Server on Large-Scale Datasets. ArXiv:1612.01835","author":"Riazi M. S.","year":"2016","unstructured":"M. S. Riazi , B. Chen , A. Shrivastava , D. S. Wallach , and F. Koushanfar . Sub-Linear Privacy-Preserving Near-Neighbor Search with Untrusted Server on Large-Scale Datasets. ArXiv:1612.01835 , 2016 . M. S. Riazi, B. Chen, A. Shrivastava, D. S. Wallach, and F. Koushanfar. Sub-Linear Privacy-Preserving Near-Neighbor Search with Untrusted Server on Large-Scale Datasets. ArXiv:1612.01835, 2016."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020488"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3471485.3471496","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3471485.3471496","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:26Z","timestamp":1750191446000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3471485.3471496"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,6,15]]}},"alternative-id":["10.1145\/3471485.3471496"],"URL":"https:\/\/doi.org\/10.1145\/3471485.3471496","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}