Cache-conscious automata for XML filtering

Bingsheng He; Qiong Luo; Byron Choi

doi:10.1109/ICDE.2005.31

Cache-conscious automata for XML filtering

Bingsheng He^*, Qiong Luo, Byron Choi

^*Corresponding author for this work

Department of Computer Science

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

9 Citations (Scopus)

Abstract

Hardware cache behavior is an important factor in the performance of memory-resident, data-intensive systems such as XML filtering engines. A key data structure in several recent XML filters is the automaton, which is used to represent the long-running XML queries in the main memory. In this paper, we study the cache performance of automaton-based XML filtering through analytical modeling and system measurement. Furthermore, we propose a cache-conscious automaton organization technique, called the hot buffer, to improve the locality of automaton state transitions. Our results show that (1) our cache performance model for XML filtering automata is highly accurate and (2) the hot buffer improves the cache performance as well as the overall performance of automaton-based XML filtering.

Original language	English
Title of host publication	Proceedings - 21st International Conference on Data Engineering, ICDE 2005
Publisher	IEEE
Pages	878-889
Number of pages	12
ISBN (Print)	0769522858
DOIs	https://doi.org/10.1109/ICDE.2005.31
Publication status	Published - Apr 2005
Event	21st International Conference on Data Engineering, ICDE 2005 - Tokyo, Japan Duration: 5 Apr 2005 → 8 Apr 2005 https://ieeexplore.ieee.org/xpl/conhome/9680/proceeding

Publication series

Name	Proceedings - International Conference on Data Engineering
ISSN (Print)	1063-6382
ISSN (Electronic)	2375-026X

Conference

Conference	21st International Conference on Data Engineering, ICDE 2005
Country/Territory	Japan
City	Tokyo
Period	5/04/05 → 8/04/05
Internet address	https://ieeexplore.ieee.org/xpl/conhome/9680/proceeding

Scopus Subject Areas

Software
Signal Processing
Information Systems

User-Defined Keywords

Cache-conscious
automata
XML filtering
query processing
cache behavior model
buffer

Access to Document

10.1109/ICDE.2005.31

Cite this

@inproceedings{8f639d6f9bf9473aa822844c80c1ad91,

title = "Cache-conscious automata for XML filtering",

abstract = "Hardware cache behavior is an important factor in the performance of memory-resident, data-intensive systems such as XML filtering engines. A key data structure in several recent XML filters is the automaton, which is used to represent the long-running XML queries in the main memory. In this paper, we study the cache performance of automaton-based XML filtering through analytical modeling and system measurement. Furthermore, we propose a cache-conscious automaton organization technique, called the hot buffer, to improve the locality of automaton state transitions. Our results show that (1) our cache performance model for XML filtering automata is highly accurate and (2) the hot buffer improves the cache performance as well as the overall performance of automaton-based XML filtering.",

keywords = "Cache-conscious, automata, XML filtering, query processing, cache behavior model, buffer",

author = "Bingsheng He and Qiong Luo and Byron Choi",

note = "The authors are grateful to Derick Wood for his advice on automata theories and to Yi Wang for his discussions. The work of Byron Choi was done in part while he was visiting HKUST and was supported by grant HKUST6197/01E. The authors thank the reviewers for their insightful suggestions, all of which improved this work.; 21st International Conference on Data Engineering, ICDE 2005 ; Conference date: 05-04-2005 Through 08-04-2005",

year = "2005",

month = apr,

doi = "10.1109/ICDE.2005.31",

language = "English",

isbn = "0769522858",

series = "Proceedings - International Conference on Data Engineering",

publisher = "IEEE",

pages = "878--889",

booktitle = "Proceedings - 21st International Conference on Data Engineering, ICDE 2005",

address = "United States",

url = "https://ieeexplore.ieee.org/xpl/conhome/9680/proceeding",

}

TY - GEN

T1 - Cache-conscious automata for XML filtering

AU - He, Bingsheng

AU - Luo, Qiong

AU - Choi, Byron

N1 - The authors are grateful to Derick Wood for his advice on automata theories and to Yi Wang for his discussions. The work of Byron Choi was done in part while he was visiting HKUST and was supported by grant HKUST6197/01E. The authors thank the reviewers for their insightful suggestions, all of which improved this work.

PY - 2005/4

Y1 - 2005/4

N2 - Hardware cache behavior is an important factor in the performance of memory-resident, data-intensive systems such as XML filtering engines. A key data structure in several recent XML filters is the automaton, which is used to represent the long-running XML queries in the main memory. In this paper, we study the cache performance of automaton-based XML filtering through analytical modeling and system measurement. Furthermore, we propose a cache-conscious automaton organization technique, called the hot buffer, to improve the locality of automaton state transitions. Our results show that (1) our cache performance model for XML filtering automata is highly accurate and (2) the hot buffer improves the cache performance as well as the overall performance of automaton-based XML filtering.

AB - Hardware cache behavior is an important factor in the performance of memory-resident, data-intensive systems such as XML filtering engines. A key data structure in several recent XML filters is the automaton, which is used to represent the long-running XML queries in the main memory. In this paper, we study the cache performance of automaton-based XML filtering through analytical modeling and system measurement. Furthermore, we propose a cache-conscious automaton organization technique, called the hot buffer, to improve the locality of automaton state transitions. Our results show that (1) our cache performance model for XML filtering automata is highly accurate and (2) the hot buffer improves the cache performance as well as the overall performance of automaton-based XML filtering.

KW - Cache-conscious

KW - automata

KW - XML filtering

KW - query processing

KW - cache behavior model

KW - buffer

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

U2 - 10.1109/ICDE.2005.31

DO - 10.1109/ICDE.2005.31

M3 - Conference proceeding

AN - SCOPUS:28444439834

SN - 0769522858

T3 - Proceedings - International Conference on Data Engineering

SP - 878

EP - 889

BT - Proceedings - 21st International Conference on Data Engineering, ICDE 2005

PB - IEEE

T2 - 21st International Conference on Data Engineering, ICDE 2005

Y2 - 5 April 2005 through 8 April 2005

ER -

Cache-conscious automata for XML filtering

Abstract

Publication series

Conference

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this