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

[Emile Cormier <[e-mail]>]

Something else that needs to be discussed/decided is whether we include
tags for list-like collections, like what I proposed in
https://github.com/ecorm/cbor-map-like/tree/with-lists

In that alternate proposal, I had included arbitrary key + uniform value
maps in order to maintain "one-hot" bit encoding for both the maps and
lists. If we don't want to include arbitrary key + uniform value maps to
save on 4 tags, the interpretation of the list tag bits will be more
complicated, but not terribly so.

On Fri, Jun 11, 2021 at 7:19 PM Emile Cormier <[e-mail]>
wrote:

> 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
>>
>