Re: [Cbor] "ordered hash"

[Alexander Pelov <[e-mail]>]

Hi all,

Several years ago we had this type of discussion for the use of
COMI/CORECONF. We called it in a couple of different ways:
- DeterministicMultimaps
- COMAP (CBOR Order-preserving Multimap)
- Order-Keeping Multimap (OKMM)

Unfortunately, I don't think we published any open specs outside the Task
Force (although we did have quite some discussion at CORE WG).

One of the latest specs we had is attached (sorry for the PDF).

Cheers,
Alexander



On Thu, Jul 30, 2020 at 6:08 AM Carsten Bormann <[e-mail]> wrote:

> On 2020-07-30, at 01:44, Kio Smallwood <[e-mail]> wrote:
> >
> > I wrote a proposal for tag 272 ordered map.
> >
> > https://github.com/Sekenre/cbor-ordered-map-spec
>
> (272 is already taken: Non-UTF-8 CESU-8 string.)
>
> > Unfortunately no one has approved the tag allocation or given me any
> guidance on how to proceed.
>
> Let’s look into this.
>
> I think this idiom is frequent enough that it should get a 1+1 tag.
>
> The difference from a map is that this is both order-preserving and
> allowing duplicate keys; whether you want one or two of these properties on
> the application data model level may differ between applications.
>
> The traditional alist (association list) is
>
> AList<K, V> = [* [K, V]]
>
> By using the exact structure of a map (except that the array head will
> have double the argument that the map head has), we can save 1 byte per k/v
> pair (“flattened alist”):
>
> FAList<K, V> = [* (K, V)]
>
> So [[“a”, 1], [“b”, 2]] becomes [“a”, 1, “b”, 2]
>
> I’m not sure which of these MCR was inquiring on.  The first is definitely
> an alist, and there is no need for a new term.  The second can be called an
> ordered multimap, but there are other structures that also deserve this
> name.
>
> If adjacent duplicate keys of non-trivial size are likely in an ordered
> multimap, a better version of the multimap is:
>
> MList<K, V> = [* (K, [* V])]
>
> So [[“aaa”, 1], [“aaa”, 2], [“bbb”, 3]] becomes [“aaa”, [1, 2], “bbb”, [3]]
>
> If V can never be an array (*), this can be further optimized into:
>
> OMList<K, V> = [* (K, [2* V] / V)]
>
> So [[“aaa”, 1], [“aaa”, 2], [“bbb”, 3]] becomes [“aaa”, [1, 2], “bbb”, 3]
>
> Further refine by using delta coding for the keys (works best with sorted
> keys), etc.  Also, a map can be used for the outer structure if order
> preservation is not actually needed:
>
> MMap<K, V> = {* K => [* V]}
> OMMap<K, V> = {* K => [2* V] / V}
>
> There are many idioms to choose from; it would probably be best to define
> tags for at least each of the ones listed here.  I think FAList (what Kio
> proposed) is the one that will see the most use.
>
> Grüße, Carsten
>
> (*) Or extra-wrap just arrays:
> OEMList<K, V> = [* (K, [2* V] / [V .and [* any]] / V)]
>
>
> _______________________________________________
> CBOR mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/cbor
>