海量數(shù)據(jù)的快速查詢算法研究.pdf

1、隨著博客、維基百科、共享空間、推特等新型應(yīng)用的興起，互聯(lián)網(wǎng)已經(jīng)進(jìn)入了一個信息爆炸的時代，需要處理的數(shù)據(jù)也越來越多，對于數(shù)據(jù)的處理要求也越來越高。面對不斷增長的數(shù)據(jù)，海量數(shù)據(jù)的快速查詢算法成為了一個研究熱點(diǎn)。
　　本文以提高海量數(shù)據(jù)的查詢效率為目標(biāo)，對已有的海量數(shù)據(jù)的查詢技術(shù)進(jìn)行了研究，重點(diǎn)研究了Top-k查詢算法。Top-k查詢根據(jù)用戶的要求對相應(yīng)的屬性計(jì)算分值，并用聚合函數(shù)聚集多個屬性的分值作為整個元組的得分，返回得分最高的k個

2、對象。Top-k查詢在海量數(shù)據(jù)的環(huán)境中有很好的查詢效率。
　　論文首先介紹了索引、SQL語句優(yōu)化、數(shù)據(jù)預(yù)取、近似匹配和分布式查詢等已有的海量數(shù)據(jù)查詢技術(shù)，并總結(jié)了各種技術(shù)的應(yīng)用范圍。接著對經(jīng)典的Top-k查詢算法進(jìn)行了分析，基于對TA(Threshold Algorithm)算法和NRA(No Random Access)算法的研究以及近似匹配查詢思想，提出了一種新的基于抽取的Top-k算法(Top-k Algorithm Bas

3、ed on Extraction，TABE)，該算法首先抽取出最優(yōu)的元組，再對這些元組運(yùn)行查詢算法。為了測試TABE算法的性能，設(shè)計(jì)了測試實(shí)驗(yàn)，實(shí)驗(yàn)中將之與經(jīng)典的NRA算法進(jìn)行了比較。測試結(jié)果表明TABE算法不僅時間復(fù)雜度低，而且有較高的精確度，能滿足常規(guī)的查詢要求。論文還順應(yīng)海量數(shù)據(jù)處理的并行化趨勢，對TABE算法在Hadoop環(huán)境下進(jìn)行了實(shí)現(xiàn)，并做了性能測試實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，借助云計(jì)算可以進(jìn)一步提高TABE算法的查詢效率。