{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T07:13:41Z","timestamp":1784099621913,"version":"3.55.0"},"reference-count":77,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,5]]},"abstract":"<jats:p>Approximate Nearest Neighbor (ANN) search is a fundamental algorithmic problem, with numerous applications in many areas of computer science. In this work, we propose<jats:italic>indexable distance estimating codes (iDEC)<\/jats:italic>, a new solution framework to ANN that extends and improves the locality sensitive hashing (LSH) framework in a fundamental and systematic way. Empirically, an iDEC-based solution has a low index space complexity of<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>) and can achieve a low average query time complexity of approximately<jats:italic>O<\/jats:italic>(log<jats:italic>n<\/jats:italic>). We show that our iDEC-based solutions for ANN in Hamming and edit distances outperform the respective state-of-the-art LSH-based solutions for both in-memory and external-memory processing. We also show that our iDEC-based in-memory ANN-H solution is more scalable than all existing solutions. We also discover deep connections between Error-Estimating Codes (EEC), LSH, and iDEC.<\/jats:p>","DOI":"10.14778\/3397230.3397243","type":"journal-article","created":{"date-parts":[[2020,6,29]],"date-time":"2020-06-29T11:46:24Z","timestamp":1593431184000},"page":"1483-1497","source":"Crossref","is-referenced-by-count":32,"title":["iDEC"],"prefix":"10.14778","volume":"13","author":[{"given":"Long","family":"Gong","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Huayi","family":"Wang","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mitsunori","family":"Ogihara","sequence":"additional","affiliation":[{"name":"University of Miami"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jun","family":"Xu","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,26]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"http:\/\/man7.org\/linux\/man-pages\/man2\/getrusage.2.html. http:\/\/man7.org\/linux\/man-pages\/man2\/getrusage.2.html."},{"key":"e_1_2_1_2_1","unstructured":"https:\/\/www.mathworks.com\/help\/matlab\/ref\/profile.html. https:\/\/www.mathworks.com\/help\/matlab\/ref\/profile.html."},{"key":"e_1_2_1_3_1","unstructured":"Annoy: Approximate nearest neighbors in C++\/Python optimized for memory usage and loading\/saving to disk. https:\/\/github.com\/spotify\/annoy. Annoy: Approximate nearest neighbors in C++\/Python optimized for memory usage and loading\/saving to disk. https:\/\/github.com\/spotify\/annoy."},{"key":"e_1_2_1_4_1","unstructured":"Datasets for approximate nearest neighbor search. http:\/\/corpus-texmex.irisa.fr\/. Datasets for approximate nearest neighbor search. http:\/\/corpus-texmex.irisa.fr\/."},{"key":"e_1_2_1_5_1","unstructured":"Enron email dataset. http:\/\/www.cs.cmu.edu\/~enron\/. Enron email dataset. http:\/\/www.cs.cmu.edu\/~enron\/."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00025-4"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"A. Andoni P. Indyk and I. P. Razenshteyn. Approximate nearest neighbor search in high dimensions. CoRR abs\/1806.09823 2018. A. Andoni P. Indyk and I. P. Razenshteyn. Approximate nearest neighbor search in high dimensions. CoRR abs\/1806.09823 2018.","DOI":"10.1142\/9789813272880_0182"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3204028.3204034"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-68474-1_3"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2012.6248038"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060840"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_2_1_15_1","unstructured":"J. L. Blanco and P. K. Rai. nanoflann: a C++11 header-only library for nearest neighbor (NN) search with KD-trees. https:\/\/github.com\/jlblancoc\/nanoflann 2014. J. L. Blanco and P. K. Rai. nanoflann: a C++11 header-only library for nearest neighbor (NN) search with KD-trees. https:\/\/github.com\/jlblancoc\/nanoflann 2014."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/17.5.419"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1291233.1291466"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897577"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509965"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851182.1851186"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/177424.177609"},{"key":"e_1_2_1_22_1","unstructured":"T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. Introduction to Algorithms Third Edition. The MIT Press 3rd edition 2009. T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. Introduction to Algorithms Third Edition. The MIT Press 3rd edition 2009."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_1_24_1","unstructured":"DBWangGroupUNSW. SRS - fast approximate nearest neighbor search in high dimensional euclidean space with a tiny index. https:\/\/github.com\/DBWangGroupUNSW\/SRS. DBWangGroupUNSW. SRS - fast approximate nearest neighbor search in high dimensional euclidean space with a tiny index. https:\/\/github.com\/DBWangGroupUNSW\/SRS."},{"issue":"3","key":"e_1_2_1_25_1","first-page":"403","article-title":"Return of the Lernaean Hydra: experimental evaluation of data series approximate similarity search","volume":"13","author":"Echihabi K.","year":"2020","journal-title":"PVLDB"},{"key":"e_1_2_1_26_1","unstructured":"R. Elmasri and S. Navathe. Fundamentals of Database Systems. Addison-Wesley Publishing Company USA 6th edition 2010. R. Elmasri and S. Navathe. Fundamentals of Database Systems. Addison-Wesley Publishing Company USA 6th edition 2010."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799361701"},{"key":"e_1_2_1_28_1","unstructured":"R. Fergus A. Torralba and W. T. Freeman. Tiny images dataset. http:\/\/horatio.cs.nyu.edu\/mit\/tiny\/data\/index.html. R. Fergus A. Torralba and W. T. Freeman. Tiny images dataset. http:\/\/horatio.cs.nyu.edu\/mit\/tiny\/data\/index.html."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/355744.355745"},{"key":"e_1_2_1_30_1","unstructured":"C. Fu C. Wang and D. Cai. Satellite system graph: Towards the efficiency up-boundary of graph-based approximate nearest neighbor search. CoRR abs\/1907.06146 2019. C. Fu C. Wang and D. Cai. Satellite system graph: Towards the efficiency up-boundary of graph-based approximate nearest neighbor search. CoRR abs\/1907.06146 2019."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303754"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213898"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2013.379"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.720541"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.616"},{"key":"e_1_2_1_37_1","first-page":"235","volume-title":"Proceedings of the IEEE International Conference on Computer Communications","author":"Hua N.","year":"2012"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254756.2254773"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591971.2591976"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850470"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_42_1","first-page":"13771","volume-title":"Advances in Neural Information Processing Systems 32","author":"Jayaram Subramanya S.","year":"2019"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2019.2921572"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2348283.2348293"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/2078331.2078340"},{"key":"e_1_2_1_46_1","article-title":"Approximate nearest neighbor search on high dimensional data - experiments, analyses, and improvement","author":"Li W.","year":"2019","journal-title":"IEEE Transactions on Knowledge and Data Engineering, pages 1--1"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPRW.2015.7301269"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00169"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732947"},{"key":"e_1_2_1_50_1","first-page":"950","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Lv Q.","year":"2007"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242592"},{"key":"e_1_2_1_53_1","volume-title":"Springer Publishing Company","author":"Manolopoulos Y.","year":"2005"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2014.2321376"},{"key":"e_1_2_1_55_1","doi-asserted-by":"crossref","unstructured":"S. Muthukrishnan. Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science 1(2) 2005. S. Muthukrishnan. Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science 1(2) 2005.","DOI":"10.1561\/0400000002"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2568012"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2012.6248043"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2578221"},{"key":"e_1_2_1_59_1","volume-title":"International Computer Science Institute","author":"Omohundro S. M.","year":"1989"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109688"},{"key":"e_1_2_1_61_1","unstructured":"J. Pennington R. Socher and C. D. Manning. GloVe: Global vectors for word representation. https:\/\/nlp.stanford.edu\/projects\/glove\/. J. Pennington R. Socher and C. D. Manning. GloVe: Global vectors for word representation. https:\/\/nlp.stanford.edu\/projects\/glove\/."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2017.2760458"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.5555\/2124405"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236214"},{"key":"e_1_2_1_65_1","volume-title":"Springer Science & Business Media","author":"Sagan H.","year":"2012"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063737"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btw753"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735462"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806907.1806912"},{"key":"e_1_2_1_70_1","volume-title":"American Mathematical Soc.","author":"Vempala S. S.","year":"2005"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/1254882.1254900"},{"key":"e_1_2_1_72_1","unstructured":"L. Yann C. Corinna and J. B. Christopher. The MNIST database of handwritten digits. http:\/\/yann.lecun.com\/exdb\/mnist\/. L. Yann C. Corinna and J. B. Christopher. The MNIST database of handwritten digits. http:\/\/yann.lecun.com\/exdb\/mnist\/."},{"key":"e_1_2_1_73_1","doi-asserted-by":"crossref","unstructured":"A. C.-C. Yao. Some complexity questions related to distributive computing (preliminary report). pages 209--213 Atlanta Georgia USA Apr. 1979. A. C.-C. Yao. Some complexity questions related to distributive computing (preliminary report). pages 209--213 Atlanta Georgia USA Apr. 1979.","DOI":"10.1145\/800135.804414"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.5555\/313559.313789"},{"key":"e_1_2_1_75_1","unstructured":"H. Zhang. String datasets. https:\/\/iu.box.com\/s\/x7hg7uxj7xmmcdvc62k7iux9txtt9doi. H. Zhang. String datasets. https:\/\/iu.box.com\/s\/x7hg7uxj7xmmcdvc62k7iux9txtt9doi."},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098003"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2017.8057134"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3397230.3397243","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T18:12:56Z","timestamp":1723140776000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3397230.3397243"}},"subtitle":["indexable distance estimating codes for approximate nearest neighbor search"],"short-title":[],"issued":{"date-parts":[[2020,5]]},"references-count":77,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["10.14778\/3397230.3397243"],"URL":"https:\/\/doi.org\/10.14778\/3397230.3397243","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,5]]}}}