Skyline代表点的选择

摘要：

Skyline查询在多维决策和数据挖掘等方面发挥重要作用，然而随着数据属性维度的增大， Skyline集变得非常庞大。为克服该不足，提出Skyline代表点查询。文中提出新的评价函数改进Skyline点的得分计算方法以选择k个具有代表性的Skyline点。在二维空间提出动态规划算法( DPBA)，利用覆盖圆的性质确定非代表点与代表点间的覆盖距离，迭代计算评价函数值，从而得到k个代表点；在高维空间针对NP-hard问题提出一个基于aR-tree结构的近似解决方法，遍历索引结构中的节点，通过与候选Skyline集比较判断是否被支配进行剪枝，降低计算开销。大量基于合成数据与真实数据的实验证明该算法的有效性。

关键词：Skyline查询、Skyline代表点、集中式环境、动态规划

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

资助基金：国家自然科学基金项目61202007;浙江省自然科学基金项目LY13F020040;宁波市自然科学基金项目2013A610063

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

页数：共8页

页码：239-246