学位论文 > 优秀研究生学位论文题录展示

海量数据的快速查询算法研究

作　者: 曾雪
导　师: 李玲娟
学　校: 南京邮电大学
专　业: 计算机软件与理论
关键词: 海量数据 Top-k Hadoop Hive
分类号: TP311.13
类　型: 硕士论文
年　份: 2012年
下　载: 391次
引　用: 1次
阅　读: 论文下载
 

内容摘要


随着博客、维基百科、共享空间、推特等新型应用的兴起,互联网已经进入了一个信息爆炸的时代,需要处理的数据也越来越多,对于数据的处理要求也越来越高。面对不断增长的数据,海量数据的快速查询算法成为了一个研究热点。本文以提高海量数据的查询效率为目标,对已有的海量数据的查询技术进行了研究,重点研究了Top-k查询算法。Top-k查询根据用户的要求对相应的属性计算分值,并用聚合函数聚集多个属性的分值作为整个元组的得分,返回得分最高的k个对象。Top-k查询在海量数据的环境中有很好的查询效率。论文首先介绍了索引、SQL语句优化、数据预取、近似匹配和分布式查询等已有的海量数据查询技术,并总结了各种技术的应用范围。接着对经典的Top-k查询算法进行了分析,基于对TA(Threshold Algorithm)算法和NRA(No Random Access)算法的研究以及近似匹配查询思想,提出了一种新的基于抽取的Top-k算法(Top-k Algorithm Based on Extraction,TABE),该算法首先抽取出最优的元组,再对这些元组运行查询算法。为了测试TABE算法的性能,设计了测试实验,实验中将之与经典的NRA算法进行了比较。测试结果表明TABE算法不仅时间复杂度低,而且有较高的精确度,能满足常规的查询要求。论文还顺应海量数据处理的并行化趋势,对TABE算法在Hadoop环境下进行了实现,并做了性能测试实验,实验结果表明,借助云计算可以进一步提高TABE算法的查询效率。论文对海量数据的快速查询做了有益的研究。

全文目录


摘要  4-5
ABSTRACT  5-8
第一章 引言  8-10
  1.1 课题的背景与意义  8-9
  1.2 论文的主要工作  9
  1.3 论文的组织  9-10
第二章 海量数据快速查询技术概述  10-19
  2.1 数据划分  10-11
  2.2 索引  11-13
  2.3 SQL语句优化  13-15
  2.4 数据预取技术  15
  2.5 近似匹配查询  15-16
  2.6 哈希表查询  16
  2.7 分布式查询优化  16-18
    2.7.1 基于语义信息的分布式查询处理  17
    2.7.2 基于收益代价比因子的贪心算法模型策略  17
    2.7.3 带碎片的分布式查询处理  17-18
    2.7.4 其他分布式查询优化算法  18
  2.8 海量数据快速查询类型  18
  2.9 本章小结  18-19
第三章 Top-k查询技术综述和分析  19-34
  3.1 Top-k查询有关概念  19
  3.2 经典的Top-k算法——TA算法  19-21
    3.2.1 TA算法流程  20-21
    3.2.2 TA算法的时间复杂度  21
  3.3 无需系统随机读的Top-k算法  21-33
    3.3.1 NRA算法  22-24
    3.3.2 Stream-Combine算法  24-27
    3.3.3 LAttice-based Rank Aggregation (LARA)算法  27-31
    3.3.4 TKEP算法  31-33
  3.4 利用索引和视图处理Top-k查询的方法  33
  3.5 本章小结  33-34
第四章 基于抽取的快速Top-k查询算法研究  34-56
  4.1 Top-k查询算法对数据的要求  34-35
  4.2 TABE算法  35-38
    4.2.1 算法产生的基础  35-36
    4.2.2 算法描述  36-38
  4.3 单机环境下的性能测试实验与结果分析  38-44
    4.3.1 实验环境  38
    4.3.2 查询精确度测试  38-39
    4.3.3 TABE算法与NRA算法执行时间比较  39-44
  4.4 基于云计算的性能测试实验与结果分析  44-54
    4.4.1 Hadoop简介与环境搭建  44-49
    4.4.2 Hive概述与安装  49-50
    4.4.3 在Hadoop环境中实现TABE算法  50-51
    4.4.4 实验结果分析  51-54
  4.5 本章小结  54-56
第五章 总结与展望  56-58
  5.1 论文工作总结  56-57
  5.2 未来工作展望  57-58
图表清单  58-60
致谢  60-61
参考文献  61-65
攻读硕士学位期间的学术论文和科研情况  65
  1. 已发表的学术论文  65
  2. 参加的科研项目  65

相似论文

  1. 海量数据压缩、操作和处理方法的研究,TP311.13
  2. 基于BAP的数据压缩、操作与查询处理系统的实现,TP311.13
  3. 基于Map/Reduce框架的分布式日志分析系统的研究及应用,TP311.52
  4. 一种面向海量数据综合评价的树状数据结构的设计与研究,TP311.12
  5. 支持Top-k查询的银行记账查询系统的设计与实现,TP311.52
  6. 地理空间数据组织及调度的研究与实现,P208
  7. 基于Hadoop的在线购物原型系统的设计与实现,TP311.52
  8. 基于Hadoop的移动学习系统设计与实现,G434
  9. 基于P2P技术的网络虚拟地理环境原型系统设计与实现,TP393.09
  10. 海量数据下列式数据库研究,TP311.13
  11. 基于HADOOP架构的社保项目网络日志分析系统的研究,TP311.52
  12. 基于MapReduce模型的eMTM三维人体模型生成引擎,TP391.41
  13. 基于云计算的软件资源服务平台研究,TP311.52
  14. 高速网络环境下的入侵检测系统的研究,TP393.08
  15. 云计算平台上的增量学习研究,TP311.13
  16. 云队列：一个基于Hadoop的大规模消息基础平台,TP311.52
  17. 基于Hadoop的文本分类研究,TP391.1
  18. 基于Hadoop的分布式服务注册中心研究和实现,TP393.09
  19. 基于多核CPU的任务级数据处理研究及其在集群平台下的性能测试,TP274
  20. 基于Hadoop的视频转码系统设计与实现,TN919.81

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机软件 > 程序设计、软件工程 > 程序设计 > 数据库理论与系统
© 2012 www.xueweilunwen.com