Skyline代表点的选择*

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

Selection of Skyline Representative Point

Skyline query plays an important role in multi-decision and data mining. However, with the growth of data dimension, Skyline set becomes very large. Skyline representative point query is studied to overcome this shortcoming. A new evaluation function is proposed to improve the score-computing of Skyline points so as to select k representative Skyline points. A dynamic programming based algorithm(DPBA) in two-dimensional space is presented. The Eulerian distance between representative point and non-representative point is determined by the cover circle. k representative points are got by computing the evaluation function iteratively. In high-dimensional space, an approximate solution based on aR-tree index is proposed to solve the NP-hard problem. The index tree is traversed to judge whether it is dominated by the candidate Skyline sets. If it is dominated, it should be pruned to reduce the computation cost. The experiments of synthetic and real data show that the proposed algorithms are effective and efficient.