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

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

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

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