{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T09:09:59Z","timestamp":1777626599217,"version":"3.51.4"},"reference-count":59,"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>A similarity join aims to find all similar pairs between two collections of records. Established algorithms utilise different similarity measures, either syntactic or semantic, to quantify the similarity between two records. However, when records are similar in forms of a mixture of syntactic and semantic relations, utilising a single measure becomes inadequate to disclose the real similarity between records, and hence unable to obtain high-quality join results.<\/jats:p>\n          <jats:p>\n            In this paper, we study a unified framework to find similar records by combining multiple similarity measures. To achieve this goal, we first develop a new similarity framework that unifies the existing three kinds of similarity measures simultaneously, including syntactic (typographic) similarity, synonym-based similarity, and taxonomy-based similarity. We then theoretically prove that finding the maximum unified similarity between two strings is generally\n            <jats:italic>NP<\/jats:italic>\n            -hard, and furthermore develop an approximate algorithm which runs in polynomial time with a non-trivial approximation guarantee. To support efficient string joins based on our unified similarity measure, we adopt the filter-and-verification framework and propose a new signature structure, called\n            <jats:italic>pebble<\/jats:italic>\n            , which can be simultaneously adapted to handle multiple similarity measures. The salient feature of our approach is that, it can judiciously select the best pebble signatures and the overlap thresholds to maximise the filtering power. Extensive experiments show that our methods are capable of finding similar records having mixed types of similarity relations, while exhibiting high efficiency and scalability for similarity joins. The implementation can be downloaded at https:\/\/github.com\/HY-UDBMS\/AU-Join.\n          <\/jats:p>","DOI":"10.14778\/3342263.3342268","type":"journal-article","created":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T18:36:11Z","timestamp":1568831771000},"page":"1289-1302","source":"Crossref","is-referenced-by-count":7,"title":["Towards a unified framework for string similarity joins"],"prefix":"10.14778","volume":"12","author":[{"given":"Pengfei","family":"Xu","sequence":"first","affiliation":[{"name":"University of Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiaheng","family":"Lu","sequence":"additional","affiliation":[{"name":"University of Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287420"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497412"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687686"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.23.3.640"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1785162.1785216"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(96)00063-7"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11780441_4"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242591"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.32"},{"key":"e_1_2_1_10_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1007\/3-540-44985-X_19","volume-title":"SWAT","author":"Berman P.","year":"2000","unstructured":"P. Berman . A d\/2 approximation for maximum weight independent set in d-claw free graphs . In SWAT , volume 1851 of Lecture Notes in Computer Science , pages 214 -- 219 . Springer , 2000 . P. Berman. A d\/2 approximation for maximum weight independent set in d-claw free graphs. In SWAT, volume 1851 of Lecture Notes in Computer Science, pages 214--219. Springer, 2000."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956759"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1155"},{"key":"e_1_2_1_13_1","volume-title":"Introduction to multivariate analysis","author":"Chatfied C.","year":"2013","unstructured":"C. Chatfied and A. J. Collins . Introduction to multivariate analysis . Springer , 2013 . C. Chatfied and A. J. Collins. Introduction to multivariate analysis. Springer, 2013."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.9"},{"key":"e_1_2_1_15_1","first-page":"73","volume-title":"IIWeb","author":"Cohen W. W.","year":"2003","unstructured":"W. W. Cohen , P. D. Ravikumar , and S. E. Fienberg . A comparison of string distance metrics for name-matching tasks . In IIWeb , pages 73 -- 78 , 2003 . W. W. Cohen, P. D. Ravikumar, and S. E. Fienberg. A comparison of string distance metrics for name-matching tasks. In IIWeb, pages 73--78, 2003."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1830440"},{"key":"e_1_2_1_17_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1007\/978-3-319-96893-3_19","volume-title":"APWeb\/WAIM (2)","author":"Dong Z.","year":"2018","unstructured":"Z. Dong , J. Fan , Lu, X. Du , and T. W. Ling . Using crowdsourcing for fine-grained entity type completion in knowledge bases . In APWeb\/WAIM (2) , volume 10988 of Lecture Notes in Computer Science , pages 248 -- 263 . Springer , 2018 . Z. Dong, J. Fan, Lu, X. Du, and T. W. Ling. Using crowdsourcing for fine-grained entity type completion in knowledge bases. In APWeb\/WAIM (2), volume 10988 of Lecture Notes in Computer Science, pages 248--263. Springer, 2018."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/BIGCOMP.2016.7425795"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10586-017-1089-8"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.3233\/SW-170275"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2014.07.007"},{"key":"e_1_2_1_22_1","first-page":"11","article-title":"Incremental calculation of weighted mean and variance","volume":"4","author":"Finch T.","year":"2009","unstructured":"T. Finch . Incremental calculation of weighted mean and variance . University of Cambridge , 4 : 11 -- 15 , 2009 . T. Finch. Incremental calculation of weighted mean and variance. University of Cambridge, 4:11--5, 2009.","journal-title":"University of Cambridge"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/800119.803884"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523693"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0402008"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376815.1376819"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732296.2732299"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575832_13"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497434"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465313"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818177"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2576232"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1667884.1667889"},{"key":"e_1_2_1_35_1","volume-title":"Markov chains and stochastic stability","author":"Meyn S. P.","year":"2012","unstructured":"S. P. Meyn and R. L. Tweedie . Markov chains and stochastic stability . Springer Science & Business Media , 2012 . S. P. Meyn and R. L. Tweedie. Markov chains and stochastic stability. Springer Science & Business Media, 2012."},{"key":"e_1_2_1_36_1","volume-title":"ICLR (Workshop)","author":"Mikolov T.","year":"2013","unstructured":"T. Mikolov , K. Chen , G. Corrado , and J. Dean . Efficient estimation of word representations in vector space . In ICLR (Workshop) , 2013 . T. Mikolov, K. Chen, G. Corrado, and J. Dean. Efficient estimation of word representations in vector space. In ICLR (Workshop), 2013."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2086753"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0105003"},{"key":"e_1_2_1_39_1","volume-title":"On local search and LP and SDP relaxations for k-set packing. CoRR, abs\/1507.07459","author":"Oosterwijk T.","year":"2015","unstructured":"T. Oosterwijk . On local search and LP and SDP relaxations for k-set packing. CoRR, abs\/1507.07459 , 2015 . T. Oosterwijk. On local search and LP and SDP relaxations for k-set packing. CoRR, abs\/1507.07459, 2015."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/D14-1162"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3275536.3275539"},{"issue":"4","key":"e_1_2_1_42_1","first-page":"3","article-title":"Problems and current approaches","volume":"23","author":"Rahm E.","year":"2000","unstructured":"E. Rahm and H. H. Do . Data cleaning : Problems and current approaches . IEEE Data Eng. Bull. , 23 ( 4 ): 3 -- 13 , 2000 . E. Rahm and H. H. Do. Data cleaning: Problems and current approaches. IEEE Data Eng. Bull., 23(4):3--13, 2000.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.195"},{"key":"e_1_2_1_44_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1007\/978-3-319-18111-0_37","volume-title":"CICLing (1)","author":"Saikh T.","year":"2015","unstructured":"T. Saikh , S. K. Naskar , C. Giri , and S. Bandyopadhyay . Textual entailment using different similarity metrics . In CICLing (1) , volume 9041 of Lecture Notes in Computer Science , pages 491 -- 501 . Springer , 2015 . T. Saikh, S. K. Naskar, C. Giri, and S. Bandyopadhyay. Textual entailment using different similarity metrics. In CICLing (1), volume 9041 of Lecture Notes in Computer Science, pages 491--501. Springer, 2015."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4573(88)90021-0"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2601325"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35176-1_34"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242667"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872427.2874809"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151113.3151118"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btm393"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824051"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213847"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.3115\/981732.981751"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367516"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3269206.3269236"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-55699-4_13"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484838.2484842"},{"key":"e_1_2_1_59_1","doi-asserted-by":"crossref","DOI":"10.1201\/9781420035346","volume-title":"CRC standard mathematical tables and formulae","author":"Zwillinger D.","year":"2002","unstructured":"D. Zwillinger . CRC standard mathematical tables and formulae . CRC press , 2002 . D. Zwillinger. CRC standard mathematical tables and formulae. CRC press, 2002."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3342263.3342268","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:58:52Z","timestamp":1672221532000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3342263.3342268"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7]]},"references-count":59,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["10.14778\/3342263.3342268"],"URL":"https:\/\/doi.org\/10.14778\/3342263.3342268","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,7]]}}}