Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #3977 > unrolled thread

Detecting differences

Back to article view | Back to comp.programming

Contents

  Detecting differences Giuliano Bertoletti <gbe32241@libero.it> - 2013-10-27 10:42 +0100
    Re: Detecting differences Nobody <nobody@nowhere.com> - 2013-10-27 10:52 +0000
    Re: Detecting differences malcolm.mclean5@btinternet.com - 2013-10-27 12:22 -0700

#3977 — Detecting differences

Hello,

I'm trying to find an efficient algorithm to solve the following problem.

I've two databases A and B that must be kept in sync.

Both contain the same fixed number of elements (scores for tournament 
matches) and most of the time one is the mirror copy of the other.
Sometimes however changes are applied either to A or B.

On a regular basis the two DB communicate and in that occasion the 
algorithm should resync them.

I've a way to resolve conflicts, so these are not a problem.

However I wish to use as less bandwith as possible to sync them.

Ideally if no changes are applied to either of them, the communication 
should be very short (in terms of bytes transfered) and in general 
proportional to the differences.

The major problem is that the elements are many and small, so my idea 
would be to hash them (with a crypto algorithm as SHA1) in different 
groups and compare the hashes to detect changes.

I could for example hash the entire sets, exchange the hashes and if 
they match I'm done. If they do not match however, I've to hunt down 
which elements have changed and I'm not sure which is the best way of 
grouping the items to miminize data exchanging.

My idea is to organize hashes for n items in this way:

Hash(0, n); Hash(0, n/2); Hash(n/2, n); Hash(0, n/4); Hash(n/4, n/2); 
Hash(n/2; 3n/4); Hash(3n/4; n); ...

so if Hash(0, n) does not match, I send Hash(0, n/2); Hash(n/2, n); and 
possibly narrow down the mismatch set.

Clearly if many differences have occurred, I could end up in a worse 
position than simply retransmitting the whole data.

Does it makes sense? Is there a cleverer way?

Giulio.

[toc] | [next] | [standalone]

#3978

On Sun, 27 Oct 2013 10:42:15 +0100, Giuliano Bertoletti wrote:

> Does it makes sense? Is there a cleverer way?

rsync uses a single level; it selects a block size based upon the size of
the file, then sends a list of hashes, one for each block. Any block
with a hash mismatch is sent in its entirety.

If you want to use multiple levels, the higher-level hashes should
be calculated over the lower-level hashes rather than over the data.

The optimum number of levels depends upon the probability of a difference.

If differences are rare, then more levels will be more efficient. For a
single difference, the asymptotically-optimal branching order is 3. If it
wasn't constrained to be an integer, it would be e = 2.71828... (the value
at which x/log(x) is a minimum).

As differences become more common, you may as well skip the first few
levels, as larger blocks will almost always have at least one difference.
In short, there's no point in sending higher-level hashes which are
likely to result in a mismatch.

If differences are extremely common, then you'll end up sending the entire
file anyhow and there's no point in sending any hashes.

[toc] | [prev] | [next] | [standalone]

#3979

On Sunday, October 27, 2013 9:42:15 AM UTC, Giuliano Bertoletti wrote:
>
> I'm trying to find an efficient algorithm to solve the following problem.
>  
> I've two databases A and B that must be kept in sync.
> 
> On a regular basis the two DB communicate and in that occasion the 
> algorithm should resync them.
> 
> Ideally if no changes are applied to either of them, the communication 
> should be very short (in terms of bytes transfered) and in general 
> proportional to the differences.
> 
Recursive hashing.

Index the database along something, it doesn't matter what, as long as you
can sensibly divide it into two roughly equal halves easily.
Then has the who database, divide it, hash those halves, divide them and so
on, until you reach single records.
So if the databases are identical then the top level hashes are identical, and 
no data needs to be exchanged. If there is one change, you do effectively
a binary search. If there are a few changes, it's several binary searches
in parallel. If the whole database is different, you've added a factor of
log N to your exchange time.

Note for this to work you need to divide on A-M N-Z, etc, not "first N/2 
entries, second N/2 entries". Otherwise a small change will have a cascading
effect on the divisions.
 

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web