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

An Algorithm to Update k-dominant Skyline

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.