云計(jì)算環(huán)境下的大規(guī)模空間近鄰查詢(xún)算法研究.pdf

1、隨著移動(dòng)互聯(lián)網(wǎng)與物聯(lián)網(wǎng)等技術(shù)的迅猛發(fā)展，出現(xiàn)了大量的帶有位置信息的數(shù)據(jù)，這給大規(guī)?？臻g數(shù)據(jù)的索引與查詢(xún)帶來(lái)了一系列的需求與挑戰(zhàn)。近鄰查詢(xún)作為典型的算法已廣泛應(yīng)用于數(shù)據(jù)挖掘、支持決策系統(tǒng)，商業(yè)定址等領(lǐng)域?，F(xiàn)有的索引技術(shù)與近鄰查詢(xún)算法，因?yàn)閮?nèi)在的順序性執(zhí)行與基于內(nèi)存設(shè)計(jì)的算法所限，而無(wú)法直接應(yīng)用于大規(guī)?？臻g數(shù)據(jù)處理中。本文深入研究如何在分布式環(huán)境下進(jìn)行可擴(kuò)展的空間索引與查詢(xún)算法設(shè)計(jì)。
　　首先，本文提出了新的分布式空間數(shù)據(jù)索引方法:倒

2、排空間網(wǎng)格索引。該索引是將分布式倒排索引與空間網(wǎng)格劃分方法相結(jié)合。松耦合與無(wú)共享的結(jié)構(gòu)使得倒排網(wǎng)格索引具備良好的可擴(kuò)展性。
　　其次，在云計(jì)算環(huán)境中基于我們的索引結(jié)構(gòu)，設(shè)計(jì)了云計(jì)算環(huán)境下的并行輪圈遍歷與分布式kNN查詢(xún)算法。證明了kNN查詢(xún)算法的收斂性，并將計(jì)算性能與可擴(kuò)展性與同類(lèi)算法在分布式環(huán)境下進(jìn)行了實(shí)驗(yàn)比較。
　　最后，實(shí)現(xiàn)了基于倒排空間網(wǎng)格索引的Basic-SRNN基準(zhǔn)算法和Lazy-SRNN、Eager-SRNN兩