I recently worked on a project where, to cut down on space, I built a custom "compressor" for lists of tree-like records. You might think of a Person record with N past addresses although this was not the actual domain. No records were cross-linked (at least not formally in the code) and the records were trees, not more general DAGs. The data contained a lot of enumerated data types (address type, gender, etc.). I didn't really care about the space usage for 1K records, but I cared about 1M. I used variable length encoding (a hacked-up subset of the Apache Avro project) for integers to take advantage of most of them being small in the datasets. Lots of lookup tables for enumerated values and commonly-repeated in practice string values. Implicit "keying" based on a record schema to avoid specifying key identifiers all over (our data was not very sparse, so this beat out a serialized pattern of KVKVKV etc.). I thought about taking advantage of most strings having very limited character sets and doing Huffman encoding per data element type, but the results were good enough before I got there. A co-worker also noted that, because parts of these records were de-normalized data, subtree pattern recognition could provide huge gains. I added some record length prefixes to allow individual records to be read one-at-a-time so that the entire dataset would not have to be read into memory at once. IIRC, compression speed was 2-3x gzip(9), and large record sets were 1/10th the size of using Java serialization plus gzip. [Yes, Java serialization is likely the worst way to serialize this sort of data]

Was all of this worth it? It solved the problem of not burning through network and memory, but it was a local optima. The root problem was that this data came from another system which did not provide repeatable reads, and providing them would have been a massive effort. However, our users wanted to meander through a consistent data set over the course of an hour or so. To provide this ability to browse, we throw these records into a somewhat transient embedded H2 DB instance. The serialized format is required primarily to provide high availability via a clustered cache. In retrospect, I would have pushed for using a MongoDB-esque cluster which could have replaced both H2 (query-ability) and the need for the the serialized format (HA).

It surprised me that there were no open source projects (at least Java-friendly ones) which provided compression schemes taking advantage of the combination of well-defined record schema and redundant-in-practice data. Kyro (http://code.google.com/p/kryo) comes closest as a space-efficient serializer, but it treats each record individually. Protobufs, Thrift, Avro, etc. are designed for RPC/Messaging wire formats and, as an explicit design decision (at least in the protobufs case) optimize on speed and the size of an individual record vs. the size of many records. The binary standards for JSON and XML beat the hell out of their textual equivalents, but they don't have any tricks which optimize on patterns in the repeated record structures.

Is this just an odd use case? Does anyone else have a similar need?