Research On The Negative Database Generation Algorithms And Applications

Negative Representation is inspired by Artificial Immune System. Different from the general information representation, Negative Representation stores the contents not in the positive database to represent the original information. Negative Databases (NDB), which is a form in Negative Representation, is very promising in information security and privacy protection. Different from the positive databases, the negative databases store the compression form of the complementary set of the positive databases. Presently work indicates that NDBs are equivalent to SAT formulas.Negative Database has been used in information hiding, privacy data collection and negative authentication. Some NDB-related applications are based on hard-to-reverse Negative Databases. So generating hard-to-reverse NDB is of great research significance. In addition, some operation in positive databases (such as selection, insert, delete, update, intersection and union) could be conducted in NDBs. So some applications in DBs could be conducted in NDBs, too.The purpose of the dissertation is to study the NDB generation algorithms and the applications. The main research work and innovation consist of the following four parts.(1) The prefix algorithm and q-hidden algorithm are mixed for generating complete and hard-to-reverse (for the SAT solvers with local search strategy such as WalkSAT) single NDBs. This hybrid algorithm generates a complete single NDB with small size, and then makes the NDB hard-to-reverse. So the generated NDBs could be both complete and hard-to-reverse.(2) The p-hidden algorithm is proposed for generating hard-to-reverse (for the SAT solvers with local search strategy such as WalkSAT, and that with DPLL such as zChaff) single NDBs. This algorithm uses two adjustable parameters to control the proportions of different kinds of NDB records. Comparing with the typical q-hidden algorithm, the p-hidden algorithm could cause more misleading for the solvers with local search strategy. So the p-hidden algorithm could generate more hard-to-reverse (for the SAT solvers with local search strategy such as WalkSAT) single NDBs. (3) An algorithm is proposed for generating hard-to-reverse (for the SAT solvers with local search strategy such as WalkSAT, and that with DPLL such as zChaff) multistring NDBs. Firstly, depending on the hard region for single NDBs, this algorithm generates NDBs based on the central strings of the two strings in the original DB. By controlling the proportion of different kinds of NDB records, the solvers with local search strategy is misguided to the reverse direction of the two strings simultaneously. That could make the two strings are both located in its respective hard region. Then the algorithm for generating hard-to-reverse double NDBs is extended to generate hard-to-reverse multistring NDBs.(4) Two algorithms are proposed for k nearest neighbor classification and k means clustering in typical single NDBs, respectively. The core of these two algorithms is a novel method for estimating the Hamming distance between a binary string and an NDB. Based on this method for calculating the Hamming distance, the k nearest neighbor classification algorithms and the k-means clustering algorithm could be conducted in NDBs.This dissertation focuses on the NDB generation algorithms and applications. Firstly, the algorithm for generating single NDBs are studied, and two algorithms are proposed for generating single NDBs. Secondly, the algorithm for generating hard-to-reverse multistring NDBs is studied. Finally, the algorithms for classifying and clustering in NDBs are proposed. This dissertation has reference value for the study of the relevant theories and methods in NDBs.