大規(guī)模圖上可達性查詢索引技術(shù)的研究.pdf

1、通過頂點和邊表達對象以及對象間聯(lián)系的圖廣泛應(yīng)用于語義網(wǎng)、生物信息、本體等領(lǐng)域的建模。這些領(lǐng)域的應(yīng)用需要解決百萬量級規(guī)模以上的圖數(shù)據(jù)處理的可擴展性問題。其中，可達性查詢是判斷傳遞關(guān)系的基本操作，它一般表示為判斷圖上兩個頂點之間是否存在一條路徑。目前研究的重點是針對大規(guī)模數(shù)據(jù)應(yīng)用背景，研究壓縮傳遞閉包的索引技術(shù)，以取得索引建立時間、索引存儲空間和查詢效率之間的優(yōu)化權(quán)衡。本文基本思路是通過拓?fù)渑判驅(qū)D中頂點進行層次編號，再根據(jù)層次編號在初等數(shù)

2、論方面的性質(zhì)，從每個頂點的祖先和后代的集合中選取部分頂點建立2-Hop標(biāo)簽，主要貢獻如下:
　　(1)給出標(biāo)簽的形式化定義和理論基礎(chǔ)。對圖中的頂點引入階的概念，再從每個頂點的祖先和后代的集合中選取按階遞增的頂點建立2-Hop標(biāo)簽，并對標(biāo)簽的正確性給出了初等數(shù)論方面的證明。此外，利用初等數(shù)論方面的性質(zhì)，提出了有效地處理跨邊的方式:每一條跨邊的頂點的祖先和后代之間的可達性關(guān)系只需要增加不超過一個虛點。
　　(2)設(shè)計索引的生成算

3、法。引入增序列和減序列的概念，利用增序列和減序列在初等數(shù)論方面的性質(zhì)，提出了高效的標(biāo)簽生成算法，避免了傳遞閉包的計算。
　　(3)對標(biāo)簽進一步優(yōu)化。使用刪除虛點的方式減小最終生成的標(biāo)簽規(guī)模;提出刪除基于虛邊的高度數(shù)的點的方式，減小建立標(biāo)簽過程中虛點的規(guī)模。
　　(4)在大規(guī)模實際數(shù)據(jù)集和合成數(shù)據(jù)集上進行實驗，考察索引建立時間、存儲空間和查詢效率三方面。實驗分析了本文提出的優(yōu)化算法對性能的影響:刪除虛點的優(yōu)化會帶來一定的計算消