Re: [Cbor] "ordered hash"

Hi Alexander, 

Thanks for this, it's good to see people thinking in similar directions!

Cheers, 

Kio 

On 2020-07-30 8:46, Alexander Pelov wrote:

> 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 <cabo@tzi.org> wrote: 
> 
>> On 2020-07-30, at 01:44, Kio Smallwood <kio@mothers-arms.co.uk> 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
>> CBOR@ietf.org
>> https://www.ietf.org/mailman/listinfo/cbor