1
$\begingroup$

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.

  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 D.W. Lower bounds on single-source shortest paths in directed graphs, but it doesn't look like being applicable to this case.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. May 12 '17 at 20:41
  • $\begingroup$ 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. $\endgroup$ – Veksi May 13 '17 at 13:27
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov May 13 '17 at 19:52
  • $\begingroup$ This probably requires a lot more I can put in currently. How do you suggest should be proceeded? $\endgroup$ – Veksi May 14 '17 at 9:09
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov May 14 '17 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.