{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,15]],"date-time":"2026-09-15T01:12:09Z","timestamp":1789434729391,"version":"build-2803163510"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,6]]},"abstract":"<jats:p>\n            Efficiently estimating the\n            <jats:italic>inclusion coefficient<\/jats:italic>\n            - the fraction of values of one column that are contained in another column - is useful for tasks such as data profiling and foreign-key detection. We present a new estimator, BML, for inclusion coefficient based on Hyperloglog sketches that results in significantly lower error compared to the state-of-the art approach that uses Bottom-k sketches. We evaluate the error of the BML estimator using experiments on industry benchmarks such as TPC-H and TPC-DS, and several real-world databases. As an independent contribution, we show how Hyperloglog sketches can be maintained incrementally with data deletions using only a constant amount of additional memory.\n          <\/jats:p>","DOI":"10.14778\/3231751.3231759","type":"journal-article","created":{"date-parts":[[2018,7,27]],"date-time":"2018-07-27T12:21:07Z","timestamp":1532694067000},"page":"1097-1109","source":"Crossref","is-referenced-by-count":12,"title":["Efficient estimation of inclusion coefficient using hyperloglog sketches"],"prefix":"10.14778","volume":"11","author":[{"given":"Azade","family":"Nazi","sequence":"first","affiliation":[{"name":"Microsoft Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bolin","family":"Ding","sequence":"additional","affiliation":[{"name":"Microsoft Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vivek","family":"Narasayya","sequence":"additional","affiliation":[{"name":"Microsoft Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Surajit","family":"Chaudhuri","sequence":"additional","affiliation":[{"name":"Microsoft Research"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0389-y"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795288490"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2398580"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2006.54"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247504"},{"key":"e_1_2_1_6_1","first-page":"21","volume-title":"Proceedings of the Compression and Complexity of Sequences","author":"Broder A.","year":"1997","unstructured":"A. Broder . On the resemblance and containment of documents . In Proceedings of the Compression and Complexity of Sequences 1997 , pages 21 --, Washington, DC, USA, 1997. IEEE Computer Society. A. Broder. On the resemblance and containment of documents. In Proceedings of the Compression and Complexity of Sequences 1997, pages 21--, Washington, DC, USA, 1997. IEEE Computer Society."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276781"},{"key":"e_1_2_1_8_1","volume-title":"Numerical analysis","author":"Burden R. L.","year":"2011","unstructured":"R. L. Burden and J. D. Faires . Numerical analysis . 2011 . R. L. Burden and J. D. Faires. Numerical analysis. 2011."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804332"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454166"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733014"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281133"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3097999"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 2007 international conference on analysis of algorithms","author":"Flajolet P.","year":"2007","unstructured":"P. Flajolet , E. Fusy , O. Gandouet, and et al. Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm . In Proceedings of the 2007 international conference on analysis of algorithms , 2007 . P. Flajolet, E. Fusy, O. Gandouet, and et al. Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm. In Proceedings of the 2007 international conference on analysis of algorithms, 2007."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2452376.2452456"},{"key":"e_1_2_1_17_1","volume-title":"Technologie und Web (BTW 2017)","author":"Kruse S.","year":"2017","unstructured":"S. Kruse , T. Papenbrock , C. Dullweber , M. Finke , M. Hegner , M. Zabel , C. Zollner , and F. Naumann . Fast approximate discovery of inclusion dependencies. Datenbanksysteme f\u00fcr Business , Technologie und Web (BTW 2017) , 2017 . S. Kruse, T. Papenbrock, C. Dullweber, M. Finke, M. Hegner, M. Zabel, C. Zollner, and F. Naumann. Fast approximate discovery of inclusion dependencies. Datenbanksysteme f\u00fcr Business, Technologie und Web (BTW 2017), 2017."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1162\/coli.2007.33.3.305"},{"key":"e_1_2_1_19_1","volume-title":"One Permutation Hashing for Efficient Search and Learning. ArXiv e-prints","author":"Li P.","year":"2012","unstructured":"P. Li , A. Owen , and C.-H. Zhang . One Permutation Hashing for Efficient Search and Learning. ArXiv e-prints , 2012 . P. Li, A. Owen, and C.-H. Zhang. One Permutation Hashing for Efficient Search and Learning. ArXiv e-prints, 2012."},{"key":"e_1_2_1_20_1","volume-title":"b-bit minwise hashing in. CoRR, abs\/1205.2958","author":"Li P.","year":"2012","unstructured":"P. Li , A. Shrivastava , and A. C. K\u00f6nig . b-bit minwise hashing in. CoRR, abs\/1205.2958 , 2012 . P. Li, A. Shrivastava, and A. C. K\u00f6nig. b-bit minwise hashing in. CoRR, abs\/1205.2958, 2012."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0306-4379(01)00027-8"},{"key":"e_1_2_1_22_1","first-page":"27","volume-title":"Proceedings of the Third IEEE International Conference on Data Mining, ICDM '03","author":"Marchi F. D.","unstructured":"F. D. Marchi and J.-M. Petit . Zigzag : A new algorithm for mining large inclusion dependencies in databases . In Proceedings of the Third IEEE International Conference on Data Mining, ICDM '03 , pages 27 --, Washington, DC, USA, 2003. IEEE Computer Society. F. D. Marchi and J.-M. Petit. Zigzag: A new algorithm for mining large inclusion dependencies in databases. In Proceedings of the Third IEEE International Conference on Data Mining, ICDM '03, pages 27--, Washington, DC, USA, 2003. IEEE Computer Society."},{"key":"e_1_2_1_23_1","volume-title":"The CTU prague relational learning repository. CoRR, abs\/1511.03086","author":"Motl J.","year":"2015","unstructured":"J. Motl and O. Schulte . The CTU prague relational learning repository. CoRR, abs\/1511.03086 , 2015 . J. Motl and O. Schulte. The CTU prague relational learning repository. CoRR, abs\/1511.03086, 2015."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590995"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.17"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594554"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824086"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752946"},{"key":"e_1_2_1_29_1","volume-title":"WebDB","author":"Rostin A.","year":"2009","unstructured":"A. Rostin , O. Albrecht , J. Bauckmann , F. Naumann , and U. Leser . A machine learning approach to foreign key discovery . In WebDB , 2009 . A. Rostin, O. Albrecht, J. Bauckmann, F. Naumann, and U. Leser. A machine learning approach to foreign key discovery. In WebDB, 2009."},{"key":"e_1_2_1_30_1","volume-title":"Improved Densification of One Permutation Hashing. ArXiv e-prints","author":"Shrivastava A.","year":"2014","unstructured":"A. Shrivastava and P. Li . Improved Densification of One Permutation Hashing. ArXiv e-prints , 2014 . A. Shrivastava and P. Li. Improved Densification of One Permutation Hashing. ArXiv e-prints, 2014."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920944"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3231751.3231759","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:39:20Z","timestamp":1672223960000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3231751.3231759"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6]]},"references-count":31,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2018,6]]}},"alternative-id":["10.14778\/3231751.3231759"],"URL":"https:\/\/doi.org\/10.14778\/3231751.3231759","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,6]]}}}