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.
Title
NFA-based Filtering for Efficient and Scalable XML Routing
Published
1905-06-23
Full Collection Name
Electrical Engineering & Computer Sciences Technical Reports
Other Identifiers
CSD-01-1159
Type
Text
Extent
11 p
Archive
The Engineering Library
Usage Statement
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).
