{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,7]],"date-time":"2026-08-07T11:00:21Z","timestamp":1786100421301,"version":"3.56.0"},"publisher-location":"New York, NY, USA","reference-count":55,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,5,27]],"date-time":"2018-05-27T00:00:00Z","timestamp":1527379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100011199","name":"FP7 Ideas: European Research Council","doi-asserted-by":"publisher","award":["614331"],"award-info":[{"award-number":["614331"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,5,27]]},"DOI":"10.1145\/3196959.3196976","type":"proceedings-article","created":{"date-parts":[[2018,5,15]],"date-time":"2018-05-15T12:26:14Z","timestamp":1526387174000},"page":"89-104","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Distance-Sensitive Hashing"],"prefix":"10.1145","author":[{"given":"Martin","family":"Aum\u00fcller","sequence":"first","affiliation":[{"name":"BARC &amp; IT University of Copenhagen, Copenhagen, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tobias","family":"Christiani","sequence":"additional","affiliation":[{"name":"BARC &amp; IT University of Copenhagen, Copenhagen, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rasmus","family":"Pagh","sequence":"additional","affiliation":[{"name":"BARC &amp; IT 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":[[2018,5,27]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2462356.2462401"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3092931.3092933"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375602"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039702"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902285"},{"key":"e_1_3_2_1_6_1","volume-title":"Handbook of Discrete and Computational Geometry","author":"Alexandr Andoni Piotr Indyk","unstructured":"Piotr Indyk Alexandr Andoni . 2017. Nearest Neighbors in High-Dimensional Spaces . In Handbook of Discrete and Computational Geometry , Third Edition. Chapman and Hall\/CRC , 1133--1153. Piotr Indyk Alexandr Andoni. 2017. Nearest Neighbors in High-Dimensional Spaces. In Handbook of Discrete and Computational Geometry, Third Edition. Chapman and Hall\/CRC, 1133--1153."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.49"},{"key":"e_1_3_2_1_8_1","volume-title":"Proc. 28th Int. Conference on Neural Information Processing Systems (NIPS). 1225--1233","author":"Andoni Alexandr","year":"2015","unstructured":"Alexandr Andoni , Piotr Indyk , Thijs Laarhoven , Ilya Razenshteyn , and Ludwig Schmidt . 2015 . Practical and Optimal LSH for Angular Distance . In Proc. 28th Int. Conference on Neural Information Processing Systems (NIPS). 1225--1233 . Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. 2015. Practical and Optimal LSH for Angular Distance. In Proc. 28th Int. Conference on Neural Information Processing Systems (NIPS). 1225--1233."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634150"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039690"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746553"},{"key":"e_1_3_2_1_12_1","first-page":"1","article-title":"Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing. In Proc. 32nd Int","volume":"9","author":"Andoni Alexandr","year":"2016","unstructured":"Alexandr Andoni and Ilya P. Razenshteyn . 2016 . Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing. In Proc. 32nd Int . Symposium on Computational Geometry (SoCG). 9 : 1 -- 9 :11. Alexandr Andoni and Ilya P. Razenshteyn. 2016. Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing. In Proc. 32nd Int. Symposium on Computational Geometry (SoCG). 9:1--9:11.","journal-title":"Symposium on Computational Geometry (SoCG)."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/2601748"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884437"},{"key":"e_1_3_2_1_15_1","volume-title":"Proc. Compression and Complexity of Sequences. 21--29","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. 21--29 . Andrei Z. Broder. 1997. On the resemblance and containment of documents. In Proc. Compression and Complexity of Sequences. 21--29."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(97)00031-7"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509965"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816813"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.02.030"},{"key":"e_1_3_2_1_20_1","volume-title":"Proc. Conference on Innovations in Theoretical Computer Science (ITCS).","author":"Chierichetti Flavio","year":"2017","unstructured":"Flavio Chierichetti , Alessandro Panconesi , Ravi Kumar , and Erisa Terolli . 2017 . The Distortion of Locality Sensitive Hashing . In Proc. Conference on Innovations in Theoretical Computer Science (ITCS). Flavio Chierichetti, Alessandro Panconesi, Ravi Kumar, and Erisa Terolli. 2017. The Distortion of Locality Sensitive Hashing. In Proc. Conference on Innovations in Theoretical Computer Science (ITCS)."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039689"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055443"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_3_2_1_24_1","first-page":"213","article-title":"Linear-Complexity Private Set Intersection Protocols Secure in Malicious Model","volume":"6477","author":"Cristofaro Emiliano De","year":"2010","unstructured":"Emiliano De Cristofaro , Jihye Kim , and Gene Tsudik . 2010 . Linear-Complexity Private Set Intersection Protocols Secure in Malicious Model . In Asiacrypt , Vol. 6477. 213 -- 231 . Emiliano De Cristofaro, Jihye Kim, and Gene Tsudik. 2010. Linear-Complexity Private Set Intersection Protocols Secure in Malicious Model. In Asiacrypt, Vol. 6477. 213--231.","journal-title":"Asiacrypt"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-4571(199009)41:6<391::AID-ASI1>3.0.CO;2-9"},{"key":"e_1_3_2_1_26_1","unstructured":"fedja (https:\/\/mathoverflow.net\/users\/1131\/fedja). 2018. Inequality for the inner product in the probabilistic simplex. MathOverflow. (2018). URL:https:\/\/mathoverflow.net\/q\/296027 (version: 2018-03--24).  fedja (https:\/\/mathoverflow.net\/users\/1131\/fedja). 2018. Inequality for the inner product in the probabilistic simplex. MathOverflow. (2018). URL:https:\/\/mathoverflow.net\/q\/296027 (version: 2018-03--24)."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24676-3_1"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/645925.671516"},{"key":"e_1_3_2_1_29_1","volume-title":"Foundations of cryptography","author":"Goldreich Oded","unstructured":"Oded Goldreich . 2009. Foundations of cryptography : volume 2 , basic applications. Cambridge University Press . Oded Goldreich. 2009. Foundations of cryptography: volume 2, basic applications. Cambridge University Press."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a014"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056110"},{"key":"e_1_3_2_1_32_1","volume-title":"Proc. 14th Symposium on Discrete Algorithms (SODA). 539--545","author":"Indyk Piotr","year":"2003","unstructured":"Piotr Indyk . 2003 . Better Algorithms for High-dimensional Proximity Problems via Asymmetric Embeddings . In Proc. 14th Symposium on Discrete Algorithms (SODA). 539--545 . Piotr Indyk. 2003. Better Algorithms for High-dimensional Proximity Problems via Asymmetric Embeddings. In Proc. 14th Symposium on Discrete Algorithms (SODA). 539--545."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_3_2_1_34_1","volume-title":"Proc. Conference on Neural Information Processing Systems (NIPS).","author":"Jain Prateek","year":"2010","unstructured":"Prateek Jain , Sudheendra Vijayanarasimhan , and Kristen Grauman . 2010 . Hashing Hyperplane Queries to Near Points with Applications to Large-Scale Active Learning . In Proc. Conference on Neural Information Processing Systems (NIPS). Prateek Jain, Sudheendra Vijayanarasimhan, and Kristen Grauman. 2010. Hashing Hyperplane Queries to Near Points with Applications to Large-Scale Active Learning. In Proc. Conference on Neural Information Processing Systems (NIPS)."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745761"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009282"},{"key":"e_1_3_2_1_37_1","volume-title":"Proc. Conference on Machine Learning (ICML).","author":"Liu Wei","year":"2012","unstructured":"Wei Liu , Jun Wang , Yadong Mu , Sanjiv Kumar , and Shih-Fu Chang . 2012 . Compact Hyperplane Hashing with Bilinear Functions . In Proc. Conference on Machine Learning (ICML). Wei Liu, Jun Wang, Yadong Mu, Sanjiv Kumar, and Shih-Fu Chang. 2012. Compact Hyperplane Hashing with Bilinear Functions. In Proc. Conference on Machine Learning (ICML)."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/050646858"},{"key":"e_1_3_2_1_39_1","volume-title":"Proc. 32nd Conference on Machine Learning (ICML). 1926--1934","author":"Neyshabur Behnam","year":"2015","unstructured":"Behnam Neyshabur and Nathan Srebro . 2015 . On Symmetric and Asymmetric LSHs for Inner Product Search . In Proc. 32nd Conference on Machine Learning (ICML). 1926--1934 . Behnam Neyshabur and Nathan Srebro. 2015. On Symmetric and Asymmetric LSHs for Inner Product Search. In Proc. 32nd Conference on Machine Learning (ICML). 1926--1934."},{"key":"e_1_3_2_1_40_1","volume-title":"Analysis of Boolean Functions","author":"O'Donnell Ryan","unstructured":"Ryan O'Donnell . 2014. Analysis of Boolean Functions . Cambridge University Press . Ryan O'Donnell. 2014. Analysis of Boolean Functions. Cambridge University Press."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2578221"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2016.07.006"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487591"},{"key":"e_1_3_2_1_44_1","unstructured":"Benny Pinkas Thomas Schneider Christian Weinert and Udi Wieder. 2017. Linear Size Circuit-based PSI via Two-Dimensional Cuckoo Hashing. (2017). Manuscript under submission.  Benny Pinkas Thomas Schneider Christian Weinert and Udi Wieder. 2017. Linear Size Circuit-based PSI via Two-Dimensional Cuckoo Hashing. (2017). Manuscript under submission."},{"key":"e_1_3_2_1_45_1","volume-title":"Proc. 21st Conference on Neural Information Processing Systems (NIPS). 1177--1184","author":"Rahimi Ali","year":"2007","unstructured":"Ali Rahimi and Benjamin Recht . 2007 . Random Features for Large-Scale Kernel Machines . In Proc. 21st Conference on Neural Information Processing Systems (NIPS). 1177--1184 . Ali Rahimi and Benjamin Recht. 2007. Random Features for Large-Scale Kernel Machines. In Proc. 21st Conference on Neural Information Processing Systems (NIPS). 1177--1184."},{"key":"e_1_3_2_1_46_1","first-page":"01835","article-title":"Sub-Linear Privacy-Preserving Near-Neighbor Search with Untrusted Server on Large-Scale Datasets. (2016)","volume":"1612","author":"Riazi M. Sadegh","year":"2016","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 . 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.","journal-title":"ArXiv"},{"key":"e_1_3_2_1_47_1","volume-title":"Fourier Analysis on Groups","author":"Rudin Walter","unstructured":"Walter Rudin . 1990. Fourier Analysis on Groups . Wiley , New York . Walter Rudin. 1990. Fourier Analysis on Groups. Wiley, New York."},{"key":"e_1_3_2_1_48_1","first-page":"93","article-title":"Mill's Ratio for Multivariate Normal Distributions","volume":"66","author":"Savage Richard I.","year":"1962","unstructured":"Richard I. Savage . 1962 . Mill's Ratio for Multivariate Normal Distributions . Jour. Res. NBS Math. Sci. 66 , 3 (1962), 93 -- 96 . Richard I. Savage. 1962. Mill's Ratio for Multivariate Normal Distributions. Jour. Res. NBS Math. Sci. 66, 3 (1962), 93--96.","journal-title":"Jour. Res. NBS Math. Sci."},{"key":"e_1_3_2_1_49_1","volume-title":"Proc. 27th Conference on Neural Information Processing Systems (NIPS). 2321--2329","author":"Shrivastava Anshumali","year":"2014","unstructured":"Anshumali Shrivastava and Ping Li . 2014 . Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) . In Proc. 27th Conference on Neural Information Processing Systems (NIPS). 2321--2329 . Anshumali Shrivastava and Ping Li. 2014. Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS). In Proc. 27th Conference on Neural Information Processing Systems (NIPS). 2321--2329."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447873"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1006\/jmva.1998.1784"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2728167"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2013.121"},{"key":"e_1_3_2_1_54_1","unstructured":"J. Wang H. T. Shen J. Song and J. Ji. 2014. Hashing for Similarity Search: A Survey. CoRR abs\/1408.2927 (2014). http:\/\/arxiv.org\/abs\/1408.2927  J. Wang H. T. Shen J. Song and J. Ji. 2014. Hashing for Similarity Search: A Survey. CoRR abs\/1408.2927 (2014). http:\/\/arxiv.org\/abs\/1408.2927"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098003"}],"event":{"name":"SIGMOD\/PODS '18: International Conference on Management of Data","location":"Houston TX USA","acronym":"SIGMOD\/PODS '18","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3196959.3196976","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3196959.3196976","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:34Z","timestamp":1750208914000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3196959.3196976"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,27]]},"references-count":55,"alternative-id":["10.1145\/3196959.3196976","10.1145\/3196959"],"URL":"https:\/\/doi.org\/10.1145\/3196959.3196976","relation":{},"subject":[],"published":{"date-parts":[[2018,5,27]]},"assertion":[{"value":"2018-05-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}