大規(guī)模圖數(shù)據(jù)可達(dá)性查詢算法研究.pdf

1、隨著大數(shù)據(jù)時(shí)代的到來(lái)，圖作為表示數(shù)據(jù)之間關(guān)系的基本結(jié)構(gòu)，由于其處理復(fù)雜對(duì)象之間關(guān)系的表達(dá)能力，在社交網(wǎng)絡(luò)、軟件工程、生物數(shù)據(jù)等領(lǐng)域有著廣泛應(yīng)用。查詢及分析圖結(jié)構(gòu)數(shù)據(jù)變得越來(lái)越重要?？蛇_(dá)性查詢是檢驗(yàn)在有向圖中是否存在一個(gè)節(jié)點(diǎn)u到另一個(gè)節(jié)點(diǎn)v的路徑，它是一種基礎(chǔ)而頻繁使用的查詢。現(xiàn)實(shí)中許多問(wèn)題都可以映射為可達(dá)性查詢。因此，迫切需求加速查詢圖數(shù)據(jù)庫(kù)的機(jī)制。
　　當(dāng)前已經(jīng)提出許多不同方法處理可達(dá)性查詢。但是大多數(shù)方法只能在小規(guī)模圖中執(zhí)行，

2、因其自身的局限性無(wú)法擴(kuò)展到大規(guī)模圖。此外，現(xiàn)有索引方法有另一個(gè)缺陷就是它們不支持圖的動(dòng)態(tài)更新。然而，現(xiàn)實(shí)應(yīng)用中的圖大多都是在不斷變化的。針對(duì)上述問(wèn)題，通過(guò)研究已有的圖可達(dá)性索引算法，并分析這些算法的優(yōu)缺點(diǎn)。本文基于區(qū)間標(biāo)簽方法展開(kāi)了一系列的相關(guān)研究，主要研究的內(nèi)容如下：
　?。?）針對(duì)索引代價(jià)過(guò)高的問(wèn)題，本文提出了一種基于雙區(qū)間標(biāo)簽的索引方法GIDIL。該索引方法為每個(gè)節(jié)點(diǎn)分配一個(gè)主區(qū)間和一個(gè)輔助區(qū)間，應(yīng)用這2個(gè)區(qū)間保存原圖的可達(dá)

3、性信息。其中主區(qū)間記錄生成樹的可達(dá)性信息，輔助區(qū)間記錄非樹邊可達(dá)性信息。并基于GIDIL索引設(shè)計(jì)了可達(dá)性算法，有效實(shí)現(xiàn)圖的可達(dá)性查詢。
　?。?）為了將索引應(yīng)用于動(dòng)態(tài)圖，支持圖的動(dòng)態(tài)更新操作，本文擴(kuò)展了靜態(tài)索引 GIDIL，提出動(dòng)態(tài)可達(dá)性索引 DGIDIL。該索引方法將每個(gè)節(jié)點(diǎn)的區(qū)間標(biāo)簽進(jìn)行擴(kuò)展處理，在動(dòng)態(tài)圖上使其能夠快速進(jìn)行索引更新，并能有效執(zhí)行可達(dá)性查詢。該索引方法支持圖中節(jié)點(diǎn)或邊的插入和刪除操作。
　　最后，本文通過(guò)大