分布式数据的反kyline查询算法研究.pdf

分布式数据的反SKYLINE查询算法研究 摘要 分分分布布布式式式数数数据据据的的的反反反SKYLINE查查查询询询算算算法法法研研研究究究 摘摘摘 要要要 反skyline查询常用在数据挖掘和决策支持系统中，用于数据的多准则优化。但 目前有关反skyline查询的研究仅限于集 中式数据，分布式数据上的反skyline查询尚 未有文献涉及。在现实应用 中，基于更新成本、性能等考虑，数据经常是分散存放 并通过网络互连 的，现有 的集 中式算法无法满足分布式环境。本文将分布式数据上 的反skyline查询作为研究重点，具体工作包括 以下几个方面： （1）分析当前集 中式数据集上的反skyline查询方法，设计 了分布式数据集上的 反skyline查询算法BBDRS。远程站点利用R树索引预计算反skyline点集 的候选集和 筛选集，并将其作为发 中央站点的数据摘要，一方面 降低了总体反应延迟，另一 方面避免发送全部数据，减少了大量的通信开销。 （2 ）针对上述R树算法花费大量时间建立索引的问题，设计 了分布式数据集上 一种使用预排序的反skyline查询算法PDRS。该算法采用上述相 同的通信策略，核心 思想是将各数据点按与查询点的”距离”进行预排序，在避免建立索引的同时大大减 少支配比较次数，节省了计算时间。在非很大规模数据上，PDRS性能较BBDRS好。 （3 ）借鉴 当前 单 数据流上的反skyline查询方法，设计 了分布式数据流上的 反skyline查询算法—DCDRS算法。客户端，利用DC树索引实时计算和维护当前窗 口 内必威体育精装版的数据摘要信息；服务器端，则利用集 中式算法计算最终结果。DCDRS算法 能够正确并有效的解决分布式数据流环境下的反skyline查询问题。 （4 ）设计并实现 了分布式数据查询实验平台。该平台通过控制端的控制功能， 实现 了文中实验的自动化完成，避免了大量手工操作，在一定程度上保证了实验数 据的真实性与精确性。 本文对分布式数据反skyline查询算法进行的研究，在用户偏好、多条件决策系 统以及数据挖掘中具有非常重要的现实意义。在数据存储越来越趋 向于分布式的今 天，本文的工作可以促进反skyline查询在分布式环境下的应用和发展。 关键词： 反skyline，分布式查询，skyline，数据库查询，数据流 作 者： 杨萍萍 指导教师： 赵 雷 I ABSTRACT Research on Reverse Skyline Query over Distributed Data Research on Reverse Skyline Query over Distributed Data Abstract Reverse skyline query, as a typical method about multi-criteria optimization, is being widely used in data mining and multi-criteria decision. However, till now, most of the work is based on the centralized data and there is no work over distributed data. In practice, most of the data is stored over dierent sites connected by network in consideration of the cost and performance. The existing centralized algorithm can’t simply satisf