大數(shù)據(jù)下空間數(shù)據(jù)索引和kNN查詢技術的研究.pdf

1、隨著移動互聯(lián)網(wǎng)和物聯(lián)網(wǎng)技術的廣泛應用，空間位置信息數(shù)據(jù)量迅速增長。而大規(guī)模的數(shù)據(jù)使得傳統(tǒng)的空間數(shù)據(jù)索引和查詢方法面臨著新的挑戰(zhàn)。例如，由于數(shù)據(jù)量的增長使得傳統(tǒng)的內(nèi)存式索引結構的磁盤訪問次數(shù)大大增加。因此，有效的空間數(shù)據(jù)查詢問題需要新的可擴展的分布式索引結構。而目前常用的少數(shù)幾種分布式索引為基于R-tree的分布式索引和基于Voronoi圖的分布式索引，這些索引結構仍存在一些不足。首先，由于R-tree的層次型結構不易分散化，使得該索引結

2、構的可擴展性不高;基于Voronoi圖的索引結構只適合處理靜態(tài)的數(shù)據(jù)集和查詢點，當有數(shù)據(jù)點動態(tài)加入時索引結構需要重建。由于缺乏有效的分布式索引結構，大數(shù)據(jù)下的空間kNN查詢處理也變得非常困難。
　　在這種背景和需求之下，Google提出了一種高效的分布式計算模型MapReduce，并因簡單、易擴展、高容錯等特性使其迅速在業(yè)界內(nèi)得到廣泛的應用。基于MapReduce模型，本文將網(wǎng)格空間劃分和倒排索引相結合，首次提出了一種新的分布式倒

3、排網(wǎng)格索引結構。該索引結構扁平化、松耦合的特點，使其更加適合索引大規(guī)?？臻g數(shù)據(jù)和進行分布式化處理。同時，我們在MapReduce框架下實現(xiàn)了分布式倒排網(wǎng)格索引結構并詳細描述了Map和Reduce的過程?；谠撍饕Y構，本文對傳統(tǒng)的kNN查詢算法進行了改進，提出了一種新的可并行的查詢算法——ParallelCircleTrip算法。另外，我們做了大量的實驗驗證倒排網(wǎng)格索引和改進的kNN查詢算法的高效性和可擴展性。實驗結果表明分布式倒排網(wǎng)格