Re: Mercurial Linux Symposium paper

On Tue, Jul 25, 2006 at 10:06:03PM -0400, Daniel Berlin wrote:
> So, i've explored about a billion different delta algorithms, including
> what mercurial does.
>

> I've got an improved delta algorithm based on rabin fingerprinting that
> is roughly 10% faster than xdelta most of the time, and up to 50-60%
> faster on larger (>a couple meg) files. The delta sizes are either the
> same, slightly smaller, or slightly larger, depending :)
>

Because I've just spent ages trying to find out what Rabin fingerprinting
is, I'll say that there's some interesting information at [1]. Not
interesting directly (it's primarily about duplicate elimination rather
than delta encoding), but interesting because it contains electronic
copies of some of the relevant papers (at [2]), which I couldn't find
anywhere else.

Dan, are you working on something like that described in this paper?

  M. Ajtai, R. Burns, R. Fagin, D. D. E. Long, and L. Stockmeyer.
  Compactly encoding unstructured inputs with differential compression.
  Journal of the ACM, 49(3):318367, May 2002.
  http://www.cs.utah.edu/~shanth/stuff/research/dup_elim/delta_encode.pdf

I've not read it properly yet, but it seems to be based around similar
concepts.

Regards,
Malcolm

[1] http://www.cs.utah.edu/~shanth/stuff/research/dup_elim/final.txt
[2] http://www.cs.utah.edu/~shanth/stuff/research/dup_elim/

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Wed Jul 26 12:55:41 2006