An Automaton-Based Index Scheme for On-Demand XML Data Broadcast

Weiwei Sun; Peng Liu; Jingjing Wu; Yongrui Qin; Baihua Zheng

doi:10.1007/978-3-642-29035-0_7

An Automaton-Based Index Scheme for On-Demand XML Data Broadcast

Weiwei Sun, Peng Liu, Jingjing Wu, Yongrui Qin, Baihua Zheng

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

8 Citations (Scopus)

Abstract

XML data broadcast is an efficient way to deliver semi-structured information in wireless mobile environment. In the literature, many approaches have been proposed to improve the performance of XML data broadcast. However, due to the appearance of wildcard "*" and double slash "//" in queries, their performance deteriorates. Consequently, in this paper, we propose a novel air 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, we propose to build the index based on the queries submitted by users. The new index treating the XPath queries with "*" or "//" as a DFA actually improves the efficiency of broadcast system significantly. We further propose an efficient compression strategy to reduce the index size of DFAI as well. Experiment results show that our new index method achieves a much better performance in terms of both access time and tuning time when compared with existing approaches.

Original language	English
Title of host publication	Database Systems for Advanced Applications
Subtitle of host publication	17th International Conference, DASFAA 2012, Busan, South Korea, April 15-19, 2012, Proceedings, Part II
Editors	Sang-goo Lee, Zhiyong Peng, Xiaofang Zhou, Yang-Sae Moon, Rainer Unland, Jaesoo Yoo
Publisher	Springer-Verlag Berlin Heidelberg
Pages	96-110
Number of pages	15
Volume	LNCS 7239
Edition	PART 2
ISBN (Electronic)	9783642290350
ISBN (Print)	9783642290343
DOIs	https://doi.org/10.1007/978-3-642-29035-0_7
Publication status	Published - 2012
Externally published	Yes
Event	17th International Conference on Database Systems for Advanced Applications - Busan, Korea, Republic of Duration: 15 Apr 2012 → 18 Apr 2012 Conference number: 17 https://www.springer.com/gp/book/9783642290220

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 2
Volume	7239 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	17th International Conference on Database Systems for Advanced Applications
Abbreviated title	DASFAA 2012
Country/Territory	Korea, Republic of
City	Busan
Period	15/04/12 → 18/04/12
Internet address	https://www.springer.com/gp/book/9783642290220

Access to Document

10.1007/978-3-642-29035-0_7Licence: Unspecified

Cite this

Sun, W., Liu, P., Wu, J., Qin, Y., & Zheng, B. (2012). An Automaton-Based Index Scheme for On-Demand XML Data Broadcast. In S. Lee, Z. Peng, X. Zhou, Y-S. Moon, R. Unland, & J. Yoo (Eds.), Database Systems for Advanced Applications: 17th International Conference, DASFAA 2012, Busan, South Korea, April 15-19, 2012, Proceedings, Part II (PART 2 ed., Vol. LNCS 7239, pp. 96-110). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7239 LNCS, No. PART 2). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/978-3-642-29035-0_7

Sun, Weiwei ; Liu, Peng ; Wu, Jingjing et al. / An Automaton-Based Index Scheme for On-Demand XML Data Broadcast. Database Systems for Advanced Applications: 17th International Conference, DASFAA 2012, Busan, South Korea, April 15-19, 2012, Proceedings, Part II. editor / Sang-goo Lee ; Zhiyong Peng ; Xiaofang Zhou ; Yang-Sae Moon ; Rainer Unland ; Jaesoo Yoo. Vol. LNCS 7239 PART 2. ed. Springer-Verlag Berlin Heidelberg, 2012. pp. 96-110 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2).

@inproceedings{0974772f36874d75aac7b539a3a6546b,

title = "An Automaton-Based Index Scheme for On-Demand XML Data Broadcast",

abstract = "XML data broadcast is an efficient way to deliver semi-structured information in wireless mobile environment. In the literature, many approaches have been proposed to improve the performance of XML data broadcast. However, due to the appearance of wildcard {"}*{"} and double slash {"}//{"} in queries, their performance deteriorates. Consequently, in this paper, we propose a novel air 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, we propose to build the index based on the queries submitted by users. The new index treating the XPath queries with {"}*{"} or {"}//{"} as a DFA actually improves the efficiency of broadcast system significantly. We further propose an efficient compression strategy to reduce the index size of DFAI as well. Experiment results show that our new index 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",

author = "Weiwei Sun and Peng Liu and Jingjing Wu and Yongrui Qin and Baihua Zheng",

year = "2012",

doi = "10.1007/978-3-642-29035-0_7",

language = "English",

isbn = "9783642290343",

volume = "LNCS 7239",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag Berlin Heidelberg",

number = "PART 2",

pages = "96--110",

editor = "Sang-goo Lee and Zhiyong Peng and Xiaofang Zhou and Yang-Sae Moon and Rainer Unland and Jaesoo Yoo",

booktitle = "Database Systems for Advanced Applications",

address = "Germany",

edition = "PART 2",

note = "17th International Conference on Database Systems for Advanced Applications, DASFAA 2012 ; Conference date: 15-04-2012 Through 18-04-2012",

url = "https://www.springer.com/gp/book/9783642290220",

}

Sun, W, Liu, P, Wu, J, Qin, Y & Zheng, B 2012, An Automaton-Based Index Scheme for On-Demand XML Data Broadcast. in S Lee, Z Peng, X Zhou, Y-S Moon, R Unland & J Yoo (eds), Database Systems for Advanced Applications: 17th International Conference, DASFAA 2012, Busan, South Korea, April 15-19, 2012, Proceedings, Part II. PART 2 edn, vol. LNCS 7239, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 2, vol. 7239 LNCS, Springer-Verlag Berlin Heidelberg, pp. 96-110, 17th International Conference on Database Systems for Advanced Applications, Busan, Korea, Republic of, 15/04/12. https://doi.org/10.1007/978-3-642-29035-0_7

An Automaton-Based Index Scheme for On-Demand XML Data Broadcast. / Sun, Weiwei; Liu, Peng; Wu, Jingjing et al.

Database Systems for Advanced Applications: 17th International Conference, DASFAA 2012, Busan, South Korea, April 15-19, 2012, Proceedings, Part II. ed. / Sang-goo Lee; Zhiyong Peng; Xiaofang Zhou; Yang-Sae Moon; Rainer Unland; Jaesoo Yoo. Vol. LNCS 7239 PART 2. ed. Springer-Verlag Berlin Heidelberg, 2012. p. 96-110 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7239 LNCS, No. PART 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - An Automaton-Based Index Scheme for On-Demand XML Data Broadcast

AU - Sun, Weiwei

AU - Liu, Peng

AU - Wu, Jingjing

AU - Qin, Yongrui

AU - Zheng, Baihua

N1 - Conference code: 17

PY - 2012

Y1 - 2012

N2 - XML data broadcast is an efficient way to deliver semi-structured information in wireless mobile environment. In the literature, many approaches have been proposed to improve the performance of XML data broadcast. However, due to the appearance of wildcard "*" and double slash "//" in queries, their performance deteriorates. Consequently, in this paper, we propose a novel air 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, we propose to build the index based on the queries submitted by users. The new index treating the XPath queries with "*" or "//" as a DFA actually improves the efficiency of broadcast system significantly. We further propose an efficient compression strategy to reduce the index size of DFAI as well. Experiment results show that our new index method achieves a much better performance in terms of both access time and tuning time when compared with existing approaches.

AB - XML data broadcast is an efficient way to deliver semi-structured information in wireless mobile environment. In the literature, many approaches have been proposed to improve the performance of XML data broadcast. However, due to the appearance of wildcard "*" and double slash "//" in queries, their performance deteriorates. Consequently, in this paper, we propose a novel air 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, we propose to build the index based on the queries submitted by users. The new index treating the XPath queries with "*" or "//" as a DFA actually improves the efficiency of broadcast system significantly. We further propose an efficient compression strategy to reduce the index size of DFAI as well. Experiment results show that our new index method achieves a much better performance in terms of both access time and tuning time when compared with existing approaches.

KW - Air indexing

KW - Deterministic finite automaton

KW - On-demand XML data broadcast

UR - http://www.scopus.com/inward/record.url?scp=84860653022&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-29035-0_7

DO - 10.1007/978-3-642-29035-0_7

M3 - Conference contribution

AN - SCOPUS:84860653022

SN - 9783642290343

VL - LNCS 7239

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 96

EP - 110

BT - Database Systems for Advanced Applications

A2 - Lee, Sang-goo

A2 - Peng, Zhiyong

A2 - Zhou, Xiaofang

A2 - Moon, Yang-Sae

A2 - Unland, Rainer

A2 - Yoo, Jaesoo

PB - Springer-Verlag Berlin Heidelberg

T2 - 17th International Conference on Database Systems for Advanced Applications

Y2 - 15 April 2012 through 18 April 2012

ER -

Sun W, Liu P, Wu J, Qin Y, Zheng B. An Automaton-Based Index Scheme for On-Demand XML Data Broadcast. In Lee S, Peng Z, Zhou X, Moon Y-S, Unland R, Yoo J, editors, Database Systems for Advanced Applications: 17th International Conference, DASFAA 2012, Busan, South Korea, April 15-19, 2012, Proceedings, Part II. PART 2 ed. Vol. LNCS 7239. Springer-Verlag Berlin Heidelberg. 2012. p. 96-110. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2). doi: 10.1007/978-3-642-29035-0_7

An Automaton-Based Index Scheme for On-Demand XML Data Broadcast

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this