XCube的計算和查詢.pdf

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

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

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

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

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

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