資源描述框架（Resource Description Framework,簡稱RDF）是語義Web中所使用的基本標(biāo)記語言,在知識的組織與管理和社會網(wǎng)絡(luò)應(yīng)用中廣泛應(yīng)用。RDF數(shù)據(jù)的規(guī)模隨著語義Web應(yīng)用的發(fā)展而增大。RDF數(shù)據(jù)具有典型的圖特征,含有復(fù)雜的結(jié)構(gòu)信息,以及大量的文本信息�？梢�,如何在大規(guī)模RDF數(shù)據(jù)上進(jìn)行高效的關(guān)鍵詞查詢是當(dāng)前研究的熱點之一。針對已有研究在查詢執(zhí)行效率和結(jié)果質(zhì)量方面存在的不足,提出了基于近似組斯坦納樹的大規(guī)模RDF數(shù)據(jù)關(guān)鍵詞查詢方法RAGS。RAGS將RDF上的關(guān)鍵詞查詢映射為組斯坦納樹問題,然后通過將組斯坦納樹問題規(guī)約為最小斯坦納樹問題進(jìn)行求解。針對經(jīng)典的最小斯坦納樹算法是非規(guī)約安全的問題,提出了改進(jìn)方法,并分析了算法的時間復(fù)雜度和近似比性能。為了使大規(guī)模RDF數(shù)據(jù)上的關(guān)鍵詞查詢具有更友好的用戶體驗,設(shè)計了最短路徑三元組倒排索引結(jié)構(gòu),通過離線預(yù)先計算全源最短路徑的方式,改善在線查詢的實時性；提出基于升序排列生成樹算法的top-k查詢方法,以便更快的為用戶返回準(zhǔn)確結(jié)果�？紤]到對于大規(guī)模RDF數(shù)據(jù)而言,索引構(gòu)建時間也是系統(tǒng)的主要瓶頸。提出基于整體同步并行計算模... 

【文章來源】：東北大學(xué)遼寧省 211工程院校 985工程院校 教育部直屬院校

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

【學(xué)位級別】：碩士

【文章目錄】：
摘要
ABSTRACT
第1章 緒論
    1.1 引言
    1.2 研究現(xiàn)狀
    1.3 挑戰(zhàn)與研究內(nèi)容
    1.4 論文結(jié)構(gòu)與安排
第2章 相關(guān)工作
    2.1 半結(jié)構(gòu)化和結(jié)構(gòu)化數(shù)據(jù)上的關(guān)鍵詞查詢
        2.1.1 XML文檔上的關(guān)鍵詞搜索
        2.1.2 關(guān)系數(shù)據(jù)庫上的關(guān)鍵詞查詢
        2.1.3 RDF數(shù)據(jù)上的關(guān)鍵詞查詢
    2.2 組斯坦納樹和最小斯坦納樹問題
        2.2.1 最小斯坦納樹問題
        2.2.2 組斯坦納樹問題
    2.3 分布式大規(guī)模圖處理技術(shù)
        2.3.1 基于MapReduce的大規(guī)模圖處理
        2.3.2 基于BSP的大規(guī)模圖處理
    2.4 本章小結(jié)
第3章 基于近似組斯坦納樹的RDF數(shù)據(jù)關(guān)鍵詞查詢方法
    3.1 問題定義
    3.2 方法概述
    3.3 RDF圖變換
    3.4 近似組斯坦納樹
        3.4.1 組斯坦納樹問題規(guī)約為最小斯坦納樹問題
        3.4.2 基于DNH最小斯坦納樹啟發(fā)算法的近似組斯坦納樹求解
    3.5 本章小結(jié)
第4章 面向大規(guī)模RDF數(shù)據(jù)關(guān)鍵詞查詢的改進(jìn)方法
    4.1 最短路徑三元組倒排索引
    4.2 TOP-K查詢
    4.3 基于BSP的分布式算法
    4.4 本章小結(jié)
第5章 實驗設(shè)計與分析
    5.1 實驗設(shè)計
        5.1.1 實驗環(huán)境
        5.1.2 測試數(shù)據(jù)集
        5.1.3 實驗評價標(biāo)準(zhǔn)
    5.2 實驗結(jié)果分析
        5.2.1 索引時間開銷和空間開銷
        5.2.2 查詢響應(yīng)時間比較
        5.2.3 查詢效果分析
        5.2.4 k值對top-k查詢響應(yīng)時間的影響
        5.2.5 基于BSP的分布式算法性能
    5.3 本章小結(jié)
第6章 結(jié)論與展望
    6.1 結(jié)論
    6.2 未來展望
參考文獻(xiàn)
致謝
攻讀碩士學(xué)位期間參與的項目


【參考文獻(xiàn)】：
期刊論文
[1]云計算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)[J]. 于戈,谷峪,鮑玉斌,王志剛.  計算機學(xué)報. 2011(10)
[2]KREAG:基于實體三元組關(guān)聯(lián)圖的RDF數(shù)據(jù)關(guān)鍵詞查詢方法[J]. 李慧穎,瞿裕忠.  計算機學(xué)報. 2011(05)
[3]XML數(shù)據(jù)的查詢技術(shù)[J]. 孔令波,唐世渭,楊冬青,王騰蛟,高軍.  軟件學(xué)報. 2007(06)
[4]細(xì)粒度語義網(wǎng)檢索[J]. 吳剛,唐杰,李涓子,王克宏.  清華大學(xué)學(xué)報(自然科學(xué)版). 2005(S1)
[5]并行計算模型在集群環(huán)境下的適應(yīng)性[J]. 宋安軍,彭勤科,胡保生.  計算機工程. 2003(18)

博士論文
[1]RDF圖數(shù)據(jù)管理的關(guān)鍵技術(shù)研究[D]. 吳剛.清華大學(xué) 2008



本文編號：3061627