基于最大覆盖的代表Skyline问题的优化算法研究

• 作者: 周新 宁博 李冠宇 王习特 白梅
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 代表skyline k-MCS 前缀算法 贪心算法 优化算法
• 年，卷（期）: 2020,（12）
• 所属期刊栏目: 云计算
• 页码范围: 2276-2297
• 页数: 22页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2020.02276

摘要

Skyline查询作为多目标决策的重要手段之一,可以根据用户偏好,在大量的数据中挖掘出用户真正感兴趣的数据.然而,随着维度的增加以及数据分布的原因,会导致skyline结果数目过多,查询结果失去意义.目前,已有一些工作对代表skyline问题进行了研究,即在全部skyline结果中选取k个最具代表性的skyline元组.综合考虑代表skyline的代表性以及稳定性,本文选取基于最大覆盖的代表skyline问题(k-Maximum Coverage Skyline,k-MCS)问题进行研究.与之前的k-MCS计算方法相比,本文提出的算法具有更好的效率.针对k-MCS问题,首先,本文提出了2维上的基于前缀的优化算法OPA(Optimal Prefix Algorithm),OPA算法利用前缀支配表,可以通过少量的加减法运算完成最后的结果计算.接着,考虑到多维上k-MCS问题是一个NP-Hard问题,本文提出了优化贪心算法OGA和e OGA,OGA比基本贪心算法减少了50％以上的计算量.而e-OGA通过引入参数ε,与OGA算法相比,仅牺牲ε/(1+ε)的精度,大大加快了计算效率.最后,通过大量的实验验证了本文所提算法OPA、OGA和ε-OGA的有效性和高效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李冠宇		108	867	15.0	25.0
2	宁博		8	15	2.0	3.0
3	白梅		8	2	1.0	1.0
4	王习特		6	1	1.0	1.0
5	周新		4	13	3.0	3.0