基于共享策略的k-支配轮廓体的求解算法

Sharing-based Algorithm to Find the Kdominant Skyline Cube

现有的k支-配轮廓算法虽然可以对给定的高维数据集计算出不同k(k≤d)值对应的k-支配轮廓,但是,由于不能共享计算结果,会导致很多冗余操作.提出k-支配轮廓体的概念,即所有的k(k≤d)值对应的k-支配轮廓的集合,在此基础上,提出两种基于共享策略的k-支配轮廓体算法——由下到上算法(BTA)和由上到下算法(TBA).理论分析和实验验证表明,所提算法可有效的减少冗余操作.

The existing algorithms can compute k-dominant skylines for different k value（k≤d） in high dimensional data set, because of not sharing the result, lead to much repeated work. A new concept of k-dominant skyline cube is proposed in this paper, which consists of all the k-dominant skylines（k≤d）, and two sharing-based algorithms-BTA algorithm and TBA algorithm are proposed too. FUrthermore, detailed theoretical analyses and extensive experiments show that our algorithms can decrease much repeat work effectively.