{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T22:23:12Z","timestamp":1780438992828,"version":"3.54.1"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2016,8]]},"abstract":"<jats:p>\n            We study\n            <jats:italic>the problem of domain search<\/jats:italic>\n            where a domain is a set of distinct values from an unspecified universe. We use Jaccard set containment score, defined as |\n            <jats:italic>Q<\/jats:italic>\n            \u2229\n            <jats:italic>X<\/jats:italic>\n            |\/|\n            <jats:italic>Q<\/jats:italic>\n            |, as the measure of relevance of a domain\n            <jats:italic>X<\/jats:italic>\n            to a query domain\n            <jats:italic>Q<\/jats:italic>\n            . Our choice of Jaccard set containment over Jaccard similarity as a measure of relevance makes our work particularly suitable for searching Open Data and data on the web, as Jaccard similarity is known to have poor performance over sets with large differences in their domain sizes. We demonstrate that the domains found in several real-life Open Data and web data repositories show a power-law distribution over their domain sizes.\n          <\/jats:p>\n          <jats:p>\n            We present a new index structure, Locality Sensitive Hashing (LSH) Ensemble, that solves the domain search problem using set containment at Internet scale. Our index structure and search algorithm cope with the data volume and skew by means of data sketches using Minwise Hashing and domain partitioning. Our index structure does not assume a prescribed set of data values. We construct a cost model that describes the accuracy of LSH Ensemble with any given partitioning. This allows us to formulate the data partitioning for LSH Ensemble as an optimization problem. We prove that there exists an\n            <jats:italic>optimal<\/jats:italic>\n            partitioning for any data distribution. Furthermore, for datasets following a power-law distribution, as observed in Open Data and Web data corpora, we show that the optimal partitioning can be approximated using equi-depth, making it particularly efficient to use in practice.\n          <\/jats:p>\n          <jats:p>We evaluate our algorithm using real data (Canadian Open Data and WDC Web Tables) containing up over 262 million domains. The experiments demonstrate that our index consistently outperforms other leading alternatives in accuracy and performance. The improvements are most dramatic for data with large skew in the domain sizes. Even at 262 million domains, our index sustains query performance with under 3 seconds response time.<\/jats:p>","DOI":"10.14778\/2994509.2994534","type":"journal-article","created":{"date-parts":[[2016,9,6]],"date-time":"2016-09-06T15:27:03Z","timestamp":1473175623000},"page":"1185-1196","source":"Crossref","is-referenced-by-count":120,"title":["LSH ensemble"],"prefix":"10.14778","volume":"9","author":[{"given":"Erkang","family":"Zhu","sequence":"first","affiliation":[{"name":"University of Toronto"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fatemeh","family":"Nargesian","sequence":"additional","affiliation":[{"name":"University of Toronto"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ken Q.","family":"Pu","sequence":"additional","affiliation":[{"name":"UOIT"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ren\u00e9e J.","family":"Miller","sequence":"additional","affiliation":[{"name":"University of Toronto"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807267"},{"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\/1066157.1066283"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060840"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.126"},{"key":"e_1_2_1_6_1","first-page":"21","volume-title":"Compression and Complexity of Sequences","author":"Broder A.","year":"1997","unstructured":"A. Broder . On the resemblance and containment of documents . In Compression and Complexity of Sequences , pages 21 -- 28 , 1997 . A. Broder. On the resemblance and containment of documents. In Compression and Complexity of Sequences, pages 21--28, 1997."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453916"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509965"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.228"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281133"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35176-1_4"},{"key":"e_1_2_1_13_1","first-page":"670","volume-title":"VLDB","author":"Hristidis V.","year":"2002","unstructured":"V. Hristidis and Y. Papakonstantinou . Discover: Keyword search in relational databases . In VLDB , pages 670 -- 681 , 2002 . V. Hristidis and Y. Papakonstantinou. Discover: Keyword search in relational databases. In VLDB, pages 670--681, 2002."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391729.1391730"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2594533"},{"key":"e_1_2_1_17_1","volume-title":"CRC Standard Probability and Statistics Tables and Formulae","author":"Kokoska S.","year":"2000","unstructured":"S. Kokoska and D. Zwillinger . CRC Standard Probability and Statistics Tables and Formulae , chapter 2.2.24.1. Chapman & Hall\/CRC , 2000 . S. Kokoska and D. Zwillinger. CRC Standard Probability and Statistics Tables and Formulae, chapter 2.2.24.1. Chapman & Hall\/CRC, 2000."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872518.2889386"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2015.05.001"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1921005"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1394399"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2336664.2336665"},{"key":"e_1_2_1_23_1","first-page":"886","volume-title":"AISTATS","author":"Shrivastava A.","year":"2014","unstructured":"A. Shrivastava and P. Li . In defense of minhash over simhash . In AISTATS , pages 886 -- 894 , 2014 . A. Shrivastava and P. Li. In defense of minhash over simhash. In AISTATS, pages 886--894, 2014."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741285"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002939"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213848"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2994509.2994534","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:54:33Z","timestamp":1672224873000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2994509.2994534"}},"subtitle":["internet-scale domain search"],"short-title":[],"issued":{"date-parts":[[2016,8]]},"references-count":26,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2016,8]]}},"alternative-id":["10.14778\/2994509.2994534"],"URL":"https:\/\/doi.org\/10.14778\/2994509.2994534","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2016,8]]}}}