计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (6): 160-165.

• 数据库与信息处理 • 上一篇    下一篇

Skyline计算研究综述

朱 琳1,关佶红2,周水庚1   

  1. 1.复旦大学 计算机科学与工程系,上海 200433
    2.同济大学 计算机科学与技术系,上海 201804
  • 收稿日期:2007-09-07 修回日期:2007-12-11 出版日期:2008-02-21 发布日期:2008-02-21
  • 通讯作者: 朱 琳

Skyline computation:survey

ZHU Lin1,GUAN Ji-hong2,ZHOU Shui-geng1   

  1. 1.Department of Computer Science and Engineering,Fudan University,Shanghai 200433,China
    2.Department of Computer Science and Technology,Tongji University,Shanghai 201804,China
  • Received:2007-09-07 Revised:2007-12-11 Online:2008-02-21 Published:2008-02-21
  • Contact: ZHU Lin

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

Abstract: 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.