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

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

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

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