Negative representations of information

Fernando Esponda, Stephanie Forrest, Paul Helman

Research output: Contribution to journalArticlepeer-review

29 Scopus citations


In a negative representation, a set of elements (the positive representation) is depicted by its complement set. That is, the elements in the positive representation are not explicitly stored, and those in the negative representation are. The concept, feasibility, and properties of negative representations are explored in the paper; in particular, its potential to address privacy concerns. It is shown that a positive representation consisting of n l-bit strings can be represented negatively using only O (ln) strings, through the use of an additional symbol. It is also shown that membership queries for the positive representation can be processed against the negative representation in time no worse than linear in its size, while reconstructing the original positive set from its negative representation is an N P-hard problem. The paper introduces algorithms for constructing negative representations as well as operations for updating and maintaining them.

Original languageEnglish (US)
Pages (from-to)331-345
Number of pages15
JournalInternational Journal of Information Security
Issue number5
StatePublished - 2009
Externally publishedYes


  • Data representations
  • Immune-inspired algorithms
  • Negative databases
  • Privacy information hiding

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Safety, Risk, Reliability and Quality
  • Computer Networks and Communications

Cite this