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

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

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


本文編號(hào)：3286112