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

作     者：曾雪 

作者单位：南京邮电大学 

学位级别：硕士

导师姓名：李玲娟

授予年度：2012年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主      题：海量数据 Top-k Hadoop Hive 

摘      要：随着博客、维基百科、共享空间、推特等新型应用的兴起,互联网已经进入了一个信息爆炸的时代,需要处理的数据也越来越多,对于数据的处理要求也越来越高。面对不断增长的数据,海量数据的快速查询算法成为了一个研究热点。 本文以提高海量数据的查询效率为目标,对已有的海量数据的查询技术进行了研究,重点研究了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算法的查询效率。 论文对海量数据的快速查询做了有益的研究。