一种更新k-支配轮廓的算法  

An Algorithm to Update k-dominant Skyline

作　　者：董雷刚[1,2] 崔晓微[1] 刘国华[2] 

机构地区：[1]大庆师范学院计算机科学与信息技术学院,大庆163712 [2]东华大学信息科学与技术学院,上海201620

出　　处：《科学技术与工程》2014年第22期235-239,共5页Science Technology and Engineering

基　　金：黑龙江教育厅科技项目(12523004)资助

摘　　要：k-支配轮廓查询技术在计算高维空间数据集时,解决了查询结果集合过大的问题,更有利于用户决策;然而,现有的算法都是针对静态k值设计的,不适合k值动态变化的情况。为了解决此问题,提出一种思路,即当k值改变以后,以现有的查询结果为基础,通过对可能发生身份变化的数据点进行判断,得到新的k-支配轮廓。在此基础上分别针对k值增大和k值减小这两种情况提出了相应的更新算法。通过理论分析和实验,算法能快速完成运算并返回正确查询结果。k-dominant skyline query technology reduces the result sets in high dimensional space,which is more convenient for user to make decision.But all the existent algorithms are for static k,not suitable to dynamic k.To solve this problem,a new idea is proposed,updating the k-dominant skyline for new k by computing the partial points based on existent k-dominant skyline.Based on which,two algorithms are proposed for k increasing and decreasing.Furthermore,detailed theoretical analyses and extensive experiments demonstrate that the algorithms can effectively finish computation work,and return the correct result.

关 键 词：k-支配轮廓查询 高维空间 动态变化 更新 

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