針對K-匿名數(shù)據(jù)的top-k查詢問題研究.pdf

1、隨著網(wǎng)絡(luò)信息技術(shù)的飛速發(fā)展，今天，信息在社會生活中扮演著越來越重要的角色。各行各業(yè)都需要從海量的數(shù)據(jù)中搜索對自身有用的信息來以滿足發(fā)展。但這樣有很大的可能導(dǎo)致個體隱私的泄露，隨之而來的是對各種隱私信息（如日常習(xí)慣、敏感信息、不良歷史、信譽程度、以往病史等）保護的研究，以減少信息泄露的風(fēng)險。在多數(shù)的隱私保護模型中最有代表性的是K-匿名隱私保護模型，K-匿名模型經(jīng)過長時間的研究，已經(jīng)形成了較完善的理論體系。K-匿名數(shù)據(jù)則越來越多地出現(xiàn)在網(wǎng)絡(luò)

2、上。在傳統(tǒng)數(shù)據(jù)庫中，數(shù)據(jù)的確定性和精確性均是確定，而K-匿名數(shù)據(jù)卻是不確定的，這就使得數(shù)據(jù)在存儲、查詢、挖掘以及管理方面遇到了各種問題，這些匿名的數(shù)據(jù)不能被企業(yè)很好的應(yīng)用并發(fā)揮最大的功效。因此，提高數(shù)據(jù)的可用性是K-匿名模型亟待解決的問題，而查詢是數(shù)據(jù)應(yīng)用的一個主要操作。
　　首先，根據(jù)Certainty(確定性問題)的定義即(V)I∈rep(T)(S(c)I)，其中S是給定的元組集，T是給定的某一k-匿名表，從計算理論的角度，通

3、過多項式時間歸約的方法，證明該問題是CoNP-完全的。再結(jié)合已有的查詢問題的復(fù)雜性為k-匿名隱私保護模型中不確定性數(shù)據(jù)查詢方法的研究奠定了理論基礎(chǔ)。
　　其次，通過研究已有的不確定數(shù)據(jù)Top-k查詢算法，再結(jié)合K-匿名數(shù)據(jù)來源的獨特性和其表現(xiàn)形式的不同，探索了一種基于有向圖的K-匿名數(shù)據(jù)的Top-k查詢處理方法，用以提高K-匿名數(shù)據(jù)的可用性，滿足更多不同的應(yīng)用需求。(1)運用有向圖建立高效的索引結(jié)構(gòu)，并在此基礎(chǔ)上提出了新的查詢算法

4、DiGU-Topk(U-Topk based on direct graph)，該算法主要常用于一些需要排序的查詢中;(2)采用優(yōu)先隊列對此算法進行優(yōu)化，提出了DiGOPTU-Topk(U-Topk based on direct graph with optimize queue)算法，使得算法能夠更快的收斂到目標頂點;(3)根據(jù)剪枝規(guī)則對有向圖進行修剪，提出了DiGPU-Topk(U-Topk based on direct gra