Abstract | ||
---|---|---|
Twig pattern matching plays an important role in XML query processing, holistic twig pattern matching algorithms have been proposed and are considered to be effective since they avoid producing large number of intermediate results. Meanwhile, automaton-based approaches are naturally used in filtering XML streams, because Finite State Machines(FSMs) are driven by events which conform to event-based XML parser SAX. In this paper, we proposed a hybrid approach combining FSM and holistic twig matching algorithm to find occurrences of twig pattern in XML streams. That is, we locate the lowest common ancestor(LCA) of return node(s) in twig pattern, decompose the twig pattern according to the LCA, use automaton-based approach for processing the sub twig pattern above LCA, and regular holistic twig pattern matching algorithm for the sub twig pattern below LCA. It only needs to buffer the elements between the start and end tag of LCA. Experiments show the effectiveness of this approach. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/978-3-642-29426-6_6 | APWeb Workshops |
Keywords | Field | DocType |
xml stream,holistic twig,sub twig pattern,hybrid approach,regular holistic twig pattern,automaton-based approach,twig pattern,twig pattern matching,xml query processing,holistic twig pattern | String searching algorithm,Data mining,Twig,Lowest common ancestor,XML,Computer science,Automaton,Finite-state machine,Theoretical computer science,Pattern matching,Database,Blossom algorithm | Conference |
Citations | PageRank | References |
1 | 0.37 | 10 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ziqiang Deng | 1 | 1 | 0.37 |
Husheng Liao | 2 | 20 | 11.82 |
Hongyu Gao | 3 | 238 | 12.05 |