{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T14:24:16Z","timestamp":1785594256874,"version":"3.56.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"8","license":[{"start":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T00:00:00Z","timestamp":1658361600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1907400"],"award-info":[{"award-number":["CCF-1907400"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["20174LF3T8"],"award-info":[{"award-number":["20174LF3T8"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008398","name":"Villum Fonden","doi-asserted-by":"publisher","award":["16582"],"award-info":[{"award-number":["16582"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2022,8]]},"abstract":"<jats:p>\n            Similarity search is a fundamental algorithmic primitive, widely used in many computer science disciplines. Given a set of points\n            <jats:italic>S<\/jats:italic>\n            and a radius parameter\n            <jats:italic>r<\/jats:italic>\n            &gt; 0, the\n            <jats:italic>r<\/jats:italic>\n            -near neighbor (\n            <jats:italic>r<\/jats:italic>\n            -NN) problem asks for a data structure that, given any query point\n            <jats:italic>q<\/jats:italic>\n            , returns a point\n            <jats:italic>p<\/jats:italic>\n            within distance at most\n            <jats:italic>r<\/jats:italic>\n            from\n            <jats:italic>q.<\/jats:italic>\n            In this paper, we study the\n            <jats:italic>r<\/jats:italic>\n            -NN problem in the light of individual fairness and providing equal opportunities: all points that are within distance\n            <jats:italic>r<\/jats:italic>\n            from the query should have the same probability to be returned. The problem is of special interest in high dimensions, where\n            <jats:italic>Locality Sensitive Hashing<\/jats:italic>\n            (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.\n          <\/jats:p>","DOI":"10.1145\/3543667","type":"journal-article","created":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T16:21:39Z","timestamp":1658420499000},"page":"83-90","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Sampling near neighbors in search for fairness"],"prefix":"10.1145","volume":"65","author":[{"given":"Martin","family":"Aum\u00fcller","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, IL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sepideh","family":"Mahabadi","sequence":"additional","affiliation":[{"name":"Toyota Technological Institute at Chicago, IL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rasmus","family":"Pagh","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Francesco","family":"Silvestri","sequence":"additional","affiliation":[{"name":"University of Padova, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,7,21]]},"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","volume-title":"Proc. 35th Int. Symposium on Computational Geometry (SoCG)","volume":"129","author":"Afshani P.","year":"2019","unstructured":"Afshani , P. , Phillips , J.M. Independent range sampling, revisited again. In G. Barequet, and Y. Wang, eds . Proc. 35th Int. Symposium on Computational Geometry (SoCG) , volume 129 of LIPIcs ( 2019 ), 4:1--4:13. Afshani, P., Phillips, J.M. Independent range sampling, revisited again. In G. Barequet, and Y. Wang, eds. Proc. 35th Int. Symposium on Computational Geometry (SoCG), volume 129 of LIPIcs (2019), 4:1--4:13."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.16"},{"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","doi-asserted-by":"publisher","DOI":"10.1145\/3471485.3471496"},{"key":"e_1_2_1_8_1","volume-title":"Sampling a near neighbor in high dimensions---Who is the fairest of them all? to appear in ACM Transaction of Database Systems","author":"Aum\u00fcller M.","year":"2022","unstructured":"Aum\u00fcller , M. , Har-Peled , S. , Mahabadi , S. , Pagh , R. , Silvestri , F. Sampling a near neighbor in high dimensions---Who is the fairest of them all? to appear in ACM Transaction of Database Systems ( 2022 .). Aum\u00fcller, M., Har-Peled, S., Mahabadi, S., Pagh, R., Silvestri, F. Sampling a near neighbor in high dimensions---Who is the fairest of them all? to appear in ACM Transaction of Database Systems (2022.)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387648"},{"key":"e_1_2_1_10_1","volume-title":"Proc. Compression and Complexity of Sequences","author":"Broder A.Z.","year":"1997","unstructured":"Broder , A.Z. On the resemblance and containment of documents . In Proc. Compression and Complexity of Sequences ( 1997 ), 21--29. Broder, A.Z. On the resemblance and containment of documents. In Proc. Compression and Complexity of Sequences (1997), 21--29."},{"key":"e_1_2_1_11_1","volume-title":"Proc. 58th IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Charikar M.","year":"2017","unstructured":"Charikar , M. , Siminelakis , P. Hashing-based-estimators for kernel density in high dimensions. In C. Umans, ed . Proc. 58th IEEE Symposium on Foundations of Computer Science (FOCS) ( 2017 ), 1032--1043. Charikar, M., Siminelakis, P. Hashing-based-estimators for kernel density in high dimensions. In C. Umans, ed. Proc. 58th IEEE Symposium on Foundations of Computer Science (FOCS) (2017), 1032--1043."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1089\/big.2016.0047"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090255"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1538772"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a014"},{"key":"e_1_2_1_17_1","volume-title":"Proc. 32nd Neural Info. Proc. Sys. (NeurIPS)","author":"Har-Peled S.","year":"2019","unstructured":"Har-Peled , S. , Mahabadi , S. Near neighbor : Who is the fairest of them all? In Proc. 32nd Neural Info. Proc. Sys. (NeurIPS) ( 2019 ), 13176--13187. Har-Peled, S., Mahabadi, S. Near neighbor: Who is the fairest of them all? In Proc. 32nd Neural Info. Proc. Sys. (NeurIPS) (2019), 13176--13187."},{"key":"e_1_2_1_18_1","volume-title":"Proc. Sys. (NIPS)","author":"Hardt M.","year":"2016","unstructured":"Hardt , M. , Price , E. , Srebro , N. Equality of opportunity in supervised learning. In Neural Info . Proc. Sys. (NIPS) ( 2016 ), 3315--3323. Hardt, M., Price, E., Srebro, N. Equality of opportunity in supervised learning. In Neural Info. Proc. Sys. (NIPS) (2016), 3315--3323."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594545"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_21_1","first-page":"64","article-title":"Monte-Carlo algorithms for enumeration and reliability problems. In 24th Symposium on Foundations of Computer Science (SFCS)","volume":"56","author":"Karp R.M.","year":"1983","unstructured":"Karp , R.M. , Luby , M . Monte-Carlo algorithms for enumeration and reliability problems. In 24th Symposium on Foundations of Computer Science (SFCS) , IEEE Computer Society , 1983 , 56 -- 64 . Karp, R.M., Luby, M. Monte-Carlo algorithms for enumeration and reliability problems. In 24th Symposium on Foundations of Computer Science (SFCS), IEEE Computer Society, 1983, 56--64.","journal-title":"IEEE Computer Society"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1098\/rsif.2005.0051"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.spl.2012.05.017"},{"key":"e_1_2_1_24_1","first-page":"1","article-title":"Sampling from spatial databases","volume":"5","author":"Olken F.","year":"1995","unstructured":"Olken , F. , Rotem , D . Sampling from spatial databases . Stat. Comput 5 , 1 ( Mar 1995 ), 43--57. Olken, F., Rotem, D. Sampling from spatial databases. Stat. Comput 5, 1 (Mar 1995), 43--57.","journal-title":"Stat. Comput"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2008.79"},{"key":"e_1_2_1_26_1","volume-title":"Sublinear privacy-preserving near-neighbor search with untrusted server on large-scale datasets. arXiv:1612.01835","author":"Riazi M.S.","year":"2016","unstructured":"Riazi , M.S. , Chen , B. , Shrivastava , A. , Wallach , D.S. , Koushanfar , F. Sublinear privacy-preserving near-neighbor search with untrusted server on large-scale datasets. arXiv:1612.01835 ( 2016 ). Riazi, M.S., Chen, B., Shrivastava, A., Wallach, D.S., Koushanfar, F. Sublinear privacy-preserving near-neighbor search with untrusted server on large-scale datasets. arXiv:1612.01835 (2016)."},{"key":"e_1_2_1_27_1","volume-title":"Proc. 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)","author":"Thanh B.L.","year":"2011","unstructured":"Thanh , B.L. , Ruggieri , S. , Turini , F. k-nn as an implementation of situation testing for discrimination discovery and prevention . In Proc. 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) ( 2011 ), 502--510. Thanh, B.L., Ruggieri, S., Turini, F. k-nn as an implementation of situation testing for discrimination discovery and prevention. In Proc. 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) (2011), 502--510."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3543667","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3543667","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3543667","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:48Z","timestamp":1750186848000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3543667"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,21]]},"references-count":27,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["10.1145\/3543667"],"URL":"https:\/\/doi.org\/10.1145\/3543667","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,21]]},"assertion":[{"value":"2022-07-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}