Попробовал xdelta для создания патчей. Для теста взял совсем далёкие по времени карты, да ещё и эксопртированные разными сервисами, да ещё и по разным границам вырезанные:
Карта Эстонии 11 октября, 74.9 MB, от extract.bbbike.org
Карта Эстонии 1 декабря, 84.3 MB, конвертировал сам
Результат - патч в 32.0 MB.
Чтобы убедиться, что это не просто фокус за счёт того, что патч в сжатом формате - сжал исходную карту винраром, с максимальными опциями. Вышло 52.0 MB.
(upd)
Попробовал bsdiff в тех же условиях. Патч вышел ещё меньше, 23 MB. Но он сожрал 2гб памяти и рожал несколько минут 