XCube的計算和查詢.pdf

1、隨著B2B等應用的普及，越來越多的數據以XML文檔的形式出現，如何對XML文檔中的數據進行聯機分析引起了研究工作者的關注。傳統(tǒng)的做法是先將XML中數據轉換為關系的元組，再進行計算。本文中，我們通過直接對XML文檔進行操作，避免了數據轉換過程，提高了運算效率。XCube是關于XML的一個立方體結構，在實際應用過程中，當輸入數據量太大時，受內存限制，無法完成運算。若把數據分批輸入進行運算，則會產生許多重復的中間結果，要形成最終結果需從磁盤中

2、把這些中間結果讀入內存再進行大量的合并工作。因為涉及磁盤的讀操作及大量的合并操作，使運算時間增加好幾個數量級。通過分析和實驗，我們對XCube算法進行了改進，提出了“分批輸入分次計算”的方法。當數據量很大時，按照新改進的方法進行分批輸入計算時，我們只生成最終結果的分支，對于中間結果的分支不予計算，避免了對中間結果中某些分支的合并過程。通過對數據進行分次計算的方法，生成剩余分支，使運算順利完成。因為運算中沒有涉及到從磁盤中讀中間結果進行分

3、支合并的過程，所以提高了運算效率。
　　 Bloom Filter(布隆過濾器)是1970年由Bloom提出的，它利用hashtable，通過hash函數將元素映射成bitarray中一個點。當檢索時，只要查看相應點的值是否為1就可知這個元素是否在集合中。為了增加準確度，Bloom Filter中可以利用多個hash函數。通過對相關查詢算法研究，我們發(fā)現XCube的點查詢?yōu)橐粋€從根節(jié)點到葉子節(jié)點的路徑匹配過程，于是我們按照Blo

4、omFilter的思想提出了一個新的壓縮查詢算法：BXCube算法。把XCube算法中產生的每條從根節(jié)點到葉子節(jié)點的路徑作為整體，通過多個(兩個或三個)hash函數進行計算，分別產生多個hash值。我們只存儲由hash值、度量值及Tag域構成的結構，稱為Bloom元組。相對于存儲整條路徑，存儲Bloom元組，節(jié)省了存儲空間并對機密數據提供了一定的安全保障。路徑長度越長，效果越明顯，更適用于高維數據。由于hash函數本身的問題，當數據量太

5、大時，不可避免的會出現hash沖突。為了消除因為hash沖突而使查詢結果錯誤的問題，我們設計了一個過濾結構：過濾器表。在運算時，把同一棵子樹的所有路徑經過運算，放入過濾器表中，經排序后，若相鄰的臨時Bloom元組hash值相同，而度量值不同，則需要把這兩個路徑字符串經過一個新的hash函數進行hash計算，當產生的hash值可區(qū)分時，把第一個路徑字符串產生的hash值、兩條路徑對應的度量值及所用的hash函數ID放入沖突表中，而在查詢表

6、中，只存儲一個Bloom元組，其Tag域的值指明如何解決沖突。若相鄰的三個元組間存在沖突時(概率極小)，則通過路徑表處理。當沖突檢測完后，把結果放在查詢表中，同時在索引表中記錄該棵子樹產生的Bloom元組在查詢表中的位置。當查詢時，首先通過查詢路徑的根節(jié)點的值在索引表中查找查詢范圍。若值在索引表中，則可通過查詢得到在查詢表中的查詢范圍。把整條查詢路徑作為一個整體經過相應hash函數計算，生成臨時元組。把臨時元組在查詢范圍內進行折半查找，