{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:57Z","timestamp":1750220697374,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,14]],"date-time":"2020-06-14T00:00:00Z","timestamp":1592092800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"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"}]},{"DOI":"10.13039\/100014718","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CRII-1755791 and CCF-1910873"],"award-info":[{"award-number":["CRII-1755791 and CCF-1910873"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011199","name":"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":[[2020,6,14]]},"DOI":"10.1145\/3375395.3387649","type":"proceedings-article","created":{"date-parts":[[2020,5,29]],"date-time":"2020-05-29T15:10:29Z","timestamp":1590765029000},"page":"205-212","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["On the I\/O Complexity of the k-Nearest Neighbors Problem"],"prefix":"10.1145","author":[{"given":"Mayank","family":"Goswami","sequence":"first","affiliation":[{"name":"Queens College CUNY, Flushing, NY, USA"}]},{"given":"Riko","family":"Jacob","sequence":"additional","affiliation":[{"name":"IT University of Copenhagen, K\u00f8benhavn S, Denmark"}]},{"given":"Rasmus","family":"Pagh","sequence":"additional","affiliation":[{"name":"BARC and IT University of Copenhagen, K\u00f8benhavn S, Denmark"}]}],"member":"320","published-online":{"date-parts":[[2020,6,14]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_1_1_1","DOI":"10.1145\/2261250.2261301"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_2_1","DOI":"10.1109\/FOCS.2009.58"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_3_1","DOI":"10.1145\/48529.48535"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_4_1","DOI":"10.1109\/FOCS.2015.18"},{"key":"e_1_3_2_1_5_1","volume-title":"Approximate nearest neighbor search in high dimensions. arXiv preprint","author":"Andoni Alexandr","year":"1806","unstructured":"Alexandr Andoni , Piotr Indyk , and Ilya Razenshteyn . 2018. Approximate nearest neighbor search in high dimensions. arXiv preprint 1806 .09823 (2018). Also appears in proceedings of ICM 2018. Alexandr Andoni, Piotr Indyk, and Ilya Razenshteyn. 2018. Approximate nearest neighbor search in high dimensions. arXiv preprint 1806.09823 (2018). Also appears in proceedings of ICM 2018."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_6_1","DOI":"10.1137\/1.9781611974782.4"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_7_1","DOI":"10.1007\/s00453-007-9126-2"},{"key":"e_1_3_2_1_8_1","volume-title":"Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. 2055--2063","author":"Babenko Artem","year":"2016","unstructured":"Artem Babenko and Victor Lempitsky . 2016 . Efficient indexing of billion-scale datasets of deep descriptors . In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. 2055--2063 . Artem Babenko and Victor Lempitsky. 2016. Efficient indexing of billion-scale datasets of deep descriptors. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. 2055--2063."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_9_1","DOI":"10.1007\/978-3-319-10590-1_38"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_10_1","DOI":"10.1145\/2396761.2398596"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.1006\/jcss.2002.1831"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_12_1","DOI":"10.1145\/263661.263671"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_13_1","DOI":"10.1145\/301250.301330"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_14_1","DOI":"10.1109\/FOCS.2004.12"},{"key":"e_1_3_2_1_15_1","volume-title":"Proceedings of 25th International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, 518--529","author":"Gionis Aristides","year":"1999","unstructured":"Aristides Gionis , Piotr Indyk , and Rajeev Motwani . 1999 . Similarity Search in High Dimensions via Hashing . In Proceedings of 25th International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, 518--529 . http:\/\/www.vldb.org\/conf\/1999\/P49.pdf Aristides Gionis, Piotr Indyk, and Rajeev Motwani. 1999. Similarity Search in High Dimensions via Hashing. In Proceedings of 25th International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, 518--529. http:\/\/www.vldb.org\/conf\/1999\/P49.pdf"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_16_1","DOI":"10.4086\/toc.2012.v008a014"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_17_1","DOI":"10.1145\/505241.505244"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_18_1","DOI":"10.1145\/263661.263688"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.5555\/645921.673145"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_20_1","DOI":"10.1145\/2594538.2594545"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_21_1","DOI":"10.1145\/3311967"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_22_1","DOI":"10.1006\/jcss.2001.1781"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_23_1","DOI":"10.1145\/1250790.1250881"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_24_1","DOI":"10.1145\/2745754.2745761"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_25_1","DOI":"10.1137\/S0097539798347177"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_26_1","DOI":"10.1109\/FOCS.2017.64"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_27_1","DOI":"10.1137\/1.9781611973105.20"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_28_1","DOI":"10.1007\/BF02761110"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_29_1","DOI":"10.1109\/TPAMI.2014.2321376"},{"key":"e_1_3_2_1_30_1","volume-title":"One-Probe Search. In Proceedings of 29th international colloquium on automata, languages and programming (ICALP). 439--450","author":"\u00d6stlin Anna","year":"2002","unstructured":"Anna \u00d6stlin and Rasmus Pagh . 2002 . One-Probe Search. In Proceedings of 29th international colloquium on automata, languages and programming (ICALP). 439--450 . Anna \u00d6stlin and Rasmus Pagh. 2002. One-Probe Search. In Proceedings of 29th international colloquium on automata, languages and programming (ICALP). 439--450."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_31_1","DOI":"10.1109\/FOCS.2010.82"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_32_1","DOI":"10.1007\/s00453-012-9638-2"},{"key":"e_1_3_2_1_33_1","first-page":"367","article-title":"Indexing schemes for similarity search: An illustrated paradigm","volume":"70","author":"Pestov Vladimir","year":"2006","unstructured":"Vladimir Pestov and Aleksandar Stojmirovi\u0107 . 2006 . Indexing schemes for similarity search: An illustrated paradigm . Fundamenta Informaticae , Vol. 70 , 4 (2006), 367 -- 385 . Vladimir Pestov and Aleksandar Stojmirovi\u0107. 2006. Indexing schemes for similarity search: An illustrated paradigm. Fundamenta Informaticae, Vol. 70, 4 (2006), 367--385.","journal-title":"Fundamenta Informaticae"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_34_1","DOI":"10.1145\/3188745.3188916"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_35_1","DOI":"10.5555\/3118734.3118825"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_36_1","DOI":"10.1145\/1806907.1806912"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_37_1","DOI":"10.1145\/1583991.1584055"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_38_1","DOI":"10.1145\/1559795.1559825"}],"event":{"sponsor":["SIGMOD ACM Special Interest Group on Management of Data"],"acronym":"SIGMOD\/PODS '20","name":"SIGMOD\/PODS '20: International Conference on Management of Data","location":"Portland OR USA"},"container-title":["Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3375395.3387649","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3375395.3387649","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:32:48Z","timestamp":1750199568000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3375395.3387649"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,14]]},"references-count":38,"alternative-id":["10.1145\/3375395.3387649","10.1145\/3375395"],"URL":"https:\/\/doi.org\/10.1145\/3375395.3387649","relation":{},"subject":[],"published":{"date-parts":[[2020,6,14]]},"assertion":[{"value":"2020-06-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}