基于頻繁子圖的圖查詢技術(shù)研究.pdf

1、隨著計(jì)算機(jī)科學(xué)與技術(shù)的發(fā)展，圖數(shù)據(jù)結(jié)構(gòu)在各個(gè)領(lǐng)域內(nèi)得到廣泛應(yīng)用。圖數(shù)據(jù)管理和查詢已經(jīng)成為一種研究熱點(diǎn)。其中，圖查詢的基本方式分為子圖匹配查詢和圖相似性查詢。子圖匹配查詢返回圖數(shù)據(jù)庫(kù)中包含查詢圖的數(shù)據(jù)圖，圖形似性查詢返回在一定的距離范圍內(nèi)與查詢圖相似的數(shù)據(jù)圖。在這兩種查詢中，分別需要圖同構(gòu)驗(yàn)證或相似度的計(jì)算，這兩種計(jì)算都已被證明是NP困難的，因此提升查詢的性能也只能是最大化過(guò)濾掉非結(jié)果集。目前，對(duì)于這兩種查詢的優(yōu)化，主要是基于過(guò)濾驗(yàn)證機(jī)制

2、，即在查詢時(shí)通過(guò)查詢圖的特征過(guò)濾掉不符的數(shù)據(jù)圖，得到規(guī)模較小的候選集，然后對(duì)候選集進(jìn)行同構(gòu)驗(yàn)證或者相似度的計(jì)算。其中，一般選用圖集中的頻繁子圖作為特征進(jìn)行過(guò)濾，因?yàn)槠浔Ａ袅巳值慕Y(jié)構(gòu)信息，過(guò)濾性更強(qiáng)。
　　在子圖匹配查詢問(wèn)題中，現(xiàn)有的方式一般是通過(guò)圖集中的特征建立索引，在查詢時(shí)對(duì)查詢圖進(jìn)行邊擴(kuò)展的方式得到相應(yīng)的候選集。此方式在進(jìn)行查詢時(shí)的時(shí)間復(fù)雜度較高，并且沒(méi)有充分利用查詢圖包含的特征進(jìn)行索引的過(guò)濾，為此，本文提出了一種利用節(jié)點(diǎn)鄰

3、接特征進(jìn)行過(guò)濾的索引結(jié)構(gòu)Vindex。針對(duì)特定的領(lǐng)域，考慮圖集特征之間的位置關(guān)系，結(jié)合用戶的查詢記錄，提取其中較為有價(jià)值的特征位置關(guān)系，建立了基于嵌入特征關(guān)系的索引結(jié)構(gòu)，用于減小候選集的大小。并提出利用特征之間的包含關(guān)系以及特征與數(shù)據(jù)圖之間的關(guān)系，在一定程度上對(duì)索引項(xiàng)和候選集進(jìn)行縮減。
　　在圖相似性查詢問(wèn)題中，現(xiàn)有的方法大多致力于減小編輯距離的計(jì)算時(shí)間，而對(duì)于縮小候選集規(guī)模沒(méi)有提出合適的索引結(jié)構(gòu)和查詢過(guò)濾方法。本文結(jié)合編輯距離的

4、概念和查詢圖的結(jié)構(gòu)特征，對(duì)圖集之中的數(shù)據(jù)圖進(jìn)行過(guò)濾，將相差度較大的圖剔除。然后利用子圖向量異或乘的方式對(duì)圖進(jìn)行聚集，將于查詢圖較為相似的圖聚集在候選集中的前一部分，然后利用分支映射距離結(jié)合動(dòng)態(tài)調(diào)整的方式得到一個(gè)較為精確的候選集。在驗(yàn)證階段，利用圖之間的編輯距離關(guān)系，建立了基于編輯距離的索引GDindex，在驗(yàn)證時(shí)首先與在索引之中的圖進(jìn)行計(jì)算，然后利用查詢圖和索引圖的編輯距離關(guān)系，對(duì)候選集中的其他數(shù)據(jù)圖進(jìn)行處理，通過(guò)此種方式的處理可以減小