一种求解动态数据集中k-支配轮廓的算法  

Algorithm of Finding k-dominant Skylines for Dynamic Datasets

作　　者：董雷刚[1] 刘国华[1] 崔晓微[1] 张东明[1] 

机构地区：[1]燕山大学信息科学与工程学院,河北秦皇岛066004

出　　处：《小型微型计算机系统》2009年第4期617-622,共6页Journal of Chinese Computer Systems

基　　金：国家"十一五"科技支撑计划项目(2006BAK05B02)资助;国家自然科学基金项目(60773100)资助

摘　　要：在对高维数据集进行轮廓查询时,k-支配轮廓查询算法能够返回较少的轮廓点,有利于用户的决策,但目前的算法都是针对静态数据集设计,无法对动态数据集进行处理.动态数据可分为非数据流数据和数据流数据,本文针对这两种情况提出了相应的增量求解算法,即当数据集发生变化时,以现有的k-支配轮廓为基础,通过对部分数据点进行计算得到新的k-支配轮廓.证明了算法的正确性和有效性,并通过实验对算法进行了分析和验证.K-dominant skylines query can return little number of skyline points in high dimensional spaces, helping users to make decisions. But at present all the algorithms are designed for static datasets, not for dynamic datasets. Dynamic data consists of non-data-stream and data-stream, in this paper, the increasement algorithms for these two instances are proposed, getting the new result through computing partial points based on the existent k-dominant skylines when dataset changes. The correctness and validity of the algorithm are proved, and the algorithm is analyzed and validated by experiments.

关 键 词：高维空间 动态数据集 k-支配轮廓查询 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]