{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,5]],"date-time":"2026-09-05T01:09:55Z","timestamp":1788570595791,"version":"build-2803163510"},"reference-count":73,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,4]]},"abstract":"<jats:p>\n                    Nearest neighbor searching of large databases in high-dimensional spaces is inherently difficult due to the curse of dimensionality. A flavor of approximation is, therefore, necessary to practically solve the problem of nearest neighbor search. In this paper, we propose a novel yet simple indexing scheme,\n                    <jats:italic>HD-Index<\/jats:italic>\n                    , to solve the problem of\n                    <jats:italic>approximate k-nearest neighbor queries<\/jats:italic>\n                    in massive high-dimensional databases. HD-Index consists of a set of novel hierarchical structures called\n                    <jats:italic>RDB-trees<\/jats:italic>\n                    built on Hilbert keys of database objects. The leaves of the RDB-trees store distances of database objects to reference objects, thereby allowing efficient pruning using distance filters. In addition to triangular inequality, we also use Ptolemaic inequality to produce better lower bounds. Experiments on massive (up to billion scale) high-dimensional (up to 1000+) datasets show that HD-Index is\n                    <jats:italic>effective, efficient<\/jats:italic>\n                    , and\n                    <jats:italic>scalable.<\/jats:italic>\n                  <\/jats:p>","DOI":"10.14778\/3204028.3204034","type":"journal-article","created":{"date-parts":[[2018,5,22]],"date-time":"2018-05-22T15:56:10Z","timestamp":1527004570000},"page":"906-919","source":"Crossref","is-referenced-by-count":81,"title":["HD-index"],"prefix":"10.14778","volume":"11","author":[{"given":"Akhil","family":"Arora","sequence":"first","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sakshi","family":"Sinha","sequence":"additional","affiliation":[{"name":"Fresh Gravity Inc., Pune, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Piyush","family":"Kumar","sequence":"additional","affiliation":[{"name":"Visa Inc., Bangalore, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arnab","family":"Bhattacharya","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology, Kanpur, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Evaluation of approximate nearest neighbors: Large datasets. http:\/\/corpus-texmex.irisa.fr\/.  Evaluation of approximate nearest neighbors: Large datasets. http:\/\/corpus-texmex.irisa.fr\/."},{"key":"e_1_2_1_2_1","unstructured":"The CASS Project Repository. http:\/\/cs.princeton.edu\/cass\/audio.tar.gz.  The CASS Project Repository. http:\/\/cs.princeton.edu\/cass\/audio.tar.gz."},{"key":"e_1_2_1_3_1","unstructured":"The Enron Database. http:\/\/www.cs.cmu.edu\/enron\/.  The Enron Database. http:\/\/www.cs.cmu.edu\/enron\/."},{"key":"e_1_2_1_4_1","unstructured":"The Glove Database. https:\/\/nlp.stanford.edu\/projects\/glove\/.  The Glove Database. https:\/\/nlp.stanford.edu\/projects\/glove\/."},{"key":"e_1_2_1_5_1","unstructured":"The SUN Database. http:\/\/groups.csail.mit.edu\/vision\/SUN\/.  The SUN Database. http:\/\/groups.csail.mit.edu\/vision\/SUN\/."},{"key":"e_1_2_1_6_1","unstructured":"The Yorck Project. https:\/\/commons.wikimedia.org\/wiki\/Category:PD-Art_(Yorck_Project).  The Yorck Project. https:\/\/commons.wikimedia.org\/wiki\/Category:PD-Art_(Yorck_Project)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1459693.1459731"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020576"},{"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.1145\/93605.98741"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/846219.847319"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/276305.276318"},{"key":"e_1_2_1_13_1","first-page":"28","volume-title":"VLDB","author":"Berchtold S.","year":"1996","unstructured":"S. Berchtold , D. Keim , and H. P. Kriegel . The X-tree: An index structure for high-dimensional data . In VLDB , pages 28 -- 39 , 1996 . S. Berchtold, D. Keim, and H. P. Kriegel. The X-tree: An index structure for high-dimensional data. In VLDB, pages 28--39, 1996."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","DOI":"10.1201\/b17767","volume-title":"Fundamentals of Database Indexing and Searching","author":"Bhattacharya A.","year":"2014","unstructured":"A. Bhattacharya . Fundamentals of Database Indexing and Searching . CRC Press , 2014 . A. Bhattacharya. Fundamentals of Database Indexing and Searching. CRC Press, 2014."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502809"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISM.2006.137"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(03)00065-5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SISAP.2008.12"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1971.223258"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113317"},{"key":"e_1_2_1_22_1","first-page":"426","volume-title":"VLDB","author":"Ciaccia P.","year":"1997","unstructured":"P. Ciaccia , M. Patella , and P. Zezula . M-tree: An efficient access method for similarity search in metric spaces . In VLDB , pages 426 -- 435 , 1997 . P. Ciaccia, M. Patella, and P. Zezula. M-tree: An efficient access method for similarity search in metric spaces. In VLDB, pages 426--435, 1997."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.006"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872795"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213898"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2013.379"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/971697.602266"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0031-3203(02)00326-6"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2012.05.011"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2014.2343223"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.66"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850470"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-005-0178-0"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/170088.170403"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253347"},{"key":"e_1_2_1_40_1","first-page":"798","volume-title":"SODA","author":"Krauthgamer R.","year":"2004","unstructured":"R. Krauthgamer and J. R. Lee . Navigating nets: simple algorithms for proximity search . In SODA , pages 798 -- 807 , 2004 . R. Krauthgamer and J. R. Lee. Navigating nets: simple algorithms for proximity search. In SODA, pages 798--807, 2004."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/646102.681186"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000486.2000490"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/645484.656398"},{"key":"e_1_2_1_44_1","first-page":"825","volume-title":"NIPS","author":"Liu T.","year":"2004","unstructured":"T. Liu , A. W. Moore , A. G. Gray , and K. Yang . An investigation of practical approximate nearest neighbor algorithms . In NIPS , pages 825 -- 832 , 2004 . T. Liu, A. W. Moore, A. G. Gray, and K. Yang. An investigation of practical approximate nearest neighbor algorithms. In NIPS, pages 825--832, 2004."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732947"},{"key":"e_1_2_1_46_1","first-page":"950","volume-title":"VLDB","author":"Lv Q.","year":"2007","unstructured":"Q. Lv , W. Josephson , Z. Wang , M. Charikar , and K. Li . Multi-probe lsh: efficient indexing for high-dimensional similarity search . In VLDB , pages 950 -- 961 , 2007 . Q. Lv, W. Josephson, Z. Wang, M. Charikar, and K. Li. Multi-probe lsh: efficient indexing for high-dimensional similarity search. In VLDB, pages 950--961, 2007."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPR.2006.275"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.006"},{"key":"e_1_2_1_49_1","volume-title":"Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. arXiv:1603.09320 {cs.DS}","author":"Malkov Y. A.","year":"2016","unstructured":"Y. A. Malkov and D. A. Yashunin . Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. arXiv:1603.09320 {cs.DS} , 2016 . Y. A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. arXiv:1603.09320 {cs.DS}, 2016."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/1394399"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69384-0_38"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(94)90095-7"},{"key":"e_1_2_1_54_1","first-page":"36","article-title":"Scalable nearest neighbor algorithms for high dimensional data. Pattern Analysis and Machine Intelligence","author":"Muja M.","year":"2014","unstructured":"M. Muja and D. G. Lowe . Scalable nearest neighbor algorithms for high dimensional data. Pattern Analysis and Machine Intelligence , IEEE Transactions on , 36 , 2014 . M. Muja and D. G. Lowe. Scalable nearest neighbor algorithms for high dimensional data. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 36, 2014.","journal-title":"IEEE Transactions on"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2013.388"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335219"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69507-3_37"},{"key":"e_1_2_1_58_1","first-page":"23","article-title":"Social choice in the south seas: Electoral innovation and the borda count in the pacific island countries","author":"Reilly B.","year":"2002","unstructured":"B. Reilly . Social choice in the south seas: Electoral innovation and the borda count in the pacific island countries . Int. Political Sc. Rev. , 23 , 2002 . B. Reilly. Social choice in the south seas: Electoral innovation and the borda count in the pacific island countries. Int. Political Sc. Rev., 23, 2002.","journal-title":"Int. Political Sc. Rev."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(86)90013-9"},{"key":"e_1_2_1_60_1","doi-asserted-by":"crossref","unstructured":"H. Sagan. Space-Filling Curves. Springer 1994.  H. Sagan. Space-Filling Curves. Springer 1994.","DOI":"10.1007\/978-1-4612-0871-6"},{"key":"e_1_2_1_61_1","first-page":"516","volume-title":"VLDB","author":"Sakurai Y.","year":"2000","unstructured":"Y. Sakurai , M. Yoshikawa , S. Uemura , and H. Kojima . The A-tree: An index structure for high-dimensional spaces using relative approximation . In VLDB , pages 516 -- 526 , 2000 . Y. Sakurai, M. Yoshikawa, S. Uemura, and H. Kojima. The A-tree: An index structure for high-dimensional spaces using relative approximation. In VLDB, pages 516--526, 2000."},{"key":"e_1_2_1_62_1","volume-title":"Morgan Kaufmann","author":"Samet H.","year":"2005","unstructured":"H. Samet . Foundations of Multidimensional and Metric Data Structures . Morgan Kaufmann , 2005 . H. Samet. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann, 2005."},{"key":"e_1_2_1_63_1","first-page":"350","volume-title":"A fast indexing method for multidimensional nearest neighbor search","author":"Shepherd J.","year":"1999","unstructured":"J. Shepherd , X. Zhu , and N. Megiddo . A fast indexing method for multidimensional nearest neighbor search . In SPIE , pages 350 -- 355 , 1999 . J. Shepherd, X. Zhu, and N. Megiddo. A fast indexing method for multidimensional nearest neighbor search. In SPIE, pages 350--355, 1999."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2008.4587638"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735462"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559905"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/1458082.1458181"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0062-1"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(94)90094-9"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/2393347.2393378"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-14998-1_18"},{"key":"e_1_2_1_72_1","first-page":"194","volume-title":"VLDB","author":"Weber R.","year":"1998","unstructured":"R. Weber , H.-J. Schek , and S. Blott . A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces . In VLDB , pages 194 -- 205 , 1998 . R. Weber, H.-J. Schek, and S. Blott. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In VLDB, pages 194--205, 1998."},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.5555\/645481.655573"},{"key":"e_1_2_1_74_1","first-page":"421","volume-title":"VLDB","author":"Yu C.","year":"2001","unstructured":"C. Yu , B. C. Ooi , K.-L. Tan , and H. V. Jagadish . Indexing the distance: An efficient method to knn processing . In VLDB , pages 421 -- 430 , 2001 . C. Yu, B. C. Ooi, K.-L. Tan, and H. V. Jagadish. Indexing the distance: An efficient method to knn processing. In VLDB, pages 421--430, 2001."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3204028.3204034","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T05:21:28Z","timestamp":1672204888000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3204028.3204034"}},"subtitle":["pushing the scalability-accuracy boundary for approximate kNN search in high-dimensional spaces"],"short-title":[],"issued":{"date-parts":[[2018,4]]},"references-count":73,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["10.14778\/3204028.3204034"],"URL":"https:\/\/doi.org\/10.14778\/3204028.3204034","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,4]]}}}