Skyline计算研究综述

Skyline computation:survey

近年来,skyline计算以其在多目标决策、数据挖掘、数据库可视化等方面的潜在应用引起了越来越多研究者的关注。集中式skyline计算作为最早的研究重点得到了深入的研究,许多有效的skyline计算算法被提出来,例如BNL、NN、BBS等等。其中,BBS被认为是当前最佳的集中式skyline计算算法。分布式skyline计算的研究也取得了明显进展,已有的工作分别对面向分布式数据库、移动自组织网络和对等网络等的skyline计算进行了探索。Skyline计算还被扩展为其它更复杂的计算问题,包括任意子空间上的skyline,所有子空间上的skyline,k-支配的skyline,空间skyline计算等等。然而,迄今为止,国内外还没有一篇论文对sky-line计算技术作过全面的分析与评述。对skyline计算技术进行系统的综述。在介绍已有代表性算法的基础上,通过分析它们的特点和比较它们的性能,总结了各算法的优势和不足,并指出了skyline计算的未来发展方向。

In recent years,the database community has witnessed a growing interest in skyline computation,mainly due to the awareness of its importance in many applications involving multi-criteria decision making,data mining,and database visualization. Centralized skyline computation has been extensively studied,and some effective algorithms have been proposed,such as BNL, NN,BBS,etc.Distributed skyline computation has also received considerable attention recently,and studies have been conducted on distributed databases,mobile ad-hoc networks,and peer-to-peer networks.Furthermore,the study of skyline has also been extended in different directions,like subsky,skycube,k-dominant skyline,spatial skyline and so on.In despite of the extensive study on skyline computation,there is no survey on this topic in the literature.In this paper,the author conducts a comprehensive survey on skyline computation techniques.And introduces the typical skyline computation algorithms,analyzes their characteristics,compares them with each other,and outlines the directions for future research.