基于MDD的大規(guī)模圖數(shù)據(jù)表示與管理研究.pdf

1、隨著信息技術(shù)的發(fā)展，現(xiàn)代社會越來越多的行業(yè)及領(lǐng)域需要使用計(jì)算機(jī)處理大規(guī)模的各種數(shù)據(jù)。其中一類數(shù)據(jù)必須用圖數(shù)據(jù)的方式來表示。對包含億萬個(gè)頂點(diǎn)和邊的圖數(shù)據(jù)進(jìn)行高效、緊湊的表示和操作，是大規(guī)模圖數(shù)據(jù)分析與管理的基礎(chǔ)。緊湊的圖數(shù)據(jù)表示不僅可以降低圖數(shù)據(jù)的存儲空間，而且還可以提高圖數(shù)據(jù)的管理效率。圖數(shù)據(jù)表示/存儲、查詢/編輯等操作是大規(guī)模圖數(shù)據(jù)管理的核心支撐技術(shù)。為此，本文引入多值決策圖(Multi-valued Decision Diagram

2、, MDD)來進(jìn)行大規(guī)模圖數(shù)據(jù)的表示與管理研究。MDD能夠隱式地將k2樹和kn樹中的同構(gòu)子樹合并以有效解決其大量冗余節(jié)點(diǎn)的問題。本文的主要內(nèi)容和研究成果如下：
　　(1)針對 k2樹存在的問題，提出基于決策圖的大規(guī)模圖數(shù)據(jù)的一種表示方法——k2-MDD，給出了k2-MDD的構(gòu)造過程以及圖的邊查詢、外(內(nèi))鄰查詢、出(入)度查詢、添加(刪除)邊等基本操作。該表示方法在k2樹的基礎(chǔ)上進(jìn)行優(yōu)化與改進(jìn)，對圖的鄰接矩陣進(jìn)行k2劃分后，采用多

3、值決策圖進(jìn)行存儲，從而達(dá)到存儲結(jié)構(gòu)更為緊湊的目的。對真實(shí)網(wǎng)頁圖和社交網(wǎng)絡(luò)圖數(shù)據(jù)的實(shí)驗(yàn)結(jié)果表明 k2-MDD結(jié)構(gòu)在節(jié)點(diǎn)數(shù)上僅為 k2樹的2.59%~4.51%，達(dá)到了預(yù)期效果。對隨機(jī)圖的實(shí)驗(yàn)結(jié)果表明k2-MDD結(jié)構(gòu)不僅適用于稀疏圖，同樣也適用于稠密圖。
　　(2)拓展k2-MDD的高效性到多維數(shù)據(jù)，結(jié)合kn樹和MDD提出一種支持多維矩陣高效基本查詢和編輯的kn-MDD表示方法。kn-MDD同樣具有k2-MDD的緊湊性，并且解決了kn

4、樹不適用于稠密圖和動態(tài)圖的缺陷。圖數(shù)據(jù)的k2-MDD和kn-MDD表示，既具有k2樹和kn樹表示的緊湊性和查詢的高效性，又能實(shí)現(xiàn)符號決策圖表示下的圖模式高效操作，從而實(shí)現(xiàn)了描述和計(jì)算能力的統(tǒng)一。
　　(3)分析實(shí)際應(yīng)用中的大規(guī)模圖數(shù)據(jù)，如二進(jìn)制圖像、GIS數(shù)據(jù)等柵格存儲結(jié)構(gòu)數(shù)據(jù)，以及Web服務(wù)組合和時(shí)態(tài)圖等二元或多元數(shù)據(jù)等的特性，并使用k2-MDD或者kn-MDD來提高這些大規(guī)模數(shù)據(jù)的存儲效率，為它們的管理提供新的理論、方法和技術(shù)