一種對等雲平臺上構建希爾伯特r樹索引的方法
2023-06-24 10:46:46 2
一種對等雲平臺上構建希爾伯特r樹索引的方法
【專利摘要】一種對等結構雲平臺上構建希爾伯特R樹索引的方法，在P2P雲平臺中的主節點組織成對等結構的Chord網絡。首先，通過映射方法讀取數據對象，基於其地理位置得到其所處空間的希爾伯特曲線編碼；其次，基於這一編碼對數據對象進行分區，並將其傳給相應的歸約方法；然後，歸約方法對各個分區的數據對象進行希爾伯特R子樹的構建；最後，通過安全散列函數得到希爾伯特R子樹根節點編號的散列值，並將其發布到處於Chord環中的主節點上，構成完整的分布式希爾伯特R樹索引。本方法能並行地建立希爾伯特R樹，減少了建樹的時間；同時，建立的希爾伯特R樹是分布式的，加強了索引的穩定性和查找效率。
【專利說明】—種對等雲平臺上構建希爾伯特R樹索引的方法
【技術領域】
[0001]本發明涉及一種對等雲平臺上構建希爾伯特R樹索引的方法，屬於空間數據索引和對等雲平臺的融合【技術領域】。
【背景技術】
[0002]雲計算是一種商業計算模型將計算任務分布在大量計算機構成的資源池上，使各種應用系統能夠根據需要獲取計算力、存儲空間和信息服務。現在Google公司和開源雲計算平臺Hadoop等都使用Map-Reduce平行計算模型，該模型為海量數據的處理提供了一個通用、高效的技術框架，從而在地理空間數據查詢處理、數據挖掘等領域得到了越來越廣泛的應用。
[0003]P2P (Peer-to-Peer,對等網)計算是指不同系統之間通過直接交換，實現計算機資源和服務共享、進行信息處理的過程。這裡，資源可以是處理器、緩存和磁碟空間等；服務包括信息交換、數據計算等。P2P模式與傳統客戶/伺服器模式的關鍵區別在於Peer (對等體)與Peer在通信過程中，可以完全摒棄伺服器的角色，通過直接通信獲得共享資源或服務。
[0004]面對空間數據挖掘、空間決策支持、空間多維動態可視化分析與模擬等諸多屬於計算密集型和I/o密集型的空間應用，傳統GIS的計算和數據處理能力不能很好地滿足應用需求。隨著網格計算技術在GIS中的應用逐漸成為研究熱點，其分布式並行計算模式與系統架構將有助於提高GIS的整體性能和運行效率。因此，分布式並行計算將成為解決傳統GIS計算能力不足問題的重要方法。海量空間數據的組織與管理技術是各類複雜空間應用的基礎，也是GIS技術的核心問題。其中，空間索引技術是數據組織與管理的重要研究內容。目前，在資料庫管理系統及GIS等科研領域，空間索引技術的研究成果非常豐富，應用較為廣泛。然而，針對海量空間數據的組織、管理、存取、處理與應用的分布式並行空間索引技術研究成果較少。
[0005]ArielCary等提出了在雲平臺下運用MapReduce並行構建子R樹，將子R樹合併，形成的R樹索引是一個集中式的，這個集中式的R樹成為了它的瓶頸。
[0006]AnirbanMondal等提出了再對等網絡下建立R樹索引，其將空間劃分為相等的塊，每個對等節點維護一個等分的塊，由於存儲信息的對等節點不一定是連續的，可能破壞地理空間的連續性。
【發明內容】
[0007]本發明所要解決的技術問題是針對上述【背景技術】的不足，提供了一種在對等雲平臺上對地理空間數據建立分布式R樹索引的方法。
[0008]本發明為實現上述發明目的採用如下技術方案:一種對等結構雲平臺上構建希爾伯特R樹索引的方法，其特徵是:在P2P雲平臺中的主節點(Master)組織成對等結構的Chord網絡，首先，通過映射方法(Map)讀取數據對象，基於其地理位置得到其所處空間的希爾伯特曲線編碼；其次，基於這一編碼對數據對象進行分區，並將其傳給相應的歸約方法(Reduce);然後，歸約方法對各個分區的數據對象進行希爾伯特R子樹的構建；最後，通過安全散列函數(SHA-1)得到希爾伯特R子樹根節點編號的散列值，並將其發布到處於Chord環中的主節點(Master)上,構成完整的分布式希爾伯特R樹索引；包括如下步驟:
[0009]步驟I，假設數據集為D，設0 e D為數據集中的任一數據對象，0.1d為數據對象0的標識符，0.P為數據對象0的地理位置坐標；
[0010]步驟2，用映射方法(Map)將數據集D中的數據對象讀入，映射方法(Map)輸入的關鍵字為0.1d，值為0.P，對於輸入的數據對象O，根據其地理位置坐標0.P，將該對象映射到公階的希爾伯特空間曲線填充上(希爾伯特曲線的階數由數據集的大小決定，數據集大
小ID I,則Z1 = |_log|l)|」)，並產生相應希爾伯特編碼0.he ；
[0011]步驟3，基於希爾伯特編碼0.hc，調用分區方法f將數據對象0映射到相應的分
區，分區方法f的輸入為數據對象的希爾伯特編碼，輸出為分區號，定義如下:
[0012]
J (0.hc) = \_0.hc /21' /:」IS 0.hc < 21'
[0013]則映射方法(Map)輸出的關鍵字為分區號f (0.he)，值為O，根據分區方法f，數據對象將被映射到^個分區中，分區數目由處於Chord環中的主節點(Master)的數目決定，
設主節點(Master)是數目為N,則/2 = [log A7J;
[0014]步驟4，用2/2個歸約方法(Reduce)接收映射方法(Map)的輸出作為輸入，其關鍵字為分區號f (0.hc)，值為O，各個歸約方法(Reduce)對於輸入的某一分區的數據對象分別進行希爾伯特R子樹的構建，並將該分區號作為構建好的希爾伯特R子樹根節點的編號；
[0015]步驟5，通過安全散列算法，計算出希爾伯特R子樹根節點編號的散列值，並將該散列值對應的希爾伯特R子樹的根節點發布到Chord環中的相應的主節點(Master)上,構成完整的分布式希爾伯特R樹索引；
[0016]至此，在對等雲平臺下建立分布式希爾伯特R樹索引已經完成，在對等雲平臺中的單獨一個主節點(Master)起到一個局部索引的作用，基於Chord的所有的主節點(Master)起到一個全局索引的作用。
[0017]本發明具有以下優點及有益效果:
[0018]I)本發明方法解決了現有技術的缺點，形成了分布式的R樹索引，較好的解決了集中式R樹的瓶頸，利用希爾伯特曲線進行分區，較好的解決了地理空間的連續性的問題。
[0019]2)在為空間數據並行建立希爾伯特R樹，其相對於傳統的建立希爾伯特R樹的索引方法其建立希爾伯特R樹索引的速度有顯著的提升。
[0020]3)本發明將緩存根節點的Mater節點組織成了 Chord環,相對於單個Master節點，不但減少了 Master節點的負擔,而且提高了 Master節點的並行處理能力，其維護開銷要低於傳統的R樹；能有效的加速查詢，其維護開銷要低於傳統的R樹，減少了 Master節點失效所造成的損失。且建立的是希爾伯特R樹的分布式索引，有效的解決了集中式索引的瓶頸，如:並行查詢的能力，處理查詢的最大的負載等。【專利附圖】
【附圖說明】
[0021]圖1是對等結構雲平臺上構建希爾伯特R樹索引的總流程圖；
[0022]圖2是對等結構雲平臺上已構建完成的希爾伯特R樹索引結構示意圖。
【具體實施方式】
[0023]下面結合附圖對發明的技術方案進行詳細說明:
[0024]在P2P雲平臺中的主節點(Master)組織成對等結構的Chord網絡。在對等結構雲平臺上構建希爾伯特R樹索引的總流程圖，如圖1所示:
[0025]步驟I，假設數據集為D，設O e D為數據集中的任一數據對象，0.1d為數據對象0的標識符，0.P為數據對象0的地理位置坐標。
[0026]步驟2，用映射方法(Map)將數據集D中的數據對象讀入。映射方法(Map)輸入的關鍵字為0.1d，值為0.P。對於輸入的數據對象O，根據其地理位置坐標0.P，將該對象映射到公階的希爾伯特空間曲線填充上(希爾伯特曲線的階數由數據集的大小決定，本文中數
據集大小ID I，則I1 = Llog|D|J),並產生相應希爾伯特編碼0.he。
[0027]步驟3，基於希爾伯特編碼0.he,調用分區方法f將數據對象0映射到相應的分
區。分區方法f的輸入為數據對象的希爾伯特編碼，輸出為分區號，定義如下:
[0028]
f {0.hc、= \_0.hc /2,',:」I < 0.hc < 21'
[0029]則映射方法(Map)輸出的關鍵字為分區號f(0.he)，值為O。根據分區方法f，數據對象將被映射到2/2個分區中，分區數目由處於Chord環中的主節點的數目決定，設主節點
是數目為N,則/2 - LloS
[0030]步驟4，用^個歸約方法(Reduce)接收映射方法的輸出作為輸入，其關鍵字為分區號f (0.hc)，值為O，各個歸約方法(Reduce)對於輸入的某一分區的數據對象分別進行希爾伯特R子樹的構建，並將該分區號作為構建好的希爾伯特R子樹根節點的編號。
[0031]步驟5，通過安全散列算法，計算出希爾伯特R子樹根節點編號的散列值，並將該散列值對應的希爾伯特R子樹的根節點發布到Chord環中的相應的主節點上，構成完整的分布式希爾伯特R樹索引，如圖2所示，P2P雲平臺中的主節點(Master)構成一個Chord環，根據安全散列算法，希爾伯特R子樹能均勻地分布到Chord網絡中，從而實現負載均衡的目的。
[0032]綜上所述，首先，通過映射方法(Map)讀取數據對象，基於其地理位置得到其所處空間的希爾伯特曲線編碼；其次，基於這一編碼對數據對象進行分區，並將其傳給相應的歸約方法(Reduce);然後，歸約方法對各個分區的數據對象進行希爾伯特R子樹的構建；最後，通過安全散列函數得到希爾伯特R子樹根節點編號的散列值，並將其發布到處於Chord環中的主節點(Master)上，構成完整的分布式希爾伯特R樹索引。這種方法能夠有效的建立希爾伯特R樹索引，加速希爾伯特R樹的查詢，並且能減少Master節點的負擔和負載均衡，適用於在對等雲平臺上對空間數據建立希爾伯特R樹索引。
【權利要求】
1.一種對等結構雲平臺上構建希爾伯特R樹索引的方法，其特徵是:在P2P雲平臺中的主節點組織成對等結構的Chord網絡，首先，通過映射方法讀取數據對象，基於其地理位置得到其所處空間的希爾伯特曲線編碼；其次，基於這一編碼對數據對象進行分區，並將其傳給相應的歸約方法；然後，歸約方法對各個分區的數據對象進行希爾伯特R子樹的構建；最後，通過安全散列函數得到希爾伯特R子樹根節點編號的散列值，並將其發布到處於Chord環中的主節點上,構成完整的分布式希爾伯特R樹索引；包括如下步驟: 步驟I，假設數據集為D，設0 e D為數據集中的任一數據對象，0.1d為數據對象0的標識符，0.p為數據對象0的地理位置坐標； 步驟2，用映射方法將數據集D中的數據對象讀入，映射方法輸入的關鍵字為0.1d,值為0.P，對於輸入的數據對象O，根據其地理位置坐標0.P，將該對象映射到分階的希爾伯特空間曲線填充上，希爾伯特曲線的階數由數據集的大小決定，數據集大小|D|，則Ix =l_l0g|D|_|，並產生相應希爾伯特編碼0.he ； 步驟3，基於希爾伯特編碼0.he,調用分區方法f將數據對象0映射到相應的分區，分區方法f的輸入為數據對象的希爾伯特編碼，輸出為分區號，定義如下:
【文檔編號】H04L29/08GK103617162SQ201310478326
【公開日】2014年3月5日 申請日期:2013年10月14日 優先權日:2013年10月14日
【發明者】吳家皋, 劉傑, 鄒志強 申請人:南京郵電大學