计算机科学与探索

作者：韩希先，宋翠，戈韵如，高宏，李建中

单位：哈尔滨工业大学 计算机科学与技术学院，哈尔滨 150001

关键词：海量数据,top-k Skyline,RSTS算法,表扫描,剪切操作

在许多应用中，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结果。

来源：2019年第5期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2019年第5期