{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:53:58Z","timestamp":1758272038162,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,10,23]],"date-time":"2015-10-23T00:00:00Z","timestamp":1445558400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF China","award":["61472427"],"award-info":[{"award-number":["61472427"]}]},{"DOI":"10.13039\/100007797","name":"University of Helsinki","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007797","id-type":"DOI","asserted-by":"crossref"}]},{"name":"973 Program of China","award":["2012CB316205"],"award-info":[{"award-number":["2012CB316205"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2015,10,23]]},"abstract":"<jats:p>\n            A string-similarity measure quantifies the similarity between two text strings for approximate string matching or comparison. For example, the strings \u201cSam\u201d and \u201cSamuel\u201d can be considered to be similar. Most existing work that computes the similarity of two strings only considers syntactic similarities, for example, number of common words or\n            <jats:italic>q<\/jats:italic>\n            -grams. While this is indeed an indicator of similarity, there are many important cases where syntactically-different strings can represent the same real-world object. For example, \u201cBill\u201d is a short form of \u201cWilliam,\u201d and \u201cDatabase Management Systems\u201d can be abbreviated as \u201cDBMS.\u201d Given a collection of predefined synonyms, the purpose of this article is to explore such existing knowledge to effectively evaluate the similarity between two strings and efficiently perform similarity searches and joins, thereby boosting the quality of approximate string matching.\n          <\/jats:p>\n          <jats:p>In particular, we first present an expansion-based framework to measure string similarities efficiently while considering synonyms. We then study efficient algorithms for similarity searches and joins by proposing two novel indexes, called SI-trees and QP-trees, which combine signature-filtering and length-filtering strategies. In order to improve the efficiency of our algorithms, we develop an estimator to estimate the size of candidates to enable an online selection of signature filters. This estimator provides strong low-error, high-confidence guarantees while requiring only logarithmic space and time costs, thus making our method attractive both in theory and in practice. Finally, the experimental results from a comprehensive study of the algorithms with three real datasets verify the effectiveness and efficiency of our approaches.<\/jats:p>","DOI":"10.1145\/2818177","type":"journal-article","created":{"date-parts":[[2015,10,24]],"date-time":"2015-10-24T18:27:12Z","timestamp":1445711232000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Boosting the Quality of Approximate String Matching by Synonyms"],"prefix":"10.1145","volume":"40","author":[{"given":"Jiaheng","family":"Lu","sequence":"first","affiliation":[{"name":"Renmin University of China and University of Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chunbin","family":"Lin","sequence":"additional","affiliation":[{"name":"University of California, San Diego, La Jolla, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Wang","sequence":"additional","affiliation":[{"name":"University of New South Wales, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chen","family":"Li","sequence":"additional","affiliation":[{"name":"University of California, Irvine, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaokui","family":"Xiao","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,10,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"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"},{"volume-title":"Proceedings of the VLDB Conference (VLDB'06)","author":"Arasu A.","key":"e_1_2_1_4_1","unstructured":"A. Arasu , V. Ganti , and R. Kaushik . 2006. Efficient exact set-similarity joins . In Proceedings of the VLDB Conference (VLDB'06) . 918--929. A. Arasu, V. Ganti, and R. Kaushik. 2006. Efficient exact set-similarity joins. In Proceedings of the VLDB Conference (VLDB'06). 918--929."},{"volume-title":"Proceedings of the 6th International Workshop on Randomization and Approximation Techniques (RANDOM'02)","author":"Bar-Yossef Z.","key":"e_1_2_1_5_1","unstructured":"Z. Bar-Yossef , T. S. Jayram , R. Kumar , D. Sivakumar , and L. Trevisan . 2002. Counting distinct elements in a data stream . In Proceedings of the 6th International Workshop on Randomization and Approximation Techniques (RANDOM'02) . 1--10. Z. Bar-Yossef, T. S. Jayram, R. Kumar, D. Sivakumar, and L. Trevisan. 2002. Counting distinct elements in a data stream. In Proceedings of the 6th International Workshop on Randomization and Approximation Techniques (RANDOM'02). 1--10."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242591"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956759"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9322-y"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(97)00031-7"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872796"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559919"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.127"},{"volume-title":"Proceedings of the IJCAI-03 Workshop on Information Integration (IIWeb'03)","author":"Cohen W. W.","key":"e_1_2_1_14_1","unstructured":"W. W. Cohen , P. D. Ravikumar , and S. E. Fienberg . 2003. A comparison of string distance metrics for name-matching tasks . In Proceedings of the IJCAI-03 Workshop on Information Integration (IIWeb'03) . 73--78. W. W. Cohen, P. D. Ravikumar, and S. E. Fienberg. 2003. A comparison of string distance metrics for name-matching tasks. In Proceedings of the IJCAI-03 Workshop on Information Integration (IIWeb'03). 73--78."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/795663.796326"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0135-3"},{"volume-title":"Proceedings of the VLDB Conference (VLDB'01)","author":"Gravano L.","key":"e_1_2_1_18_1","unstructured":"L. Gravano , P. G. Ipeirotis , H. V. Jagadish , N. Koudas , S. Muthukrishnan , and D. Srivastava . 2001. Approximate string joins in a database (almost) for free . In Proceedings of the VLDB Conference (VLDB'01) . 491--500. L. Gravano, P. G. Ipeirotis, H. V. Jagadish, N. Koudas, S. Muthukrishnan, and D. Srivastava. 2001. Approximate string joins in a database (almost) for free. In Proceedings of the VLDB Conference (VLDB'01). 491--500."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453883"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1013367.1013477"},{"volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04)","author":"Iwama K.","key":"e_1_2_1_21_1","unstructured":"K. Iwama and S. Tamaki . 2004. Improved upper bounds for 3-SAT . In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04) . K. Iwama and S. Tamaki. 2004. Improved upper bounds for 3-SAT. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_34"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575832_13"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687702"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/1978665.1978666"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497434"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2078331.2078340"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465313"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/312624.312680"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989431"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4573(88)90021-0"},{"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.1093\/bioinformatics\/btm393"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213847"},{"volume-title":"Statistical Research Division","author":"Winkler W. E.","key":"e_1_2_1_35_1","unstructured":"W. E. Winkler . 1999. The state of record linkage and current research problems. Tech. rep ., Statistical Research Division , U.S. Census Bureau . W. E. Winkler. 1999. The state of record linkage and current research problems. Tech. rep., Statistical Research Division, U.S. Census Bureau."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453957"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000824.2000825"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818177","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2818177","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:39:01Z","timestamp":1750221541000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818177"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,23]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,10,23]]}},"alternative-id":["10.1145\/2818177"],"URL":"https:\/\/doi.org\/10.1145\/2818177","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2015,10,23]]},"assertion":[{"value":"2014-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-10-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}