mapreduce框架下的不确定数据top鄄k查询计算-模式识别与人工.pdf

第26 卷摇 第7 期摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 模式识别与人工智能摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 Vol.26摇 No.7 摇 2013年7月摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 PR AI摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 Jul摇 2013 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 MapReduce框架下的不确定数据Top鄄k查询计算* 卢摇 鑫摇 摇 陈华辉摇 摇 董一鸿摇 摇 钱江波 (宁波大学 信息科学与工程学院摇 宁波315211) 摘摇 要摇 Top鄄k查询是不确定性数据管理中普遍采用的一种技术.基于参数化排名函数的Top鄄k查询语义是近年 来提出的各种查询语义的统一.文中针对海量不确定数据,提出一种基于MapReduce框架的Top鄄k计算的有效方 法.通过分析基于参数化排名函数的不确定数据Top鄄k查询语义,设计一种获得未计算元组的排名函数值上界的算 法,避免计算所有元组的排名函数值,解决Top鄄k计算中的剪枝问题.在MapReduce计算模型中提出两种不同的策 略来实现该算法.文中针对单机环境和Hadoop分布式计算平台进行两组不同的对比实验.实验表明在处理海量不 确定数据时,该算法在计算时间上有较高的性能提升. 关键词摇 不确定数据,Top鄄k查询,MapReduce 中图法分类号摇 TP311.13 Top鄄k Query Calculations onUncertainDataset under MapReduce Framework LU Xin,CHEN Hua鄄Hui,DONG Yi鄄Hong,QIANJiang鄄Bo (School of Information Science and Engineering,Ningbo University,Ningbo 315211) ABSTRACT Top鄄k query is commonly used in the management and application on uncertain data. And the Top鄄k query semantics base on parameterized rankingfunctions (PRF) isthe unified approach of variousquery semanticsproposed in recent years. Aiming at the massive uncertain dataset,an effective methodfor the Top鄄k query based on MapReduce is proposed. Through the analysis on the Top鄄k query semantics of parameterized ranking functions,an algorithm is presented to get the upper bound of an un鄄retrieved tuple. In thisway,the pruning strategy is used to get the Top鄄k tuples without retrieving every tuple in the dataset. Furthermore, two different strategies are presented to implement the proposed algorithm under the MapReduce computing model in Hadoop. Finally,two groups of experiments are performed