基于修改空間的圖形數(shù)據(jù)庫Top-K查詢研究.pdf

1、近年來,計算機應用正以各種方式越來越快地滲透到各個領域之中。其中以數(shù)據(jù)庫,尤其是關系數(shù)據(jù)庫的應用最為廣泛。關系數(shù)據(jù)庫以集合代數(shù)為基礎,利用關系模型來建立問題和領域結構模型。然而這種建模方式有一定的局限性,難以直接且深入的描述現(xiàn)實世界對象間復雜聯(lián)系。圖形是一種描述性很強的數(shù)據(jù)結構。通過加以標記的頂點和邊,圖形既可以深入描述一組實體間的關系,也可以直觀地描述這些關系間的屬性。在復雜結構數(shù)據(jù)建模方面,如化合物分子結構,蛋白質基因結構,電路結構

2、,Web和XML文檔等,圖形起著很重要的作用,圖形數(shù)據(jù)庫也由此得到廣泛的關注及應用。 隨著圖形數(shù)據(jù)庫越來越大,對于快速有效圖形查詢搜索系統(tǒng)的需要也越來越迫切?，F(xiàn)有的圖形搜索方法是將數(shù)據(jù)庫中的頻繁結構碎片作為索引項,根據(jù)各個圖形所包含的結構碎片邊的特性做高維索引,查詢時把圖形進行分解,在索引中查找包含所有碎片的圖形。但是圖形頻繁結構碎片需由圖形數(shù)據(jù)庫的挖掘獲得,頻繁結構邊數(shù)的不同使得每個索引項的維數(shù)也不確定,而且查詢圖形難以實現(xiàn)最

3、優(yōu)分解。 GString技術是目前圖形表示的最新方法,該方法給出了三種基本結構及語法規(guī)則來描述基本子圖,進而通過基本子圖的組合表示圖形。本文以此為基礎,構建了一個圖形修改空間,通過不同的權值分配,把每個基本子圖頂點,分支和邊的修改作為其在圖形修改空間中各方向的位移。在此修改空間基礎上,本文為屬于相同類型的基本子圖建立三維R-tree索引,并對R-tree索引的相關算法進行修改,以滿足對圖形修改的特定需要。圖形修改空間的實例和模擬