面向大规模数据集的并行化Top-k Skyline查询算法

来源：计算机科学与探索杂志2015年第8期北京时间：

作者：杨林青，李湛，牟雁超，樊里略，李红燕，王腾蛟，雷凯

单位：1. 北京大学 信息工程学院 深圳市云计算关键技术与应用重点实验室，广东 深圳 5180552. 北京大学 高可信软件技术教育部重点实验室，北京 1008713. 北京大学 信息科学技术学院，北京 1008714. 北京大学 机器感知与智能教育部重点实验室，北京 100871

摘要：随着数据规模的日益庞大，在大规模数据集中帮助用户定位出数据量可控的代表性信息显得越发重要。虽然Top-k Skyline查询能够找到数据集中前k个最具代表性的信息，在获取代表性信息的同时又控制了结果规模，满足了上述要求，但是现有的Top-k Skyline查询在面对大规模数据集时效率较低，并不适用于大规模数据集。为了解决这个问题，将Top-k Skyline查询与并行化处理相结合，提出了一种面向大规模数据集的并行化Top-k Skyline查询算法PTKS（parallel Top-k Skyline），通过充分利用分布式资源，将原有查询进行有效的并行化处理，同时设计了基于用户偏好的用于缩减结果数据量的筛选规则，满足用户需求。在真实数据集上进行了相关实验，并与现有方法进行了对比，结果表明PTKS在大规模数据集上的查询效率更具有优势，能很好地适用于大规模数据集。

关键词：大规模数据集,Top-k Skyline,代表性信息,并行化处理,筛选规则