›› 2016, Vol. 31 ›› Issue (6): 1212-1227.doi: 10.1007/s11390-016-1693-8

Special Issue: Data Management and Data Mining

• Regular Paper • Previous Articles     Next Articles

An Efficient Approach of Processing Multiple Continuous Queries

Wen Liu1, Yan-Ming Shen1*, Member, CCF, Peng Wang2   

  1. 1 School of Computer Science and Technology, Dalian University of Technology, Dalian 116024, China;
    2 School of Computer Science, Fudan University, Shanghai 201203, China
  • Received:2015-08-03 Revised:2016-06-22 Online:2016-11-05 Published:2016-11-05
  • Supported by:

    This work was supported by the National Natural Science Foundation of China under Grant No. 61173160, the National Basic Research 973 Program of China under Grant No. 2015CB358800, and the Scientific Research Program of the Higher Education Institution of Xinjiang Uygur Autonomous Region of China under Grant No. XJEDU2014S087.

As stream data is being more frequently collected and analyzed,stream processing systems are faced with more design challenges.One challenge is to perform continuous window aggregation,which involves intensive computation.When there are a large number of aggregation queries,the system may suffer from scalability problems.The queries are usually similar and only differ in window specifications.In this paper,we propose collaborative aggregation which promotes aggregate sharing among the windows so that repeated aggregate operations can be avoided.Different from the previous approaches in which the aggregate sharing is restricted by the window pace,we generalize the aggregation over multiple values as a series of reductions.Therefore,the results generated by each reduction step can be shared.The sharing process is formalized in the feed semantics and we present the compose-and-declare framework to determine the data sharing logic at a very low cost.Experimental results show that our approach offers an order of magnitude performance improvement to the state-of-the-art results and has a small memory footprint.

[1] Zhu Y, Shasha D. StatStream:Statistical monitoring of thousands of data streams in real time. In Proc. the 28th VLDB, Aug. 2002, pp.358-369.

[2] Naidu K V M, Rastogi R, Satkin S, Srinivasan A. Memoryconstrained aggregate computation over data streams. In Proc. the 27th IEEE International Conference on Data Engineering (ICDE), Apr. 2011, pp.852-863.

[3] Krishnamurthy S, Franklin M J, Davis J, Farina D, Golovko P, Li A, Thombre N. Continuous analytics over discontinuous streams. In Proc. the 29th ACM SIGMOD International Conference on Management of Data, June 2010, pp.1081-1092.

[4] Arasu A, Babu S, Widom J. The CQL continuous query language:Semantic foundations and query execution. The VLDB Journal, 2006, 15(2):121-142.

[5] Deshpande P, Ramasamy K, Shukla A, Naughton J F. Caching multidimensional queries using chunks. In Proc. the 17th ACM SIGMOD International Conference on Management of Data, June 1998, pp.259-270.

[6] Mistry H, Roy P, Sudarshan S, Ramamritham K. Materialized view selection and maintenance using multi-query optimization. ACM SIGMOD Record, 2000, 30(2):307-318.

[7] Sellis T K. Multiple-query optimization. ACM Transactions on Database Systems, 1988, 13(1):23-52.

[8] Roy P, Seshadri S, Sudarshan S, Bhobe S.Efficient and extensible algorithms for multi query optimization. ACM SIGMOD Record, 2000, 29(2):249-260.

[9] Ghanem T, Hammad M, Mokbel M, Aref W, Elmagarmid A. Incremental evaluation of sliding-window queries over data streams. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(1):57-72.

[10] Li J, Maier D, Tufte K, Papadimos V, Tucker P A. Semantics and evaluation techniques for window aggregates in data streams. In Proc. the 24th ACM SIGMOD International Conference on Management of Data, June 2005, pp.311-322.

[11] Li J, Maier D, Tufte K, Papadimos V, Tucker P A. No pane, no gain:Efficient evaluation of sliding-window aggregates over data streams. ACM SIGMOD Record, 2005, 34(1):39-44.

[12] Krishnamurthy S, Wu C, Franklin M. On-the-fly sharing for streamed aggregation. In Proc. the 25th ACM SIGMOD International Conference on Management of Data, June 2006, pp.623-634.

[13] Guirguis S, Sharaf M A, Chrysanthis P K, Labrinidis A. Three-level processing of multiple aggregate continuous queries. In Proc. the 28th IEEE International Conference on Data Engineering (ICDE), Apr. 2012, pp.929-940.

[14] Gray J, Chaudhuri S, Bosworth A, Layman A, Reichart D, Venkatrao M, Pellow F, Pirahesh H. Data cube:A relational aggregation operator generalizing groupby, cross-tab, and sub-totals. Data Mining and Knowledge Discovery, 1997, 1(1):29-53.

[15] Huebsch R, Garofalakis M, Hellerstein J M, Stoica I. Sharing aggregate computation for distributed queries. In Proc. the 26th ACM SIGMOD International Conference on Management of Data, June 2007, pp.485-496.

[16] Abadi D J, Carney D, Çetintemel U, Cherniack M, Convey C, Lee S, Stonebraker M, Tatbul N, Zdonik S.Aurora:A new model and architecture for data stream management. The VLDB Journal, 2003, 12(2):120-139.

[17] Babu S, Widom J. Continuous queries over data streams. ACM SIGMOD Record, 2001, 30(3):109-120.

[18] Bhatotia P, Dischinger M, Rodrigues R, Acar U A. Slider:Incremental sliding-window computations for large-scale data analysis. Technical Report:MPI-SWS-2012-004, Universidade Nova de Lisboa, 2012.

[19] Cormode G, Johnson T, Korn F, Muthukrishnan S, Spatscheck O, Srivastava D. Holistic UDAFS at streaming speeds. In Proc. the 23rd ACM SIGMOD International Conference on Management of Data, June 2004, pp.35-46.

[20] Guirguis S, Sharaf M A, Chrysanthis P K, Labrinidis A. Optimized processing of multiple aggregate continuous queries. In Proc. the 20th ACM International Conference on Information and Knowledge Management, Oct. 2011, pp.1515-1524.

[21] Arasu A, Widom J. Resource sharing in continuous slidingwindow aggregates. In Proc. the 30th International Conference on Very Large Data Bases, Aug.31-Sept.3, 2004, pp.336-347.

[22] Patroumpas K, Sellis T. Multi-granular time-based sliding windows over data streams. In Proc. the 17th International Symposium on Temporal Representation and Reasoning (TIME), Sept. 2010, pp.146-153.

[23] Patroumpas K, Sellis T. Subsuming multiple sliding windows for shared stream computation. In Proc. the 15th International Conference on Advances in Databases and Information Systems, Sept. 2011, pp.56-69.

[24] Patroumpas K, Sellis T. Maintaining consistent results of continuous queries under diverse window speciffications. Information Systems, 2011, 36(1):42-61.

[25] Golab L, Bijay K G, Ozsu M T. Multi-query optimization of sliding window aggregates by schedule synchronization. In Proc. the 15th ACM International Conference on Information and Knowledge Management, Nov. 2006, pp.844-845.

[26] Lee R, Xu Z. Exploiting stream request locality to improve query throughput of a data integration system. IEEE Transactions on Computers, 2009, 58(10):1356-1368.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Lu Qi; Zhang Fubo; Qian Jiahua;. Program Slicing:Its Improved Algorithm and Application in Verification[J]. , 1988, 3(1): 29 -39 .
[2] Li Weihua; Yuan Youguang;. Error Recovery in a Real-Time Multiprocessor System[J]. , 1992, 7(1): 83 -87 .
[3] Shen Yidong;. Form alizing Incomplete Knowledge in Incomplete Databases[J]. , 1992, 7(4): 295 -304 .
[4] Xu Meirui; Liu Xiaolin;. A VLSI Algorithm for Calculating the Tree to Tree Distance[J]. , 1993, 8(1): 68 -76 .
[5] Wei Guoqing; Ma Songde;. 3D Motion Estimation and Motion Fusion by Affine Region Matching[J]. , 1993, 8(1): 17 -25 .
[6] Ma Jun; Ma Shaohan;. Efficient Parallel Algorithms for Some Graph Theory Problems[J]. , 1993, 8(4): 76 -80 .
[7] Jin Guohua; Chen Fujie;. On the Problem of Optimizing Parallel Programs for Complex Memory Hierarchies[J]. , 1994, 9(1): 1 -26 .
[8] Pan Zhigeng; Shi Jiaoying; Hu Bingfeng;. DGLa: A Distributed Graphics Language[J]. , 1994, 9(2): 97 -106 .
[9] Zhou Jianqiang; Xie Li; Dai Fei; Sun Zhongxiu;. Adaptive Memory Coherence Algorithms in DSVM[J]. , 1994, 9(4): 365 -372 .
[10] Zheng Yuhua; Xie Li; Sun Zliongxiu;. Full Or-Parallemism and Restricted And-Parallelism in BTM[J]. , 1994, 9(4): 373 -381 .

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