Data mining In negative database

Abstract EN

Over the few recent years knowledge discovery (data mining) has been establishing itself as one of the major disciplines in computer science with growing industrial environment.

Research in data mining will continue and even increase over coming decades.

In the other hand the need for data to still private against any hacking still growing dramatically.

This paper shares in the way of data privacy applications through applying data mining techniques on negative database.

The most important concept of a negative database is that a set of records DB is represented by its complement set.

That is, all the records not in DB are represented, and DB itself is not explicitly stored.

It is shown that a database consisting of n records, / -bit-length records can be represented negatively using O (ln) records.

It is also clear that membership queries applied on DB can be processed over the negative representation itself in time no worse than linear in its size and that reconstructing the database DB represented by a negative database NDB given.

Assume total universe u of finite-length records (or strings), all of the same length L, and defined over a binary alphabet.

We logically divide the space of possible strings into two disjoint sets: Positive or real database DB representing the set positive records (holding the real information of interest), and u -DB denoting the set of all strings not in DB.

We assume that DB is uncompressed (each record is represented explicitly), but we allow u - DB to be stored in a compressed form called NDB.

We refer to DB as the positive database and NDB as the negative database.