用天际线算法来识别杰出科学家

武夷山    

    Journal of Informetrics杂志2016年第8期发表A. Sidiropoulosa（希腊色萨利大学电气与计算机工程系）、A. Gogogloub （希腊亚里士多德大学情报学系）、D. Katsarosc（色萨利大学电气与计算机工程系） 和Y. Manolopoulose（亚里士多德大学情报学系）合著的文章，Gazing at the skyline for star scientists（凝望天际线，寻找明星科学家）。这个标题很有意思，一语双关，一重意思是：凝望天际线，观看星辰；另一重意思是，利用天际线算法（Skyline operator）来识别明星科学家。

    文章摘要说，人们提出了很多种指标来给科学家排序，但没有任何一种指标能完全反映科学家的科研业绩和学术影响力，因为任一种指标只能反映其多重业绩的一个方面或少数几个方面。因此，科学计量学排序问题就可以视作多维排序问题，那么，人们自然会想到采用天际线算法来解决多维排序问题。本文就是这样的尝试，结果发现，用天际线算法识别出的科学家实在是卓越，其方方面面都是其他科学家无法超越的。在学术奖项提名的过程中，可以采用这种方法。

    博主：我以前没听说过天际线算法，百度百科有对“skyline查询”的解释：

_{数据库中Skyline} 

Skyline 查询是一个典型的多目标优化的问题.对它的研究最早可以追溯到1975 年.

Skyline一个经典的例子[1]  如图所示：假设去Nassau海滩旅游，想找一个既便宜又靠近海滩的旅馆，一般情况下越靠近海滩的旅馆价格越高，所以不能返回一个最好的结果，只能返回一些用户可能感兴趣的旅馆，这些旅馆在价格和距离两个方面都不比其它旅馆差，这些不被支配的旅馆就是Skyline。

Kung 在文献中针对二维或三维数据提出了一种查询复杂度为O(nlog2n)的算法,针对大于三维的数据,提出了查询复杂度为O(n(log2n)d−2)的算法.后来,Bentley 在假定各维数据分布独立的情况下,提出了人们期望的线性查询算法[4].所有这些研究都假定数据集比较小,可以放入内存,所提出的算法也都是内存算法.
　　数据库领域的研究人员对Skyline 查询的研究始于2001 年,最早由Borzsonyi 等人提出[1].主要关注在数据量很大、无法放入内存的情况下,如何处理Skyline 查询.[2] 

最近几年,对Skyline 查询的研究大体上可以分为4 类:
　　1) 单Skyline 查询处理算法.该类算法假定所有的Skyline 对象都处在某一个特定的D-维空间中,返回的结果集合只有1 个.根据查询过程中是否借助索引,单Skyline 查询处理算法又分为两类:不带索引算法和带索引算法.前者假定没有任何索引存在,通过扫描整个数据集(至少1 次)来返回Skyline 查询的结果;后者通过引入适当的索引结构,如R-树,来提高查询处理的效率.
　　2) 多Skyline 查询处理算法.针对现实生活中不同的用户可能有不同的兴趣和偏好,需要在不同的子空间中处理Skyline 查询的需求,数据仓库和OLAP 领域的研究者对在不同子空间上进行Skyline 查询的研究产生了浓厚的兴趣,提出了SKYCUBE[5]的概念.SKYCUBE 借用传统的Data Cube 的多维层次结构,提出了有效的同时计算多个Skyline 查询的思想.该类算法主要包含针对SKYCUBE 的计算、维护和压缩等.
　　3) 不同应用环境下的Skyline 查询处理.主要包括Web 信息系统中的Skyline 查询处理、P2P 网络环境下的Skyline 查询处理、数据流环境下的Skyline 查询处理、移动的公路网络环境下的Skyline 查询处理等.
　　4) Skyline 查询处理问题的扩展.例如,文献[6]中首次扩展了空间数据库中不同数据点之间的控制关系的概念,将其用于经济学框架下的商业分析,提出了控制关系分析的概念;文献[7]针对高维空间下出现在Skyline 查询结果中的点非常多,从而导致该结果在很多时候对用户失去意义的问题,提出了k-Dominant 的概念,等等.

可以看出,Skyline 的查询处理问题已经引起了国内外研究者的高度重视,近几年,在SIGMOD,VLDB,KDD,PODS,ICDE,ICDM等相关的高水平国际会议上发表了许多高质量的论文,展示出大量的研究成果.在TKDE,TODS 等期刊中也发表了大量成果.然而目前,国内和国际上还没有将Skyline 查询处理的发展情况、核心技术和研究成果进行整体上的介绍.鉴于Skyline 查询处理在多规则决策应用方面的重要价值和在实时在线服务方面的良好应用前景,为了捕捉Skyline 查询处理的发展动态,对Skyline 查询处理研究有一个总体上的把握,促进国内迅速跟上国际研究的步伐,综述这方面的工作十分有意义.

1.  The Skyline Operator  ．IEEE数据库．2001[引用日期2014-12-25]

2.  Skyline查询处理  ．软件学报．2008[引用日期2014-12-25]

如果采用skyline computation的说法，能够查到的文献更多，例如2014年发表的一篇题为Efficient Skyline Computation in MapReduce的文献，原文见http://openproceedings.org/2014/conf/edbt/MullesgaardPLZ14.pdf。