An Automaton-based Index Scheme supporting Twig Queries for On-demand XML Data Broadcast

• Main Authors: LIU, Peng, SUN, Weiwei, ZHANG, Jian, ZHENG, Baihua
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2015
• Subjects: Air indexing; Deterministic finite automaton; On-demand XML data broadcast; Twig query; Computer Sciences; Databases and Information Systems
• Online Access: https://ink.library.smu.edu.sg/sis_research/2979
• Institution: Singapore Management University

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.