期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

基于合并-分裂策略的近似等深直方图增量维护 被引量：1

Incremental Maintenance of Approximate Equal-depth Histograms Based on Merge-split Strategy
下载PDF
导出
摘要 直方图在数据库领域有着广泛的应用,是一种常用的概要数据结构生成方法。首先提出了一个基于数据流界标窗口模型的近似等深直方图构建维护算法框架,该算法框架通过桶的合并-分裂实现近似等深直方图的增量维护;然后对三种不同的桶合并-分裂策略进行了比较和讨论;最后对该算法框架和三种不同的桶合并-分裂策略进行了实验分析。 Histogram is one of effective methods for construction of synopsis data structures on landmark windows over data streams. This paper presented a new framework for incremental maintenance of approximate equal-depth histograms by merging and splitting the buckets, and compared three different merge＆split strategies. The experimental results show that the algorithms are effective and efficient for continuous streaming data processing over landmark window model.
作者 张龙波 李战怀 王勇
机构地区 山东理工大学计算机学院 西北工业大学计算机学院
出处 《计算机科学》 CSCD 北大核心 2009年第8期182-184,共3页 Computer Science
基金 国家自然科学基金(60873196) 山东理工大学博士基金资助
关键词 数据流 界标窗口模型 概要数据结构 直方图 Data stream, Landmark window model, Synopsis data structure, Histogram
分类号 TP311 [自动化与计算机技术—计算机软件与理论]
  • 相关文献

参考文献10

  • 1Babcock B, Babu S, Datar M R, et al. Models and issues in data stream systems[C]//Proc, of 21st ACM SIGACT-SIGMODSIGART Symp. on Principles of Database Systems. Madison, Wisconsin, May 2002: 1-16.
  • 2金澈清,钱卫宁,周傲英.流数据分析与管理综述[J].软件学报,2004,15(8):1172-1181. 被引量：161
  • 3Ioanidis Y. The History of Histogram (abridged)[C] //Proeeedings of the 29th VLDB Conference. Berlin, Germany, 2003.
  • 4Gibbons P B, Matias Y, Poosala V. Fast incremental maintenance of approximate histograms[C]//Proc. of the 23rd Int'l Conf. on Very Large Data Bases ( VLDB ' 97 ). Athens, Greece, 1997:466-475.
  • 5Jagadish H V, Koudas N, Muthukrishnan S, et al. Optimal Histograms with Quality Guarantees[C] //Proceedings of VLDB' 98. August 1998:275-286.
  • 6Guha S, Koudas N K. Approximating a Data Stream for Querying and Estimation: Algorithm Performance Evaluation[C] // Proc. of ICDE'02.
  • 7Guha S, Koudas N,Shim K. Data Streams and Histograms[C]//Syrnposiumon the Theory of Computing (STOC). July 2001.
  • 8韩近强,杨东青,唐世渭.数据流处理中一种自适应的直方图维护算法[C]∥第20届全国数据库学术会议论文集A集.长沙,Oct.2003:178-181.
  • 9姚春芬,陈红.分布偏斜的流数据上的一种直方图维护算法[C]∥第23届全国数据库学术会议论文集.广州,Nov.2006:83-86.
  • 10http://research.microsoft. com/-Gray/.

二级参考文献52

  • 1Babcock B, Babu S, Datar M, Motwani R, Widom J. Models and issues in data streams. In: Popa L, ed. Proc. of the 21st ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems. Madison: ACM Press, 2002. 1～16.
  • 2Terry D, Goldberg D, Nichols D, Oki B. Continuous queries over append-only databases. SIGMOD Record, 1992,21(2):321-330.
  • 3Avnur R, Hellerstein J. Eddies: Continuously adaptive query processing. In: Chen W, Naughton JF, Bernstein PA, eds. Proc. of the 2000 ACM SIGMOD Int'l Conf. on Management of Data. Dallas: ACM Press, 2000. 261～272.
  • 4Hellerstein J, Franklin M, Chandrasekaran S, Deshpande A, Hildrum K, Madden S, Raman V, Shah MA. Adaptive query processing: Technology in evolution. IEEE Data Engineering Bulletin, 2000,23(2):7-18.
  • 5Carney D, Cetinternel U, Cherniack M, Convey C, Lee S, Seidman G, Stonebraker M, Tatbul N, Zdonik S. Monitoring streams?A new class of DBMS applications. Technical Report, CS-02-01, Providence: Department of Computer Science, Brown University, 2002.
  • 6Guha S, Mishra N, Motwani R, O'Callaghan L. Clustering data streams. In: Blum A, ed. The 41st Annual Symp. on Foundations of Computer Science, FOCS 2000. Redondo Beach: IEEE Computer Society, 2000. 359-366.
  • 7Domingos P, Hulten G. Mining high-speed data streams. In: Ramakrishnan R, Stolfo S, Pregibon D, eds. Proc. of the 6th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. Boston: ACM Press, 2000. 71-80.
  • 8Domingos P, Hulten G, Spencer L. Mining time-changing data streams. In: Provost F, Srikant R, eds. Proc. of the 7th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. San Francisco: ACM Press, 2001. 97～106.
  • 9Zhou A, Cai Z, Wei L, Qian W. M-Kernel merging: Towards density estimation over data streams. In: Cha SK, Yoshikawa M, eds. The 8th Int'l Conf. on Database Systems for Advanced Applications (DASFAA 2003). Kyoto: IEEE Computer Society, 2003. 285～292.
  • 10Gibbons PB, Matias Y. Synopsis data structures for massive data sets. In: Tarjan RE, Warnow T, eds. Proc. of the 10th Annual ACM-SIAM Symp. on Discrete Algorithms. Baltimore: ACM/SIAM, 1999. 909-910.

共引文献160

同被引文献1

引证文献1

二级引证文献6

计算机科学
2009年 第8期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部