Memory-Efficient Query Processing over XML Fragment Stream with Fragment Labeling

Authors

  • Sangwook Lee
  • Jin Kim
  • Hyunchul Kang

Keywords:

XML, XML fragment stream, XML fragment labeling, hole-filler model, XML stream query processing, mobile computing

Abstract

The portable/hand-held devices deployed in mobile computing environment are mostly limited in memory. To make it possible for them to locally process queries over a large volume of XML data, the data needs to be streamed in fragments of manageable size and the queries need to be processed over the stream with as little memory as possible. In this paper, we report a considerable improvement of the state-of-the-art techniques of query processing over XML fragment stream in memory efficiency. We use XML fragment labeling (XFL) as a method of representing XML fragmentation, and show that XFL is much more effective than the popular hole-filler (HF) model employed in the state-of-the-art in reducing the amount of memory required for query processing. The state-of-the-art with the HF model requires more memory as the stream size increases. With XFL, we overcome this fundamental limitation, proposing the techniques to make query processing scalable in the sense that memory requirement is not affected by the size of the stream as long as the stream is bounded. The improvement is verified through implementation and a detailed set of experiments.

Downloads

Download data is not yet available.

Author Biographies

Sangwook Lee

School of Computer Science and Engineering
Chung-Ang University
Seoul, 156-756, Korea

Jin Kim

School of Computer Science and Engineering
Chung-Ang University
Seoul, 156-756, Korea

Hyunchul Kang

School of Computer Science and Engineering
Chung-Ang University
Seoul, 156-756, Korea

Downloads

Published

2012-01-26

How to Cite

Lee, S., Kim, J., & Kang, H. (2012). Memory-Efficient Query Processing over XML Fragment Stream with Fragment Labeling. COMPUTING AND INFORMATICS, 29(5), 757–782. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/112