云环境下基于超球面投影分区的Skyline计算

摘要

目前,Skyline查询在集中式数据库、分布式数据库、数据流及分类属性数据集上的良好应用前景,使其成为当前数据库界研究的重点和热点之一,受到了学术界和工业界的广泛关注,它作为一种重要的数据挖掘技术广泛应用于多目标优化、城市导航系统、用户偏好查询及约束决策、智能防御系统以及地理信息系统等领域.随着人类可以采集和利用的数据信息的急剧增长,如何处理大数据的Skyline查询成为急需解决的问题.针对云计算环境,在Map-Reduce框架下设计并实现了基于超球面投影分区的分布式Skyline算法HSPD-Skyline,其主要思想是通过对高维数据点的超平面投影映射,即由空间坐标转换为超球面坐标,可以有效提高分区内数据点的平均减枝力度,降低Skyline的计算代价.同时,使用基于空间分区树的启发式策略HA-SPT,进一步提高了HSPD-Skyline算法的处理效率.通过详细的理论分析和实验验证表明,在不考虑数据分布和进一步优化算法的条件下,提出的HSPD-Skyline算法的总体性能(可扩展性、Skyline查询时间等)优于同类算法.