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

• 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
• ISSN: 1041-4347; 1558-2191
• DOI: 10.1109/TKDE.2008.83

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.