一种分布式环境中的二分式多层网格skyline算法

Dichotomous multi-layer grid method for skyline query in distributed computing environments

skyline计算在数据挖掘、多标准决策和数据库可视化等领域有着非常重要的作用,这些年已经得到了广泛的关注,以往对于skyline查询的研究大多集中在处理集中的数据集上,即集中式skyline查询,已经得到了很多的研究成果。然而,实际情况是:相关数据几乎分散在几个不同的服务器上,因此在分布式环境中的skyline查询计算需要从各个服务器收集大量的数据;现有的在分布式环境中的skyline查询方法有两个主要问题:一是skyline查询的处理时间较慢;二是在网络中服务器之间传输了很多不必要的重叠数据。提出了一种二分式多层网格法(DMLG),可以有效地处理在分布式环境中的skyline查询。该方法利用网格的方法,借鉴二分法,最大限度地减少了不必要的重叠数据传输,基于不同的数据集的实验表明,这种方法优于现有的方法。

In recent years,the skyline query has received more and more attention.This is because of its importance in many applications involving database visualization multi-criteria decision making,data mining and so on.Most of the previous works have put their attention on processing skyline queries on centralized data sets which is called centralized skyline query,and many research results have got.However,the reality is that the related data practically scatter at several different servers.The skyline query computation needs to gather a lot of data from the connected servers in distributed environment.The existing methods for distributed skyline query computation have two problems： firstly,their processing time for a skyline query is slow;secondly,they transfer many unnecessary data among servers in the network.This paper proposes a Dichotomous Multi-Layer Grid method（DMLG）.The proposed method based on the grid mechanism uses the dichotomy to minimize the unnecessary transferred data.Experiments based on different data sets show that this proposed method is better than the existing methods.