直方圖應(yīng)用中的新型數(shù)據(jù)管理技術(shù)研究.pdf

1、直方圖由20世紀(jì)統(tǒng)計(jì)學(xué)的偉大奠基人Karl Pearson提出，經(jīng)過多年的發(fā)展，現(xiàn)已成為估計(jì)統(tǒng)計(jì)對(duì)象分布特性的一個(gè)重要數(shù)學(xué)工具。直方圖在信息科學(xué)的眾多領(lǐng)域都得到了廣泛應(yīng)用，其中包括統(tǒng)計(jì)數(shù)據(jù)發(fā)布、概率數(shù)據(jù)建模和多媒體數(shù)據(jù)特征抽取和表征等。然而在這些實(shí)際應(yīng)用中，使用直方圖對(duì)數(shù)據(jù)建模仍面臨一些挑戰(zhàn)性問題，表現(xiàn)在以下幾個(gè)方面:首先，近期研究發(fā)現(xiàn)直接發(fā)布敏感數(shù)據(jù)集的直方圖仍有可能泄露用戶隱私;其次，現(xiàn)有的直方圖相似性搜索技術(shù)僅使用簡(jiǎn)單的距離函數(shù)（

2、例如Lp范式距離）來量化直方圖之間的相似性，容易造成搜索結(jié)果與人們的直觀預(yù)期不匹配。為了解決這些問題，本文對(duì)直方圖應(yīng)用中的新型數(shù)據(jù)管理技術(shù)進(jìn)行研究，對(duì)于直方圖應(yīng)用的進(jìn)一步發(fā)展具有重要的理論意義和實(shí)用價(jià)值。
　　本文以直方圖的典型應(yīng)用場(chǎng)景為出發(fā)點(diǎn)，從直方圖的構(gòu)造、直方圖的索引存儲(chǔ)和直方圖的相似性搜索這三個(gè)方面展開研究。在直方圖的構(gòu)造方面，信息安全領(lǐng)域的研究人員發(fā)現(xiàn)在敏感數(shù)據(jù)集上直接構(gòu)造出的數(shù)據(jù)統(tǒng)計(jì)直方圖有可能泄露用戶的隱私。由于對(duì)攻

3、擊者的背景知識(shí)和攻擊手段沒有嚴(yán)格的假設(shè)，差分隱私（Differential Privacy）作為一種新型的隱私保護(hù)模型受到了廣泛關(guān)注，因此構(gòu)造高可用性的差分隱私直方圖是當(dāng)下數(shù)據(jù)安全領(lǐng)域的研究熱點(diǎn)。本文設(shè)計(jì)了新型的差分隱私直方圖的構(gòu)造方法，在保證直方圖不會(huì)泄露用戶敏感信息的前提下盡可能提高直方圖的數(shù)據(jù)可用性。在直方圖的索引存儲(chǔ)和相似性搜索方面，計(jì)算機(jī)視覺領(lǐng)域的研究發(fā)現(xiàn)基于EMD距離(Earth Mover's Distance)對(duì)直方圖進(jìn)

4、行相似性搜索能夠返回與人們預(yù)期的搜索結(jié)果相一致的搜索結(jié)果。然而求解EMD距離的函數(shù)卻具有三次方的高時(shí)間復(fù)雜度。本文設(shè)計(jì)了面向EMD距離的高效索引存儲(chǔ)結(jié)構(gòu)，并在此基礎(chǔ)上分別提出了數(shù)據(jù)庫環(huán)境下和數(shù)據(jù)流環(huán)境下基于EMD距離的直方圖相似性搜索算法。本文提出的算法都極大提高了基于EMD距離的相似性搜索的處理效率。本文的主要研究?jī)?nèi)容和創(chuàng)新點(diǎn)包括:
　　第一，提出了基于均值的差分隱私直方圖構(gòu)造方法，包括Mean-NoiseFirst方法和Mea

5、n-StructureFirst方法。利用V-Optimal直方圖構(gòu)造技術(shù)將原始頻數(shù)序列上位置鄰近取值相似的頻數(shù)合并到一個(gè)數(shù)據(jù)桶。由于使用均值統(tǒng)計(jì)量作為數(shù)據(jù)桶內(nèi)各個(gè)頻數(shù)的代表頻數(shù)，可以有效平滑或降低為了滿足差分隱私模型限制而向數(shù)據(jù)桶內(nèi)各個(gè)頻數(shù)上添加的噪音。使用真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)評(píng)估證明:Mean-NoiseFirst方法和Mean-StructureFirst方法構(gòu)造的差分隱私直方圖比之前最好的方法構(gòu)造的差分隱私直方圖在數(shù)據(jù)精度上有顯著

6、提高。
　　第二，提出了基于中位數(shù)的差分隱私直方圖構(gòu)造方法，包括Median-NoiseFirst方法和Median-StructureFirst方法。由于使用中位數(shù)統(tǒng)計(jì)量作為數(shù)據(jù)桶內(nèi)各個(gè)頻數(shù)的代表頻數(shù)，有效避免了數(shù)據(jù)桶內(nèi)添加的極端值噪音對(duì)數(shù)據(jù)桶代表頻數(shù)的影響。實(shí)驗(yàn)證實(shí)，基于中位數(shù)的Median-StructureFirst方法不但顯著優(yōu)于基于均值的Mean-StructureFirst方法，更比之前最好的Boost方法和Priv

7、elet方法所構(gòu)造直方圖的數(shù)據(jù)質(zhì)量平均提高了1倍。當(dāng)隱私保護(hù)需求較高時(shí)，基于中位數(shù)的Median-NoiseFirst方法顯著優(yōu)于基于均值的Mean-NoiseFirst方法。而在隱私保護(hù)需求較低時(shí)，Mean-NoiseFirst方法則更有優(yōu)勢(shì)。特別地，Median-NoiseFirst方法構(gòu)造的差分隱私直方圖在應(yīng)答單位范圍計(jì)數(shù)查詢時(shí)的結(jié)果精度比之前最好的Dwork方法的結(jié)果精度最多提高了5倍。
　　第三，提出了面向EMD距離的直

8、方圖高效索引和存儲(chǔ)策略。利用線性規(guī)劃中的對(duì)偶理論將直方圖映射至一維實(shí)數(shù)空間，繼而采用經(jīng)典的B+樹結(jié)構(gòu)索引一維映射空間內(nèi)的各個(gè)映射點(diǎn)。為了使索引結(jié)構(gòu)高效支持基于EMD距離的相似性搜索，搭建了直方圖在B+樹上的鍵值和直方圖之間的EMD距離的聯(lián)系，為基于索引的數(shù)據(jù)剪枝提供了基本思路。與先前提出的索引結(jié)構(gòu)不同，基于該索引結(jié)構(gòu)進(jìn)行剪枝過濾能夠保證查詢結(jié)果的完備性，即不會(huì)錯(cuò)誤過濾掉任一查詢結(jié)果對(duì)象。
　　第四，以面向EMD距離的直方圖索引和存

9、儲(chǔ)策略為基礎(chǔ)，提出了數(shù)據(jù)庫環(huán)境下基于EMD距離的直方圖相似性搜索算法，包括范圍查詢算法和k-近鄰查詢算法。在處理范圍查詢時(shí)，將對(duì)直方圖記錄集的范圍查詢轉(zhuǎn)變?yōu)閷?duì)B+樹索引鍵值空間的子范圍查詢，成功過濾掉了大量無關(guān)記錄。在處理k-近鄰查詢時(shí)，根據(jù)當(dāng)前的查詢結(jié)果自動(dòng)調(diào)整B+樹上的搜索范圍，成功約簡(jiǎn)了k-近鄰查詢的搜索空間。基于真實(shí)數(shù)據(jù)集進(jìn)行大量實(shí)驗(yàn)評(píng)估證實(shí)了本文提出的基于EMD距離的相似性搜索技術(shù)的查詢處理性能比先前最好方法的查詢處理性能平均

10、提高了1倍。
　　第五，提出了數(shù)據(jù)流環(huán)境下基于EMD距離的直方圖連續(xù)相似性搜索技術(shù)。利用EMD距離的對(duì)偶線性規(guī)劃問題的可行解高效過濾數(shù)據(jù)流上的無關(guān)直方圖記錄。同時(shí)結(jié)合數(shù)據(jù)流的特性，設(shè)計(jì)了可行解動(dòng)態(tài)更新策略和多查詢共享策略，進(jìn)一步提高系統(tǒng)的查詢處理效率。以本文提出的基于EMD距離的連續(xù)相似性搜索技術(shù)為基礎(chǔ)，開發(fā)了在線視頻流盜版視頻幀實(shí)時(shí)檢測(cè)系統(tǒng)。由于使用了一系列針對(duì)數(shù)據(jù)流環(huán)境的查詢優(yōu)化策略，演示系統(tǒng)在同時(shí)處理80個(gè)連續(xù)查詢時(shí)，仍能保