The optimum would seem to be a compression algorithm which could be patched without decompressing. I would guess that the number of actual compression frames that change on a daily basis is actually quite small and some sort of post compression diff could be used. How this would actually work (how many bytes of the file change) I don't know and I would assume that the algorithm would have to be specifically designed to allow it.

Apologies if you have already considered it but Kosmos may do the job with a lot less work (designed as a desktop rather than server application)

osm.wiki/index.php/Kosmos