MapReduce框架下的不确定数据Top-k查询计算

摘要：

　　Top-k查询是不确定性数据管理中普遍采用的一种技术。基于参数化排名函数的Top-k查询语义是近年来提出的各种查询语义的统一。文中针对海量不确定数据，提出一种基于MapReduce框架的Top-k计算的有效方法。通过分析基于参数化排名函数的不确定数据Top-k查询语义，设计一种获得未计算元组的排名函数值上界的算法，避免计算所有元组的排名函数值，解决Top-k计算中的剪枝问题。在MapReduce计算模型中提出两种不同的策略来实现该算法。文中针对单机环境和Hadoop分布式计算平台进行两组不同的对比实验。实验表明在处理海量不确定数据时，该算法在计算时间上有较高的性能提升。

关键词：不确定数据、Top-k查询、MapReduce

分类号：TP311.13(计算技术、计算机技术)

资助基金：国家自然科学基金项目60973047;浙江省自然科学基金项目Y1091189;浙江省公益性技术应用研究计划项目2011C21076;宁波市自然科学基金项目2009A610072;宁波大学胡岚博士基金项目2011277

在线出版日期：2013-08-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：695-704