Database Reference
In-Depth Information
7.2.2
The Partenum Signature
Partenum is another popular string signature that has been proposed in
the literature. The partenum signature uses a fine-grained partitioning
and enumeration strategy, more complex than that of signature PG x .
The partenum signature is constructed by first partitioning the vectors
into
θ +1
2 partitions of consecutive dimensions from the permuted uni-
verse h (Λ). A simple counting argument proves that given two vectors
with Hamming distance smaller or equal to θ , then at least one of the
θ +1
2 partitions has Hamming distance smaller or equal to one. Hence,
we can construct one signature per partition with a new, smaller Ham-
ming threshold θ = 1, and use the union of all partition signatures
as the signature of the string. For each partition we use PG y as the
signature of the partition, by constructing 1 + y sub-partitions. The
partenum signature consists of the union of the
2 PG y signatures.
An example is shown in Figure 7.4. Given a pair of vectors, if all parti-
tions are within Hamming distance greater than one, then the pair of
vectors cannot be within Hamming distance smaller equal to θ . Hence,
a pair of vectors is reported as a candidate if and only if at least one
of the PG y signatures corresponding to the same partition matches
(meaning that at least one of the θ +1
θ +1
partitions has Hamming distance
2
smaller or equal to one).
The probability of a positive answer for partenum can be expressed
similarly to that of Lemma 7.9.
Fig. 7.4 First, the vector is split into θ + 2 = 2 partitions. A pair of vectors is within Ham-
ming distance three iff the vectors have Hamming distance smaller equal to one in at least
one of the two partitions. Then, for each partition we create a PG 1 signature. We can use
the PG 1 signatures to eciently verify whether each partition between a pair of vectors is
within Hamming distance one. If at least one such partition exists, it is possible that the
pair of vectors is within Hamming distance three, and we report the pair as a candidate.
 
Search WWH ::




Custom Search