{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:48:50Z","timestamp":1750308530394,"version":"3.41.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,10,12]],"date-time":"2015-10-12T00:00:00Z","timestamp":1444608000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["DMS1418265 ,SHF1217353"],"award-info":[{"award-number":["DMS1418265 ,SHF1217353"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2015,10,26]]},"abstract":"<jats:p>\n            Given a collection of objects and an associated similarity measure, the all-pairs similarity search problem asks us to find all pairs of objects with similarity greater than a certain user-specified threshold. In order to reduce the number of candidates to search, locality-sensitive hashing (LSH) based indexing methods are very effective. However, most such methods only use LSH for the first phase of similarity search\u2014that is, efficient indexing for candidate generation. In this article, we present\n            <jats:italic>BayesLSH<\/jats:italic>\n            , a principled Bayesian algorithm for the subsequent phase of similarity search\u2014performing candidate pruning and similarity estimation using LSH. A simpler variant,\n            <jats:italic>BayesLSH-Lite<\/jats:italic>\n            , which calculates similarities exactly, is also presented. Our algorithms are able to quickly prune away a large majority of the false positive candidate pairs, leading to significant speedups over baseline approaches. For BayesLSH, we also provide probabilistic guarantees on the quality of the output, both in terms of accuracy and recall. Finally, the quality of BayesLSH\u2019s output can be easily tuned and does not require any manual setting of the number of hashes to use for similarity estimation, unlike standard approaches. For two state-of-the-art candidate generation algorithms, AllPairs and LSH, BayesLSH enables significant speedups, typically in the range 2 \u00d7 --20 \u00d7 for a wide variety of datasets.\n          <\/jats:p>\n          <jats:p>\n            We also extend the BayesLSH algorithm for kernel methods\u2014in which the similarity between two data objects is defined by a kernel function. Since the embedding of data points in the transformed kernel space is unknown, algorithms such as AllPairs which rely on building inverted index structure for fast similarity search do not work with kernel functions. Exhaustive search across all possible pairs is also not an option since the dataset can be huge and computing the kernel values for each pair can be prohibitive. We propose\n            <jats:italic>K-BayesLSH<\/jats:italic>\n            an all-pairs similarity search problem for kernel functions. K-BayesLSH leverages a recently proposed idea\u2014\n            <jats:italic>kernelized locality sensitive hashing<\/jats:italic>\n            (KLSH)\u2014for hash bit computation and candidate generation, and uses the aforementioned BayesLSH idea for candidate pruning and similarity estimation. We ran a broad spectrum of experiments on a variety of datasets drawn from different domains and with distinct kernels and find a speedup of 2 \u00d7 --7 \u00d7 over vanilla KLSH.\n          <\/jats:p>","DOI":"10.1145\/2778990","type":"journal-article","created":{"date-parts":[[2015,10,13]],"date-time":"2015-10-13T22:31:00Z","timestamp":1444775460000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["A Bayesian Perspective on Locality Sensitive Hashing with Extensions for Kernel Methods"],"prefix":"10.1145","volume":"10","author":[{"given":"Aniket","family":"Chakrabarti","sequence":"first","affiliation":[{"name":"The Ohio State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venu","family":"Satuluri","sequence":"additional","affiliation":[{"name":"Twitter Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Atreya","family":"Srivathsan","sequence":"additional","affiliation":[{"name":"Amazon.com Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Srinivasan","family":"Parthasarathy","sequence":"additional","affiliation":[{"name":"The Ohio State University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,10,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2001269.2001293"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327494"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242591"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276781"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(97)00031-7"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741665"},{"key":"e_1_2_1_7_1","volume-title":"Patrice Koehl, Michael Levitt, and Steven E. Brenner.","author":"Chandonia John-Marc","year":"2004","unstructured":"John-Marc Chandonia , Gary Hon , Nigel S. Walker , Loredana Lo Conte , Patrice Koehl, Michael Levitt, and Steven E. Brenner. 2004 . The ASTRAL compendium in 2004. Nucleic acids research 32, suppl 1 (2004), D189--D192. John-Marc Chandonia, Gary Hon, Nigel S. Walker, Loredana Lo Conte, Patrice Koehl, Michael Levitt, and Steven E. Brenner. 2004. The ASTRAL compendium in 2004. Nucleic acids research 32, suppl 1 (2004), D189--D192."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509965"},{"key":"e_1_2_1_9_1","first-page":"1","article-title":"The devil is in the details: An evaluation of recent feature encoding methods. In Proc. BMVC. Scotland","volume":"76","author":"Chatfield Ken","year":"2011","unstructured":"Ken Chatfield , Victor Lempitsky , Andrea Vedaldi , and Andrew Zisserman . 2011 . The devil is in the details: An evaluation of recent feature encoding methods. In Proc. BMVC. Scotland , UK , 76 . 1 -- 76 .12. Ken Chatfield, Victor Lempitsky, Andrea Vedaldi, and Andrew Zisserman. 2011. The devil is in the details: An evaluation of recent feature encoding methods. In Proc. BMVC. Scotland, UK, 76.1--76.12.","journal-title":"UK"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/131766.131776"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063873"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-009-0275-4"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1032643.1033069"},{"key":"e_1_2_1_15_1","volume-title":"VLDB","volume":"99","author":"Gionis Aristides","year":"1999","unstructured":"Aristides Gionis , Piotr Indyk , Rajeev Motwani , and others. 1999 . Similarity search in high dimensions via hashing . In VLDB , Vol. 99 . Edinburgh, Scotland, UK, 518--529. Aristides Gionis, Piotr Indyk, Rajeev Motwani, and others. 1999. Similarity search in high dimensions via hashing. In VLDB, Vol. 99. Edinburgh, Scotland, UK, 518--529."},{"volume-title":"IEEE 11th International Conference on Computer Vision (ICCV\u201907)","author":"Goesele Michael","key":"e_1_2_1_16_1","unstructured":"Michael Goesele , Noah Snavely , Brian Curless , Hugues Hoppe , and Steven M. Seitz . 2007. Multi-view stereo for community photo collections . In IEEE 11th International Conference on Computer Vision (ICCV\u201907) . IEEE, Rio de Janeiro, Brazil, 1--8. Michael Goesele, Noah Snavely, Brian Curless, Hugues Hoppe, and Steven M. Seitz. 2007. Multi-view stereo for community photo collections. In IEEE 11th International Conference on Computer Vision (ICCV\u201907). IEEE, Rio de Janeiro, Brazil, 1--8."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835946"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148170.1148222"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2008.4587841"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88682-2_24"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2011.5995709"},{"key":"e_1_2_1_23_1","volume-title":"International Conference on Artificial Intelligence and Statistics. La Palma, Canary Islands, 592--600","author":"Kaufmann Emilie","year":"2012","unstructured":"Emilie Kaufmann , Olivier Capp\u00e9 , and Aur\u00e9lien Garivier . 2012 . On Bayesian upper confidence bounds for bandit problems . In International Conference on Artificial Intelligence and Statistics. La Palma, Canary Islands, 592--600 . Emilie Kaufmann, Olivier Capp\u00e9, and Aur\u00e9lien Garivier. 2012. On Bayesian upper confidence bounds for bandit problems. In International Conference on Artificial Intelligence and Statistics. La Palma, Canary Islands, 592--600."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2011.219"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1005332.1005345"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772759"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.v58:7"},{"key":"e_1_2_1_29_1","volume-title":"Zhe Wang, Moses Charikar, and Kai Li.","author":"Lv Qin","year":"2007","unstructured":"Qin Lv , William Josephson , Zhe Wang, Moses Charikar, and Kai Li. 2007 . Multi-probe LSH: Efficient indexing for high-dimensional similarity search. In VLDB. Vienna, Austria , 950--961. http:\/\/dl.acm.org\/citation.cfm?id=1325851.1325958. Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. 2007. Multi-probe LSH: Efficient indexing for high-dimensional similarity search. In VLDB. Vienna, Austria, 950--961. http:\/\/dl.acm.org\/citation.cfm?id=1325851.1325958."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242592"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-2836(05)80134-2"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.3115\/1219840.1219917"},{"volume-title":"Mathematical statistics and data analysis. Cengage Learning","author":"Rice John A.","key":"e_1_2_1_34_1","unstructured":"John A. Rice . 2007. Mathematical statistics and data analysis. Cengage Learning , Boston, MA, USA . John A. Rice. 2007. Mathematical statistics and data analysis. Cengage Learning, Boston, MA, USA."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth141"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1951365.1951407"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140440"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989399"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1162\/089976698300017467"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33718-5_18"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-007-0107-3"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559905"},{"key":"e_1_2_1_43_1","volume-title":"Local alignment kernels for biological sequences. Kernel methods in computational biology","author":"Vert Jean-Philippe","year":"2004","unstructured":"Jean-Philippe Vert , Hiroto Saigo , and Tatsuya Akutsu . 2004. Local alignment kernels for biological sequences. Kernel methods in computational biology ( 2004 ), 131--154. Jean-Philippe Vert, Hiroto Saigo, and Tatsuya Akutsu. 2004. Local alignment kernels for biological sequences. Kernel methods in computational biology (2004), 131--154."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2009.5206839"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000824.2000825"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989428"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2006.301"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/1717872"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2778990","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2778990","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:55:52Z","timestamp":1750272952000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2778990"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,12]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,10,26]]}},"alternative-id":["10.1145\/2778990"],"URL":"https:\/\/doi.org\/10.1145\/2778990","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2015,10,12]]},"assertion":[{"value":"2014-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-10-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}