Evolutionary Dynamic Database Partitioning Optimization for Privacy and Utility

Distributed database system (DDBS) technology has shown its advantages with respect to query processing efficiency, scalability, and reliability. Moreover, by partitioning attributes of sensitive associations into different fragments, DDBSs can be used to protect data privacy. However, it is complex to design a DDBS when one has to optimize privacy and utility in a time-varying environment. This paper proposes a distributed prediction-randomness framework for the evolutionary dynamic multiobjective partitioning optimization of databases. In the proposed framework, two sub-populations contain individuals representing database partitioning solutions. One sub-population utilizes a Markov chain-based predictor to predict discrete-domain solutions for database partitioning when the environment changes, and the other sub-population utilizes the random initialization operator to maintain population diversity. In addition, a knee-driven migration operator is utilized to exchange information between two sub-populations. Experimental results show that the proposed algorithm outperforms the competing solutions with respect to accuracy, convergence speed, and scalability.