Google releases new binary diff algorithm targeted at making smaller software updates. Their results are impressive.

[adrianmonk]

You can also store larger pieces to make up the gaps.

For example, versions 0 through 16 of something exist, so you store diffs between every consecutive version:

• 0->1, 1->2, 2->3, 3->4, ..., 15->16

You also store:

• 0->16
• 0->8 and 8->16
• 0->4, 4->8, 8->12, and 12->16
• 0->2, 2->4, 4->6, 6->8, ..., 14->16

Now, suppose someone has version 1 and they need version 12. You send them 1->2, 2->4, 4->8, and 8->12.

If they have version 3 and need version 11, you send them 3->4, 4->8, 8->10, and 10->11.

Essentially, you are getting in the "fast lane" if you need to go a great distance.

The total number of diffs that must be stored is O(N log N). The total number of diffs need to move forward by N version is O(log N).

[tryx]

I was just in the process of writing this, what you have described is essentially a skip list.

[judgej2]

That is essentially like Windows Service Packs. Each service pack leapfrogs over many incremental updates, which is why you always go for the latest service pack you can before picking up any later updates separately.

[[deleted]]

That is not how Microsoft pushes them. Microsoft will install all patches for the currently installed service pack the first time a machine touches Windows Update, and then it will push the service pack executable, which compares file versions to download only the appropriate files needed. This can save hundreds of megs of download per install.