An Automaton-based Index Scheme supporting Twig Queries for On-demand XML Data Broadcast
Publication Type
Journal Article
Publication Date
12-2015
Abstract
XML data broadcast is an efficient way to deliver semi-structured information in a wireless mobile environment. In the literature, many approaches have been proposed to disseminate XML data via wireless broadcast. However, because of the existence of “*” and “//” in queries, their performance deteriorates. In this paper, we propose a novel indexing method called Deterministic Finite Automaton-based Index (abbreviated as DFAI) on the XPath queries. Different from existing approaches which build index based on XML documents, DFAI is built based on the submitted queries. The new index treats the XPath queries as a DFA and it improves the efficiency of broadcast systems significantly. We further propose a compression strategy to reduce the index size of DFAI as well. Besides, as an extension, we extend the DFAI to support twig queries. Experiment results show that our method achieves a much better performance in terms of both access time and tuning time when compared with existing approaches.
Keywords
Air indexing, Deterministic finite automaton, On-demand XML data broadcast, Twig query
Discipline
Computer Sciences | Databases and Information Systems
Publication
Journal of Parallel and Distributed Computing
Volume
86
First Page
82
Last Page
97
ISSN
0743-7315
Identifier
10.1016/j.jpdc.2015.07.010
Publisher
Elsevier
Citation
LIU, Peng; SUN, Weiwei; ZHANG, Jian; and ZHENG, Baihua.
An Automaton-based Index Scheme supporting Twig Queries for On-demand XML Data Broadcast. (2015). Journal of Parallel and Distributed Computing. 86, 82-97.
Available at: https://ink.library.smu.edu.sg/sis_research/2979
Additional URL
http://dx.doi.org/10.1016/j.jpdc.2015.07.010