An automaton-based index scheme supporting twig queries for on-demand XML data broadcast

摘要

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.