loading...
Incrementally-Updatable Stream Processors for XPath Queries based on Merging Automata via Ordered Hash-keys
Regensburg, Germany September 03-September 07
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/DEXA.2007.1318th International Conference on Data ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Hajime Takekawa, Polytechnic University, Japan
Hiroshi Ishikawa, Sizuoka University, Japan
Various kinds of data such as news articles and sensor data are generated continuously in the form of XML data on the network. The processing systems (e.g., systems for selective dissemination of information and notification) must evaluate many filters for every XML data. Therefore, Gupta and Suciu proposed an automaton called the XPush machine, which can efficiently evaluate a large number of XPath filters, each with many predicates, on a stream of XML documents. The XPush machine is constructed by creating an AFA (Alternating Finite Automaton) for each filter, and then transforming the set of AFAs into a single DPDA (Deterministic PushDown Automaton). Since the XPush machine cannot be partially updated inherently, however, addition of a single filter necessitates recalculation (i.e., reconstruction) of the XPush machine as a whole. In other words, the cost of updating an automaton depends on the total number of AFAs (or filters). In this paper, we propose and evaluate an integrated XPush machine, which enables incremental update by constructing the whole machine from a set of sub-XPush machines. The evaluation result positively demonstrates that efficient partial exchange of the AFAs is possible without significantly affecting all of the state transition tables.
Citation:
Hajime Takekawa, Hiroshi Ishikawa, "Incrementally-Updatable Stream Processors for XPath Queries based on Merging Automata via Ordered Hash-keys," dexa, pp.40-44, 18th International Conference on Database and Expert Systems Applications (DEXA 2007), 2007
Usage of this product signifies your acceptance of the Terms of Use.