云計算環(huán)境下的大規(guī)?？臻g近鄰查詢算法研究.pdf

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

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