Time and Space Tradeoffs in Version Control Storage
ericsink.com
ericsink.com
First try a zlib of the entire thing, not each version, since it will effectively find all the common lines and not repeat them.
Next, instead of pure keyframes, let the keyframes themself be chained. That should save a ton of space, without being really slow. (And then recurse if you like - every ten keyframes, add a supra-keyframe, etc. recurse all the way down.)
I would like to see his code and test data, but I couldn't find a link.