摘要
在SFS算法的预排序思想基础上,借助数据集R上的单调分值函数,将R的点分组,提出计算Skyline的迭代算法。算法有效地支持用户的偏爱。给出证明:若R的点的个数为n,R的Skyline的点的个数为m,则在计算R的Skyline的过程中,需要对点之间所做的支配比较的次数不超过m(n-m/2-1/2);如果分组的组数为k,则分组算法比SFS减少比较次数不少于m(m-k)/2k。
In this paper, we proposed the presorting grouping algorithm for skyline computation. This algorithm was based on SFS algorithm, and efficiently supported the preference of users. We proved that, for computing skyline, the number required compar- isons between two points does not exceed m（n -m/2 - 1/2）, where n being the number of points, and m being the number of skyline points ; if the number of groups being k, then the number required comparisons used in the presorting grouping algorithm reduced m（ m - k）/2k.
出处
《计算机与现代化》
2014年第2期69-72,共4页
Computer and Modernization
关键词
多元目标优化
预排序
轮廓
分组算法
multi-objective optimization
presorting
skyline
grouping algorithm
