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

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

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

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