{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,30]],"date-time":"2025-09-30T10:59:29Z","timestamp":1759229969824},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"13","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:p>\n            Approximate Nearest Neighbor Search (ANNS) is a fundamental algorithmic problem, with numerous applications in many areas of computer science. Locality-Sensitive Hashing (LSH) is one of the most popular solution approaches for ANNS. A common shortcoming of many LSH schemes is that since they probe only a single bucket in a hash table, they need to use a large number of hash tables to achieve a high query accuracy. For ANNS-\n            <jats:italic>L<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            , a multi-probe scheme was proposed to overcome this drawback by strategically probing multiple buckets in a hash table. In this work, we propose MP-RW-LSH, the first and so far only multi-probe LSH solution to ANNS in\n            <jats:italic>L<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            distance, and show that it achieves a better tradeoff between scalability and query efficiency than all existing LSH-based solutions. We also explain why a state-of-the-art ANNS\n            <jats:italic>-L<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            solution called Cauchy projection LSH (CP-LSH) is fundamentally not suitable for multi-probe extension. Finally, as a use case, we construct, using MP-RW-LSH as the underlying \"ANNS-\n            <jats:italic>L<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            engine\", a new ANNS-E (E for edit distance) solution that beats the state of the art.\n          <\/jats:p>","DOI":"10.14778\/3484224.3484226","type":"journal-article","created":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T22:36:50Z","timestamp":1635460610000},"page":"3267-3280","source":"Crossref","is-referenced-by-count":2,"title":["MP-RW-LSH"],"prefix":"10.14778","volume":"14","author":[{"given":"Huayi","family":"Wang","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingfan","family":"Meng","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Long","family":"Gong","sequence":"additional","affiliation":[{"name":"Facebook"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun","family":"Xu","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mitsunori","family":"Ogihara","sequence":"additional","affiliation":[{"name":"University of Miami"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,10,28]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. Annoy: Approximate Nearest Neighbors in C++\/Python optimized for memory usage and loading\/saving to disk. https:\/\/github.com\/spotify\/annoy.  [n.d.]. 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_2_1","unstructured":"[n.d.]. Audio Dataset. http:\/\/www.cs.princeton.edu\/cass\/audio.tar.gz.  [n.d.]. Audio Dataset. http:\/\/www.cs.princeton.edu\/cass\/audio.tar.gz."},{"key":"e_1_2_1_3_1","unstructured":"[n.d.]. Datasets for ANN neighbor search. http:\/\/corpus-texmex.irisa.fr\/.  [n.d.]. Datasets for ANN neighbor search. http:\/\/corpus-texmex.irisa.fr\/."},{"key":"e_1_2_1_4_1","unstructured":"[n.d.]. Enron Email Dataset. http:\/\/www.cs.cmu.edu\/~enron\/.  [n.d.]. Enron Email Dataset. http:\/\/www.cs.cmu.edu\/~enron\/."},{"key":"e_1_2_1_5_1","unstructured":"[n.d.]. FALCONN - FAst Lookups of Cosine and Other Nearest Neighbors. https:\/\/github.com\/FALCONN-LIB\/FALCONN.  [n.d.]. FALCONN - FAst Lookups of Cosine and Other Nearest Neighbors. https:\/\/github.com\/FALCONN-LIB\/FALCONN."},{"key":"e_1_2_1_6_1","unstructured":"[n.d.]. FLANN - Fast Library for Approximate Nearest Neighbors. https:\/\/github.com\/flann-lib\/flann.  [n.d.]. FLANN - Fast Library for Approximate Nearest Neighbors. https:\/\/github.com\/flann-lib\/flann."},{"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":"publisher","DOI":"10.1145\/2783258.2783405"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1347082.1347120"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2969239.2969376"},{"key":"e_1_2_1_11_1","unstructured":"Artem Babenko and Victor Lempitsky. [n.d.]. Deep: Datasets of deep descriptors. http:\/\/sites.skoltech.ru\/compvision\/noimi\/.  Artem Babenko and Victor Lempitsky. [n.d.]. Deep: Datasets of deep descriptors. http:\/\/sites.skoltech.ru\/compvision\/noimi\/."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/17.5.419"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.9"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1614191"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3397271.3401045"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374452"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799361701"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303754"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1975.224297"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213898"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397243"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2011.193"},{"key":"e_1_2_1_25_1","volume-title":"randomness and some discrete distributions. Journal of applied probability","author":"Hickey Raymond J","year":"1983"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0472-7"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_28_1","volume-title":"3rd international workshop on statistical and computational theories of vision (at ICCV)","volume":"2","author":"Indyk Piotr","year":"2003"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSIA.2017.8339084"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461466.2461485"},{"key":"e_1_2_1_31_1","volume-title":"kd-Trees. https:\/\/www.cs.cmu.edu\/~ckingsf\/bioinfo-lectures\/kdtrees.pdf. [Online","author":"Kingsford Carl","year":"2019"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/3045118.3045221"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389778"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2909204"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPRW.2015.7301269"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1325851.1325958"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2014.2321376"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060623"},{"key":"e_1_2_1_39_1","unstructured":"Jeffrey Pennington Richard Socher and Christopher D. Manning. [n.d.]. GloVe: Global Vectors for Word Representation. https:\/\/nlp.stanford.edu\/projects\/glove\/.  Jeffrey Pennington Richard Socher and Christopher D. Manning. [n.d.]. GloVe: Global Vectors for Word Representation. https:\/\/nlp.stanford.edu\/projects\/glove\/."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2017.2760458"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/2124405"},{"key":"e_1_2_1_42_1","volume-title":"Heavy-tail phenomena: probabilistic and statistical modeling","author":"Resnick Sidney I"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2011.6126544"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026543900054"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140440"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2008.4587638"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063737"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081956"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559905"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2012.48"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2007.86"},{"key":"e_1_2_1_53_1","unstructured":"Simon Winder Matt Brown Noah Snavely Steven Seitz and Richard Szeliski. [n.d.]. Trevi: Local Image Descriptors Data. http:\/\/phototour.cs.washington.edu\/patches\/default.htm.  Simon Winder Matt Brown Noah Snavely Steven Seitz and Richard Szeliski. [n.d.]. Trevi: Local Image Descriptors Data. http:\/\/phototour.cs.washington.edu\/patches\/default.htm."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0258-2"},{"key":"e_1_2_1_55_1","unstructured":"LeCun Yann Cortes Corinna and J.C. Burges Christopher. [n.d.]. THE MNIST DATABASE of handwritten digits. http:\/\/yann.lecun.com\/exdb\/mnist\/.  LeCun Yann Cortes Corinna and J.C. Burges Christopher. [n.d.]. THE MNIST DATABASE of handwritten digits. http:\/\/yann.lecun.com\/exdb\/mnist\/."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1873951.1874004"},{"key":"e_1_2_1_57_1","unstructured":"Haoyu Zhang. [n.d.]. String Datasets. https:\/\/iu.box.com\/s\/x7hg7uxj7xmmcdvc62k7iux9txtt9doi.  Haoyu Zhang. [n.d.]. String Datasets. https:\/\/iu.box.com\/s\/x7hg7uxj7xmmcdvc62k7iux9txtt9doi."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098003"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/3377369.3377374"},{"key":"e_1_2_1_60_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\/3484224.3484226","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:36:43Z","timestamp":1672220203000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3484224.3484226"}},"subtitle":["an efficient multi-probe LSH solution to ANNS-\n            <i>L<\/i>\n            <sub>1<\/sub>"],"short-title":[],"issued":{"date-parts":[[2021,9]]},"references-count":59,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["10.14778\/3484224.3484226"],"URL":"https:\/\/doi.org\/10.14778\/3484224.3484226","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,9]]}}}