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

概率数据流上Skyline查询处理算法 被引量：17

Algorithm on Computing Skyline over Probabilistic Data Stream
下载PDF
导出
摘要 概率数据流管理与分析逐步引起了研究者们的关注.Skyline查询技术是近年来数据库领域的研究热点.此前相关工作仅限于静态数据集或传统确定性数据流上的Skyline查询处理,尚无人考虑概率数据流上的Skyline计算问题,本文提出的SOPDS算法则较好地解决了该问题.在采用适应性更强的网格索引的基础上,提出了概率定界、逐步求精、提前淘汰与选择补偿等启发式规则对算法从时间和空间两方面进行了系统地优化.实验表明,算法在时间与空间上具有较高的整体性能. Management and analysis of uncertain,probabilistic data stream has attracted considerable attention within database community.Skyline query processing is an open question recently.Although previous work has addressed skyline computations over static data or traditional data stream,skyline computation over probabilistic data stream is still at large.We propose an efficient algorithm SOPDS to handle this issue.Based on more adaptable grid index,a set of heuristic rules like probability bounding,progressive refinement,pre-elimination and selective compensation are developed to improve the comprehensive performance of SOPDS from point of reducing both CPU overhead and memory consumption.Massive experiments demonstrate that SOPDS is of high overall performance.
作者 孙圣力 戴东波 黄震华 张齐勋 周立新
机构地区 北京大学软件与微电子学院 复旦大学计算机科学技术学院 同济大学电信学院
出处 《电子学报》 EI CAS CSCD 北大核心 2009年第2期285-293,共9页 Acta Electronica Sinica
基金 国家973重点基础研究发展规划(No.2005CB321905)
关键词 概率数据流 SKYLINE 逐步求精 提前淘汰 probabilistic data stream skyline progressive refinement pre-elimination strategy
分类号 TP391.41 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献17

  • 1Borzsonyi S, Kossmann D and Stocker K. The Skyline Operator [ A]. Proc of ICDE[ C]. Washington: IEEE Computer Society, 2001.421 - 430.
  • 2Tao Y,Papadias D. Maintaining sliding window skylines on data streams[ J]. IEEE Transactions on Knowledge and Data Engineering ( IEEE TKDE), 2006,18 (3) : 377 - 391.
  • 3Lin X, Yuan Y, Wang W, Lu H. Stabbing the Sky: Efficient Skyline Computation Over Sliding Windows[ A]. Proc of ICDE [ C ]. Washington: IEEE Computer Society, 2005.502 - 513.
  • 4Papadias D, Tao Y, Fu G, Seeger B. Progressive skyline computation in database systems[ J]. ACM Transations on Database Systems, 2005,30( 1 ) : 41 - 82.
  • 5Chomicki J, Godfrey P, Gryz J and Liang D. Skyline with presorting [A]. Proc of the ICDE[ C]. Washington: IEEE Computer Society, 2003.717 - 719.
  • 6Pei J, Jiang B, Lin X, Yuan Y. Probabilistic skylines on uncertain data [A]. Proc of the VLDB[ C]. Vienna: ACM Press, 2007.15 - 16.
  • 7Babcock B., Babu S, Datar M, Motwani R, Widom J. Models and issues in data stream systems[ A]. Proc of the ACM PODS [C] .New York: ACM Press,2002.1 - 16
  • 8Cormode G, Crarofalakis M. Sketching probabifistic data streams [ A]. Proc of the ACM SIGMOD [ C]. Beijing: ACM Press,2007.281 - 292
  • 9Dalvi N, Suciu D. Efficient query evaluation on probabilisfic databases[ A]. Proc of VLDB[C]. Toronto: Morgan Kaufmann Publishers, 2004. 864 - 875.
  • 10Burdick D, Deshpande PM, Jayram TS, Ramakrishnan R, Vaithyanathan S. OLAP over uncertain and imprecise data[A]. Proc of VLDB[C ]. Trondheim: ACM Press, 2005. 970 - 981.

二级参考文献29

  • 1Agrawal R,Srikant R.Fast algorithms for mining association rules in large databases[A].Proceedings of the 20th International Conference on Very Large Data Bases[C].San Francisco:Morgan Kaufmann,1994.487-499.
  • 2Han J,Pei J,Yin Y.Mining frequent patterns without candidate generation[A].2000 ACM SIGMOD International Conference on Management of Data[C].Dallas:ACM Press,2000.1-12.
  • 3Pasquier N,Bastide Y,Taouil R,Lakhal L.Discovering frequent closed itemsets for association rules[A].In Proceeding of the 7th International Conference on Database Theory[C].Jerusalem,Israel:Springer,1999.398-416.
  • 4Pei J,Han J,Mao R.CLOSET:an efficient algorithm for mining frequent closed itemsets[A].ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery[C].Dallas:ACM Press,2000.21-30.
  • 5Burdick D,Calimlim M,Gehrke J.MAFIA:a maximal frequent itemset algorithm for transactional databases[A].Proceedings of the 17th International Conference on Data Engineering[C].Heidelberg:IEEE Computer Society Press,2001.443-452.
  • 6Zaki M,Hsiao C.Charm:an efficient algorithm for closed association rule mining[R].New York:RPI,1999.
  • 7Zhu Y,Shasha D.StatStream:statistical monitoring of thousands of data streams in real time[A].Proceedings of the 20th International Conference on Very Large Data Bases[C].Hong Kong,China:Morgan Kaufmann,2002.358-369.
  • 8Giannella C,Han J,Robertson E,Liu C.Mining frequent itemsets over arbitrary time intervals in data streams[R].Bloomington:Indiana University,2003.
  • 9Manku G,Motwani R.Approximate frequency counts over data streams[A].Proceedings of the 28th International Conference on Very Large Data Bases[C].Hong Kong,China:Morgan Kaufmann,2002.346-357.
  • 10Teng W-G,Chen M-S,Yu P S.A regression-based temporal pattern mining scheme for data streams[A].Proceedings of the 29th International Conference on Very Large Data Bases[C].Berlin,Germany:Morgan Kaufmann,2003.607-617.

共引文献21

同被引文献210

引证文献17

二级引证文献54

电子学报
2009年 第2期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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