基於Hilbert曲線與R-tree的HBase多維查詢系統的構建及其查詢方法
2023-05-03 17:04:16 1
基於Hilbert曲線與R-tree的HBase多維查詢系統的構建及其查詢方法
【專利摘要】本發明公開了一種基於Hilbert曲線與R-tree的HBase多維查詢系統的構建及其查詢方法，本發明一方面利用Hilbert曲線對多維數據從多維降到一維，另一方面針對HBase上的多維數據建立R樹。映射的一維Hilbert曲線的標誌符Hilbert ID能夠將信息與原始的高維數據ID建立對應關係。通過R樹，高維數據的查詢可以高效地映射為一維的Hilbert ID集合。從而實現在HBase上多維數據的快捷查詢。
【專利說明】基於H i I bert曲線與R-tree的HBase多維查詢系統的構建 及其查詢方法
【技術領域】
[0001] 本發明涉及一種基於Hilbert曲線與R-tree的HBase多維查詢系統的構建及其 查詢方法。
【背景技術】
[0002] 近年來，各種管理數據的技術在不斷創新，其中Hadoop開源產品系列在商業實踐 中取得了廣泛認可，幾近成為事實上的大數據管理行業標準平臺。Hadoop雲計算平臺的一 個主要特點是可以提供可擴展的計算能力和存儲能力，實現交互式的數據查詢也是用戶所 關心的，是雲計算成功的關鍵因素。HBase作為一種NoSQL存儲系統，專門設計用來快速隨 機讀寫大規模數據。作為Apache Hadoop項目的子項目，一個分布式的、面向列的開源數據 庫，HBase不同於一般的關係資料庫，它是一個適合於非結構化數據存儲的資料庫，能夠很 好地解決在數據規模劇增時導致的系統擴展性和存儲性能問題，而這些都是傳統關係型數 據庫無法很好應付的。同時，Jffiase不受限於Hadoop MapReduce編程框架的高延遲數據處 理機制，使得HBase可以滿足大規模數據實時處理應用的需求。然而，HBase只有對一維數 據的索引，沒有多維數據索引。在多維數據查詢時只能全表掃描，並使用Filter進行過濾， 查詢效率低下。易用性和實時性差，難以滿足大部分應用需求。
[0003] 隨著各種資料庫的興起，空間資料庫索引的研究引起了人們越來越多的興趣和關 注，其中1984年Guttman提出的R樹是目前最流行的動態空間索引結構，廣泛應用於原型 研究和商用空間資料庫系統。R樹是一種層次數據結構，是B樹在K維空間上的自然擴展。 近年來，很多學者致力於R樹的研究，在R樹的基礎上衍生出許多變種，比較典型的有R+ 樹，壓縮R樹等。基於R樹索引結構需要解決的主要問題仍然是減少區域的重疊，提高搜索 效率。
[0004] 因此針對HBase的數據建立R樹索引，可改進HBase的易用性，提升查詢性能和效 率，節省成本，能極大促進HBase的發展，對大規模數據的存儲，分析和管理，以及對社會信 息化的發展，都具有現實應用價值和實際意義。
【發明內容】
[0005] 為解決上述問題，本發明提供了一種基於Hilbert曲線與R-tree的HBase多維查 詢系統的構建及其查詢方法。
[0006] 為實現上述目的，本發明採取的技術方案為：
[0007] -種基於Hilbert曲線與R-tree的HBase多維查詢系統的構建方法，包括如下步 驟：
[0008] S1、初始化Hilbert編碼產生器。根據數據維數N及Hilbert階數Level,初始化 Hilbert編碼產生器；
[0009] S2、根據數據維數N，初始化R樹；
[0010] S3、根據用戶指定的表名初始化HBase表；
[0011] S4 :根據多維對象各維屬性（ai，a2,……，aN)的值，確定所在網格的網格坐標（ Xl， x2,……，xN)，待管理多維範圍為（[0,800]，[0,400])，每個網格單元的大小為200*100時， 則多維對象O1 (250, 260)產生的網格坐標為（1，2)。
[0012] S5、根據網格坐標（X1, X2, ......，xN)，確定Hilbert編碼Hilbert ID ;如多對象O1 產生的Hilbert ID為7。
[0013] S6、根據網格坐標（X1, x2，......，xN)在R樹中查詢，若存在數據則不需要插入；否 則將網格坐標（X1, X2, ......，Xn)作為範圍，Hilbert ID作為數據插入到R樹中；如多維對 象〇1插入到R樹的範圍為（1，2)，數據為7。
[0014] S7、對多維對象的各維屬性值進行編碼，得到字節數組ByteArray ;如對象O1編碼 後的ByteArray為一個24位元組的數組，各字節的16進位分別為00 00 00 00 00 00 00 02 40 6f 40 00 00 00 00 00 40 70 40 00 00 00 00 00。
[0015] S8、將多維對象插入到HBase中，其中Hilbert ID作為RowKey，ID作為列名， ByteArray作為Value ;如多維對象O1將插入到HBase中的第7行，第1列中，Value為24 字節數組 00 00 00 00 00 00 00 02 40 6f 40 00 00 00 00 00 40 70 40 00 00 00 00 00〇
[0016] S9、插入其它多維數據對象重複S4?S8 ;
[0017] S10、結束。
[0018] 作為優選，所述步驟S7中的編碼方式如下：字節數組前8個字節對應多維對象屬 性個數的整型值。之後每8個字節表示該多維對象的一個維度屬性對應的雙精度浮點型 值。
[0019] 上述的一種基於Hilbert曲線與R-tree的HBase多維查詢系統的查詢方法，包括 如下步驟：
[0020] S21、根據查詢範圍確定查詢所在網格坐標範圍；如查詢Ql([110,310]，[110， 280])，得到的網格坐標範圍為（[0，1]，[1，2])。
[0021] S22、根據網格範圍在R樹中查詢，得到在查詢範圍內的Hilbert ID集合；
[0022] S23、對於每一個Hilbert ID，在HBase中查詢，得到字節數組；如Hilbert ID = 7 時，得到第 1 列的字節數組00 00 00 00 00 00 00 02 40 6f 40 00 00 00 00 00 40 70 40 00 00 00 00 00。
[0023] S24、對步驟3結果進行解碼，得到多維對象；如對字節數組00 00 00 00 00 00 00 02 40 6f 40 00 00 00 00 00 40 70 40 00 00 00 00 00 進行解碼，得到多維對象維 數為2,其屬性值為（250, 260)
[0024] S25、對於步驟4查詢到的多維對象，根據查詢範圍精確進行精確匹配，若多維對 象在查詢範圍內，則將其加入結果集中；如果該對象不在查詢範圍中，則將其淘汰；
[0025] S26、結束，結果集中數據即為查詢結果。
[0026] 作為優選，解碼方法如下；讀取前8個字節內容，得到多維對象屬性數。接著逐一 對之後的每8個字節解碼為雙精度浮點型數據，並賦給多維對象對應屬性上。
[0027] 本發明一方面利用Hilbert曲線對多維數據從多維降到一維，另一方面針對 HBase上的多維數據建立R樹。映射的一維Hilbert曲線的標誌符Hilbert ID能夠將信息 與原始的高維數據ID建立對應關係。通過R樹，高維數據的查詢可以高效地映射為一維的 Hilbert ID集合。從而實現在HBase上多維數據的快捷查詢。
【專利附圖】
【附圖說明】
[0028] 圖1本發明實施例1中的Hi Ibert二維編碼。
[0029] 圖2為本發明實施例1中剛初始化的R樹。
[0030] 圖3為本發明實施例1各個對象對應的點在網格中的位置。
[0031] 圖4為本發明實施例1插入O1後的R樹。
[0032] 圖5為本發明實施例1插入〇2、〇3、〇4、〇 5、O6後的R樹。
[0033] 圖6為本發明實施例1對應的最小邊界矩形。
[0034] 圖7為本發明實施例1各多維對象及查詢範圍表示。
【具體實施方式】
[0035] 為了使本發明的目的及優點更加清楚明白，以下結合實施例對本發明進行進一步 詳細說明。應當理解，此處所描述的具體實施例僅僅用以解釋本發明，並不用於限定本發 明。
[0036] 實施例1
[0037] 本實施例採用5臺IBM X3650M4伺服器為測試平臺，每臺伺服器的軟硬 件配置如下；CPU :2*Xeon E5-2620CPU(6Cores 12Thread);內存：32G Bytes ;硬 盤：6T Bytes，lOOOOrpm，raid5 ;作業系統：CentOS 6. 4x86_64 ;開發工具：Eclipse, GNU Toolkits(GCC、G++、GDB), Vim 等；開發語言：Java，C++ ;Hadoop 版本：cl oudera hadoop-2. 3. 0_cdh5. 0? IHBase 版本：cloudera hbase-0. 96. I. I_cdh5. 0? I
[0038] 設待索引對象數據維數為N = 2,待管理多維範圍為（[0,800]，[0,400])，每個網 格單元的大小為200*100,多維數據實例對象有6個，每個數據對象用唯一標識符ID來標 識，各個ID對應的點的二維屬性如表1所示。
[0039] 表1各個點對象的二維屬性
[0040]
【權利要求】
1. 一種基於Hilbert曲線與R-tree的HBase多維查詢系統的構建方法，其特徵在於， 包括如下步驟： 51、 初始化Hilbert編碼產生器。根據數據維數N及Hilbert階數Level,初始化 Hilbert編碼產生器； 52、 根據數據維數N，初始化R樹； 53、 根據用戶指定的表名初始化HBase表； S4 :根據多維對象各維屬性（&1，a2，……，aN)的值，確定所在網格的網格坐標（ Xl， X2，......? xN)； 55、 根據網格坐標（Xp x2，......，xN)，確定 Hilbert 編碼 Hilbert ID ; 56、 根據網格坐標（Xl，x2,……，xN)在R樹中查詢，若存在數據則不需要插入；否則將 網格坐標（Xi, x2, ......，XN)作為範圍，Hilbert ID作為數據插入到R樹中； 57、 對多維對象的各維屬性值進行編碼，得到字節數組ByteArray ; 58、 將多維對象插入到HBase中，其中Hilbert ID作為RowKey，ID作為列名，ByteArray 作為Value ; 59、 插入其它多維數據對象重複S4?S8 ; S10、結束。
2. 根據權利要求1所述的一種基於Hilbert曲線與R-tree的HBase多維查詢系統的 構建方法，其特徵在於，所述步驟S7中的編碼方式如下：字節數組前8個字節對應多維對象 屬性個數的整型值。之後每8個字節表示該多維對象的一個維度屬性對應的雙精度浮點型 值。
3. -種基於Hilbert曲線與R-tree的HBase多維查詢系統的查詢方法，其特徵在於， 包括如下步驟： 521、 根據查詢範圍確定查詢所在網格坐標範圍； 522、 根據網格範圍在R樹中查詢，得到在查詢範圍內的Hilbert ID的集合； 523、 對於每一個Hilbert ID，在HBase中查詢，得到字節數組； 524、 對步驟3結果進行解碼，得到多維對象； 525、 對於步驟4查詢到的多維對象，根據查詢範圍精確進行精確匹配，若多維對象在 查詢範圍內，則將其加入結果集中；如果該對象不在查詢範圍中，則將其淘汰； 526、 結束，結果集中數據即為查詢結果。
4. 根據權利要求3所述的一種基於Hilbert曲線與R-tree的HBase多維查詢系統的 查詢方法，其特徵在於，解碼方法如下；讀取前8個字節內容，得到多維對象屬性數。接著逐 一對之後的每8個字節解碼為雙精度浮點型數據，並賦給多維對象對應屬性上。
【文檔編號】G06F17/30GK104408039SQ201410462268
【公開日】2015年3月11日 申請日期:2014年9月6日 優先權日:2014年9月6日
【發明者】王國仁, 王波濤, 黃山, 祝景陽, 劉增蘭 申請人:東北大學