{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,14]],"date-time":"2026-08-14T09:33:53Z","timestamp":1786700033701,"version":"build-2736575974"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2008,2,15]],"date-time":"2008-02-15T00:00:00Z","timestamp":1203033600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2010,2]]},"abstract":"<jats:p>When integrating data from autonomous sources, exact matches of data items that represent the same real-world object often fail due to a lack of common keys. Yet in many cases structural information is available and can be used to match such data. Typically the matching must be approximate since the representations in the sources differ.<\/jats:p>\n          <jats:p>\n            We propose\n            <jats:italic>pq<\/jats:italic>\n            -grams to approximately match hierarchical data from autonomous sources and define the\n            <jats:italic>pq<\/jats:italic>\n            -gram distance between ordered labeled trees as an effective and efficient approximation of the fanout weighted tree edit distance. We prove that the\n            <jats:italic>pq<\/jats:italic>\n            -gram distance is a lower bound of the fanout weighted tree edit distance and give a normalization of the\n            <jats:italic>pq<\/jats:italic>\n            -gram distance for which the triangle inequality holds. Experiments on synthetic and real-world data (residential addresses and XML) confirm the scalability of our approach and show the effectiveness of\n            <jats:italic>pq<\/jats:italic>\n            -grams.\n          <\/jats:p>","DOI":"10.1145\/1670243.1670247","type":"journal-article","created":{"date-parts":[[2010,2,16]],"date-time":"2010-02-16T20:51:06Z","timestamp":1266353466000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":56,"title":["The\n            <i>pq<\/i>\n            -gram distance between ordered labeled trees"],"prefix":"10.1145","volume":"35","author":[{"given":"Nikolaus","family":"Augsten","sequence":"first","affiliation":[{"name":"Free University of Bozen-Bolzano, Bozen-Bolzano, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"B\u00f6hlen","sequence":"additional","affiliation":[{"name":"Free University of Bozen-Bolzano, Bozen-Bolzano, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Johann","family":"Gamper","sequence":"additional","affiliation":[{"name":"Free University of Bozen-Bolzano, Bozen-Bolzano, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2008,2,15]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE). IEEE Computer Science Press, 141--152","author":"Al-Khalifa S."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497490"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Augsten N. B\u00f6hlen M. and \n      \n      \n      Gamper J\n      \n  \n  . \n  2004\n  . Reducing the integration of public administration databases to approximate tree matching. In Proceedings of the 3rd International Conference on Electronic Government. R. Traunm\u00fcller Ed. Lecture Notes in Computer Science\n   vol. \n  3183\n  . \n  Springer 102--107.  Augsten N. B\u00f6hlen M. and Gamper J. 2004. Reducing the integration of public administration databases to approximate tree matching. In Proceedings of the 3rd International Conference on Electronic Government. R. Traunm\u00fcller Ed. Lecture Notes in Computer Science vol. 3183. Springer 102--107.","DOI":"10.1007\/978-3-540-30078-6_17"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). ACM Press, 301--312","author":"Augsten N."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564727"},{"key":"e_1_2_1_6_1","first-page":"48","article-title":"Trees, databases and SQL","volume":"7","author":"Celko J.","year":"1994","journal-title":"Datab. Program. Des."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Celko J. 2004. Trees and Hierarchies in SQL for Smarties. Morgan Kaufmann San Francisco CA.   Celko J. 2004. Trees and Hierarchies in SQL for Smarties. Morgan Kaufmann San Francisco CA.","DOI":"10.1016\/B978-155860920-4\/50002-7"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233366"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1170"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE). IEEE Computer Science Press, 41--52","author":"Cob\u00e9na G."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2004.11.009"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872832"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP'07)","volume":"4596","author":"Demaine E. D."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.27"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061326"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). Morgan Kaufmann, 491--500","author":"Gravano L."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564705"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564725"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). ACM Press, 1022--1032","author":"Helmer S.","year":"2007"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). Morgan Kaufmann, 273--284","author":"Jiang H."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)80015-8"},{"key":"e_1_2_1_22_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 6th European Symposium on Algorithms","author":"Klein P. N."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.19"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/375360.375365"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 5th International Workshop on the Web and Databases (WebDB).","author":"Nierman A."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/11563983_17"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007686"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007599"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/11687238_46"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85713-6_18"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2007.05.008"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90064-3"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/322139.322143"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564715"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90143-4"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SPIRE.2001.989761"},{"key":"e_1_2_1_37_1","unstructured":"van Rijsbergen C. J. 1979. Information Retrieval 2nd Ed. Butterworth-Heinemann UK.   van Rijsbergen C. J. 1979. Information Retrieval 2nd Ed. Butterworth-Heinemann UK."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066207"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066243"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380210706"},{"key":"e_1_2_1_41_1","unstructured":"Yianilos P. N. 1991 2002. Normalized forms for two common metrics. Tech. rep. NEC Research Institute.  Yianilos P. N. 1991 2002. Normalized forms for two common metrics. Tech. rep. NEC Research Institute."},{"key":"e_1_2_1_42_1","volume-title":"Advances in Database Systems","volume":"32","author":"Zezula P."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375722"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(94)00109-Y"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218082"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1670243.1670247","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1670243.1670247","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:40:58Z","timestamp":1750250458000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1670243.1670247"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,2,15]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,2]]}},"alternative-id":["10.1145\/1670243.1670247"],"URL":"https:\/\/doi.org\/10.1145\/1670243.1670247","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,2,15]]},"assertion":[{"value":"2008-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-02-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}