不確定圖數(shù)據(jù)TOP-K查詢算法研究.pdf

1、近年來，圖數(shù)據(jù)模型廣泛應(yīng)用于生物信息、計算化學(xué)、語義網(wǎng)等領(lǐng)域。現(xiàn)有的圖數(shù)據(jù)查詢處理技術(shù)大多基于頻繁子圖，是一個過濾、驗證過程，即首先通過挖掘出來的頻繁子圖構(gòu)造索引，然后根據(jù)索引產(chǎn)生侯選集，最后對侯選集中的每一個圖進行子圖同構(gòu)驗證，最終獲取結(jié)果集。在這類算法中，索引構(gòu)造時的參數(shù)選擇策略影響查詢圖侯選集的大小，同時驗證階段需要對每一個侯選圖進行子圖同構(gòu)測試，沒有利用圖之間的差異性。
　　 本文針對確定圖的子圖同構(gòu)查詢，定義了圖數(shù)據(jù)相

2、似度，根據(jù)相似度構(gòu)造索引，進行圖數(shù)據(jù)的查詢處理。相似度基于圖之間的子圖映射關(guān)系，是兩個圖之間最大公共子圖的集合。相似度索引基于倒排索引，通過計算任意圖與其它圖之間的相似度構(gòu)造成相似度集合。與基于頻繁子圖索引的查詢流程不同，基于相似度索引的圖數(shù)據(jù)查詢處理是一個迭代收斂過程，首先從數(shù)據(jù)庫中按照對查詢圖的搜索空間大小選擇一個候選圖，然后計算查詢圖與侯選圖的最大匹配圖，如果侯選圖包含查詢圖，則根據(jù)相似度索引輸出查詢結(jié)果集；否則，根據(jù)最大匹配圖過

3、濾圖數(shù)據(jù)庫并重復(fù)以上過程。
　　 本文針對不確定圖數(shù)據(jù)TOP-K包含查詢問題，將概率上界信息集成到確定圖數(shù)據(jù)庫頻繁子圖索引和相似度索引中，提出了不確定圖數(shù)據(jù)庫索引結(jié)構(gòu)。通過比較概率上界與中間結(jié)果集優(yōu)先隊列中的概率值，減少子圖匹配計算次數(shù)，提高TOP-K查詢效率。
　　 實驗結(jié)果表明，與頻繁子圖索引相比，本文提出的基于相似度索引的查詢方法，對于確定圖查詢和不確定圖TOP-K查詢問題，極大減少了子圖同構(gòu)次數(shù)，具有更高的查詢性