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ù)的查詢帶來了新的挑戰(zhàn)。另外,隨著云計(jì)算的普及,人們對于數(shù)據(jù)的隱私保護(hù)越來越重視,在數(shù)據(jù)安全與可用性之間需要作出審慎的權(quán)衡。針對不確定數(shù)據(jù)top-k查詢處理面臨的挑戰(zhàn),對該問題的研究工作分別從以下三個維度進(jìn)行開展:首先,針對不確定數(shù)據(jù)上查詢語義多樣性導(dǎo)致查詢復(fù)雜度高的問題,給出了基于期望編輯距離的不確定字符串top-k查詢的形式化定義,提出了一個新的距離語義概率n-gram集合映射距離,進(jìn)而結(jié)合查詢語義以及概率n-gram分詞的特點(diǎn),提出基于概率n-gram集合映射距離的近似匹配過濾算法,并通過建立基于概率n-gram劃分的多層倒排索引以及頻率矩陣來進(jìn)一步優(yōu)化算法實(shí)現(xiàn)。通過對該算法進(jìn)行時間復(fù)雜度分析和一系列對比實(shí)驗(yàn)性能評測,驗(yàn)證該算法實(shí)現(xiàn)對不確定字符串top-k查詢的高效處理,相比于基準(zhǔn)算法具有較高的剪枝過濾能力和良好的可擴(kuò)展性。其次,針對查詢候選集規(guī)模膨脹導(dǎo)致單... 

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

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

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

【部分圖文】：

基于概率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 的近似匹配過濾算法定理 2.1 給定兩個不確定字符串1S 和2S ，如果 (,)12SSe 的值小于等于 τ，那么 至少包含有 (S,S) 12 個 n-gram 的 gram 映射編輯距離 GED 小于等 (0 n)，其中(S,S){|S|,|S|}-n1-(,,)1212 max n + (2即，1S 和2S 至多有 ( , ,n)個 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ù)集中字符串平均長度的變化，TUSK 算法和 Baseline 基準(zhǔn)算法（在以下實(shí)驗(yàn)數(shù)據(jù)圖中標(biāo)注為 Direct）在執(zhí)行時間和過濾效果上的性能對比。通過分別令 y 0,1,2,3，分別得到字符串平均長度從 13.6, 27.2, 40.8 到 54.4 不等的不確定字符串集合。如圖 2.5（a）所示，隨著字符串長度的增加，TUSK 和 Baseline 基準(zhǔn)算法的查詢時間都隨之增大，但無論是從查詢時間絕對值還是查詢時間增長的速率來看，TUSK 都明顯優(yōu)于基準(zhǔn)算法；同時，如圖 2.5（b）所示，基準(zhǔn)算法無論在何種情況下都需要遍歷所有的測試集合才能返回查詢結(jié)果，而 TUSK 只需要訪問其中很小一部分?jǐn)?shù)據(jù)，大概 80%以上的數(shù)據(jù)都被算法剪枝過濾掉了，這些實(shí)驗(yàn)結(jié)果也從另一個角度反映了 TUSK 算法的查詢性能要明顯優(yōu)于基準(zhǔn)算法。

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

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



本文編號：2952879