HD-Baton樹——基于Baton樹的空間數(shù)據(jù)檢索結(jié)構(gòu).pdf

1、隨著科技的發(fā)展,數(shù)據(jù)量呈現(xiàn)出了爆炸式的增長方式,數(shù)據(jù)類型也由一維結(jié)構(gòu)化數(shù)據(jù)發(fā)展為高維非結(jié)構(gòu)化數(shù)據(jù),這給傳統(tǒng)的數(shù)據(jù)存儲與檢索方式帶來了巨大的挑戰(zhàn)。其中,空間數(shù)據(jù)在越來越多的領(lǐng)域得到了廣泛的應用,比如城市規(guī)劃與管理、氣象監(jiān)控、空間遙感信息圖像處理等。但空間數(shù)據(jù)有其自身的復雜性,且空間數(shù)據(jù)的應用領(lǐng)域數(shù)據(jù)量通常都非常大,使用傳統(tǒng)的C/S模式來存儲和檢索需要付出高昂的代價。而且空間數(shù)據(jù)這些應用領(lǐng)域通常需要執(zhí)行大量的并發(fā)操作,但C/S模式對并發(fā)操作

2、的支持有限。而P2P拓撲動態(tài)易于擴展,基于分布式支持高并發(fā)操作,面向應用,軟件易于開發(fā),非常適用于空間數(shù)據(jù)的應用領(lǐng)域。P2P作為一種成熟的基于分布式計算的點對點通信技術(shù),已經(jīng)證明了它能替代傳統(tǒng)的C/S模式。在P2P模式下對復雜而龐大的空間數(shù)據(jù)進行存儲和檢索,是一種高效而代價低廉的方法。另外,將P2P模式應用于數(shù)據(jù)的存儲與檢索早就得到了證明。
　　傳統(tǒng)的P2P空間數(shù)據(jù)存儲與檢索方法——降維后存儲和空間填充技術(shù)(或稱空間分割技術(shù)),均

3、有無法逾越的缺陷,降維破壞了原數(shù)據(jù)的空間特性,無法進行范圍查詢;空間填充技術(shù)雖然保持了數(shù)據(jù)的空間特性,但引入了空間分割算法,操作復雜且可擴展性差。理想的P2P空間數(shù)據(jù)存儲與檢索方法應該是能保留原數(shù)據(jù)的空間信息、支持范圍查詢、操作簡單、具有自組織和容錯性、可擴展性等特性,而樹形結(jié)構(gòu)有很多特征與上述要求吻合,比如自組織、可擴展性強、易于設計范圍查詢算法等。因此本文在充分參考了現(xiàn)有的各種 P2P路由算法的基礎(chǔ)上,提出了一種基于Baton樹的空

4、間數(shù)據(jù)存儲與檢索結(jié)構(gòu)——HD-Baton樹,將樹形結(jié)構(gòu)應用于空間數(shù)據(jù)的存儲與查詢。主要研究工作及成果如下:
　?、倩贐aton樹做出結(jié)構(gòu)改進,設計適用于空間數(shù)據(jù)存儲與檢索的HD-Baton樹結(jié)構(gòu)。
　?、卺槍D-Baton樹的結(jié)構(gòu),參考Baton樹原有的一維數(shù)據(jù)檢索算法,設計適用于空間數(shù)據(jù)精確匹配檢索和范圍檢索的算法。
　?、蹖τ跇湫谓Y(jié)構(gòu)可以增加孩子結(jié)點來加速逼近的特點,通過增加孩子結(jié)點的數(shù)量使查詢時間復雜度由O(