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

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

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

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

4、間數(shù)據(jù)存儲(chǔ)與檢索結(jié)構(gòu)——HD-Baton樹,將樹形結(jié)構(gòu)應(yīng)用于空間數(shù)據(jù)的存儲(chǔ)與查詢。主要研究工作及成果如下:
　　①基于Baton樹做出結(jié)構(gòu)改進(jìn),設(shè)計(jì)適用于空間數(shù)據(jù)存儲(chǔ)與檢索的HD-Baton樹結(jié)構(gòu)。
　?、卺槍?duì)HD-Baton樹的結(jié)構(gòu),參考Baton樹原有的一維數(shù)據(jù)檢索算法,設(shè)計(jì)適用于空間數(shù)據(jù)精確匹配檢索和范圍檢索的算法。
　?、蹖?duì)于樹形結(jié)構(gòu)可以增加孩子結(jié)點(diǎn)來(lái)加速逼近的特點(diǎn),通過(guò)增加孩子結(jié)點(diǎn)的數(shù)量使查詢時(shí)間復(fù)雜度由O(