Top-k查詢作為一種重要的數(shù)據(jù)管理操作,在信息檢索、生物醫(yī)療、多目標(biāo)決策支持等領(lǐng)域都發(fā)揮著重要的作用。由于網(wǎng)絡(luò)傳輸延遲、數(shù)據(jù)采集設(shè)備精度限制、以及保護(hù)用戶隱私數(shù)據(jù)等主客觀原因,在日常的生產(chǎn)生活中,不確定數(shù)據(jù)廣泛存在,從而為數(shù)據(jù)的查詢帶來(lái)了新的挑戰(zhàn)。另外,隨著云計(jì)算的普及,人們對(duì)于數(shù)據(jù)的隱私保護(hù)越來(lái)越重視,在數(shù)據(jù)安全與可用性之間需要作出審慎的權(quán)衡。針對(duì)不確定數(shù)據(jù)top-k查詢處理面臨的挑戰(zhàn),對(duì)該問(wèn)題的研究工作分別從以下三個(gè)維度進(jìn)行開(kāi)展:首先,針對(duì)不確定數(shù)據(jù)上查詢語(yǔ)義多樣性導(dǎo)致查詢復(fù)雜度高的問(wèn)題,給出了基于期望編輯距離的不確定字符串top-k查詢的形式化定義,提出了一個(gè)新的距離語(yǔ)義概率n-gram集合映射距離,進(jìn)而結(jié)合查詢語(yǔ)義以及概率n-gram分詞的特點(diǎn),提出基于概率n-gram集合映射距離的近似匹配過(guò)濾算法,并通過(guò)建立基于概率n-gram劃分的多層倒排索引以及頻率矩陣來(lái)進(jìn)一步優(yōu)化算法實(shí)現(xiàn)。通過(guò)對(duì)該算法進(jìn)行時(shí)間復(fù)雜度分析和一系列對(duì)比實(shí)驗(yàn)性能評(píng)測(cè),驗(yàn)證該算法實(shí)現(xiàn)對(duì)不確定字符串top-k查詢的高效處理,相比于基準(zhǔn)算法具有較高的剪枝過(guò)濾能力和良好的可擴(kuò)展性。其次,針對(duì)查詢候選集規(guī)模膨脹導(dǎo)致單... 

【文章來(lái)源】：華中科技大學(xué)湖北省 211工程院校 985工程院校 教育部直屬院校

【文章頁(yè)數(shù)】：111 頁(yè)

【學(xué)位級(jí)別】：博士

【部分圖文】：

基于概率n-gram劃分的兩層倒排索引

n-grams 的其他可能映射顯示為虛線，從而計(jì)算得出1SG 與2SG 的 (,)12SSe ：=1+1+(0.8×1+0.2×1)+(0.8×1+0.2×2)+(0.8×1+0.2×1)+1=5.4.3.2 基于 GMD 的近似匹配過(guò)濾算法定理 2.1 給定兩個(gè)不確定字符串1S 和2S ，如果 (,)12SSe 的值小于等于 τ，那么 至少包含有 (S,S) 12 個(gè) n-gram 的 gram 映射編輯距離 GED 小于等 (0 n)，其中(S,S){|S|,|S|}-n1-(,,)1212 max n + (2即，1S 和2S 至多有 ( , ,n)個(gè) n-gram 的 GED 大于 (0 n)，其中 ( , ,n) max{1,n 2 }+n( 1)(2

華 中 科 技 大 學(xué) 博 士 學(xué) 位 論 文圖 2.5（a）和圖 2.5（b）分別描述了隨著不確定字符串?dāng)?shù)據(jù)集中字符串平均長(zhǎng)度的變化，TUSK 算法和 Baseline 基準(zhǔn)算法（在以下實(shí)驗(yàn)數(shù)據(jù)圖中標(biāo)注為 Direct）在執(zhí)行時(shí)間和過(guò)濾效果上的性能對(duì)比。通過(guò)分別令 y 0,1,2,3，分別得到字符串平均長(zhǎng)度從 13.6, 27.2, 40.8 到 54.4 不等的不確定字符串集合。如圖 2.5（a）所示，隨著字符串長(zhǎng)度的增加，TUSK 和 Baseline 基準(zhǔn)算法的查詢時(shí)間都隨之增大，但無(wú)論是從查詢時(shí)間絕對(duì)值還是查詢時(shí)間增長(zhǎng)的速率來(lái)看，TUSK 都明顯優(yōu)于基準(zhǔn)算法；同時(shí)，如圖 2.5（b）所示，基準(zhǔn)算法無(wú)論在何種情況下都需要遍歷所有的測(cè)試集合才能返回查詢結(jié)果，而 TUSK 只需要訪問(wèn)其中很小一部分?jǐn)?shù)據(jù)，大概 80%以上的數(shù)據(jù)都被算法剪枝過(guò)濾掉了，這些實(shí)驗(yàn)結(jié)果也從另一個(gè)角度反映了 TUSK 算法的查詢性能要明顯優(yōu)于基準(zhǔn)算法。

【參考文獻(xiàn)】：
期刊論文
[1]指數(shù)衰減模式下基于矩陣機(jī)制的差分隱私流數(shù)據(jù)發(fā)布算法[J]. 吳英杰,葛晨,張立群,孫嵐.  中國(guó)科學(xué):信息科學(xué). 2017(11)
[2]面向數(shù)據(jù)發(fā)布和分析的差分隱私保護(hù)[J]. 張嘯劍,孟小峰.  計(jì)算機(jī)學(xué)報(bào). 2014(04)
[3]云數(shù)據(jù)管理系統(tǒng)中查詢技術(shù)研究綜述[J]. 史英杰,孟小峰.  計(jì)算機(jī)學(xué)報(bào). 2013(02)
[4]云環(huán)境下一種隱私保護(hù)的高效密文排序查詢方法[J]. 程芳權(quán),彭智勇,宋偉,王書(shū)林,崔一輝.  計(jì)算機(jī)學(xué)報(bào). 2012(11)
[5]不確定性Top-K查詢處理[J]. 李文鳳,彭智勇,李德毅.  軟件學(xué)報(bào). 2012(06)
[6]P2P環(huán)境下面向不確定數(shù)據(jù)的Top-k查詢[J]. 孫永佼,袁野,王國(guó)仁.  計(jì)算機(jī)學(xué)報(bào). 2011(11)
[7]集合和字符串的相似度查詢[J]. 林學(xué)民,王煒.  計(jì)算機(jī)學(xué)報(bào). 2011(10)
[8]一種面向不確定對(duì)象的可見(jiàn)k近鄰查詢算法[J]. 王艷秋,徐傳飛,于戈,谷峪,陳默.  計(jì)算機(jī)學(xué)報(bào). 2010(10)
[9]面向查詢服務(wù)的數(shù)據(jù)隱私保護(hù)算法[J]. 朱青,趙桐,王珊.  計(jì)算機(jī)學(xué)報(bào). 2010(08)
[10]不確定性數(shù)據(jù)管理技術(shù)研究綜述[J]. 周傲英,金澈清,王國(guó)仁,李建中.  計(jì)算機(jī)學(xué)報(bào). 2009(01)

博士論文
[1]面向多維不確定數(shù)據(jù)的若干查詢處理關(guān)鍵技術(shù)的研究[D]. 徐傳飛.東北大學(xué) 2013



本文編號(hào)：2952879