T Cell–Inspired Algorithms - Immunological Computation: Theory and Applications - page 106

“hard to reverse,” but this specifi c algorithm does not provide any properties that
can be used to prove the empirical performance of any given NDB (Figure 4.21).
In Figure 4.21, the main loop generates all prefi xes that are not represented by
the PDB similar to the prefi x algorithm. It then uses a Pattern_Generate function
to randomize the wildcards and assign positions in the bit positions at the end of
the prefi x. h e algorithm can generate every possible entry that is not a positive
record. An example of NDBs generated by the preceding two algorithms is shown
as follows (Table 4.5):

Randomize_ NDB algorithm
Let w i denote an i -bit prefix and W i a set
of i -length patterns.
1. i

[log 2 ( l )]
2. Initialize W i to the set of every pattern
of i bits.
3. Set W i +1 to every pattern not present in
DB s w i +1 but with prefix in W i
4. for each pattern V p in W i +1 {
5. Randomly choose 1

←

≤ ≤ l

6. for k = 1 to j do {
7. V pg ←

Pattern_Generate ( ( DB ), V p )

8. Insert V pg in NDB .}}
9. Increment i by one
10. Set W i to every pattern in DB s w i
11. Return to step 3 as long as i < l.

Figure 4.21 Algorithm B, the randomized NDB algorithm. This generates an
NDB that is intuitively diffi cult to reverse, but it is not tunable and provides no
guarantee of “hardness.” (From Esponda F., S. Forrest and P. Helman. Enhancing
Privacy through Negative Representations of Data . UNM Computer Science
Technical Report TR-CS-2004-18, March 2004.)

Table 4.5 Column 1 Gives an Example of DB and Column 2 Gives

NDB Generated by Prefi x Algorithm and Column
3 Gives NDB Generated by Randomized Algorithm

DB Prefi x NDB Randomized NDB

0011 10** 10**

0101 000* *00*

1100 011* 011*

1111 0010 0*10

0100 0*00

1101 1*01

1110 **10

*110
*010