{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T18:07:14Z","timestamp":1790791634808,"version":"4.1.0"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>\"Robert\" and \"Bob\" refer to the same first name but are textually far apart. Traditional string similarity functions do not allow a flexible way to account for such synonyms, abbreviations and aliases. Recently, string transformations have been proposed as a mechanism to make matching robust to such variations. However, in many domains, identifying an appropriate set of transformations is challenging as the space of possible transformations is large. In this paper, we investigate the problem of leveraging examples of matching strings to learn string transformations. We formulate an optimization problem where we are required to learn a concise set of transformations that explain most of the differences. We propose a greedy approximation algorithm for this NP-hard problem. Our experiments over real-life data illustrate the benefits of our approach.<\/jats:p>","DOI":"10.14778\/1687627.1687686","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"514-525","source":"Crossref","is-referenced-by-count":41,"title":["Learning string transformations from examples"],"prefix":"10.14778","volume":"2","author":[{"given":"Arvind","family":"Arasu","sequence":"first","affiliation":[{"name":"Microsoft Research, Redmond, WA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Surajit","family":"Chaudhuri","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raghav","family":"Kaushik","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497412"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.3115\/1075218.1075255"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1325851.1325891"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"S. Chaudhuri V. Ganti and D. Xin. Mining document collections to facilitate accurate approximate entity match 2009. Under submission.  S. Chaudhuri V. Ganti and D. Xin. Mining document collections to facilitate accurate approximate entity match 2009. Under submission.","DOI":"10.14778\/1687627.1687673"},{"key":"e_1_2_1_5_1","unstructured":"DBLP. http:\/\/www.informatik.uni-trier.de\/~ley\/db\/index.html.  DBLP. http:\/\/www.informatik.uni-trier.de\/~ley\/db\/index.html."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066168"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.9"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335409"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1213810"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142599"},{"key":"e_1_2_1_12_1","first-page":"68","volume-title":"Proc. of the 6th Intl. Workshop on Information Integration on the Web (IIWeb)","author":"Michelson M.","year":"2007"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2005.7"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775087"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1642293.1642589"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"P. D. Turney. Mining the Web for synonyms: PMI-IR versus LSA on TOEFL. Lecture Notes in Computer Science (2167):491--503 2001.   P. D. Turney. Mining the Web for synonyms: PMI-IR versus LSA on TOEFL. Lecture Notes in Computer Science (2167):491--503 2001.","DOI":"10.1007\/3-540-44795-4_42"},{"key":"e_1_2_1_17_1","unstructured":"United States Postal Service (USPS). http:\/\/www.usps.com.  United States Postal Service (USPS). http:\/\/www.usps.com."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1687627.1687686","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:29:12Z","timestamp":1672226952000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1687627.1687686"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.14778\/1687627.1687686"],"URL":"https:\/\/doi.org\/10.14778\/1687627.1687686","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}