不确定性键值对数据模型及改进Top-k查询算法  

An Uncertain Key-value Data Model and Improved Top-k Query Algorithm

作　　者：易俗[1] 吴亚坤[1] 付天宇[2] 张一川[2] 

机构地区：[1]辽宁大学计算中心,沈阳110031 [2]东北大学软件学院,沈阳110819

出　　处：《小型微型计算机系统》2015年第12期2656-2661,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61202088)资助;第54批中国博士后科学基金项目(2013M540232)资助;教育部项目博士点基金项目(20130042120006)资助;教育部项目基本科研业务费项目重大科技创新项目(N120817002)资助

摘　　要：现有基于可能世界建模的Top-k算法难以适应大数据量和键值对(Key-Value)数据模型下的不确定性Top-k查询.研究首先建立了不确定性Key-Value数据模型;随后在已有U-TopK查询语义的基础上,提出了优化的EU-TopK(Early Terminated Uncertain Top-k Query)算法,该算法优先建立以最可能的Top-k元组为树根的可能世界树形结构,并利用两种优化策略来优化算法,降低了元组访问深度,使得该算法在时间复杂度上较原算法有所改进.此外采用MapReduce实现EU-TopK算法,使EU-TopK能够适应大数据分析.最后,通过实验验证EU-TopK算法功能性,并对其查询时间、扫描深度进行评价.The existing researches, most of which are based on possible world model, are unsuitable to big data and key-value data model. This research, first designs a new key-value data model for uncertain data; secondly proposes EU-TopK （ Early Terminated Un- certain Top-k Query ） algorithm which optimizes the original U-TopK algorithm by searching for suitable termination conditions and u- sing efficient data structure. Different from U-TopK algorithm, the EU-TopK algorithm uses the most favorable Top-k records with a relatively greater possibility as the first choice as the root of a possible world tree. Furthermore, the research designs MapReduce-based EU-TopK which can be well adopt in the Big Data analyze. The functionality, query time and scan depth of EU-TopK is proved by ex- periments.

关 键 词：不确定性数据 TOP-K查询 MAPREDUCE 大数据 键值对数据 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]