{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T16:04:17Z","timestamp":1775491457158,"version":"3.50.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,8]]},"abstract":"<jats:p>Fuzzy join is an important primitive for data cleaning. The ability to customize fuzzy join is crucial to allow applications to address domain-specific data quality issues such as synonyms and abbreviations. While efficient indexing techniques exist for single-node implementations of customizable fuzzy join, the state-of-the-art scale-out techniques do not support customization, and exhibit poor performance and scalability characteristics. We describe the design of a scale-out fuzzy join operator that supports customization. We use a locality-sensitive-hashing (LSH) based signature scheme, and introduce optimizations that result in significant speed up with negligible impact on recall. We evaluate our implementation on the Azure Databricks version of Spark using several real-world and synthetic data sets. We observe speedups exceeding 50X compared to the best-known prior scale-out technique, and close to linear scalability with data size and number of nodes.<\/jats:p>","DOI":"10.14778\/3352063.3352128","type":"journal-article","created":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T18:36:11Z","timestamp":1568831771000},"page":"2106-2117","source":"Crossref","is-referenced-by-count":10,"title":["Customizable and scalable fuzzy join for big data"],"prefix":"10.14778","volume":"12","author":[{"given":"Zhimin","family":"Chen","sequence":"first","affiliation":[{"name":"Microsoft Research"}]},{"given":"Yue","family":"Wang","sequence":"additional","affiliation":[{"name":"Microsoft Research"}]},{"given":"Vivek","family":"Narasayya","sequence":"additional","affiliation":[{"name":"Microsoft Research"}]},{"given":"Surajit","family":"Chaudhuri","sequence":"additional","affiliation":[{"name":"Microsoft Research"}]}],"member":"320","published-online":{"date-parts":[[2019,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Azure Data Factory version 2(v2). https:\/\/docs.microsoft.com\/en-us\/rest\/api\/datafactory\/v2.  Azure Data Factory version 2(v2). https:\/\/docs.microsoft.com\/en-us\/rest\/api\/datafactory\/v2."},{"key":"e_1_2_1_2_1","unstructured":"Azure ML Data Prep SDK. https:\/\/github.com\/Microsoft\/AMLDataPrepDocs.  Azure ML Data Prep SDK. https:\/\/github.com\/Microsoft\/AMLDataPrepDocs."},{"issue":"2","key":"e_1_2_1_3_1","first-page":"14","article-title":"Experiences with using data cleaning technology for bing services","volume":"35","author":"Arasu A.","year":"2012","unstructured":"A. Arasu , S. Chaudhuri , Z. Chen , K. Ganjam , R. Kaushik , and V. Narasayya . Experiences with using data cleaning technology for bing services . IEEE Data Eng. Bull. , 35 ( 2 ): 14 -- 23 , 2012 . A. Arasu, S. Chaudhuri, Z. Chen, K. Ganjam, R. Kaushik, and V. Narasayya. Experiences with using data cleaning technology for bing services. IEEE Data Eng. Bull., 35(2):14--23, 2012.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497412"},{"key":"e_1_2_1_5_1","first-page":"918","volume-title":"Proc. VLDB","author":"Arasu A.","year":"2006","unstructured":"A. Arasu , V. Ganti , and R. Kaushik . Efficient exact set-similarity joins . In Proc. VLDB , pages 918 -- 929 , 2006 . A. Arasu, V. Ganti, and R. Kaushik. Efficient exact set-similarity joins. In Proc. VLDB, pages 918--929, 2006."},{"key":"e_1_2_1_6_1","unstructured":"Azure Databricks: Fast easy and collaborative Apache Spark based analytics service. https:\/\/azure.microsoft.com\/en-us\/services\/databricks\/.  Azure Databricks: Fast easy and collaborative Apache Spark based analytics service. https:\/\/azure.microsoft.com\/en-us\/services\/databricks\/."},{"key":"e_1_2_1_7_1","volume-title":"Modern information retrieval","author":"Baeza-Yates R.","year":"2011","unstructured":"R. Baeza-Yates and B. Ribeiro-Neto . Modern information retrieval . Pearson Addison Wesley , 2011 . R. Baeza-Yates and B. Ribeiro-Neto. Modern information retrieval. Pearson Addison Wesley, 2011."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.70"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872796"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.9"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1402020"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5244\/C.22.50"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732981"},{"key":"e_1_2_1_14_1","unstructured":"Data Ladder Product Matching. https:\/\/www.dataladder.com.  Data Ladder Product Matching. https:\/\/www.dataladder.com."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816663"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856330"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1557690.1557767"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3231751.3231760"},{"key":"e_1_2_1_20_1","first-page":"518","volume-title":"PVLDB","author":"Gionis A.","year":"1999","unstructured":"A. Gionis , P. Indyk , and R. Motwani . Similarity search in high dimensions via hashing . In PVLDB , pages 518 -- 529 , 1999 . A. Gionis, P. Indyk, and R. Motwani. Similarity search in high dimensions via hashing. In PVLDB, pages 518--529, 1999."},{"key":"e_1_2_1_21_1","first-page":"491","volume-title":"PVLDB","author":"Gravano L.","year":"2001","unstructured":"L. Gravano , H. Jagadish , P. G. Ipeirotis , D. Srivastava , N. Koudas , and S. Muthukrishnan . Approximate string joins in a database (almost) for free . In PVLDB , pages 491 -- 500 , 2001 . L. Gravano, H. Jagadish, P. G. Ipeirotis, D. Srivastava, N. Koudas, and S. Muthukrishnan. Approximate string joins in a database (almost) for free. In PVLDB, pages 491--500, 2001."},{"key":"e_1_2_1_22_1","unstructured":"Internet Movie Data Base. http:\/\/www.imdb.com.  Internet Movie Data Base. http:\/\/www.imdb.com."},{"key":"e_1_2_1_23_1","unstructured":"Informatica Data Quality. http:\/\/help.informatica.com.  Informatica Data Quality. http:\/\/help.informatica.com."},{"key":"e_1_2_1_24_1","unstructured":"Knime. https:\/\/www.knime.com\/nodeguide\/other-analytics-types\/text-processing\/fuzzy-string-matching.  Knime. https:\/\/www.knime.com\/nodeguide\/other-analytics-types\/text-processing\/fuzzy-string-matching."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142599"},{"key":"e_1_2_1_26_1","unstructured":"Melissa Data Matching. https:\/\/www.melissa.com\/data-deduplication.  Melissa Data Matching. https:\/\/www.melissa.com\/data-deduplication."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212353"},{"key":"e_1_2_1_28_1","unstructured":"MurmurHash. https:\/\/en.wikipedia.org\/wiki\/MurmurHash.  MurmurHash. https:\/\/en.wikipedia.org\/wiki\/MurmurHash."},{"key":"e_1_2_1_29_1","unstructured":"Microsoft Power Query. https:\/\/docs.microsoft.com\/en-us\/power-query\/.  Microsoft Power Query. https:\/\/docs.microsoft.com\/en-us\/power-query\/."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.151"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.195"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007652"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213935"},{"key":"e_1_2_1_34_1","unstructured":"Spark Package for Fuzzy Matching. https:\/\/spark-packages.org\/package\/itspawanbhardwaj\/spark-fuzzy-matching.  Spark Package for Fuzzy Matching. https:\/\/spark-packages.org\/package\/itspawanbhardwaj\/spark-fuzzy-matching."},{"key":"e_1_2_1_35_1","unstructured":"Fuzzy Lookup in SQL Server Integration Services. https:\/\/docs.microsoft.com\/en-us\/sql\/integration-services\/data-flow\/transformations\/fuzzy-lookup-transformation.  Fuzzy Lookup in SQL Server Integration Services. https:\/\/docs.microsoft.com\/en-us\/sql\/integration-services\/data-flow\/transformations\/fuzzy-lookup-transformation."},{"key":"e_1_2_1_36_1","unstructured":"Talend Fuzzy Matching. https:\/\/help.talend.com.  Talend Fuzzy Matching. https:\/\/help.talend.com."},{"key":"e_1_2_1_37_1","unstructured":"Trillium Global Locator. https:\/\/www.syncsort.com\/en\/Products\/DataQuality\/Trillium-Global-Locator.  Trillium Global Locator. https:\/\/www.syncsort.com\/en\/Products\/DataQuality\/Trillium-Global-Locator."},{"key":"e_1_2_1_38_1","unstructured":"USPS Database. https:\/\/postalpro.usps.com\/.  USPS Database. https:\/\/postalpro.usps.com\/."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807222"},{"key":"e_1_2_1_40_1","first-page":"10","volume-title":"Proc. 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 Proc. HotCloud , pages 10 -- 10 , 2010 . M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica. Spark: Cluster computing with working sets. In Proc. HotCloud, pages 10--10, 2010."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3352063.3352128","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:42:42Z","timestamp":1672224162000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3352063.3352128"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8]]},"references-count":40,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2019,8]]}},"alternative-id":["10.14778\/3352063.3352128"],"URL":"https:\/\/doi.org\/10.14778\/3352063.3352128","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,8]]}}}