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

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

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

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

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