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

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

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

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

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