Title

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

Research Areas

Data Management and Analytics

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

Additional URL

http://dx.doi.org/10.1016/j.jpdc.2015.07.010

This document is currently not available here.

Share

COinS