利用k-d树索引改进数据流skyline查询算法

摘要 skyline查询技术近来引起了研究者们的广泛关注,面向数据流的skyline查询是其中的热点.对面向数据流的skyline查询问题进行了研究.对现有方法进行了改进,提出一种基于k-d树的skyline增量更新算法.该方法采用事件链机制来处理数据点的状态变化,避免重复计算过期数据点排它支配域上的skyline;增量数据点的处理过程中采用k-d树作为索引结构,以增强索引结构对数据流变化的自适应性;针对kd树索引提出多个剪枝规则来减小搜索域,提高搜索效率.理论分析及实验表明,该方法能够更快地响应用户的查询请求,更适用于大规模、疏密分布变化的高速数据流应用场景