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

Groups > comp.programming > #3977

Detecting differences

Show all headers | View raw

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.

Back to comp.programming | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

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

csiph-web