分布式环境下skyline查询处理技术研究

摘要

Skyline查询处理是数据库技术领域的一个研究重点和热点,它在多目标决策、数据挖掘和可视化、用户偏好查询等方面有着广阔的应用。Skyline查询输出数据集中不被其它任意数据点所支配的点所组成的集合,使得用户可以在小规模的skyline结果集上选择自己感兴趣的对象,而不必关心那些被过滤掉的对象。随着分布式网络系统的深入应用和云计算的发展,分布式的skyline查询计算近年来受到广泛关注。由于全局知识的缺乏和不同分布式环境的特殊要求,分布式的skyline查询面临着巨大的挑战。本文针对分布式环境下的skyline计算及其相关问题进行了深入的分析研究。本文的主要工作和创新点如下:
　　(1)研究了无线传感器网络中的连续skyline查询问题,提出了一种基于预测技术和数据映射的skyline查询算法。Sink收集所有节点的预测误差,用以预测值为中心、两倍预测误差为边长的超正方体来表示节点的真实感应数据值,然后基于超正方体之间的支配关系进行节点剪枝。节点上传真实感应值,当且仅当节点收到sink发出的“上传”消息。为了最大化预测获益,提出了一种分段线性预测技术,根据查询结果自适应地更新预测模型参数值。实验结果表明,该算法可以有效地减少传感器网络中执行连续skyline查询时的通信代价。
　　(2)研究了传感器网络中反相关或簇状分布数据集下的过滤器设计问题,提出了基于数据簇表示模式的针对性数据过滤算法。现有过滤器算法普遍通过从数据集中选择支配能力最强的数据点(或者相关数据值)作为过滤器,存在过滤效果受限于数据分布的问题。本算法为不同的节点设计不同的过滤器,来适应不同的数据分布。为了降低过滤器计算代价和最大化过滤获益,设计了一种新颖的数据簇表示模式和一种基于历史查询结果的抽样技术。实验结果表明,该算法在正确返回查询结果的同时,减少了无线传感器网络中的过滤器计算代价和总的查询通信能耗。
　　(3)研究了无线传感器网络中的连续反skyline查询问题,将前面提出的连续skyline查询算法思想应用到反skyline计算中。不同于skyline计算,反skyline查询算子是不可分解的,即不能随意删除非结果数据,否则容易导致误报。为此,提出了扩展半支配和扩展全支配的概念,用来基于数据映射知识对产生反skyline数据集的节点、不产生结果集的节点和能立即删除的节点进行识别。对这些节点进行分阶段探测,以减少需要上传真实感应数据的节点数目。实验结果表明,算法能输出正确的结果集,且具有较好的能量有效性。
　　(4)探讨了客户端/服务器模型下的skyline查询问题,提出了基于数据划分技术的分布式skyline算法。该算法将每个服务器上的数据按照其和其它服务器数据的依赖关系划分成若干数据区域,使得不相互依赖的数据域能够并行地执行查询。这些不相互依赖的数据区域可以来自不同的服务器,也可以来自相同的服务器。同时,基于数据区域之间的依赖关系,制定查询计划,既有利于选择过滤效力强的数据作为过滤器,又使得算法能够渐进性地输出查询结果。并行式的查询和过滤器技术有效地缩短了查询时间。理论上证明了查询计划的最大跳数存在上界。

目录

封面

声明

中文摘要

英文摘要

目录

插图索引

附表索引

第1章 绪论

1.1研究背景

1.2 国内外研究现状综述

1.3分布式环境下的skyline查询问题

1.4本文的研究工作

1.5本文的组织结构

第2章 分布式skyline查询的研究现状

2.1研究现状

2.2现状分析

2.3本章小结

第3章 无线传感器网络中的连续skyline查询算法

3.1问题描述

3.2基于预测技术的连续skyline查询算法

3.3 实验测试与结果分析

3.4 本章小结

第4章 分簇传感器网络中一种基于数据过滤的skyline查询算法

4.1问题描述

4.2已有工作

4.3 预备知识和问题定义

4.4 算法整体框架

4.5 数据簇表示模式

4.6 算法具体过程

4.7实验测试与结果分析

4.8本章小结

第5章 无线传感器网络中的连续反skyline查询算法

5.1问题描述

5.2相关工作

5.3预备知识和问题定义

5.4数据映射模式

5.5 ECRS算法

5.6实验测试与结果分析

5.7 本章小结

第6章 基于数据划分的分布式skyline计算

6.1问题描述

6.2相关工作

6.3预备知识

6.4算法整体框架

6.5基于依赖关系的数据划分

6.6区域间的查询计划

6.7实验测试与结果分析

6.8 本章小结

总结与展望

1 本文工作总结

2 未来工作展望

参考文献

致谢

附录A 攻读学位期间发表的论文

附录B 攻读学位期间申请的发明专利

附录C 攻读学位期间参与的项目