{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T03:06:05Z","timestamp":1787022365518,"version":"build-2736575974"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,7]]},"abstract":"<jats:p>We analyze the problem of discovering dependencies from distributed big data. Existing (non-distributed) algorithms focus on minimizing computation by pruning the search space of possible dependencies. However, distributed algorithms must also optimize communication costs, especially in shared-nothing settings, leading to a more complex optimization space. To understand this space, we introduce six primitives shared by existing dependency discovery algorithms, corresponding to data processing steps separated by communication barriers. Through case studies, we show how the primitives allow us to analyze the design space and develop communication-optimized implementations. Finally, we support our analysis with an experimental evaluation on real datasets.<\/jats:p>","DOI":"10.14778\/3342263.3342638","type":"journal-article","created":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T14:36:11Z","timestamp":1568817371000},"page":"1624-1636","source":"Crossref","is-referenced-by-count":22,"title":["Distributed implementations of dependency discovery algorithms"],"prefix":"10.14778","volume":"12","author":[{"given":"Hemant","family":"Saxena","sequence":"first","affiliation":[{"name":"University of Waterloo"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lukasz","family":"Golab","sequence":"additional","affiliation":[{"name":"University of Waterloo"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ihab F.","family":"Ilyas","sequence":"additional","affiliation":[{"name":"University of Waterloo"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Metanome. https:\/\/github.com\/HPI-Information-Systems\/metanome-algorithms.  Metanome. https:\/\/github.com\/HPI-Information-Systems\/metanome-algorithms."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0389-y"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661829.2661884"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3157794.3157800"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/2983200.2983203"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536258.2536262"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCSim.2014.6903725"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/42.2.100"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26187-4_15"},{"key":"e_1_2_1_10_1","first-page":"289","volume-title":"F. Li","author":"Li W.","year":"2016","unstructured":"W. Li , Z. Li , Q. Chen , T. Jiang , and Z. Yin . Discovering approximate functional dependencies from distributed big data . In F. Li , K. Shim, K. Zheng, and G. Liu, editors, Web Technologies and Applications, pages 289 -- 301 , Cham, 2016 . Springer International Publishing . W. Li, Z. Li, Q. Chen, T. Jiang, and Z. Yin. Discovering approximate functional dependencies from distributed big data. In F. Li, K. Shim, K. Zheng, and G. Liu, editors, Web Technologies and Applications, pages 289--301, Cham, 2016. Springer International Publishing."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.197"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(96)00141-X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794377"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915203"},{"key":"e_1_2_1_15_1","first-page":"195","volume-title":"BTW","author":"Papenbrock T.","year":"2017","unstructured":"T. Papenbrock and F. Naumann . A hybrid approach for efficient unique column combination discovery . In BTW , pages 195 -- 204 . Gesellschaft fr Informatik, Bonn , 2017 . T. Papenbrock and F. Naumann. A hybrid approach for efficient unique column combination discovery. In BTW, pages 195--204. Gesellschaft fr Informatik, Bonn, 2017."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90024-9"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00149"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2010.5496972"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3067421.3067422"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/646110.679455"},{"key":"e_1_2_1_21_1","volume-title":"HotCloud","author":"Zaharia M.","year":"2010","unstructured":"M. Zaharia , M. Chowdhury , M. J. Franklin , S. Shenker , and I. Stoica . Spark: Cluster computing with working sets . In HotCloud , 2010 . M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica. Spark: Cluster computing with working sets. In HotCloud, 2010."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3342263.3342638","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T04:56:10Z","timestamp":1672203370000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3342263.3342638"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7]]},"references-count":21,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["10.14778\/3342263.3342638"],"URL":"https:\/\/doi.org\/10.14778\/3342263.3342638","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,7]]}}}