{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T04:40:49Z","timestamp":1773895249358,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>\n            Nearest neighbor (NN) search in high-dimensional spaces is inherently computationally expensive due to the curse of dimensionality. As a well-known solution to approximate NN search, locality-sensitive hashing (LSH) is able to answer c-approximate NN (\n            <jats:italic>c<\/jats:italic>\n            -ANN) queries in sublinear time with constant probability. Existing LSH methods focus mainly on building hash bucket based indexing such that the candidate points can be retrieved quickly. However, existing coarse-grained structures fail to offer accurate distance estimation for candidate points, which translates into additional computational overhead when having to examine unnecessary points. This in turn reduces the performance of query processing. In contrast, we propose a fast and accurate LSH framework, called PM-LSH, that aims to compute the\n            <jats:italic>c<\/jats:italic>\n            -ANN query on large- scale, high-dimensional datasets. First, we adopt a simple yet effective PM-tree to index the data points. Second, we develop a tunable confidence interval to achieve accurate distance estimation and guarantee high result quality. Third, we propose an efficient algorithm on top of the PM-tree to improve the performance of computing\n            <jats:italic>c<\/jats:italic>\n            -ANN queries. Extensive experiments with real-world data offer evidence that PM-LSH is capable of outperforming existing proposals with respect to both efficiency and accuracy.\n          <\/jats:p>","DOI":"10.14778\/3377369.3377374","type":"journal-article","created":{"date-parts":[[2020,2,19]],"date-time":"2020-02-19T18:58:53Z","timestamp":1582138733000},"page":"643-655","source":"Crossref","is-referenced-by-count":76,"title":["PM-LSH"],"prefix":"10.14778","volume":"13","author":[{"given":"Bolong","family":"Zheng","sequence":"first","affiliation":[{"name":"Huazhong University of Science and Technology"}]},{"given":"Xi","family":"Zhao","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology"}]},{"given":"Lianggui","family":"Weng","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology"}]},{"given":"Nguyen Quoc Viet","family":"Hung","sequence":"additional","affiliation":[{"name":"Griffith University"}]},{"given":"Hang","family":"Liu","sequence":"additional","affiliation":[{"name":"Stevens Institute of Technology"}]},{"given":"Christian S.","family":"Jensen","sequence":"additional","affiliation":[{"name":"Aalborg University"}]}],"member":"320","published-online":{"date-parts":[[2020,2,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11192-017-2569-6"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783405"},{"key":"e_1_2_1_3_1","unstructured":"A. Andoni and P. Indyk. LSH algorithm and implementation (E2LSH) 2016.  A. Andoni and P. Indyk. LSH algorithm and implementation (E2LSH) 2016."},{"key":"e_1_2_1_4_1","first-page":"651","volume-title":"WWW","author":"Bawa M.","year":"2005"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113317"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275495"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242610"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1458082.1458172"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213898"},{"key":"e_1_2_1_12_1","first-page":"518","volume-title":"VLDB","author":"Gionis A.","year":"1999"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2012.193"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516446"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/548894"},{"key":"e_1_2_1_16_1","volume-title":"ICML","author":"He J.","year":"2012"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850470"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2009.5459466"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183750"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2909204"},{"key":"e_1_2_1_22_1","first-page":"950","volume-title":"PVLDB","author":"Lv Q.","year":"2007"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137765.3137836"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1951365.1951422"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109688"},{"key":"e_1_2_1_26_1","first-page":"181","volume-title":"HLT-NAACL","author":"Petrovic S.","year":"2010"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2914838"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236214"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140440"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/11408079_73"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735462"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556574"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559905"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2017.2699960"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882930"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3377369.3377374","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:32:26Z","timestamp":1672219946000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3377369.3377374"}},"subtitle":["A fast and accurate LSH framework for high-dimensional approximate NN search"],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":35,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.14778\/3377369.3377374"],"URL":"https:\/\/doi.org\/10.14778\/3377369.3377374","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}