Cache-conscious automata for XML filtering

Bingsheng He*, Qiong Luo, Byron Choi

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

9 Citations (Scopus)


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 languageEnglish
Title of host publicationProceedings - 21st International Conference on Data Engineering, ICDE 2005
Number of pages12
ISBN (Print)0769522858
Publication statusPublished - Apr 2005
Event21st International Conference on Data Engineering, ICDE 2005 - Tokyo, Japan
Duration: 5 Apr 20058 Apr 2005

Publication series

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


Conference21st International Conference on Data Engineering, ICDE 2005
Internet address

Scopus Subject Areas

  • Software
  • Signal Processing
  • Information Systems

User-Defined Keywords

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


Dive into the research topics of 'Cache-conscious automata for XML filtering'. Together they form a unique fingerprint.

Cite this