一種面向近似查詢的圖數(shù)據(jù)庫索引方法.pdf

1、圖論是組合數(shù)學(xué)領(lǐng)域的一個分支，20世紀(jì)60年代末，隨著計算機(jī)技術(shù)的產(chǎn)生和發(fā)展，組合數(shù)學(xué)，特別是圖論理論得到了人們越來越多的關(guān)注，時至今日，人們面對的計算模型以及數(shù)據(jù)結(jié)構(gòu)仍然在變得越來越復(fù)雜，由于圖可以很方便的表示關(guān)系數(shù)據(jù)模型，因此圖論中的許多與關(guān)系數(shù)據(jù)表示相關(guān)的理論及算法被廣泛的應(yīng)用到數(shù)據(jù)建模以及數(shù)據(jù)庫設(shè)計領(lǐng)域中來。
　　 在數(shù)據(jù)庫設(shè)計中，圖結(jié)構(gòu)經(jīng)常被用來存儲以及表示關(guān)系數(shù)據(jù)，例如一些復(fù)雜的文檔格式(XML文檔)，蛋白質(zhì)化學(xué)結(jié)構(gòu)

2、，大分子的化學(xué)式，向量圖形等等，圖論中的一些基本算法如最小生成樹算法，最短路徑算法，以及完美匹配算法也是許多最優(yōu)調(diào)度問題的基礎(chǔ)，最近的一些圖論的成果已經(jīng)被大量應(yīng)用在圖像處理，生物信息學(xué)，以及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的研究中。
　　 圖的匹配是圖數(shù)據(jù)庫領(lǐng)域中近年來一個熱點(diǎn)的研究問題，即對于一個包含大量圖的集合，如何在這個集合中迅速找到滿足給定查詢要求的答案。相比于精確圖查詢，相似性查詢是一個較為新穎且難度較大的問題。針對這個問題，本文對圖數(shù)據(jù)

3、庫中的相似性查詢方法以及數(shù)據(jù)庫的索引方法進(jìn)行了深入研究，提出了一種在大規(guī)模圖數(shù)據(jù)庫上建立索引以加快相似查詢速度的高效方法。本文的主要工作總結(jié)如下：
　　 (1)本文首先提出了一種新的衡量圖相似性的標(biāo)準(zhǔn)，這種標(biāo)準(zhǔn)利用編輯距離的定義方式，很精確地表達(dá)了兩個圖之間的近似程度，相對于其他度量方式，編輯距離能好的反映兩個圖之間基于編輯操作的相似性，從而更方便地描述圖和圖之間的轉(zhuǎn)化關(guān)系。
　　 (2)針對以往方法只能在兩個圖上做編輯

4、距離計算的不足，利用一種新的索引結(jié)構(gòu)——k-鄰接子圖，提出了一種基于鄰接子圖比對的數(shù)據(jù)庫倒排索引方法以避免時間和空間效率都很差的順序查找。這種方法在編輯距離閾值相對不大的稀疏圖數(shù)據(jù)庫查詢中有很好的過濾性能。
　　 (3)由于鄰接子圖匹配在子圖規(guī)模較大時的高復(fù)雜性，我們進(jìn)一步提出將鄰接子圖以鄰接樹的形式表示的方法，通過放寬嚴(yán)格的同構(gòu)匹配條件，并利用在圖的鄰接樹上做偽同構(gòu)匹配的方法，加快了數(shù)據(jù)庫索引的構(gòu)造以及提取在線查詢的特征信息的