不确定数据Top-k查询算法  

Top-k query processing on probabilistic data

作　　者：周帆[1] 李树全[1] 肖春静[1] 吴跃[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,成都611731

出　　处：《电子测量与仪器学报》2010年第7期650-657,共8页Journal of Electronic Measurement and Instrumentation

基　　金：电子科技大学博士点基金(编号:20070614008)资助项目;国家"863"计划(编号:2007AA01Z443)资助项目

摘　　要：不确定数据普遍存在于大量应用之中,如移动计算、RFID技术和传感器网络等。针对不确定数据的各种查询算法是数据库领域近年来的热点研究课题。其中,基于不确定数据的Top-k查询和排序查询提出了很多有价值的查询语义和查询算法。详细分析这一最新领域提出的各种查询算法、数据模型、算法复杂度和不同算法所适应的应用场景,并用实验从多个方面比较不同查询算法执行效率、查询语义以及结果集的关联程度。Uncertain data arises from a few important applications,such as mobile computing,RFID technology and wireless sensor networks.Recently,there have been several important query semantics and algorithms proposed regarding top-k querying processing on uncertain data.In this paper,the probabilistic top-k query and rank query on uncertain data are researched,which attracts a lot of researchers in both database and dada mining community.Various algorithms based on application scenarios are introduced and explained.This work also compares and analyzes the complexity of querying algorithms based on both theoretical and experimental study.Finally,Kendall＇s tau distance is presented for analyzing the similarity/dissimilarity among answer set of different querying semantics.

关 键 词：概率数据库 不确定Top-k查询 排序查询 查询算法 数据处理 

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