论文部分内容阅读
Top-K支配查询返回数据集中支配其它数据点个数最多的前K个点，它继承了Skyline查询和Top-K查询的优点而避免了二者的缺点，在偏好搜索、多标准决策支持等领域具有重要作用。目前关于Top-K支配查询的研究局限于集中式数据集。然而，在金融信息分析、传感器网络等新兴应用领域，数据从地理上分布的不同数据源以流的形式连续地传送到中央数据仓库的特征日益显现。如何从这些分布的、流动的海量数据中实时地挖掘到有用信息是近年来流数据挖掘领域中的研究热点。本文将分布式数据流上Top-K支配查询作为研究重点，具体工作包括以下几个方面： （1）发现Top-K支配查询结果是K-Skyband查询结果的子集，并以此提出通过预先维护分布式数据流上的K-Skyband来进一步求解Top-K支配查询结果的思想。 （2）本文基于网格索引提出一种分布式数据流上连续K-Skyband查询算法GBIFA。GBIFA通过传送K-Skyband增量来减少站点间通信开销。此外，GBIFA对网格索引进行支配区域划分，避免了更新时大量的支配测试，减少了时间开销。 （3）本文实现了一种基于K-Skyband的分布式数据流上连续Top-K支配查询算法GKTDM。围绕减少时间开销为目的，该算法将K-Skyband作为Top-K支配查询结果的候选集，只对K-Skyband点而非全部数据计算支配能力；此外，提出保留支配能力的思想，避免更新后重新计算K-Skyband点的支配能力；最后，采用远程站点预先判定新数据身份的策略，避免中央站点在接收到局部站点的候选K-Skyband点时也对全局K-Skyband集合进行更新维护。 （4）本文以多线程服务器/客户机模型模拟分布式数据流环境，设计了一个分布式数据流查询实验平台，可以高效和自动地测试所提算法在不同参数下的性能。 本文对分布式数据流上Top-K支配查询的研究，在偏好搜索、多标准决策支持等领域具有重要的现实意义。在分布式数据流上的数据挖掘越来越受关注的今天，本文的工作可以促进Top-K支配查询在分布式数据流环境下的应用。