直方圖應用中的新型數據管理技術研究.pdf

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

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

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

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

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

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

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

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

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

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