Twig Pattern Matching Running on XML Streams
| Autor: | Hongyu Gao, Husheng Liao, Ziqiang Deng |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
Finite-state machine
Theoretical computer science Computer science computer.internet_protocol InformationSystems_DATABASEMANAGEMENT String searching algorithm computer.software_genre Automaton Twig ComputingMethodologies_DOCUMENTANDTEXTPROCESSING Pattern matching Data mining computer Lowest common ancestor Blossom algorithm XML |
| Zdroj: | Web Technologies and Applications ISBN: 9783642294259 APWeb Workshops |
| DOI: | 10.1007/978-3-642-29426-6_6 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|