一种有效的海量数据Top-k Dominating查询算法

扫码查看

原文链接

NETL

中文摘要：在多准则决策支持等多个应用中,top-k dominating查询是一种十分实用的查询,它在潜在的巨大的数据空间中返回k个支配分数最大的元组.现有算法,要么需要为特定的属性组合构建索引,要么需要较大的I/O费用或内存费用,从而无法有效处理海量数据上top-k dominating查询.文中提出一种新的查询算法TDEP,该算法利用以较小代价为每个属性构建的有序列表来有效返回海量数据上的top-k dominating查询结果.文中将TDEP算法的执行明确地分为两个阶段:增长阶段和收缩阶段.在每个阶段,TDEP算法以round-robin方式读取涉及到的有序列表并维护候选元组,直到满足结束条件.文中分析了两个阶段的执行行为,提出一种新的不需要重新读取有序列表的支配分数计算方法.同时,文中还提出有效的早剪切操作,可以有效减少TDEP算法需要维护的候选元组数量.实验结果表明:和现有算法相比,TDEP算法具有较大的性能优势.

作者：

HAN Xi-Xian、韩希先、LI Jian-Zhong、李建中、GAO Hong、高宏

展开 >

作者单位：

Department of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001

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

关键词：

海量数据 Top-k Dominating查询 TDEP算法剪切技术

主办单位：

中国计算机学会

会议名称：

2013中国计算机大会

会议时间：

2013-10-01

会议地点：

长沙

会议母体文献：

2013中国计算机大会论文集

页码：

2132-2145

出版时间：

2013