计算 SKY 的预排序分组算法

• 作者: 刘萍
• 来源期刊: 计算机与现代化
• 学科: 工学
• 关键词: 多元目标优化 预排序 轮廓 分组算法
• 年，卷（期）: 2014,（2）
• 所属期刊栏目: 数据库
• 页码范围: 69-72
• 页数: 4页
• 分类号: TP311
• 字数: 4154字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-2475.2014.02.016

摘要

在SFS算法的预排序思想基础上，借助数据集R上的单调分值函数，将R的点分组，提出计算Skyline的迭代算法。算法有效地支持用户的偏爱。给出证明：若R的点的个数为n，R的Skyline的点的个数为m，则在计算R的Skyline的过程中，需要对点之间所做的支配比较的次数不超过m（n-m/2-1/2）；如果分组的组数为k，则分组算法比SFS减少比较次数不少于m（m-k）/2k。