View article

Several applications based on XML stream processing have recently emerged, such as those for air traffic control and the selective dissemination of information (SDI). Their common need is to process a large number of XPath expressions in continuous XML streams at high throughput.This paper proposes four techniques for XPath expression processing based on Deterministic Finite Automata (DFA) for two purposes: to improve the memory usage efficiency of the automata and to support the processing of branching XPath expressions. The first technique, called n-DFA, clusters the given XPath expressions into n clusters to reduce the number of DFA states. The second, called shared NFA state table, lets the Non-Deterministic Finite Automata (NFA) state set be shared among the DFA states. Our experiments show that memory usage in an 8-DFA can, with the shared NFA state table, be reduced to 1/40th that of the …