微信服务号

微信订阅号

2025年4月2日 0:58 星期三
首页 > 过刊浏览>2004年第15卷第12期 >1800-1814
PDF HTML阅读 XML下载 导出引用 引用提醒
滑动窗口规模的动态调整算法
作者:
基金项目:

Supported by the National Natural Science Foundation of China under Grant No.60273082 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2002AA444110 (国家高技术研究发展计划(863)); the NationalGrand Fundamental Research 973 Program of China under Grant No.G1999032704 (国家重点基础研究发展规划(973)); the Natural Science Foundation of Heilongjiang Province of China under Grant No.zjg03-05 (黑龙江省自然科学基金)


Algorithms for Dynamically Adjusting the Sizes of Sliding Windows
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [23]
    • |
  • 相似文献 [20]
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    讨论当数据流系统的数据流流速或连续查询发生变化时,滑动窗口规模的动态调整问题.根据可用内存空间大小和连续查询需求,提出了3类动态调整滑动窗口规模的算法,实现了对连续查询3种服务质量级别的支持,提高了连续查询处理的效率和效果.理论分析与实验结果表明,提出的算法可以有效地应用于数据流系统.

    Abstract:

    The problem of dynamically adjusting the sizes of sliding windows when the rates of data streams or continuous queries change in data stream systems is studied in this paper. Based on the amount of available memory resource and the requirement of queries, three classes of algorithms for dynamically adjusting the sizes of sliding windows are proposed. These algorithms provide three levels of quality of service to all kinds of continuous queries and enhance the efficiency and effectiveness of processing continuous queries. Analytical and experimental results show that the algorithms can be applied to data stream systems effectively.

    参考文献
    [1]Araru A, Babu S, Widom J. An abstract semantics and concrete language for continuous queries over streams and relations.Technical Report, Stanford University Database Group. 2002. http://dbpubs.stanford.edu/pub/2002-57
    [2]Guha S, Koudas N. Approximating a data stream for querying and estimation: Algorithms and performance evaluation. In: Stefano C, Christoph F, Pat S, eds. Proc. of the 18th Int'l Conf. on Data Engineering. San Jose: IEEE Computer Society, 2002. 567～576.
    [3]Golab L, Ozsu MT. Processing sliding window multi-joins in continuous queries over data streams. In: Freytag JC, Lockemann PC,Abiteboul S, eds. Proc. of the 29th Int'l Conf. on Very Large Data Bases. Berlin: Morgan Kaufmann Publishers, 2003. 500～511.
    [4]Viglas SD, Naughton JF, Burger J. Maximizing the output rate of multi-way join queries over streaming information sources. In:Freytag JC, Lockemann PC, Abiteboul S, eds. Proc. of the 29th Int'l Conf. on Very Large Data Bases. Berlin: Morgan Kaufmann Publishers, 2003. 285～296.
    [5]Hammad MA, Franklin MJ, Aref WG, Elmagarmid AK. Scheduling for shared window joins over data streams. In: Freytag JC,Lockemann PC, Abiteboul S, eds. Proc. of the 29th Int'l Conf. on Very Large Data Bases. Berlin: Morgan Kaufmann Publishers,2003. 297～308.
    [6]Babcock AK, Babu S, Datar M. Model and issues in data stream systems. In: Popa L, eds. Proc. of the 21st ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems. Madison: ACM, 2002. 1～16.
    [7]Golab L, Ozsu MT. Issues in data stream management. SIGMOD Record, 2003,32(2):5～14.
    [8]Motwani R, Widom J, Arasu A. Query processing, approximation, and resource management in a data stream management system.In: Proc. of the 1 st Biennial Conf. on Innovative Data Syst. Res (CIDR). 2003. http://newdbpubs.stanford.edu/pub/2002-41
    [9]Madden S, Franklin MJ. Fjording the stream: An architecture for queries over streaming sensor data. In: Proc. of the 18th Int'l Conf.on Data Engineering. San Jose: IEEE Computer Society, 2002. 555～566.
    [10]Chandraskearan S, Franklin MJ. Streaming queries over streaming data. In: Bernstein PA, Loannidis YE, Ramakrishnan R, eds.Proc. of the 28th Int'l Conf. on Very Large Data Bases. Hong Kong SAR: Morgan Kaufmann Publishers, 2002. 203～214.
    [11]Carney D, Cetintemel U, Cherniack M. Monitoring streams: A new class of data management applications. In: Bernstein PA,Loannidis YE, Ramakrishnan R, eds. Proc. of the 28th Int'l Conf. on Very Large Data Bases. Hong Kong SAR: Morgan Kaufmann Publishers, 2002.215～226.
    [12]Babcock B, Babu S, Datar M, Motwani R. Chain: Operator scheduling for memory minimization in data stream systems. In: Halevy AY, Ives ZG, Doan A, eds. Proc. of the 2003 ACM SIGMOD Int'l Conf. on Management of Data. San Diego: ACM, 2003.253～264.
    [13]Olston C, Jiang J, Widom J. Adaptive filters for continuous queries over distributed data streams. In: Halevy AY, Ives ZG, Doan A,eds. Proc. of the 2003 ACM SIGMOD Int'l Conf. on Management of Data. San Diego: ACM, 2003. 563～574.
    [14]Madden S, Shah M, Hellerstein JM, Raman V. Continuously adaptive continuous queries over streams. In: Franklin MJ, Moon B,Ailamaki A, eds. Proc. of the 2002 ACM SIGMOD Int'l Conf. on Management of Data. Madison: ACM, 2002.49～60.
    [15]Tatbul N, Cetintemel U, Zdonik S. Load shedding in a data stream manager. In: Freytag JC, Lockemann PC, Abiteboul S, eds. Proc.of the 29th Int'l Conf. on Very Large Data Bases, Berlin: Morgan Kaufmann Publishers, 2003. 309～320.
    [16]Carney D, Cetintemel U, Rasin A, Zdonik S, Cherniack M, Stonebraker M. Operator scheduling in a data stream manager. In:Freytag JC, Lockemann PC, Abiteboul S, eds. Proc. of the 29th Int'l Conf. on Very Large Data Bases. Berlin: Morgan Kaufmann Publishers, 2003. 838～849.
    [17]Cherniack M, Balakrishnan H, Balazinska M. Scalable distributed stream processing. In: Proc. of the 1st Biennial Conf. on Innovative Data Syst. Res (CIDR). 2003. http://nms.lcs.mit.edu/papers/medusa-cidr03.html
    [18]Arasu A, Babcock B, Babu S. Characterizing memory requirements for queries over continuous data streams. In: Popa L, eds. Proc.of the 21 st ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems. Madison: ACM, 2002.221～232.
    [19]Kang J, Naughton JF, Viglas SD. Evaluating window joins over unbounded streams. In: Umeshwar D, Krithi R, Vijayaraman TM,eds. Proc. of the 19th Int'l Conf. on Data Engineering. Bangalore: IEEE Computer Society, 2003.341～352.
    [20]Haas PJ. Large-Sample and deterministic confidence intervals for online aggregation. In: Proc. of the 9th Int'l Conf. on Scientific and Statistical Database Management (SSDBM, 1997). 1997. 51～63.
    [21]Hellerstein JM, Hass PJ, Wang HJ. Online aggregation. In: Peckham J, ed. Proc. of the ACM SIGMOD Int'l Conf. on Management of Data. Tucson: ACM Press, 1997. 171～182.
    [22]Babcock B, Datar M, Motwani R. Load shedding for aggregation queries over data streams. In: Rundensteiner E. Proc. of the 20th Int'l Conf. on Data Engineering. Boston: IEEE Computer Society, 2004. 350～361.
    [23]Garey MR, Johnson DS. Computers and Intractability: A Guide to the Theory of NP-Completeness. Bell Laboratories, 1978.
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

李建中,张冬冬.滑动窗口规模的动态调整算法.软件学报,2004,15(12):1800-1814

复制
分享
文章指标
  • 点击次数:8346
  • 下载次数: 8861
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2004-07-26
  • 最后修改日期:2004-09-06
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19766475位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号