Re: [Cbor] Maps: Need for additional compactness?

[Emile Cormier <[e-mail]>]

Hi Everyone,

I've watched the recording of the meeting starting from the Map-like
slides. Here are my comments...

The MList encoding becomes a pessimization if there are few duplicate keys
and a large number of key-value pairs. It might not be so bad to assume
that keys tend to be generally short - they are often things like database
IDs.

The OMList encoding not allowing array values seems like a showstopper to
me.

For OEMList, I'm not clear on this part:

So [[“aaa”, 1], [“aaa”, 2], [“bbb”, 3], [“ccc”, [4]]] becomes [“aaa”, [1,
> 2], “bbb”, 3, [“ccc”, [[4]]]]
>

Is the resulting singleton array [“ccc”, [[4]]] used as an indicator so
that the decoder interprets [[4]] as the array [4] to be associated with
the key "ccc"? If so, how is the decoder supposed to distinguish this from
an array key in heterogeneous maps? This problem is more obvious if you
change the example to this:

[[“aaa”, 1], [“aaa”, 2], [“bbb”, [3]], [“ccc”, 4]] becomes [“aaa”, [1, 2],
[“bbb”, [[3]]], “ccc”, 4]

and a decoder interprets this as:
Key,     Value
"aaa",    1
"aaa",    2
[“bbb”, [[3]]],    "ccc"
4,    <missing value>

It seems to me the only way to avoid the possible pessimization of MList,
while also avoiding ambiguities with keys/values that can themselves be
arrays/maps, is to introduce a new CBOR special value (or "abuse" CBOR
break) to indicate the "shared key" special case. This has the disadvantage
that it can't be directly transcoded to JSON.

Another possibility would be to use a special tag so that [[“aaa”, 1],
[“aaa”, 2], [“bbb”, [3]], [“ccc”, 4]] becomes [“aaa”, <MultiValuesTag>[1,
2], [“bbb”, [3]], “ccc”, 4]. While this can be transcoded to JSON by
dropping the tag, an application consuming the resulting JSON would still
be vexed by the ambiguity of the (“aaa”, [1, 2]) pair even if it knows it's
decoding a multimap.

While the desire to avoid repeating duplicate keys is understandable, these
compression schemes lead to the following complications for a generic CBOR
encoding/decoding library:

1. For something like OEMList, when encoding a multimap, an encoder needs
to look ahead to see if there are multiple values associated with the same
key.

2. A simple SAX-like decoder can no longer emit alternating (key, value)
events without having to memorize the shared key, which can be a complex,
nested entity. This can be overcome by emitting a MultiMapValuesStart
"meta" event after emitting the shared key, and then the SAX handler knows
there will be multiple value events associated with the same key while
populating the multimap. MultiMapValuesStart then has to be treated as a
special state (along with the usual ArrayStart and MapStart) in the
decoder's state stack.

If there ends up being a viable compression scheme, the specification
should still allow an application to use the "naive" scheme with repeated
keys. If everyone agrees with this, then we should be able to proceed
without the optimized encodings and add them later, while preserving
backward compatibility with the naive scheme.

Cheers,
Emile Cormier

On Wed, Jun 9, 2021 at 1:03 PM Christian Amsüss <[e-mail]>
wrote:

> Hello Emile, hello Kio,
> and hello CBOR group in general,
>
> during the last CBOR interim meeting[1], the question as to how far we'd
> like to go in map-like data structure optimization came up. These do not
> relate to the information model (these variations are covered in tags),
> but only to how data is put on the wire, so it'd be about variations of
> not placing items into inner lists when avoidable, delta encoding for
> ordered lists or other compression steps.
>
> An idea floated during the meeting was go with the obvious encoding now,
> and only go there later if use cases really need those.
>
> What are your needs with respect to compactness? Does it suffice to
> address the high-level (homogenity) aspects of map data structures?
>
> BR
> Christian
>
> [1]
>   minutes:
> https://datatracker.ietf.org/meeting/interim-2021-cbor-10/materials/minutes-interim-2021-cbor-10-202106021600-00
>   relevant slides:
> https://datatracker.ietf.org/meeting/interim-2021-cbor-10/materials/slides-interim-2021-cbor-10-sessa-map-like-data-draft-bormann-cbor-cddl-map-like-data-00
>   video: https://www.youtube.com/watch?v=IfrxbspRcQo
>   ... and also from me: sorry for the time mismatch.
>
> --
> There's always a bigger fish.
>   -- Qui-Gon Jinn
> _______________________________________________
> CBOR mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/cbor
>