This might be a daft quesstion, but here comes. I became intriqued about data serialization formats and tried to look for research on what could be the information theoric lower bound on encoding object graphs to storage (wire) format. I'm sure there is applicable research into this, but I it seems my base information is failing to provide the right terms to feed into search engines.
I have tried something like "information theoretic lower bound graph node types" and variants, but the results are something I don't understand could be related to the question in hand. Maybe something I could understand is the paper Succinct Posets, which states
Partially ordered sets, or posets, are useful for modelling relationships between objects, and appear in many different areas, such as natural language processing, machine learning, and database systems. As problem instances in these areas are ever-increasing in size, developing more space efficient data structures for representing posets is becoming an increasingly important problem
Maybe, though, I'm having the wrong terms. Maybe I understand it wrongly on how could one decode a type of concrete instantiations of classes be encoded efficiently, i.e. maybe preserving the order of internal fields, their types and the data. Is there research that could be useful for this purpose?
As for a concrete pondering on this subject, here's one useful speclet on what I'm thinking besides the Wikipedia link.
<edit 2017-05-13: As per question by D.W. That is a good clarification to ask. I am not sure if this is the right forum to ask and if I ask makes sense, but I try to construct this in more detail.
- I see there are multiple serialization systems that each try to be as space efficient and fast as possible when encoding to the storage/wire representation. Then when decoding back to a class, the systems try to be as fast as possible.
- What comes to part
1., it looks the systems are vague on the principles, if any, on how close they come to the possible bounds.
When I'm searching on this, I'm searching things like:
- Lower bound graph compression.
- Lower bound information compression.
- Succinct data structures (e.g. Burrows-Wheeler).
- Encoding object graph lower bound.
I get interesting links for sure, but I fail to find on something that would somehow treat "nodes" (e.g. objects having data member fields in programs) and the graph structure that the objects point to other objects together with compressing the relations and data types for fast reconstruction of that structure.
I do get interesting links with those search terms in
3., but nothing I feel is on this particular matter. So, what I perhaps hope are pointers to what to look for – if it's possible to understand from this description – in way of research applicable to this rather practical problem. This isn't that easy. I have looked for here too, I found, for instance, the question asked recently by D.W. Lower bounds on single-source shortest paths in directed graphs, but it doesn't look like being applicable to this case.