Skip navigation
Pages 884-890
First published 2 September 2013

Real-Valued Negative Databases

Dongdong Zhao, Wenjian Luo


The negative database (NDB) is the negative representation of original data. Existing work has demonstrated that NDB can be used to preserve privacy and hide information. However, most work about NDB is based on binary representation. In some applications which are naturally descripted in real-valued space, the binary negative database is hard to be applied appropriately. Therefore, the real-valued negative database is proposed in this paper, and reversing the real-valued negative database is proved to be an NP-hard problem. Moreover, an effective algorithm for generating real-valued negative databases is given. Finally, an example of applying the realvalued negative database to the privacy-preserving data publication is descripted, and it shows that the real-valued negative database is valuable in practice.