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

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

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

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

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