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

一种乱序数据流上的偏倚抽样算法

Biased Sampling Algorithm on the Out-of-order Data Streams
下载PDF
导出
摘要 抽样是生成和维护数据流概要结构的常用方法.乱序数据流中,延时到达的数据通常被丢弃,从而会降低聚集运算的精度.提出一种新的利用双时间戳进行偏倚抽样的方法,通过所设计的衰减函数确定数据流元组的权重,根据该权重进行抽样,不仅可以保证将最新产生的数据抽中,保留在滑动窗口内,还可以保证部分重要的延时数据不被丢弃.利用平衡二叉树存储滑动窗口内数据流元组的权重,以提高数据流操作的响应时间.实验结果表明根据双时间戳计算出的数据权重更能反映数据的实时性和代表性;与顺序结构相比,利用平衡二叉树可提高最小权重的查找速度,流数据量越大,速度提高越明显. 抽样是生成和维护数据流概要结构的常用方法.乱序数据流中,延时到达的数据通常被丢弃,从而会降低聚集运算的精度.提出一种新的利用双时间戳进行偏倚抽样的方法,通过所设计的衰减函数确定数据流元组的权重,根据该权重进行抽样,不仅可以保证将最新产生的数据抽中,保留在滑动窗口内,还可以保证部分重要的延时数据不被丢弃.利用平衡二叉树存储滑动窗口内数据流元组的权重,以提高数据流操作的响应时间.实验结果表明根据双时间戳计算出的数据权重更能反映数据的实时性和代表性;与顺序结构相比,利用平衡二叉树可提高最小权重的查找速度,流数据量越大,速度提高越明显.
作者 秦林新 刘奇志
机构地区 南京大学计算机软件新技术国家重点实验室 南京大学计算机科学与技术系
出处 《计算机研究与发展》 EI CSCD 北大核心 2011年第S3期298-303,共6页 Journal of Computer Research and Development
基金 国家自然科学基金项目(60775046)
关键词 乱序数据流 概要结构 双时间戳 抽样 out-of-order data streams synopsis double timestamps sampling
分类号 TP3 [自动化与计算机技术—计算机科学与技术]
  • 相关文献

参考文献1

二级参考文献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

计算机研究与发展
2011年 第S3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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