XCube的計(jì)算和查詢.pdf

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

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

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

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

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

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