Approximate XML joins

Sudipto Guha, H. V. Jagadish, Nick Koudas, Divesh Srivastava, Ting Yu

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

XML is widely recognized as the data interchange standard for tomorrow, because of its ability to represent data from a wide variety sources. Hence, XML is likely to be the format through which data from multiple sources is integrated.In this paper 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 approximate match in structure, in addition to, content has to be folded in the join operation. We quantify approximate match in structure and content using well defined notions of distance. For structure, we propose computationally inexpensive lower and upper bounds for the tree edit distance metric between two trees. We then show how the tree edit distance, and other metrics that quantify distance between trees, can be incorporated in a join framework. We introduce the notion 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. This gives rise to a variety of algorithmic approaches for the problem, which we formulate and analyze. We demonstrate the practical utility of our solutions using large collections of real and synthetic XML data sets.

Original languageEnglish
Title of host publicationProceedings of the 2002 ACM SIGMOD International Conference on Management of Data, SIGMOD 2002
PublisherAssociation for Computing Machinery, Inc
Pages287-298
Number of pages12
ISBN (Electronic)1581134975, 9781581134971
DOIs
Publication statusPublished - 3 Jun 2002
Externally publishedYes
Event2002 ACM SIGMOD International Conference on Management of Data, SIGMOD 2002 - Madison, United States
Duration: 3 Jun 20026 Jun 2002

Publication series

NameProceedings of the 2002 ACM SIGMOD International Conference on Management of Data, SIGMOD 2002

Conference

Conference2002 ACM SIGMOD International Conference on Management of Data, SIGMOD 2002
Country/TerritoryUnited States
CityMadison
Period3/06/026/06/02

Fingerprint

Dive into the research topics of 'Approximate XML joins'. Together they form a unique fingerprint.

Cite this