{"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":1785594255484,"version":"3.56.0"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T00:00:00Z","timestamp":1648684800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF AF award","award":["CCF-1907400"],"award-info":[{"award-number":["CCF-1907400"]}]},{"DOI":"10.13039\/501100003500","name":"UniPD","doi-asserted-by":"crossref","award":["SID18"],"award-info":[{"award-number":["SID18"]}],"id":[{"id":"10.13039\/501100003500","id-type":"DOI","asserted-by":"crossref"}]},{"name":"PRIN","award":["20174LF3T8 AHeAD"],"award-info":[{"award-number":["20174LF3T8 AHeAD"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2022,3,31]]},"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 r-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. In the low-dimensional case, this problem was first studied by Hu, Qiao, and Tao (PODS 2014).\n            <jats:bold>Locality sensitive hashing (LSH)<\/jats:bold>\n            , the theoretically strongest approach to similarity search in high dimensions, does not provide such a fairness guarantee.\n          <\/jats:p>\n          <jats:p>\n            In this work, we show that\n            <jats:sans-serif>LSH<\/jats:sans-serif>\n            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 develop a data structure for fair similarity search under inner product that requires nearly-linear space and exploits locality sensitive filters. The paper concludes with an experimental evaluation that highlights the unfairness of state-of-the-art NN data structures and shows the performance of our algorithms on real-world datasets.\n          <\/jats:p>","DOI":"10.1145\/3502867","type":"journal-article","created":{"date-parts":[[2022,2,4]],"date-time":"2022-02-04T21:57:23Z","timestamp":1644011843000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Sampling a Near Neighbor in High Dimensions \u2014 Who is the Fairest of Them All?"],"prefix":"10.1145","volume":"47","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7212-6476","authenticated-orcid":false,"given":"Martin","family":"Aum\u00fcller","sequence":"first","affiliation":[{"name":"IT University of Copenhagen, K\u00f8benhavn S, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2638-9635","authenticated-orcid":false,"given":"Sariel","family":"Har-Peled","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5004-8991","authenticated-orcid":false,"given":"Sepideh","family":"Mahabadi","sequence":"additional","affiliation":[{"name":"Toyota Technological Institute at Chicago, Chicago, IL, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1516-9306","authenticated-orcid":false,"given":"Rasmus","family":"Pagh","sequence":"additional","affiliation":[{"name":"BARC and University of Copenhagen, K\u00f8benhavn \u00d8, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3441-7413","authenticated-orcid":false,"given":"Francesco","family":"Silvestri","sequence":"additional","affiliation":[{"name":"University of Padova, Padova, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,4,6]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3092931.3092933"},{"key":"e_1_3_3_3_2","unstructured":"Eytan Adar. 2007. User 4xxxxx9: Anonymizing query logs. (01 2007). http:\/\/www2007.org\/workshops\/paper_52.pdf. Appeared in the workshop Query Log Analysis: Social and Technological Challenges in association with WWW 2007."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2013.0570"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2019.4"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2017.3"},{"key":"e_1_3_3_7_2","series-title":"Proc. of Mach. Learn. Research","first-page":"60","volume-title":"Proc. 35th Int. Conf. Mach. Learning (ICML)","author":"Agarwal Alekh","year":"2018","unstructured":"Alekh Agarwal, Alina Beygelzimer, Miroslav Dud\u00edk, John Langford, and Hanna M. Wallach. 2018. A reductions approach to fair classification. In Proc. 35th Int. Conf. Mach. Learning (ICML)(Proc. of Mach. Learn. Research), Jennifer G. Dy and Andreas Krause (Eds.), Vol. 80. PMLR, 60\u201369. http:\/\/proceedings.mlr.press\/v80\/agarwal18a.html."},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039702"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327494"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.18"},{"key":"e_1_3_3_11_2","unstructured":"Alexandr Andoni. 2005. E2LSH 0.1 User manual. (2005). https:\/\/www.mit.edu\/andoni\/LSH\/manual.pdf."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039690"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2019.02.006"},{"key":"e_1_3_3_14_2","first-page":"89","volume-title":"Proc. 37th ACM Symposium on Principles of Database Systems (PODS)","author":"Aum\u00fcller Martin","year":"2018","unstructured":"Martin Aum\u00fcller, Tobias Christiani, Rasmus Pagh, and Francesco Silvestri. 2018. Distance-sensitive hashing. In Proc. 37th ACM Symposium on Principles of Database Systems (PODS). Association for Computing Machinery, New York, NY, USA, 89\u2013104."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3471485.3471496"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387648"},{"key":"e_1_3_3_17_2","first-page":"405","volume-title":"Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA (Proceedings of Machine Learning Research)","volume":"97","author":"Backurs Arturs","year":"2019","unstructured":"Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, and Tal Wagner. 2019. Scalable fair clustering. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA (Proceedings of Machine Learning Research), Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.), Vol. 97. PMLR, 405\u2013413. http:\/\/proceedings.mlr.press\/v97\/backurs19a.html."},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/646978.711822"},{"key":"e_1_3_3_19_2","article-title":"Edge estimation with independent set oracles","volume":"1711","author":"Beame Paul","year":"2017","unstructured":"Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, and Makrand Sinha. 2017. Edge estimation with independent set oracles. CoRR abs\/1711.07567 (2017), 29. arxiv:1711.07567http:\/\/arxiv.org\/abs\/1711.07567.","journal-title":"CoRR"},{"key":"e_1_3_3_20_2","first-page":"4955","volume-title":"Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada","author":"Bera Suman Kalyan","year":"2019","unstructured":"Suman Kalyan Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. 2019. Fair algorithms for clustering. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d\u2019Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett (Eds.). Curran Associates, Inc., Red Hook, NY, USA, 4955\u20134966. http:\/\/papers.nips.cc\/paper\/8741-fair-algorithms-for-clustering."},{"key":"e_1_3_3_21_2","first-page":"21","volume-title":"Proc. Compression and Complexity of Sequences","author":"Broder Andrei Z.","year":"1997","unstructured":"Andrei Z. Broder. 1997. On the resemblance and containment of documents. In Proc. Compression and Complexity of Sequences. IEEE Computer Society, USA, 21\u201329."},{"key":"e_1_3_3_22_2","first-page":"380","volume-title":"Proc. 34th ACM Symposium on Theory of Computing (STOC)","author":"Charikar Moses","year":"2002","unstructured":"Moses Charikar. 2002. Similarity estimation techniques from rounding algorithms. In Proc. 34th ACM Symposium on Theory of Computing (STOC). ACM, USA, 380\u2013388."},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.99"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.5555\/3295222.3295256"},{"key":"e_1_3_3_25_2","first-page":"2212","volume-title":"Proceedings of Machine Learning Research","volume":"89","author":"Chierichetti Flavio","year":"2019","unstructured":"Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvtiskii. 2019. Matroids, matchings, and fairness. In Proceedings of Machine Learning Research, Kamalika Chaudhuri and Masashi Sugiyama (Eds.), Vol. 89. PMLR, 2212\u20132220. http:\/\/proceedings.mlr.press\/v89\/chierichetti19a.html."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1089\/big.2016.0047"},{"key":"e_1_3_3_27_2","first-page":"31","volume-title":"Proc. 28th Symposium on Discrete Algorithms (SODA)","author":"Christiani Tobias","year":"2017","unstructured":"Tobias Christiani. 2017. A framework for similarity search with space-time tradeoffs using locality-sensitive filtering. In Proc. 28th Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, USA, 31\u201346."},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_3_3_30_2","volume-title":"Order Statistics (3rd ed.)","author":"David Herbert Aron","year":"2004","unstructured":"Herbert Aron David and Haikady Navada Nagaraja. 2004. Order Statistics (3rd ed.). John Wiley & Sons, New York, NY."},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.5555\/3327144.3327203"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090255"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3287560.3287571"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401921"},{"key":"e_1_3_3_35_2","volume-title":"Cluster Analysis (4th ed.)","author":"Everitt Brian S.","year":"2009","unstructured":"Brian S. Everitt, Sabine Landau, and Morven Leese. 2009. Cluster Analysis (4th ed.). Wiley Publishing, Chicago, IL."},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3433949"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a014"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.1"},{"key":"e_1_3_3_40_2","first-page":"13176","volume-title":"Proc. 32nd Neural Info. Proc. Sys. NeurIPS","author":"Har-Peled Sariel","year":"2019","unstructured":"Sariel Har-Peled and Sepideh Mahabadi. 2019. Near neighbor: Who is the fairest of them all?. In Proc. 32nd Neural Info. Proc. Sys. NeurIPS, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d\u2019Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett (Eds.). Curran Associates, Inc., Red Hook, NY, USA, 13176\u201313187. http:\/\/papers.nips.cc\/paper\/9476-near-neighbor-who-is-the-fairest-of-them-all."},{"key":"e_1_3_3_41_2","first-page":"3315","volume-title":"Neural Info. Proc. Sys. NIPS","author":"Hardt Moritz","year":"2016","unstructured":"Moritz Hardt, Eric Price, and Nati Srebro. 2016. Equality of opportunity in supervised learning. In Neural Info. Proc. Sys. NIPS, Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett (Eds.). Curran Associates Inc., Red Hook, NY, USA, 3315\u20133323. http:\/\/papers.nips.cc\/paper\/6374-equality-of-opportunity-in-supervised-learning."},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45294-X_3"},{"key":"e_1_3_3_43_2","first-page":"33","article-title":"Solving the problem of the K parameter in the KNN classifier using an ensemble learning approach","volume":"1409","author":"Hassanat Ahmad Basheer","year":"2014","unstructured":"Ahmad Basheer Hassanat, Mohammad Ali Abbadi, Ghada Awad Altarawneh, and Ahmad Ali Alhasanat. 2014. Solving the problem of the K parameter in the KNN classifier using an ensemble learning approach. CoRR abs\/1409.0919 (2014), 33\u201339. arxiv:1409.0919http:\/\/arxiv.org\/abs\/1409.0919.","journal-title":"CoRR"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594545"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.5555\/2976456.2976532"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3287560.3287578"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1098\/rsif.2005.0051"},{"issue":"1","key":"e_1_3_3_49_2","first-page":"237","article-title":"Human decisions and machine predictions","volume":"133","author":"Kleinberg Jon","year":"2017","unstructured":"Jon Kleinberg, Himabindu Lakkaraju, Jure Leskovec, Jens Ludwig, and Sendhil Mullainathan. 2017. Human decisions and machine predictions. The Quarterly Journal of Economics 133, 1 (2017), 237\u2013293.","journal-title":"The Quarterly Journal of Economics"},{"key":"e_1_3_3_50_2","first-page":"3458","volume-title":"Proceedings of the 36th International Conference on Machine Learning (Proceedings of Machine Learning Research)","volume":"97","author":"Kleindessner Matth\u00e4us","year":"2019","unstructured":"Matth\u00e4us Kleindessner, Samira Samadi, Pranjal Awasthi, and Jamie Morgenstern. 2019. Guarantees for spectral clustering with fairness constraints. In Proceedings of the 36th International Conference on Machine Learning (Proceedings of Machine Learning Research), Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.), Vol. 97. PMLR, Long Beach, California, USA, 3458\u20133467. http:\/\/proceedings.mlr.press\/v97\/kleindessner19b.html."},{"key":"e_1_3_3_51_2","volume-title":"The Art of Computer Programming, Volume II: Seminumerical Algorithms, 3rd Edition","author":"Knuth Donald Ervin","year":"1998","unstructured":"Donald Ervin Knuth. 1998. The Art of Computer Programming, Volume II: Seminumerical Algorithms, 3rd Edition. Addison-Wesley, Boston, MA. https:\/\/www.worldcat.org\/oclc\/312898417."},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2009.263"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.spl.2012.05.017"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/5.726791"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/3184558.3186949"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772759"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020488"},{"key":"e_1_3_3_58_2","unstructured":"Executive Office of the President. 2016. Big Data: A Report on Algorithmic Systems Opportunity and Civil Rights. (2016)."},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.3301663"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00140664"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00140665"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/D14-1162"},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","DOI":"10.5555\/3295222.3295319"},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2008.79"},{"key":"e_1_3_3_65_2","unstructured":"M. Sadegh Riazi Beidi Chen Anshumali Shrivastava Dan S. Wallach and Farinaz Koushanfar. 2016. Sub-Linear Privacy-Preserving Near-Neighbor Search with Untrusted Server on Large-Scale Datasets. (2016). ArXiv:1612.01835."},{"key":"e_1_3_3_66_2","doi-asserted-by":"publisher","DOI":"10.1145\/3287560.3287598"},{"key":"e_1_3_3_67_2","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/4908.001.0001"},{"key":"e_1_3_3_68_2","doi-asserted-by":"publisher","DOI":"10.1006\/jmva.1998.1784"},{"key":"e_1_3_3_69_2","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2011.5995347"},{"key":"e_1_3_3_70_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"e_1_3_3_71_2","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052660"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3502867","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3502867","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:34Z","timestamp":1750188634000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3502867"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,31]]},"references-count":70,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3,31]]}},"alternative-id":["10.1145\/3502867"],"URL":"https:\/\/doi.org\/10.1145\/3502867","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,31]]},"assertion":[{"value":"2021-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-04-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}