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

Groups > comp.programming > #3979

Re: Detecting differences

Show all headers | View raw

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.
 

Back to comp.programming | Previous | Next — Previous 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