<p>This might be a daft quesstion, but here comes. I became intriqued about <a href="https://en.wikipedia.org/wiki/Comparison_of_data_serialization_formats" rel="nofollow noreferrer">data serialization formats</a> 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.</p>

<p>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 <a href="https://arxiv.org/pdf/1204.1957.pdf" rel="nofollow noreferrer">Succinct Posets</a>, which states</p>

<blockquote>
  <p>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 </p>
</blockquote>

<p>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?</p>

<p>As for a concrete pondering on this subject, <a href="https://gist.github.com/ReubenBond/edffb6615e02a87ac22f00131290e2c2" rel="nofollow noreferrer">here's one useful speclet</a> on what I'm thinking besides the Wikipedia link.</p>

<p>&lt;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.</p>

<ol>
<li>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.</li>
<li>What comes to part <code>1.</code>, it looks the systems are vague on the principles, if any, on how close they come to the possible bounds.</li>
</ol>

<p>When I'm searching on this, I'm searching things like:</p>

<ol>
<li>Lower bound graph compression.</li>
<li>Lower bound information compression.</li>
<li>Succinct data structures (e.g. Burrows-Wheeler).</li>
<li>Encoding object graph lower bound.</li>
</ol>

<p>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.</p>

<p>I do get interesting links with those search terms in <code>1.</code>, <code>2.</code> and <code>3.</code>, but nothing I feel is on this particular matter. So, what I perhaps hope are pointers to what to look for &ndash; if it's possible to understand from this description &ndash; 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. <a href="https://cstheory.stackexchange.com/questions/25920/lower-bounds-on-single-source-shortest-paths-in-directed-graphs">Lower bounds on single-source shortest paths in directed graphs</a>, but it doesn't look like being applicable to this case.</p>

CC BY-SA 3.0
2017-05-12T20:41:14.243Z
What kind of bound are you looking for?  What are the parameters?  What form would you want the bound to take?  How do you plan to use the bound?  What efforts/progress have you made so far, to try to construct a bound?  Right now the question is pretty open-ended, so it's not clear it is a good fit for the site yet.  We want questions to be self-contained so people don't have to click through to read other web pages, so material on an external web page ("speclet") isn't ideal.
D.W.
CC BY-SA 3.0
2017-05-13T13:27:25.737Z
Hi! Indeed, I don't know if this is a good fit question on this site. I tried to clarify what I'm looking for. It would look like theoretical experts could more easily point to applicable research if I could describe this in understandable terms. If I'm asking from programmers, well, it would be like me figuring out something via web searches and swapping ideas.
Veksi
CC BY-SA 3.0
2017-05-13T19:52:49.380Z
This question needs a lot of work. I understand  you may lack the background to formulate it precisely, but in that case maybe this is not the place to ask. What you describe sounds vaguely like succinct data structures, but it's not clear what operations you want to be efficiently supported, or how efficiently.
Sasho Nikolov
CC BY-SA 3.0
2017-05-14T09:09:12.493Z
This probably requires a lot more I can put in currently. How do you suggest  should be proceeded?
Veksi
CC BY-SA 3.0
2017-05-14T12:35:38.383Z
You are asking me how to proceed given that you do not have the time to make your question precise enough to be answerable? I do not know how to answer that.
Sasho Nikolov
CC BY-SA 3.0
2017-05-14T21:07:01.743Z
Consider a few very small instances of your problem. Then start removing irrelevant details. Then try describing it using graphs, sets, etc. If you write that up, people might be be able to refine it further?
nish2575
CC BY-SA 3.0
2017-05-15T09:06:17.573Z
Oh, I worded poorly. What I meant is that should I somehow close this question or answer myself or what would be right course of action in this case. Maybe not just delete this question. Maybe accept the answer by `user45367`?
Veksi
<ds.data-structures><lower-bounds><it.information-theory><succinct>
Information theoretic lower-bound on object graph serialization
Veksi
# Information theoretic lower-bound on object graph serialization

(Asked by: username_0 on 2017-05-12)

This might be a daft quesstion, but here comes. I became intriqued about [data serialization formats](https://en.wikipedia.org/wiki/Comparison_of_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](https://arxiv.org/pdf/1204.1957.pdf), 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](https://gist.github.com/ReubenBond/edffb6615e02a87ac22f00131290e2c2) on what I'm thinking besides the Wikipedia link.

1. 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.
2. 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:

1. Lower bound graph compression.
2. Lower bound information compression.
3. Succinct data structures (e.g. Burrows-Wheeler).
4. 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 `1.`, `2.` and `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 username_1 [Lower bounds on single-source shortest paths in directed graphs](https://cstheory.stackexchange.com/questions/25920/lower-bounds-on-single-source-shortest-paths-in-directed-graphs), but it doesn't look like being applicable to this case.

**Tags:** ds.data-structures, lower-bounds, it.information-theory, succinct

> **Comments:**
> **username_1**: What kind of bound are you looking for?  What are the parameters?  What form would you want the bound to take?  How do you plan to use the bound?  What efforts/progress have you made so far, to try to construct a bound?  Right now the question is pretty open-ended, so it's not clear it is a good fit for the site yet.  We want questions to be self-contained so people don't have to click through to read other web pages, so material on an external web page ("speclet") isn't ideal.  
> **username_0**: Hi! Indeed, I don't know if this is a good fit question on this site. I tried to clarify what I'm looking for. It would look like theoretical experts could more easily point to applicable research if I could describe this in understandable terms. If I'm asking from programmers, well, it would be like me figuring out something via web searches and swapping ideas.  
> **username_2**: This question needs a lot of work. I understand  you may lack the background to formulate it precisely, but in that case maybe this is not the place to ask. What you describe sounds vaguely like succinct data structures, but it's not clear what operations you want to be efficiently supported, or how efficiently.  
> **username_0**: This probably requires a lot more I can put in currently. How do you suggest  should be proceeded?  
> **username_2**: You are asking me how to proceed given that you do not have the time to make your question precise enough to be answerable? I do not know how to answer that.  
> **username_3**: Consider a few very small instances of your problem. Then start removing irrelevant details. Then try describing it using graphs, sets, etc. If you write that up, people might be be able to refine it further?  
> **username_0**: Oh, I worded poorly. What I meant is that should I somehow close this question or answer myself or what would be right course of action in this case. Maybe not just delete this question. Maybe accept the answer by `user45367`?  

---

## 0 answers

