圖結(jié)構(gòu)數(shù)據(jù)上的子圖查詢.pdf

1、子圖查詢返回圖數(shù)據(jù)集合中所有包含查詢圖的數(shù)據(jù)圖。本文從兩個不同角度對子圖查詢進行研究。首先是頻繁更新的（確定）圖數(shù)據(jù)上的子圖查詢，然后是不確定圖上的子圖查詢。
　　定義了圖的雙分支特征圖和雙分支特征編碼，基于特征編碼提出了一種迭代式子圖查詢處理算法，稱為基于雙分支特征編碼的子圖查詢算法。算法通過動態(tài)優(yōu)化子圖特征迭代順序和限制全局迭代次數(shù)來提高候選結(jié)果集的計算效率。為了高效地完成該查詢算法執(zhí)行過程中的圖數(shù)據(jù)過濾，設計了雙分支特征編碼

2、的索引結(jié)構(gòu)DBrIndex。該索引的創(chuàng)建不依賴于任何頻繁子圖挖掘方法，易于增量式維護，適合于索引頻繁更新的動態(tài)圖數(shù)據(jù)集合。實驗結(jié)果表明：與現(xiàn)有同類方法相比，DBrIndex索引體積小，維護代價低，能夠高效地支持子圖查詢處理。
　　在查詢圖和數(shù)據(jù)圖同時為不確定性圖的前提下，提出了不確定圖間的期望子圖同構(gòu)定義和α-β子圖同構(gòu)匹配定義。查詢圖的不確定性反應了用戶對查詢圖中各種元素(邊、頂點或標號信息)存在的可能性的期望。不確定圖間的期望