• Articles • Previous Articles     Next Articles

MRST---An Efficient Monitoring Technology of Summarization on Stream Data

Xiao-Bo Fan, Ting-Ting Xie, Cui-Ping Li, and Hong Chen   

  1. School of Information, Renmin University of China, Beijing 100872, China Key Laboratory of Data Engineering and Knowledge Engineering, MOE, Beijing 100872, China
  • Received:2006-05-01 Revised:2006-12-21 Online:2007-03-10 Published:2007-03-10

Monitoring on data streams is an efficient method of acquiring the characters of data stream. However the available resources for each data stream are limited, so the problem of how to use the limited resources to process infinite data stream is an open challenging problem. In this paper, we adopt the wavelet and sliding window methods to design a multi-resolution summarization data structure, the Multi-Resolution Summarization Tree (MRST) which can be updated incrementally with the incoming data and can support point queries, range queries, multi-point queries and keep the precision of queries. We use both synthetic data and real-world data to evaluate our algorithm. The results of experiment indicate that the efficiency of query and the adaptability of MRST have exceeded the current algorithm, at the same time the realization of it is simpler than others.

Key words: Concurrent computation; process algebra; computational model;



[1] Akyildiz I, Su W, Sankarasubramaniam Y, Cayirci E. Wireless sensor networks: A survey. -\it Computer Networks}, 2002, 38(4): 393--422.

[2] Min R, Bhardwaj M, Cho S \it et al. \rm Low power wireless sensor networks. In -\it Proc. Int. Conf. VLSI Design}, Bangalore, India, January 2001, pp.205--215.

[3] Nath S, Deshpande A, Ke Y \it et al. \rm IrisNet: An architecture for compute-intensive wide-area sensor network services. Intel Research Technical Report IRP-TR-02-10, 2002.

[4] Chen J, DeWitt D, Tian F, Wang Y. NiagaraCQ: A scalable continuous query system for Internet databases. In -\it Proc. ACM Int. Conf. Management of Data}, Dallas, USA, 2000, pp.379--390.

[5] Carney D, Cetinternel U, Cherniack M \it et al. \rm Monitoring streams---A new class of data management applications. In -\it Proc. the 28th VLDB Conference}, Hong Kong, China, 2002, pp.215--226.

[6] Babcock B, Babu S, Datar M \it et al. \rm Models and issues in data stream systems. In -\it Proc. Principles of Database Systems}, Madison (PODS), USA, 2002, pp.1--16.

[7] Terry D, Goldberg D, Nichols D, Oki B. Continuous queries over append-only databases. In -\it Proc. the 1992 ACM SIGMOD Int. Conf. Management of Data}, San Diego, USA, June 1992, pp.321--330.

[8] Golab L, Ozsu M T. Issues in data stream management. -\it SIGMOD Record}, 2003, 32(2): 5--14.

[9] Mouratidis K I. Data stream processing: An overview of recent research
[Dissertation]. Hong Kong University of Science and Technology, 2003.

[10] Tatbul N, Cetintemel U, Zdonik S \it et al. \rm Load Shedding in a data stream manager. In -\it Proc. the 29th VLDB Conference}, Berlin, Germany, 2003, pp.309--320.

[11] Chi Y, Wang H, Yu P S. Load star: Load shedding in data stream mining. In -\it Proc. the 31st VLDB Conf}., Trondheim, Norway, 2005, pp.1302--1305.

[12] Tu Y, Prabhakar S. Control-based load shedding in data stream management systems. To appear in Ph.D. Workshop of ICDE 2006, Seoul, Korea.

[13] Alon N, Matias Y, Szegedy M. The space complexity of approximating the frequency moments. In -\it Proc. the 1996 Annual ACM Symp. Theory of Computing}, Philadelphia, USA, 1996, pp.20--29.

[14] Jagadish H V, Koudas N, Muthukrishnan S \it et al. \rm Optimal histograms with quality guarantees. In -\it Proc. VLDB}, New York City, USA, 1998, pp.275--286.

[15] Jawerth B, Sweldens W. An overview of wavelet based multiresolution analyses. -\it SIAM Review}, 1994, 36(3): 377--412.

[16] Matias Y, Vitter J S, Wang M. Wavelet-based histograms for selectivity estimation. In -\it Proc. ACM SIGMOD Int. Conf. Management of Data}, Haas L M, Tiwary A (eds.), Seattle, Washington, USA, June 2--4, 1998, pp.448--459.

[17] Vitter J S, Wang M. Approximate computation of multidimensional aggregates of sparse data using wavelets. In -\it Proc. ACM SIGMOD Int. Conf. Management of Data}, June 1--3, 1999, Philadelphia, Pennsylvania, 1999, pp.193--204.

[18] Chakrabarti K, Garofalakis M N, Rastogi R, Shim K. Approximate query processing using wavelets. In -\it Proc. 26th Int. Conf. Very Large Data Bases}, Cairo, Egypt, 2000, pp.111--122.

[19] Chan K-P, Fu A W C. Efficient time series matching by wavelets. In -\it Proc. the 15th Int. Conf. Data Engineering}, Sydney, Australia, 1999, pp.126--133.

[20] Gehrke J, Korn F, Srivastava D. On computing correlated aggregates over continual data streams. In -\it Proc. ACM SIGMOD Int. Conf. Management of Data}, Santa Barbara, USA, 2001, pp.13--24.

[21] Bulut A, Singh A K. SWAT: Hierarchical stream summarization in large networks. In -\it Proc. the 19th Int. Conf. Data Engineering}, Bangalore, India, March 2003, pp.303--314.

[22] Datar M, Gionis A, Indyk P, Motwani R. Maintaining stream statistics over sliding windows. In -\it Proc. the 13th Annual ACM-SIAM Symp. Discrete Algorithms}, San Francisco, CA, USA. ACM/SIAM, 2002, pp.635--644.

[23] Zhu Y, Shasha D. Efficient elastic burst detection in data streams. In -\it Proc. SIGKDD}, Washington DC, USA, 2003, pp.336--345.

[24]http://www.ipm.ucdavis.edu/WEATHER/wxretrieve.html.
[1] Yan-Fang Ma and Min Zhang. The Infinite Evolution Mechanism of ε-Bisimilarity [J]. , 2013, 28(6): 1097-1105.
[2] Xu-Tao Du (杜旭涛), Chun-Xiao Xing (邢春晓), Member, CCF, IEEE and Li-Zhu Zhou (周立柱), Member, ACM. Modeling and Verifying Concurrent Programs with Finite Chu Spaces [J]. , 2010, 25(6): 1168-1183.
[3] Chang-Le Zhou, Yun Yang, and Xiao-Xi Huang. Computational Mechanisms for Metaphor in Languages: A Survey [J]. , 2007, 22(2): 308-319 .
[4] Guang-Ping Qin and Jin-Zhao Wu. Action Refinement for Real-Time Concurrent Processes with Urgency [J]. , 2005, 20(4): 514-525 .
[5] Xiu-Li Sun, Wen-Yin Zhang, and Jin-Zhao Wu. Event-Based Operational Semantics and a Consistency Result for Real-Time Concurrent Processes with Action Refinement [J]. , 2004, 19(6): 0-0.
[6] Fu Yuxi;. Reaction Graph [J]. , 1998, 13(6): 510-530.
[7] David de Frutos-Escrig; Luis Liana-Diaz; Manuel Nunez;. An invitation to Friendly Testing [J]. , 1998, 13(6): 531-545.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved