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

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

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

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