負(fù)數(shù)據(jù)庫生成算法及應(yīng)用研究.pdf

1、信息的負(fù)表示(Negative Representation)是受人工免疫系統(tǒng)啟發(fā)而來的，與一般的信息表示的區(qū)別在于負(fù)表示通過不在傳統(tǒng)數(shù)據(jù)集中的內(nèi)容來表示原信息。負(fù)數(shù)據(jù)庫(Negative Databases，NDB)作為負(fù)表示的一種形式，在信息安全和隱私保護(hù)上有著重要的研究意義和良好的應(yīng)用前景。負(fù)數(shù)據(jù)庫與正數(shù)據(jù)庫的區(qū)別在于負(fù)數(shù)據(jù)庫存儲的內(nèi)容是正數(shù)據(jù)庫補(bǔ)集的一種壓縮形式。已有的工作表明，負(fù)數(shù)據(jù)與SAT公式是等價的。
　　 負(fù)數(shù)據(jù)

2、庫已經(jīng)被用于信息隱藏，隱私數(shù)據(jù)收集和密碼負(fù)認(rèn)證。一些與負(fù)數(shù)據(jù)庫相關(guān)的典型的應(yīng)用是基于難以逆轉(zhuǎn)的負(fù)數(shù)據(jù)庫，因此，生成難以逆轉(zhuǎn)的負(fù)數(shù)據(jù)庫具有重要的研究意義。此外，負(fù)數(shù)據(jù)庫也適用于正數(shù)據(jù)庫上的一些操作（如:選擇、插入、刪除、更新、交集、并集等），因此，正數(shù)據(jù)庫上的一些應(yīng)用也可以適用于負(fù)數(shù)據(jù)庫。
　　 本論文旨在研究負(fù)數(shù)據(jù)庫生成算法及應(yīng)用。本論文的主要研究內(nèi)容和創(chuàng)新之處有如下幾個方面。
　　 (1)提出基于前綴算法和q-hidd

3、en算法的混合算法，用于生成完備并且難以逆轉(zhuǎn)（對諸如WalkSAT之類的采用局部搜索策略的SAT求解器）的單串負(fù)數(shù)據(jù)庫。該混合算法先生成一個小規(guī)模的完備的負(fù)數(shù)據(jù)庫，然后使得這個完備的負(fù)數(shù)據(jù)庫難以逆轉(zhuǎn)，進(jìn)而同時具有完備性和難解性。
　　 (2)提出p-hidden算法，該算法能生成難以逆轉(zhuǎn)（對諸如WalkSAT之類的采用局部搜索策略的SAT求解器，以及諸如zChaff之類的采用DPLL策略的SAT求解器）的單串負(fù)數(shù)據(jù)庫。該算法通過

4、兩個可變的參數(shù)來控制負(fù)數(shù)據(jù)庫中不同類型的記錄的比例。與只用一個可變參數(shù)的q-hidden算法相比較，p-hidden算法可以對局部搜索的求解器造成更強(qiáng)的誤導(dǎo)，進(jìn)而生成更加難以逆轉(zhuǎn)（對諸如WalkSAT之類的采用局部搜索策略的SAT求解器）的單串負(fù)數(shù)據(jù)庫。
　　 (3)提出難以逆轉(zhuǎn)（對諸如WalkSAT之類的采用局部搜索策略的SAT求解器，以及諸如zChaff之類的采用DPLL策略的SAT求解器）的多串負(fù)數(shù)據(jù)庫生成算法。首先，依據(jù)

5、單串負(fù)數(shù)據(jù)庫的難解區(qū)域，該算法以數(shù)據(jù)庫中兩個串的中心串為基礎(chǔ)來生成負(fù)數(shù)據(jù)庫，通過控制負(fù)數(shù)據(jù)庫中不同類型的記錄的比例，使得局部搜索策略的求解器被誤導(dǎo)到向數(shù)據(jù)庫中兩個串的反方向搜索，即這兩個串都位于各自對應(yīng)的難解區(qū)域內(nèi)，進(jìn)而生成難以逆轉(zhuǎn)的兩串負(fù)數(shù)據(jù)庫。其次，本文將難以逆轉(zhuǎn)的兩串負(fù)數(shù)據(jù)庫生成算法推廣到多個串的情況，生成難以逆轉(zhuǎn)的多串負(fù)數(shù)據(jù)庫。
　　 (4)提出在典型的單串負(fù)數(shù)據(jù)庫上進(jìn)行k近鄰分類和k均值聚類的算法。這兩個算法的核心都是