對圖結(jié)構(gòu)數(shù)據(jù)的查詢,關(guān)鍵字搜索是結(jié)構(gòu)化查詢語言的一種替代方式。關(guān)鍵字查詢的結(jié)果是圖結(jié)構(gòu)數(shù)據(jù)上一個連接的結(jié)構(gòu),其覆蓋所有或部分關(guān)鍵字。文本覆蓋率和結(jié)構(gòu)緊湊性是評價關(guān)鍵字查詢結(jié)果是否相關(guān)的兩個主要屬性。以往研究通過排序函數(shù)對比所有候選結(jié)果的上述屬性。但是,該過程耗時長,不符合人們在交互系統(tǒng)中短時得到返回結(jié)果的需求。近期研究通過在搜索過程中限制搜素結(jié)果的結(jié)構(gòu)形狀并考察其覆蓋率和緊湊性來解決上述問題。然而,這些方法仍無法解決檢索結(jié)果中存在冗余節(jié)點的問題。本文針對關(guān)鍵字查詢結(jié)果提出基于r-子團最小覆蓋（minimal covered r-clique, MCCr）的概念,作為現(xiàn)有定義的擴展模型,并給出高效算法以檢測給定查詢的MCCr。這些算法的優(yōu)勢在于不僅可以檢索出某個關(guān)鍵字查詢的全部非重復(fù)MCCr,還可以分布式方式執(zhí)行。此外,提出這些算法的近似版本,以多項式時間復(fù)雜度檢索最高的k個近似MCCr。論文表明近似算法可基于成對近似排序檢索出結(jié)果�；趦蓚�真實數(shù)據(jù)集的大量實驗驗證了所提算法的效率和有效性。 

【文章來源】：Frontiers of Information Technology & Electronic Engineering. 2020,21(03)EISCICSCD

【文章頁數(shù)】：18 頁


本文編號：3286112