EECS technical reports

Conditions of Use

Archive Home Page

NFA-based Filtering for Efficient and Scalable XML Routing

Diao, Yanlei
Zhang, Hao
Franklin, Michael J.
Technical Report Identifier: CSD-01-1159

Abstract: Soon, much of the data exchanged over the Internet will be encoded in XML. This encoding can be used as the basis for sophisticated filtering and content-based routing of data using XML queries. Filtering systems such as XFilter represent XML path expressions as Finite State Machines and index them; In contrast, work on continuous query processing for database systems has focused on grouping common parts of relational-style queries. It is clear that for scalable and efficient XML filtering and routing both types of techniques will be needed. We propose a new approach based on Nondeterministic Finite Automata (NFA) that indexes path expressions and captures the overlap between queries naturally. The approach also has the potential of gracefully handling other problems in this environment such as concurrent filtering and online updates. Preliminary experimental results show that the NFA approach can dramatically improve filtering performance.