计算机与现代化

• 数据库与数据挖掘 • 上一篇    下一篇

不确定数据流上的并行反Skyline查询

  

  1. (南京航空航天大学计算机科学与技术学院,江苏南京210016)
  • 收稿日期:2014-10-09 出版日期:2015-01-19 发布日期:2015-01-21
  • 作者简介:张建荣(1987-),男,江西余干人,南京航空航天大学计算机科学与技术学院硕士研究生,研究方向:Skyline查询,数据库; 毛宇光(1962-),男,江苏海门人,副教授,研究方向:软件测试,数据仓库。
  • 基金资助:
    国家自然科学基金资助项目(41301407)

Parallel Reverse Skyline Query over Uncertain Data Streams

  1. (College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China)
  • Received:2014-10-09 Online:2015-01-19 Published:2015-01-21

摘要: 作为Skyline查询的一种重要变体,不确定数据流上的反Skyline查询已经成为研究的热点。已有的单机算法无法应对诸如高速数据流、高数据维度、大滑动窗口等情况,相应提出并行查询处理算法PRSUDS。算法采用基于角度划分的分发策略将处理任务分发至各并行节点,给出该分发策略的正确性证明,进而设计、实现算法的并行处理框架。实验结果表明PRSUDS算法较单机算法具有更好的综合性能,更能满足数据流查询的实时性要求。

关键词: 反Skyline查询, 不确定数据流, 并行处理, 分发策略

Abstract: As an important variant of Skyline query, reverse Skyline query over uncertain data streams has become a hot topic recently. However, existing standalone algorithm can’t cope with data streams with highspeed, high data dimensions, large sliding windows, etc. A novel parallel processing algorithm named PRSUDS is proposed. PRSUDS adopts anglepartitioningbased dispatch strategy to assign processing tasks to peer nodes; the correctness of the dispatch strategy is presented. Then the design and implementation of parallel processing framework are presented. Results of massive experiments show that PRSUDS has better overall performance compared to existing algorithms.

Key words: reverse Skyline query, uncertain data streams, parallel processing, dispatch strategy

中图分类号: