{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,23]],"date-time":"2026-09-23T03:22:59Z","timestamp":1790133779566,"version":"4.0.1"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2016,7]]},"abstract":"<jats:p>Data deduplication refers to the process of identifying tuples in a relation that refer to the same real world entity. The complexity of the problem is inherently quadratic with respect to the number of tuples, since a similarity value must be computed for every pair of tuples. To avoid comparing tuple pairs that are obviously non-duplicates, blocking techniques are used to divide the tuples into blocks and only tuples within the same block are compared. However, even with the use of blocking, data deduplication remains a costly problem for large datasets. In this paper, we show how to further speed up data deduplication by leveraging parallelism in a shared-nothing computing environment. Our main contribution is a distribution strategy, called Dis-Dedup, that minimizes the maximum workload across all worker nodes and provides strong theoretical guarantees. We demonstrate the effectiveness of our proposed strategy by performing extensive experiments on both synthetic datasets with varying block size distributions, as well as real world datasets.<\/jats:p>","DOI":"10.14778\/2983200.2983203","type":"journal-article","created":{"date-parts":[[2016,8,5]],"date-time":"2016-08-05T08:34:02Z","timestamp":1470386042000},"page":"864-875","source":"Crossref","is-referenced-by-count":57,"title":["Distributed data deduplication"],"prefix":"10.14778","volume":"9","author":[{"given":"Xu","family":"Chu","sequence":"first","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"}]},{"given":"Paraschos","family":"Koutris","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Apache hadoop. http:\/\/hadoop.apache.org.  Apache hadoop. http:\/\/hadoop.apache.org."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739056"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-014-0357-y"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287420"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594558"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2006.13"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.127"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2750545"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_11_1","first-page":"27","volume-title":"VLDB","author":"DeWitt D. J.","year":"1992","unstructured":"D. J. DeWitt , J. F. Naughton , D. A. Schneider , and S. Seshadri . Practical skew handling in parallel joins . In VLDB , pages 27 -- 40 , 1992 . D. J. DeWitt, J. F. Naughton, D. A. Schneider, and S. Seshadri. Practical skew handling in parallel joins. In VLDB, pages 27--40, 1992."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.9"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367564"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/jcd.3180030404"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2594530"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/568271.223807"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000045"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1131"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367527"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.22"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920904"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989423"},{"key":"e_1_2_1_23_1","first-page":"159","volume-title":"RANDOM","author":"Raab M.","year":"1998","unstructured":"M. Raab and A. Steger . \" balls into bins\" - A simple and tight analysis . In RANDOM , pages 159 -- 170 , 1998 . M. Raab and A. Steger. \"balls into bins\" - A simple and tight analysis. In RANDOM, pages 159--170, 1998."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732981"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1964.14.1405"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2331042.2331053"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807222"},{"key":"e_1_2_1_28_1","first-page":"10","volume-title":"HotCloud","volume":"10","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 , volume 10 , page 10 , 2010 . M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica. Spark: cluster computing with working sets. In HotCloud, volume 10, page 10, 2010."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2983200.2983203","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T05:28:45Z","timestamp":1672205325000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2983200.2983203"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7]]},"references-count":27,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["10.14778\/2983200.2983203"],"URL":"https:\/\/doi.org\/10.14778\/2983200.2983203","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2016,7]]}}}