{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T16:51:57Z","timestamp":1759683117315,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2006,3,1]],"date-time":"2006-03-01T00:00:00Z","timestamp":1141171200000},"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":[[2006,3]]},"abstract":"<jats:p>XML is widely recognized as the data interchange standard of tomorrow because of its ability to represent data from a variety of sources. Hence, XML is likely to be the format through which data from multiple sources is integrated. In this article, we study the problem of integrating XML data sources through correlations realized as join operations. A challenging aspect of this operation is the XML document structure. Two documents might convey approximately or exactly the same information but may be quite different in structure. Consequently, an approximate match in structure, in addition to content, has to be folded into the join operation. We quantify an approximate match in structure and content for pairs of XML documents using well defined notions of distance. We show how notions of distance that have metric properties can be incorporated in a framework for joins between XML data sources and introduce the idea of reference sets to facilitate this operation. Intuitively, a reference set consists of data elements used to project the data space. We characterize what constitutes a good choice of a reference set, and we propose sampling-based algorithms to identify them. We then instantiate our join framework using the tree edit distance between a pair of trees. We next turn our attention to utilizing well known index structures to improve the performance of approximate XML join operations. We present a methodology enabling adaptation of index structures for this problem, and we instantiate it in terms of the R-tree. We demonstrate the practical utility of our solutions using large collections of real and synthetic XML data sets, varying parameters of interest, and highlighting the performance benefits of our approach.<\/jats:p>","DOI":"10.1145\/1132863.1132868","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"161-207","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Integrating XML data sources using approximate joins"],"prefix":"10.1145","volume":"31","author":[{"given":"Sudipto","family":"Guha","sequence":"first","affiliation":[{"name":"University of Pennsylvania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H. V.","family":"Jagadish","sequence":"additional","affiliation":[{"name":"University of Michigan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nick","family":"Koudas","sequence":"additional","affiliation":[{"name":"University of Toronto"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Divesh","family":"Srivastava","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs--Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ting","family":"Yu","sequence":"additional","affiliation":[{"name":"North Carolina State University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,3]]},"reference":[{"volume-title":"Proceedings of ICDE.","author":"Al-Khalifa S.","key":"e_1_2_1_1_1","unstructured":"Al-Khalifa , S. , Jagadish , H. V. , Koudas , N. , Patel , J. M. , Srivastava , D. , and Wu , Y . 2002. Structural joins: A primitive for efficient XML query pattern matching . Proceedings of ICDE. Al-Khalifa, S., Jagadish, H. V., Koudas, N., Patel, J. M., Srivastava, D., and Wu, Y. 2002. Structural joins: A primitive for efficient XML query pattern matching. Proceedings of ICDE."},{"key":"e_1_2_1_2_1","unstructured":"Apostolico A. and Galil Z. 1992. Pattern Matching Algorithms. Oxford University Press.   Apostolico A. and Galil Z. 1992. Pattern Matching Algorithms. Oxford University Press."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"volume-title":"Tree Edit Distance, Alignment Distance and Inclusion. Tech. rep. TR-2003-23 IT","author":"Bille P.","key":"e_1_2_1_4_1","unstructured":"Bille , P. 2003. Tree Edit Distance, Alignment Distance and Inclusion. Tech. rep. TR-2003-23 IT , University of Copenhagen. Bille, P. 2003. Tree Edit Distance, Alignment Distance and Inclusion. Tech. rep. TR-2003-23 IT, University of Copenhagen."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170075"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564727"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502808"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253266"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233366"},{"volume-title":"Proceedings of VLDB. 426--435","author":"Ciaccia P.","key":"e_1_2_1_10_1","unstructured":"Ciaccia , P. , Patella , M. , and Zezula , P . 1997. M-tree: An Efficient access method for similarity search metric spaces . Proceedings of VLDB. 426--435 . Ciaccia, P., Patella, M., and Zezula, P. 1997. M-tree: An Efficient access method for similarity search metric spaces. Proceedings of VLDB. 426--435."},{"volume-title":"Proceedings of ICDE. 41--52","author":"Cobena G.","key":"e_1_2_1_11_1","unstructured":"Cobena , G. , Abideboul , S. , and Marian , A . 2002. Detecting changes in XML documents . Proceedings of ICDE. 41--52 . Cobena, G., Abideboul, S., and Marian, A. 2002. Detecting changes in XML documents. Proceedings of ICDE. 41--52."},{"volume-title":"Indexing Multimedia Databases","author":"Faloutsos C.","key":"e_1_2_1_12_1","unstructured":"Faloutsos , C. 1996. Indexing Multimedia Databases . Kluwer , Academic Publishing . Faloutsos, C. 1996. Indexing Multimedia Databases. Kluwer, Academic Publishing."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191925"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/280277.280279"},{"volume-title":"Proceedings of VLDB. 230--242","author":"Garcia Y.","key":"e_1_2_1_15_1","unstructured":"Garcia , Y. , Lopez , M. , and Leutteneger , S . 1998. On optimal node splitting for R-trees . Proceedings of VLDB. 230--242 . Garcia, Y., Lopez, M., and Leutteneger, S. 1998. On optimal node splitting for R-trees. Proceedings of VLDB. 230--242."},{"volume-title":"Proceedings of VLDB. 133--145","author":"Garhaldas H.","key":"e_1_2_1_16_1","unstructured":"Garhaldas , H. , Florescu , D. , Shasha , D. , Simon , E. , and Saita , E . 2001. Declerative data cleaning . Proceedings of VLDB. 133--145 . Garhaldas, H., Florescu, D., Shasha, D., Simon, E., and Saita, E. 2001. Declerative data cleaning. Proceedings of VLDB. 133--145."},{"volume-title":"Proceedings of VLDB. 144--156","author":"Gravano L.","key":"e_1_2_1_17_1","unstructured":"Gravano , L. , Ipeirotis , P. , Jagadish , H. , Koudas , N. , Muthukrishnan , S. , and Srivastava , D . 2001. Approximate strings joins in a database (almost) for free . Proceedings of VLDB. 144--156 . Gravano, L., Ipeirotis, P., Jagadish, H., Koudas, N., Muthukrishnan, S., and Srivastava, D. 2001. Approximate strings joins in a database (almost) for free. Proceedings of VLDB. 144--156."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/645474.653881"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564705"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564725"},{"volume-title":"International Conference on Data Engineering (ICDE). 303--306","author":"Guha S.","key":"e_1_2_1_21_1","unstructured":"Guha , S. , Koudas , N. , Srivastava , D. , and Yu , T . 2003. Index based approximate XML joins . International Conference on Data Engineering (ICDE). 303--306 . Guha, S., Koudas, N., Srivastava, D., and Yu, T. 2003. Index based approximate XML joins. International Conference on Data Engineering (ICDE). 303--306."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276312"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/645478.654973"},{"volume-title":"Algorithms on Strings, Trees and Sequences","author":"Gusfield D.","key":"e_1_2_1_24_1","unstructured":"Gusfield , D. 1998. Algorithms on Strings, Trees and Sequences . Cambridge University Press . Gusfield, D. 1998. Algorithms on Strings, Trees and Sequences. Cambridge University Press."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"volume-title":"Proceedings of VLDB. 396--405","author":"Huang Y. W.","key":"e_1_2_1_26_1","unstructured":"Huang , Y. W. , Jing , N. , and Rudensteiner , E . 1997. Spatial joins using R-trees: Breadth first search traversal with global optimizations . Proceedings of VLDB. 396--405 . Huang, Y. W., Jing, N., and Rudensteiner, E. 1997. Spatial joins using R-trees: Breadth first search traversal with global optimizations. Proceedings of VLDB. 396--405."},{"volume-title":"Proceedings of VLDB. 500--510","author":"Kamel I.","key":"e_1_2_1_27_1","unstructured":"Kamel , I. and Faloutsos , C . 1994. Hilbert R-tree: An Improved R-tree using fractals . Proceedings of VLDB. 500--510 . Kamel, I. and Faloutsos, C. 1994. Hilbert R-tree: An Improved R-tree using fractals. Proceedings of VLDB. 500--510."},{"volume-title":"International Conference on Data Engineering. 466--475","author":"Koudas N.","key":"e_1_2_1_28_1","unstructured":"Koudas , N. and Sevcik , K. C . 1998. High dimensional similarity joins: Algorithms and performance evaluation . International Conference on Data Engineering. 466--475 . Koudas, N. and Sevcik, K. C. 1998. High dimensional similarity joins: Algorithms and performance evaluation. International Conference on Data Engineering. 466--475."},{"key":"e_1_2_1_29_1","unstructured":"Levenshtein V. 1966. Binary codes capable of correcting insertions deletions and reversals. Cybernetics and Control Theory. 707--710.  Levenshtein V. 1966. Binary codes capable of correcting insertions deletions and reversals. Cybernetics and Control Theory. 707--710."},{"volume-title":"Proceedings of VLDB. 581--590","author":"Marian A.","key":"e_1_2_1_30_1","unstructured":"Marian , A. , Abideboul , S. , Cobena , G. , and Mignet , L . 2001. Change centric management of versions in an XML warehouse . Proceedings of VLDB. 581--590 . Marian, A., Abideboul, S., Cobena, G., and Mignet, L. 2001. Change centric management of versions in an XML warehouse. Proceedings of VLDB. 581--590."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/375360.375365"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Preparata F. P. and Shamos M. I. 1985. Computational Geometry. Springer-Verlag Berlin Germany.   Preparata F. P. and Shamos M. I. 1985. Computational Geometry. Springer-Verlag Berlin Germany.","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"e_1_2_1_33_1","unstructured":"Sankoff D. and Kruskal J. 1983. Time Warps String Edits and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley Reading MA.  Sankoff D. and Kruskal J. 1983. Time Warps String Edits and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley Reading MA."},{"key":"e_1_2_1_34_1","first-page":"4","article-title":"Special issue on data cleaning","volume":"23","author":"Sarawagi S.","year":"2000","unstructured":"Sarawagi , S. 2000 . Special issue on data cleaning . IEEE Data Engin. Bull. 23 , 4 . Sarawagi, S. 2000. Special issue on data cleaning. IEEE Data Engin. Bull. 23, 4.","journal-title":"IEEE Data Engin. Bull."},{"volume-title":"Proceedings of the International Conference on Data Engineering. 301--311","author":"Shim K.","key":"e_1_2_1_35_1","unstructured":"Shim , K. , Srikant , R. , and Agrawal , R . 1997. High-dimensional similarity joins . Proceedings of the International Conference on Data Engineering. 301--311 . Shim, K., Srikant, R., and Agrawal, R. 1997. High-dimensional similarity joins. Proceedings of the International Conference on Data Engineering. 301--311."},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Zhang K. and Shasha D. 1997. Tree pattern matching. In Pattern Matching Algorithms Apostolico and Galil Eds. Oxford Univesity Press.   Zhang K. and Shasha D. 1997. Tree pattern matching. In Pattern Matching Algorithms Apostolico and Galil Eds. Oxford Univesity Press.","DOI":"10.1093\/oso\/9780195113679.003.0014"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233324"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132863.1132868","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1132863.1132868","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:06:13Z","timestamp":1750259173000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132863.1132868"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["10.1145\/1132863.1132868"],"URL":"https:\/\/doi.org\/10.1145\/1132863.1132868","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2006,3]]},"assertion":[{"value":"2006-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}