Institutional Repository [SANDBOX]
Technical University of Crete
EN  |  EL

Search

Browse

My Space

Efficient filtering of XML documents with XPath expressions

Chan Chee-Yong, Felber Pascal , Garofalakis Minos, Rastogi Rajeev

Simple record


URIhttp://purl.tuc.gr/dl/dias/0BE2F0C6-D4B0-4D18-AEE0-E8930B3405B2-
Identifierhttp://dl.acm.org/citation.cfm?id=764205&dl=ACM&coll=DL&CFID=723856831&CFTOKEN=21128548-
Identifierhttps://doi.org/10.1007/s00778-002-0077-6-
Languageen-
Extent27 pagesen
TitleEfficient filtering of XML documents with XPath expressionsen
CreatorChan Chee-Yongen
CreatorFelber Pascal en
CreatorGarofalakis Minosen
CreatorΓαροφαλακης Μινωςel
CreatorRastogi Rajeeven
PublisherAssociation for Computing Machineryen
Content SummaryThe publish/subscribe paradigm is a popular model for allowing publishers (i.e., data generators) to selectively disseminate data to a large number of widely dispersed subscribers (i.e., data consumers) who have registered their interest in specific information items. Early publish/subscribe systems have typically relied on simple subscription mechanisms, such as keyword or ”bag of words” matching, or simple comparison predicates on attribute values. The emergence of XML as a standard for information exchange on the Internet has led to an increased interest in using more expressive subscription mechanisms (e.g., based on XPath expressions) that exploit both the structure and the content of published XML documents. Given the increased complexity of these new data-filtering mechanisms, the problem of effectively identifying the subscription profiles that match an incoming XML document poses a difficult and important research challenge. In this paper, we propose a novel index structure, termed XTrie, that supports the efficient filtering of XML documents based on XPath expressions. Our XTrie index structure offers several novel features that, we believe, make it especially attractive for large-scale publish/subscribe systems. First, XTrie is designed to support effective filtering based on complex XPath expressions (as opposed to simple, single-path specifications). Second, our XTrie structure and algorithms are designed to support both ordered and unordered matching of XML data. Third, by indexing on sequences of elements organized in a trie structure and using a sophisticated matching algorithm, XTrie is able to both reduce the number of unnecessary index probes as well as avoid redundant matchings, thereby providing extremely efficient filtering. Our experimental results over a wide range of XML document and XPath expression workloads demonstrate that our XTrie index structure outperforms earlier approaches by wide margins.en
Type of ItemPeer-Reviewed Journal Publicationen
Type of ItemΔημοσίευση σε Περιοδικό με Κριτέςel
Licensehttp://creativecommons.org/licenses/by/4.0/en
Date of Item2015-10-29-
Date of Publication2002-
SubjectXML (Document markup language)en
Bibliographic CitationC.-Y. Chan, P. Felber, M. Garofalakis and R. Rastogi, "Efficient filtering of XML documents with XPath expressions", VLDB J., vol. 11, no. 4, pp. 354-379, Dec. 2002. doi:10.1007/s00778-002-0077-6en

Services

Statistics