Home > Archive > Compression > June 2004 > Checksums to test inclusion property.
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Checksums to test inclusion property.
|
|
|
| I was hoping someone might be able to help me with the solution (or
provide relevant pointers) to a problem I have been trying to figure
out.
Given a set of 'n' 4K blocks (x1, x2, x3 ........xn) and storage for
saving individual block signatures (where each is much smaller than 4k
e.g 4 - 32 bytes) and also a cumulative signature for the entire set,
again << 4k, I want to come up with a set of checksum functions
satisfying the following properties :-
a) The checksum functions should be such that it should be possible to
detect (correction is not a requirement) if a block read is part of
the above set by only using the cumulative signature. The position of
the block within the above set is known and hence can be used as a
parameter. Storage for individual block signatures *cannot* be read
for this purpose.
b) When writing a block, the mechanism for updating the signature can
only access the current stored cumulative signature and the signature
of the block being overwritten. Again the position of the block is
known and hence can be used. The original block being overwritten
*cannot* be read.
I guess I'm looking for some form of a positional checksum which
allows me to test inclusion property.
Thanks
AG
| |
| Colin Andrew Percival 2004-06-29, 3:55 pm |
| AG <atulgoel@hotmail.com> wrote:
> Given a set of 'n' 4K blocks (x1, x2, x3 ........xn) [...]
> and also a cumulative signature for the entire set,
> again << 4k, I want to come up with a set of checksum functions
> satisfying the following properties :-
> a) The checksum functions should be such that it should be possible to
> detect (correction is not a requirement) if a block read is part of
> the above set by only using the cumulative signature. The position of
> the block within the above set is known and hence can be used as a
> parameter.
This is clearly impossible for large n; consider storing either 0 or 1 in
each block, and "reading" the values back by detecting if the block is
equal to zero.
Colin Percival
|
|
|
|
|