{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T15:19:22Z","timestamp":1787239162516,"version":"build-2736575974"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,9]]},"abstract":"\n Locality-Sensitive Hashing (LSH) and its variants are the well-known indexing schemes for the\n c<\/jats:italic>\n -Approximate Nearest Neighbor (\n c<\/jats:italic>\n -ANN) search problem in high-dimensional Euclidean space. Traditionally, LSH functions are constructed in a\n query-oblivious<\/jats:italic>\n manner in the sense that buckets are partitioned before any query arrives. However, objects closer to a query may be partitioned into different buckets, which is undesirable. Due to the use of\n query-oblivious<\/jats:italic>\n bucket partition, the state-of-the-art LSH schemes for external memory, namely C2LSH and LSB-Forest, only work with approximation ratio of integer\n c<\/jats:italic>\n \u2265 2.\n <\/jats:p>\n \n In this paper, we introduce a novel concept of\n query-aware<\/jats:italic>\n bucket partition which uses a given query as the \"anchor\" for bucket partition. Accordingly, a\n query-aware<\/jats:italic>\n LSH function is a random projection coupled with\n query-aware<\/jats:italic>\n bucket partition, which removes random shift required by traditional\n query-oblivious<\/jats:italic>\n LSH functions. Notably,\n query-aware<\/jats:italic>\n bucket partition can be easily implemented so that query performance is guaranteed. We propose a novel\n query-aware<\/jats:italic>\n LSH scheme named QALSH for\n c<\/jats:italic>\n -ANN search over external memory. Our theoretical studies show that QALSH enjoys a guarantee on query quality. The use of\n query-aware<\/jats:italic>\n LSH function enables QALSH to work with any approximation ratio\n c<\/jats:italic>\n > 1. Extensive experiments show that QALSH outperforms C2LSH and LSB-Forest, especially in high-dimensional space. Specifically, by using a ratio\n c<\/jats:italic>\n < 2, QALSH can achieve much better query quality.\n <\/jats:p>","DOI":"10.14778\/2850469.2850470","type":"journal-article","created":{"date-parts":[[2016,2,1]],"date-time":"2016-02-01T09:10:31Z","timestamp":1454317831000},"page":"1-12","source":"Crossref","is-referenced-by-count":189,"title":["Query-aware locality-sensitive hashing for approximate nearest neighbor search"],"prefix":"10.14778","volume":"9","author":[{"given":"Qiang","family":"Huang","sequence":"first","affiliation":[{"name":"Sun Yat-sen University, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jianlin","family":"Feng","sequence":"additional","affiliation":[{"name":"Sun Yat-sen University, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yikai","family":"Zhang","sequence":"additional","affiliation":[{"name":"Sun Yat-sen University, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Qiong","family":"Fang","sequence":"additional","affiliation":[{"name":"South China University of Technology, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wilfred","family":"Ng","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634150"},{"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\/872757.872795"},{"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","volume":"99","author":"Gionis A.","year":"1999"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071612"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258653"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732947"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109688"},{"key":"e_1_2_1_13_1","volume-title":"Morgan Kaufmann","author":"Samet H.","year":"2006"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735462"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806907.1806912"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2850469.2850470","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T04:47:48Z","timestamp":1672202868000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2850469.2850470"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["10.14778\/2850469.2850470"],"URL":"https:\/\/doi.org\/10.14778\/2850469.2850470","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,9]]}}}