海量数据上有效的top-k Skyline查询算法*

• 作者: 宋翠 戈韵如 李建中 韩希先 高宏
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 海量数据 top-k Skyline RSTS算法 表扫描 剪切操作
• 年，卷（期）: 2019,（5）
• 所属期刊栏目: 数据库技术
• 页码范围: 775-787
• 页数: 13页
• 分类号: TP391
• 字数: 8749字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.1807039

摘要

在许多应用中,Skyline查询是一种十分重要的查询类型,它在潜在的巨大的数据空间中返回不被其他元组支配的用户感兴趣的元组,但是Skyline查询无法控制返回结果的数量.处理一个新的top-k Skyline查询问题,该查询返回支配分数最大的k个Skyline元组,从而控制了需要向用户返回的查询结果数量.分析发现,大多数现有算法忽略了利用支配分数作为限制Skyline查询的结果数量的度量.提出一个新的基于表扫描的RSTS(ranked Skyline with table scan)算法来有效计算海量数据上的top-k Skyline结果.RSTS算法首先对表执行预排序操作,保证预排序表的元组按照对有序列表的round-robin扫描的顺序排列.RSTS算法包括两个阶段.阶段1利用对预排序表的顺序扫描来获得候选元组.阶段2计算候选元组的支配分数并返回结果.可以证明,RSTS算法具有早结束特性,并给出其扫描深度的理论分析.提出对于候选元组的剪切操作,理论剪切效果表明,绝大多数的Skyline结果可以直接丢弃.实验结果表明,RSTS算法可以有效计算top-k Skyline结果.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李建中	哈尔滨工业大学计算机科学与技术学院	237	6003	33.0	72.0
2	高宏	哈尔滨工业大学计算机科学与技术学院	109	1574	18.0	36.0
3	韩希先	哈尔滨工业大学计算机科学与技术学院	11	159	6.0	11.0
4	宋翠	哈尔滨工业大学计算机科学与技术学院	1	3	1.0	1.0
5	戈韵如	哈尔滨工业大学计算机科学与技术学院	1	3	1.0	1.0