{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T12:00:29Z","timestamp":1792756829596,"version":"4.5.0"},"publisher-location":"New York, NY, USA","reference-count":55,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,5,31]],"date-time":"2020-05-31T00:00:00Z","timestamp":1590883200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100007515","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1700521"],"award-info":[{"award-number":["1700521"]}],"id":[{"id":"10.13039\/100007515","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,11]]},"DOI":"10.1145\/3318464.3380600","type":"proceedings-article","created":{"date-parts":[[2020,5,29]],"date-time":"2020-05-29T17:12:33Z","timestamp":1590772353000},"page":"2539-2554","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":91,"title":["Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination"],"prefix":"10.1145","author":[{"given":"Conglong","family":"Li","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Minjia","family":"Zhang","sequence":"additional","affiliation":[{"name":"Microsoft AI and Research, Bellevue, WA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David G.","family":"Andersen","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuxiong","family":"He","sequence":"additional","affiliation":[{"name":"Microsoft AI and Research, Bellevue, WA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,5,31]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Additive Quantization for Extreme Vector Compression. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 931--938","author":"Babenko Artem","year":"2014","unstructured":"Artem Babenko and Victor Lempitsky . 2014 . Additive Quantization for Extreme Vector Compression. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 931--938 . Artem Babenko and Victor Lempitsky. 2014. Additive Quantization for Extreme Vector Compression. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 931--938."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2014.2361319"},{"key":"e_1_3_2_2_3_1","volume-title":"Efficient Indexing of Billion-Scale Datasets of Deep Descriptors. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2055--2063","author":"Babenko Artem","year":"2016","unstructured":"Artem Babenko and Victor Lempitsky . 2016 . Efficient Indexing of Billion-Scale Datasets of Deep Descriptors. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2055--2063 . Artem Babenko and Victor Lempitsky. 2016. Efficient Indexing of Billion-Scale Datasets of Deep Descriptors. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2055--2063."},{"key":"e_1_3_2_2_4_1","volume-title":"Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors. In European Conference on Computer Vision (ECCV). 202--216","author":"Baranchuk Dmitry","year":"2018","unstructured":"Dmitry Baranchuk , Artem Babenko , and Yury Malkov . 2018 . Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors. In European Conference on Computer Vision (ECCV). 202--216 . Dmitry Baranchuk, Artem Babenko, and Yury Malkov. 2018. Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors. In European Conference on Computer Vision (ECCV). 202--216."},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1038\/nbt.3238"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49257-7_15"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502809"},{"key":"e_1_3_2_2_8_1","volume-title":"The Hybrid Tree: An Index Structure for High Dimensional Feature Spaces. In International Conference on Data Engineering (ICDE). 440--447","author":"Chakrabarti Kaushik","year":"1999","unstructured":"Kaushik Chakrabarti and Sharad Mehrotra . 1999 . The Hybrid Tree: An Index Structure for High Dimensional Feature Spaces. In International Conference on Data Engineering (ICDE). 440--447 . Kaushik Chakrabarti and Sharad Mehrotra. 1999. The Hybrid Tree: An Index Structure for High Dimensional Feature Spaces. In International Conference on Data Engineering (ICDE). 440--447."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509965"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.3390\/s101211259"},{"key":"e_1_3_2_2_11_1","volume-title":"PAC Nearest Neighbor Queries: Approximate and Controlled Search in High-Dimensional and Metric Spaces. In International Conference on Data Engineering (ICDE). 244--255","author":"Ciaccia Paolo","year":"2000","unstructured":"Paolo Ciaccia and Marco Patella . 2000 . PAC Nearest Neighbor Queries: Approximate and Controlled Search in High-Dimensional and Metric Spaces. In International Conference on Data Engineering (ICDE). 244--255 . Paolo Ciaccia and Marco Patella. 2000. PAC Nearest Neighbor Queries: Approximate and Controlled Search in High-Dimensional and Metric Spaces. In International Conference on Data Engineering (ICDE). 244--255."},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242610"},{"key":"e_1_3_2_2_13_1","volume-title":"Proceedings of the 20th Annual Symposium on Computational Geometry (SCG). 253--262","author":"Datar Mayur","unstructured":"Mayur Datar , Nicole Immorlica , Piotr Indyk , and Vahab S. Mirrokni . 2004. Locality-Sensitive Hashing Scheme Based on p-Stable Distributions . In Proceedings of the 20th Annual Symposium on Computational Geometry (SCG). 253--262 . Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. 2004. Locality-Sensitive Hashing Scheme Based on p-Stable Distributions. In Proceedings of the 20th Annual Symposium on Computational Geometry (SCG). 253--262."},{"key":"e_1_3_2_2_14_1","volume-title":"Link and Code: Fast Indexing With Graphs and Compact Regression Codes. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 3646--3654","author":"Douze Matthijs","year":"2018","unstructured":"Matthijs Douze , Alexandre Sablayrolles , and Herv\u00e9 J\u00e9gou . 2018 . Link and Code: Fast Indexing With Graphs and Compact Regression Codes. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 3646--3654 . Matthijs Douze, Alexandre Sablayrolles, and Herv\u00e9 J\u00e9gou. 2018. Link and Code: Fast Indexing With Graphs and Compact Regression Codes. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 3646--3654."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1013203451"},{"key":"e_1_3_2_2_16_1","volume-title":"EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph. arXiv preprint arXiv:1609.07228","author":"Fu Cong","year":"2016","unstructured":"Cong Fu and Deng Cai . 2016 . EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph. arXiv preprint arXiv:1609.07228 (2016). Cong Fu and Deng Cai. 2016. EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph. arXiv preprint arXiv:1609.07228 (2016)."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303754"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783284"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588565"},{"key":"e_1_3_2_2_20_1","volume-title":"Optimized Product Quantization for Approximate Nearest Neighbor Search. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2946--2953","author":"Ge Tiezheng","year":"2013","unstructured":"Tiezheng Ge , Kaiming He , Qifa Ke , and Jian Sun . 2013 . Optimized Product Quantization for Approximate Nearest Neighbor Search. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2946--2953 . Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013. Optimized Product Quantization for Approximate Nearest Neighbor Search. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2946--2953."},{"key":"e_1_3_2_2_21_1","volume-title":"Progressive Similarity Search on Time Series Data. In International Workshop on Big Data Visual Exploration and Analytics (BigVis). 1--1.","author":"Gogolou Anna","year":"2019","unstructured":"Anna Gogolou , Theophanis Tsandilas , Themis Palpanas , and Anastasia Bezerianos . 2019 . Progressive Similarity Search on Time Series Data. In International Workshop on Big Data Visual Exploration and Analytics (BigVis). 1--1. Anna Gogolou, Theophanis Tsandilas, Themis Palpanas, and Anastasia Bezerianos. 2019. Progressive Similarity Search on Time Series Data. In International Workshop on Big Data Visual Exploration and Analytics (BigVis). 1--1."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2011.5995432"},{"key":"e_1_3_2_2_23_1","volume-title":"Asymmetric Distances for Binary Embeddings. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 729--736","author":"Gordo Albert","year":"2011","unstructured":"Albert Gordo and Florent Perronnin . 2011 . Asymmetric Distances for Binary Embeddings. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 729--736 . Albert Gordo and Florent Perronnin. 2011. Asymmetric Distances for Binary Embeddings. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 729--736."},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375800"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2396832"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850470"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_3_2_2_28_1","volume-title":"Structured Binary Code for Image Search. In IEEE International Conference on Computer Vision (ICCV). 833--842","author":"Jain Himalaya","year":"2017","unstructured":"Himalaya Jain , Joaquin Zepeda , Patrick P\u00e9rez , and R\u00e9mi Gribonval . 2017 . SUBIC: A Supervised , Structured Binary Code for Image Search. In IEEE International Conference on Computer Vision (ICCV). 833--842 . Himalaya Jain, Joaquin Zepeda, Patrick P\u00e9rez, and R\u00e9mi Gribonval. 2017. SUBIC: A Supervised, Structured Binary Code for Image Search. In IEEE International Conference on Computer Vision (ICCV). 833--842."},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_3_2_2_30_1","volume-title":"Searching in One Billion Vectors: Re-rank with Source Coding. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). 861--864","author":"J\u00e9gou Herv\u00e9","year":"2011","unstructured":"Herv\u00e9 J\u00e9gou , Romain Tavenard , Matthijs Douze , and Laurent Amsaleg . 2011 b. Searching in One Billion Vectors: Re-rank with Source Coding. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). 861--864 . Herv\u00e9 J\u00e9gou, Romain Tavenard, Matthijs Douze, and Laurent Amsaleg. 2011b. Searching in One Billion Vectors: Re-rank with Source Coding. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). 861--864."},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2019.2921572"},{"key":"e_1_3_2_2_32_1","unstructured":"Guolin Ke Qi Meng Thomas Finley Taifeng Wang Wei Chen Weidong Ma Qiwei Ye and Tie-Yan Liu. 2017. LightGBM: A Highly Efficient Gradient Boosting Decision Tree. In Advances in Neural Information Processing Systems (NIPS). 3146--3154.  Guolin Ke Qi Meng Thomas Finley Taifeng Wang Wei Chen Weidong Ma Qiwei Ye and Tie-Yan Liu. 2017. LightGBM: A Highly Efficient Gradient Boosting Decision Tree. In Advances in Neural Information Processing Systems (NIPS). 3146--3154."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3240493"},{"key":"e_1_3_2_2_34_1","volume-title":"Kernelized Locality-Sensitive Hashing for Scalable Image Search. In IEEE International Conference on Computer Vision (ICCV). 2130--2137","author":"Kulis Brian","year":"2009","unstructured":"Brian Kulis and Kristen Grauman . 2009 . Kernelized Locality-Sensitive Hashing for Scalable Image Search. In IEEE International Conference on Computer Vision (ICCV). 2130--2137 . Brian Kulis and Kristen Grauman. 2009. Kernelized Locality-Sensitive Hashing for Scalable Image Search. In IEEE International Conference on Computer Vision (ICCV). 2130--2137."},{"key":"e_1_3_2_2_35_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning (ICML). 3773--3781","author":"Lei Yifan","year":"2019","unstructured":"Yifan Lei , Qiang Huang , Mohan Kankanhalli , and Anthony Tung . 2019 . Sublinear Time Nearest Neighbor Search over Generalized Weighted Space . In Proceedings of the 36th International Conference on Machine Learning (ICML). 3773--3781 . Yifan Lei, Qiang Huang, Mohan Kankanhalli, and Anthony Tung. 2019. Sublinear Time Nearest Neighbor Search over Generalized Weighted Space. In Proceedings of the 36th International Conference on Machine Learning (ICML). 3773--3781."},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3127479.3129255"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186176"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031171.1031213"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.006"},{"key":"e_1_3_2_2_40_1","volume-title":"Yashunin","author":"Malkov Yury A.","year":"2018","unstructured":"Yury A. Malkov and Dmitry A . Yashunin . 2018 . Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence ( 2018), 1--1. Yury A. Malkov and Dmitry A. Yashunin. 2018. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence (2018), 1--1."},{"key":"e_1_3_2_2_41_1","volume-title":"Introduction to Information Retrieval","author":"Manning Christopher D.","unstructured":"Christopher D. Manning , Prabhakar Raghavan , and Hinrich Sch\u00fctze . 2008. Introduction to Information Retrieval . Cambridge University Press . Christopher D. Manning, Prabhakar Raghavan, and Hinrich Sch\u00fctze. 2008. Introduction to Information Retrieval. Cambridge University Press."},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850589"},{"key":"e_1_3_2_2_43_1","volume-title":"Object Retrieval with Large Vocabularies and Fast Spatial Matching. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 1--8.","author":"Philbin James","year":"2007","unstructured":"James Philbin , Ondrej Chum , Michael Isard , Josef Sivic , and Andrew Zisserman . 2007 . Object Retrieval with Large Vocabularies and Fast Spatial Matching. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 1--8. James Philbin, Ondrej Chum, Michael Isard, Josef Sivic, and Andrew Zisserman. 2007. Object Retrieval with Large Vocabularies and Fast Spatial Matching. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 1--8."},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223794"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2003.1238663"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2016.2598470"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2393347.2393378"},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2012.6247790"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2013.125"},{"key":"e_1_3_2_2_50_1","volume-title":"Proceedings of the 24th VLDB Conference. 194--205","author":"Weber Roger","year":"1998","unstructured":"Roger Weber , Hans-J\u00f6rg Schek , and Stephen Blott . 1998 . A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces . In Proceedings of the 24th VLDB Conference. 194--205 . Roger Weber, Hans-J\u00f6rg Schek, and Stephen Blott. 1998. A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces. In Proceedings of the 24th VLDB Conference. 194--205."},{"key":"e_1_3_2_2_51_1","volume-title":"Sanjiv Kumar, Daniel N. Holtmann-Rice, David Simcha, and Felix Yu.","author":"Wu Xiang","year":"2017","unstructured":"Xiang Wu , Ruiqi Guo , Ananda Theertha Suresh , Sanjiv Kumar, Daniel N. Holtmann-Rice, David Simcha, and Felix Yu. 2017 . Multiscale Quantization for Fast Similarity Search. In Advances in Neural Information Processing Systems (NIPS) . 5745--5755. Xiang Wu, Ruiqi Guo, Ananda Theertha Suresh, Sanjiv Kumar, Daniel N. Holtmann-Rice, David Simcha, and Felix Yu. 2017. Multiscale Quantization for Fast Similarity Search. In Advances in Neural Information Processing Systems (NIPS). 5745--5755."},{"key":"e_1_3_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3357938"},{"key":"e_1_3_2_2_53_1","volume-title":"Sparse Composite Quantization. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 4548--4556","author":"Zhang Ting","year":"2015","unstructured":"Ting Zhang , Guo-Jun Qi , Jinhui Tang , and Jingdong Wang . 2015 . Sparse Composite Quantization. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 4548--4556 . Ting Zhang, Guo-Jun Qi, Jinhui Tang, and Jingdong Wang. 2015. Sparse Composite Quantization. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 4548--4556."},{"key":"e_1_3_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882930"},{"key":"e_1_3_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00085"}],"event":{"name":"SIGMOD\/PODS '20: International Conference on Management of Data","location":"Portland OR USA","acronym":"SIGMOD\/PODS '20","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3318464.3380600","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3318464.3380600","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:23Z","timestamp":1750199903000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3318464.3380600"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,31]]},"references-count":55,"alternative-id":["10.1145\/3318464.3380600","10.1145\/3318464"],"URL":"https:\/\/doi.org\/10.1145\/3318464.3380600","relation":{},"subject":[],"published":{"date-parts":[[2020,5,31]]},"assertion":[{"value":"2020-05-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}