海量数据上有效的top-k Skyline查询算法
在许多应用中,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结果.
海量数据、top-k Skyline、RSTS算法、表扫描、剪切操作
13
TP391(计算技术、计算机技术)
The National Natural Science Foundation of China under Grant Nos. 61632010, 61502121, 61872106;the Na-tional Key Research and Development Program of China under Grant No. 2016YFB1000703;the Weihai-HIT Co-Construction Program under Grant No. ZMZ001702
2019-05-22（万方平台首次上网日期，不代表论文的发表时间）
共13页
775-787
