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

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

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

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

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

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

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

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

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

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

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