【摘要】：資源描述框架(Resource Description Framework,簡稱RDF)是語義Web網(wǎng)所使用的基本標(biāo)記語言,在諸多領(lǐng)域中有廣泛應(yīng)用。由于現(xiàn)有的本體抽取、標(biāo)注方法和測量技術(shù)存在誤差和噪聲,使得不確定RDF數(shù)據(jù)普遍存在。近年來,對于不確定RDF數(shù)據(jù)的查詢研究逐漸成為熱點(diǎn)。由于不確定RDF數(shù)據(jù)可以建模為不確定RDF圖,那么對于不確定RDF數(shù)據(jù)的關(guān)鍵字查詢的研究實(shí)際上就是對于不確定圖上關(guān)鍵字查詢的研究。本文在已有研究的基礎(chǔ)上,提出了兩種基于r-clique的不確定RDF關(guān)鍵字查詢的算法-——SABR和HABR。單詞”clique"的中文釋義是“極大團(tuán)、子群體”,這里指不確定圖中的子圖,字母r是一個表示距離閾值的變量。所以,r-clique是指包含所有查詢關(guān)鍵字的任意兩個節(jié)點(diǎn)的距離不大于給定值r的子圖。為了提高查詢速度,本文提出了一種多項(xiàng)式時延的近似算法來構(gòu)建r-clique。算法KSABR (Keyword Search Algorithm 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ù)對結(jié)果進(jìn)行排序。對于得到的k個結(jié)果,HABR算法調(diào)用打分函數(shù)對結(jié)果進(jìn)行排序,然后將top-k個結(jié)果返回給用戶。為了進(jìn)一步提高查詢的速度,本文設(shè)計(jì)了兩種索引結(jié)構(gòu)——KI (Keyword Inverted 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在時間性能上具有較好的性能,而算法HABR在時間性能和結(jié)果質(zhì)量上都具有較好的性能。
[Abstract]:Resource description Framework (Resource Description Framework,) is a basic markup language used in semantic Web nets, which is widely used in many fields. Due to the existing ontology extraction, labeling methods and measurement techniques, there are errors and noises, which make uncertain RDF data widely exist. In recent years, query for uncertain RDF data has become a hot topic. Because uncertain RDF data can be modeled as an uncertain RDF graph, the research on keyword query of uncertain RDF data is actually a study of keyword query on an uncertain RDF graph. Based on the previous research, this paper proposes two algorithms of uncertain RDF keyword query based on r-clique-SABR and Habr. The Chinese meaning of the word "clique" is "maximum mass, subgroup", which refers to a subgraph in an uncertain graph. The letter r is a variable representing the threshold of distance. Therefore, r-clique is a subgraph of any two nodes containing all query keys whose distance is not greater than a given value r. In order to improve the query speed, an approximate algorithm of polynomial delay is proposed to construct r-clique. The algorithm KSABR (Keyword Search Algorithm Based on r-clique maps the keyword query problem on uncertain RDF data to the problem of finding r-cliques on uncertain graphs. In order to improve the quality of query results, a more accurate algorithm called: Habr (Efficient Algorithm Based on r-clique is proposed on the basis of KSABR. In HABR, a scoring function is used to sort the results. For the obtained k results top-k algorithm calls the scoring function to sort the results and then returns the top-k results to the user. In order to further improve the query speed, this paper designs two index structures, Ki (Keyword Inverted Index) and PI (Probabilistic Inverted Index). Ki, which store the mapping relationship between keywords and nodes. It can be used to implement structural pruning and probabilistic pruning. Pi can store the mapping relationship between key nodes and r-clique, and it can be used to implement scoring functions. Experiments show that the proposed algorithm KSABR has better performance in time performance and HABR has better performance in both time performance and result quality.
【學(xué)位授予單位】：東北大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TP393.09

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 王煥景;李明;;“關(guān)鍵字查詢”教學(xué)設(shè)計(jì)[J];中國教育技術(shù)裝備;2007年12期

2 宋玉玲;王寧;;利用實(shí)體語義信息的關(guān)鍵字查詢結(jié)果多樣化[J];計(jì)算機(jī)科學(xué)與探索;2014年03期

3 陳子軍;周同;劉文遠(yuǎn);;面向集合和方向的空間關(guān)鍵字查詢[J];小型微型計(jì)算機(jī)系統(tǒng);2014年05期

4 任建華;周建;孟祥福;魏珂;;基于關(guān)鍵字之間結(jié)構(gòu)關(guān)系的XML查詢結(jié)果排序方法[J];計(jì)算機(jī)科學(xué);2013年06期

5 黃靜;陸嘉恒;孟小峰;;高效的XML關(guān)鍵字查詢改寫和結(jié)果生成技術(shù)[J];計(jì)算機(jī)研究與發(fā)展;2010年05期

6 王金寶;高宏;李建中;楊東華;;RB樹:一種支持空間近似關(guān)鍵字查詢的外存索引[J];計(jì)算機(jī)研究與發(fā)展;2012年10期

7 周軍鋒;孟小峰;;XML關(guān)鍵字查詢處理研究[J];計(jì)算機(jī)學(xué)報(bào);2012年12期

8 吳海濤;;一種改進(jìn)的XML關(guān)鍵字查詢算法[J];南京工程學(xué)院學(xué)報(bào)(自然科學(xué)版);2011年02期

9 李艷紅;李國徽;張聰;;路網(wǎng)中空間關(guān)鍵字連續(xù)k近鄰查詢算法研究[J];華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年12期

10 劉琰;周理;;基于VLCA的關(guān)鍵字查詢匹配算法[J];科學(xué)技術(shù)與工程;2008年02期

相關(guān)會議論文 前5條

1 謝濤;王曉玲;歐陽樹生;周傲英;;XML關(guān)鍵字檢索的最低公共祖先快速查找方法[A];第二十三屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（研究報(bào)告篇）[C];2006年

2 黃靜;陸嘉恒;孟小峰;;高效的XML關(guān)鍵字查詢改寫和結(jié)果生成技術(shù)[A];第26屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（A輯）[C];2009年

3 方非;朱皓;楊衛(wèi)東;;基于結(jié)構(gòu)摘要的XML關(guān)鍵字檢索[A];第26屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（B輯）[C];2009年

4 黃靜;徐俊勁;周軍鋒;孟小峰;;MLCEA:一種基于實(shí)體的XML關(guān)鍵字查詢語義[A];第二十五屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（二）[C];2008年

5 王小鋒;張新;謝敏;孟小峰;周軍鋒;;XML數(shù)據(jù)流上的關(guān)鍵字查詢[A];第二十三屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（研究報(bào)告篇）[C];2006年

相關(guān)博士學(xué)位論文 前1條

1 張晨靜;XML關(guān)鍵字過濾技術(shù)[D];復(fù)旦大學(xué);2011年

相關(guān)碩士學(xué)位論文 前10條

1 張丹婷;基于事前約束的XML關(guān)鍵字查詢處理研究[D];燕山大學(xué);2015年

2 徐超;基于路網(wǎng)關(guān)鍵字的選擇性估算研究[D];安徽工業(yè)大學(xué);2015年

3 林健;云環(huán)境下支持隱私保護(hù)的動態(tài)模糊多關(guān)鍵字排列查詢方法研究[D];東北大學(xué);2014年

4 張舒;基于r-clique的不確定RDF關(guān)鍵字查詢研究[D];東北大學(xué);2014年

5 李赫;個人數(shù)據(jù)空間管理系統(tǒng)關(guān)鍵字查詢的研究與實(shí)現(xiàn)[D];北京交通大學(xué);2012年

6 周月;關(guān)鍵字查詢性能優(yōu)化研究[D];天津大學(xué);2012年

7 付顏勝;面向集合的空間關(guān)鍵字查詢方法研究[D];燕山大學(xué);2012年

8 潘瑾琨;面向互聯(lián)網(wǎng)位置服務(wù)的空間關(guān)鍵字查詢技術(shù)研究與實(shí)現(xiàn)[D];國防科學(xué)技術(shù)大學(xué);2012年

9 陳坤杰;帶關(guān)鍵字的聚集路徑查詢技術(shù)研究[D];復(fù)旦大學(xué);2013年

10 賀騰;面向XML關(guān)鍵字查詢的用戶查詢意圖推斷問題研究[D];燕山大學(xué);2014年

，

本文編號：2154799