HFilter: Hybrid Finite Automaton Based Stream Filtering for Deep and Recursive XML Data

Weiwei Sun; Yongrui Qin; Ping Yu; Zhuoyao Zhang; Zhenying He

doi:10.1007/978-3-540-85654-2_48

HFilter: Hybrid Finite Automaton Based Stream Filtering for Deep and Recursive XML Data

Weiwei Sun, Yongrui Qin, Ping Yu, Zhuoyao Zhang, Zhenying He

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

5 Citations (Scopus)

Abstract

XML filtering applications are gaining increasing popularity recently. Automata are generally adopted to construct query indexes for evaluating large numbers of XPath queries over XML streams. Usually only shallow data are observed in existing approaches. How to process deep and recursive XML data with low memory limitation efficiently is still a challenging issue. In this paper, we propose HFilter, a Hybrid Finite Automaton (HFA) based stream filtering approach, to solve this problem. We introduce the basic two-tier HFA (lazy DFA tier and NFA tier) first, which realizes data prefix sharing and memory overflow control to improve the filtering throughput. Then an optimized three-tier HFA with an extra pre-expanded DFA tier is put forward, which significantly reduces the restarting cost of HFA after memory overflow. Experiments show that our approaches work more efficiently than existing ones.

Original language	English
Title of host publication	Database and Expert Systems Applications
Subtitle of host publication	19th International Conference, DEXA 2008, Turin, Italy, September 1-5, 2008. Proceedings
Publisher	Springer-Verlag Berlin Heidelberg
Pages	566-580
Number of pages	15
Volume	LNCS 5181
ISBN (Electronic)	9783540856542
ISBN (Print)	3540856536, 9783540856535
DOIs	https://doi.org/10.1007/978-3-540-85654-2_48
Publication status	Published - 2008
Externally published	Yes
Event	19th International Conference on Database and Expert Systems Applications - Turin, Italy Duration: 1 Sep 2008 → 5 Sep 2008 Conference number: 19 http://www.dexa.org/previous/dexa2008/index.html (Link to Conference Website)

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer-Verlag Berlin Heidelberg
Volume	5181 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	19th International Conference on Database and Expert Systems Applications
Abbreviated title	DEXA 2008
Country/Territory	Italy
City	Turin
Period	1/09/08 → 5/09/08
Internet address	http://www.dexa.org/previous/dexa2008/index.html (Link to Conference Website)

Access to Document

10.1007/978-3-540-85654-2_48Licence: Unspecified

Cite this

Sun, W., Qin, Y., Yu, P., Zhang, Z., & He, Z. (2008). HFilter: Hybrid Finite Automaton Based Stream Filtering for Deep and Recursive XML Data. In Database and Expert Systems Applications: 19th International Conference, DEXA 2008, Turin, Italy, September 1-5, 2008. Proceedings (Vol. LNCS 5181, pp. 566-580). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5181 LNCS). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/978-3-540-85654-2_48

Sun, Weiwei ; Qin, Yongrui ; Yu, Ping et al. / HFilter : Hybrid Finite Automaton Based Stream Filtering for Deep and Recursive XML Data. Database and Expert Systems Applications: 19th International Conference, DEXA 2008, Turin, Italy, September 1-5, 2008. Proceedings. Vol. LNCS 5181 Springer-Verlag Berlin Heidelberg, 2008. pp. 566-580 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ff7ea513e436436c9b43454e3c9830fb,

title = "HFilter: Hybrid Finite Automaton Based Stream Filtering for Deep and Recursive XML Data",

abstract = "XML filtering applications are gaining increasing popularity recently. Automata are generally adopted to construct query indexes for evaluating large numbers of XPath queries over XML streams. Usually only shallow data are observed in existing approaches. How to process deep and recursive XML data with low memory limitation efficiently is still a challenging issue. In this paper, we propose HFilter, a Hybrid Finite Automaton (HFA) based stream filtering approach, to solve this problem. We introduce the basic two-tier HFA (lazy DFA tier and NFA tier) first, which realizes data prefix sharing and memory overflow control to improve the filtering throughput. Then an optimized three-tier HFA with an extra pre-expanded DFA tier is put forward, which significantly reduces the restarting cost of HFA after memory overflow. Experiments show that our approaches work more efficiently than existing ones.",

keywords = "Data prefix sharing, Deep and recursive XML data, Hybrid finite automaton, Memory overflow control, XML stream filtering",

author = "Weiwei Sun and Yongrui Qin and Ping Yu and Zhuoyao Zhang and Zhenying He",

year = "2008",

doi = "10.1007/978-3-540-85654-2_48",

language = "English",

isbn = "3540856536",

volume = "LNCS 5181",

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

publisher = "Springer-Verlag Berlin Heidelberg",

pages = "566--580",

booktitle = "Database and Expert Systems Applications",

address = "Germany",

note = "19th International Conference on Database and Expert Systems Applications, DEXA 2008 ; Conference date: 01-09-2008 Through 05-09-2008",

url = "http://www.dexa.org/previous/dexa2008/index.html",

}

Sun, W, Qin, Y, Yu, P, Zhang, Z & He, Z 2008, HFilter: Hybrid Finite Automaton Based Stream Filtering for Deep and Recursive XML Data. in Database and Expert Systems Applications: 19th International Conference, DEXA 2008, Turin, Italy, September 1-5, 2008. Proceedings. vol. LNCS 5181, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5181 LNCS, Springer-Verlag Berlin Heidelberg, pp. 566-580, 19th International Conference on Database and Expert Systems Applications, Turin, Italy, 1/09/08. https://doi.org/10.1007/978-3-540-85654-2_48

HFilter : Hybrid Finite Automaton Based Stream Filtering for Deep and Recursive XML Data. / Sun, Weiwei; Qin, Yongrui; Yu, Ping et al.

Database and Expert Systems Applications: 19th International Conference, DEXA 2008, Turin, Italy, September 1-5, 2008. Proceedings. Vol. LNCS 5181 Springer-Verlag Berlin Heidelberg, 2008. p. 566-580 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5181 LNCS).

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

TY - GEN

T1 - HFilter

T2 - 19th International Conference on Database and Expert Systems Applications

AU - Sun, Weiwei

AU - Qin, Yongrui

AU - Yu, Ping

AU - Zhang, Zhuoyao

AU - He, Zhenying

N1 - Conference code: 19

PY - 2008

Y1 - 2008

N2 - XML filtering applications are gaining increasing popularity recently. Automata are generally adopted to construct query indexes for evaluating large numbers of XPath queries over XML streams. Usually only shallow data are observed in existing approaches. How to process deep and recursive XML data with low memory limitation efficiently is still a challenging issue. In this paper, we propose HFilter, a Hybrid Finite Automaton (HFA) based stream filtering approach, to solve this problem. We introduce the basic two-tier HFA (lazy DFA tier and NFA tier) first, which realizes data prefix sharing and memory overflow control to improve the filtering throughput. Then an optimized three-tier HFA with an extra pre-expanded DFA tier is put forward, which significantly reduces the restarting cost of HFA after memory overflow. Experiments show that our approaches work more efficiently than existing ones.

AB - XML filtering applications are gaining increasing popularity recently. Automata are generally adopted to construct query indexes for evaluating large numbers of XPath queries over XML streams. Usually only shallow data are observed in existing approaches. How to process deep and recursive XML data with low memory limitation efficiently is still a challenging issue. In this paper, we propose HFilter, a Hybrid Finite Automaton (HFA) based stream filtering approach, to solve this problem. We introduce the basic two-tier HFA (lazy DFA tier and NFA tier) first, which realizes data prefix sharing and memory overflow control to improve the filtering throughput. Then an optimized three-tier HFA with an extra pre-expanded DFA tier is put forward, which significantly reduces the restarting cost of HFA after memory overflow. Experiments show that our approaches work more efficiently than existing ones.

KW - Data prefix sharing

KW - Deep and recursive XML data

KW - Hybrid finite automaton

KW - Memory overflow control

KW - XML stream filtering

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

U2 - 10.1007/978-3-540-85654-2_48

DO - 10.1007/978-3-540-85654-2_48

M3 - Conference contribution

AN - SCOPUS:52949089707

SN - 3540856536

SN - 9783540856535

VL - LNCS 5181

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

SP - 566

EP - 580

BT - Database and Expert Systems Applications

PB - Springer-Verlag Berlin Heidelberg

Y2 - 1 September 2008 through 5 September 2008

ER -

Sun W, Qin Y, Yu P, Zhang Z, He Z. HFilter: Hybrid Finite Automaton Based Stream Filtering for Deep and Recursive XML Data. In Database and Expert Systems Applications: 19th International Conference, DEXA 2008, Turin, Italy, September 1-5, 2008. Proceedings. Vol. LNCS 5181. Springer-Verlag Berlin Heidelberg. 2008. p. 566-580. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-85654-2_48

HFilter: Hybrid Finite Automaton Based Stream Filtering for Deep and Recursive XML Data

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this