基于r-clique的不確定RDF關(guān)鍵字查詢研究.pdf

1、資源描述框架（Resource Description Framework，簡稱RDF）是語義Web網(wǎng)所使用的基本標(biāo)記語言，在諸多領(lǐng)域中有廣泛應(yīng)用。由于現(xiàn)有的本體抽取、標(biāo)注方法和測(cè)量技術(shù)存在誤差和噪聲，使得不確定RDF數(shù)據(jù)普遍存在。近年來，對(duì)于不確定RDF數(shù)據(jù)的查詢研究逐漸成為熱點(diǎn)。由于不確定RDF數(shù)據(jù)可以建模為不確定RDF圖，那么對(duì)于不確定RDF數(shù)據(jù)的關(guān)鍵字查詢的研究實(shí)際上就是對(duì)于不確定圖上關(guān)鍵字查詢的研究。本文在已有研究的基礎(chǔ)上，提

2、出了兩種基于r-clique的不確定RDF關(guān)鍵字查詢的算法——KSABR和HABR。
　　單詞”clique”的中文釋義是“極大團(tuán)、子群體”，這里指不確定圖中的子圖，字母r是一個(gè)表示距離閾值的變量。所以，r-clique是指包含所有查詢關(guān)鍵字的任意兩個(gè)節(jié)點(diǎn)的距離不大于給定值r的子圖。為了提高查詢速度，本文提出了一種多項(xiàng)式時(shí)延的近似算法來構(gòu)建r-clique。
　　算法KSABR(Keyword Search Algorith

3、m Based on r-clique)將不確定RDF數(shù)據(jù)上的關(guān)鍵字查詢問題映射為尋找不確定圖上的r-cliques的問題。為了提高查詢結(jié)果的質(zhì)量，在KSABR的基礎(chǔ)上又進(jìn)一步提出了精度更高的算法:HABR（Efficient Algorithm Based on r-clique）。HABR中采用了打分函數(shù)對(duì)結(jié)果進(jìn)行排序。對(duì)于得到的k個(gè)結(jié)果，HABR算法調(diào)用打分函數(shù)對(duì)結(jié)果進(jìn)行排序，然后將top-k個(gè)結(jié)果返回給用戶。
　　為了進(jìn)一

4、步提高查詢的速度，本文設(shè)計(jì)了兩種索引結(jié)構(gòu)——KI(KeywordInverted Index)和PI(Probabilistic Inverted Index)。KI中存放的是關(guān)鍵字和節(jié)點(diǎn)之間的映射關(guān)系，它可以用來實(shí)現(xiàn)結(jié)構(gòu)剪枝和概率剪枝。PI中存放的是關(guān)鍵字節(jié)點(diǎn)和r-clique之間的映射關(guān)系，它可以用來實(shí)現(xiàn)打分函數(shù)。
　　實(shí)驗(yàn)證明，本論文提出的算法KSABR在時(shí)間性能上具有較好的性能，而算法HABR在時(shí)間性能和結(jié)果質(zhì)量上都具有較