{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:53:43Z","timestamp":1775638423822,"version":"3.50.1"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2014,5]]},"abstract":"<jats:p>\n            Approximate Nearest Neighbor (ANN) search in high dimensional space has become a fundamental paradigm in many applications. Recently, Locality Sensitive Hashing (LSH) and its variants are acknowledged as the most promising solutions to ANN search. However, state-of-the-art LSH approaches suffer from a drawback: accesses to candidate objects require a large number of\n            <jats:italic>random<\/jats:italic>\n            I\/O operations. In order to guarantee the quality of returned results, sufficient objects should be verified, which would consume enormous I\/O cost.\n          <\/jats:p>\n          <jats:p>To address this issue, we propose a novel method, called SortingKeys-LSH (SK-LSH), which reduces the number of page accesses through locally arranging candidate objects. We firstly define a new measure to evaluate the distance between the compound hash keys of two points. A linear order relationship on the set of compound hash keys is then created, and the corresponding data points can be sorted accordingly. Hence, data points that are close to each other according to the distance measure can be stored locally in an index file. During the ANN search, only a limited number of disk pages among few index files are necessary to be accessed for sufficient candidate generation and verification, which not only significantly reduces the response time but also improves the accuracy of the returned results. Our exhaustive empirical study over several real-world data sets demonstrates the superior efficiency and accuracy of SK-LSH for the ANN search, compared with state-of-the-art methods, including LSB, C2LSH and CK-Means.<\/jats:p>","DOI":"10.14778\/2732939.2732947","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"745-756","source":"Crossref","is-referenced-by-count":74,"title":["SK-LSH"],"prefix":"10.14778","volume":"7","author":[{"given":"Yingfan","family":"Liu","sequence":"first","affiliation":[{"name":"Xidian University, China"}]},{"given":"Jiangtao","family":"Cui","sequence":"additional","affiliation":[{"name":"Xidian University, China"}]},{"given":"Zi","family":"Huang","sequence":"additional","affiliation":[{"name":"University of Queensland, Australia"}]},{"given":"Hui","family":"Li","sequence":"additional","affiliation":[{"name":"Xidian University, China"}]},{"given":"Heng Tao","family":"Shen","sequence":"additional","affiliation":[{"name":"University of Queensland, Australia"}]}],"member":"320","published-online":{"date-parts":[[2014,5]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"28","volume-title":"VLDB","author":"Berchtold S.","year":"1996","unstructured":"S. Berchtold , D. A. Keim , and H.-P. Kriegel . The X-tree : An index structure for high-dimensional data . In VLDB , pages 28 -- 39 , 1996 . S. Berchtold, D. A. 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_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1348246.1348248"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213898"},{"key":"e_1_2_1_5_1","first-page":"518","volume-title":"VLDB","author":"Gionis A.","year":"1999","unstructured":"A. Gionis , P. Indyk , and R. Motwani . Similarity search in high dimensions via hashing . In VLDB , pages 518 -- 529 , 1999 . A. Gionis, P. Indyk, and R. Motwani. Similarity search in high dimensions via hashing. In VLDB, pages 518--529, 1999."},{"key":"e_1_2_1_6_1","first-page":"2957","volume-title":"CVPR","author":"Heo J.-P.","year":"2012","unstructured":"J.-P. Heo , Y. Lee , J. He , S.-F. Chang , and S.-E. Yoon . Spherical hashing . In CVPR , pages 2957 -- 2964 , 2012 . J.-P. Heo, Y. Lee, J. He, S.-F. Chang, and S.-E. Yoon. Spherical hashing. In CVPR, pages 2957--2964, 2012."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1459359.1459389"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1459359.1459388"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253347"},{"key":"e_1_2_1_12_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_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2013.388"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109688"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066240"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-005-0167-3"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465274"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559905"},{"key":"e_1_2_1_20_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_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/645481.655573"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767837"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2732939.2732947","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:21:51Z","timestamp":1672222911000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2732939.2732947"}},"subtitle":["an efficient index structure for approximate nearest neighbor search"],"short-title":[],"issued":{"date-parts":[[2014,5]]},"references-count":22,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2014,5]]}},"alternative-id":["10.14778\/2732939.2732947"],"URL":"https:\/\/doi.org\/10.14778\/2732939.2732947","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2014,5]]}}}