论文部分内容阅读
反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查询在分布式环境下的应用和发展。