Scalable Filtering of Multiple Generalized-Tree-Pattern Queries over XML Streams

An XML publish/subscribe system needs to filter a large number of queries over XML streams. Most existing systems only consider filtering the simple XPath statements. In this paper, we focus on filtering of the more complex generalized-tree-pattern (GTP) queries. Our filtering mechanism is based on...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on knowledge and data engineering 2008-12, Vol.20 (12), p.1627-1640
Main Authors: Songting Chen, Hua-Gang Li, Tatemura, J., Wang-Pin Hsiung, Agrawal, D., Candan, K.S.
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Computer science
control theory
systems
Data processing. List processing. Character string processing
Database languages
Encoding
Exact sciences and technology
Extensible Markup Language
Filtering
Filtering algorithms
Filtration
generalized-tree-pattern queries
Information systems. Data bases
Matched filters
Memory organisation. Data processing
Merging
Polynomials
Queries
result encoding
Scalability
Software
Streams
Studies
Telecommunication traffic
Web services
XML
XML filtering
XML streams
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An XML publish/subscribe system needs to filter a large number of queries over XML streams. Most existing systems only consider filtering the simple XPath statements. In this paper, we focus on filtering of the more complex generalized-tree-pattern (GTP) queries. Our filtering mechanism is based on a novel Tree-of-Path (TOP) encoding scheme, which compactly represents the path matches for the entire document. First, we show that the TOP encodings can be efficiently produced via a shared bottom-up path matching. Second, with the aid of this TOP encoding, we can (1) achieve polynomial time and space complexity for post processing, (2) avoid redundant predicate evaluations, (3) allow an efficient duplicate-free and merge join-based algorithm for merging multiple encoded path matches and (4) simplify the processing of GTP queries. Overall our approach maximizes the sharing opportunity across queries by exploiting the suffix as well as prefix sharing. At the same time, our TOP encodings allow efficient post processing for GTP queries. Extensive performance studies show that our GFilter solution not only achieves significantly better filtering performance than state-of-the-art algorithms, but also is capable of efficiently filtering the more complex GTP queries.
ISSN:1041-4347
1558-2191
DOI:10.1109/TKDE.2008.83