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

摘要：

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

关键词：分布式Skyline计算、Map-Reduce框架、分区策略、HSPD-Skyline算法

所属期刊栏目：40

分类号：TP391(计算技术、计算机技术)

资助基金：基于大规模复杂结构知识库的知识发现机理、模型与算法研究60875029;多关系频繁模式挖掘模型、方法与一般架构的研究60675030;基于多关系的模糊认知图挖掘模型、算法与评价机制研究61175048

在线出版日期：2013-07-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：164-171