Incremental equivalent to BTreeMap

[dylanede]

I'm looking at using Adapton and IODyn, and while the documentation for Adapton looks very good, it is very sparse for IODyn, so I'm not sure about the intended use cases of each of the data structures implemented. For my particular use case of incremental computation, I would need something like an incremental version of BTreeMap - i.e. the operations consist of at least insertion, removal, lookup, and iterating over an ordered range of keys to read values. Would any of the existing data structures in IODyn be either directly suitable for this use case, or usable as building blocks for another data structure? If not, is this something that would be straightforward to construct?

Thanks

[matthewhammer]

Hi @dylanede! Thanks for your interest in Adapton/IODyn.

It looks like you want something close to our proposed finite map types: https://github.com/cuplv/iodyn.rust/issues/20

This work is on-going, and we don't yet have a complete story with good performance results. We intend to have more to show in a month or two. We are aiming for a technical report that will flesh out IODyn in that timeframe: https://github.com/cuplv/iodyn.rust/issues/22

Part of this work consists of Rust implementation stuff, and a lot of it consists of theoretical work that we are doing now.

[matthewhammer]

If you want more details, let me know: https://gitter.im/Adapton

In the meantime, if you have some code (or pseudo code) that would use the BTreeMap (or a generic finite map), I'd be interested in taking a look, and imagining how well it would work in Adapton once we have this data structure finished.

[dylanede]

A typical operation would be to iterate over one collection, and look up the "nearest" key-value-pairs in another collection as it does so, perform simple calculations involving these values and put the result in another collection (which might have similar operations done on it at a later stage). By "nearest", I mean the existing keys that would immediately precede and succeed a given key were that key to be inserted into the ordered collection. This is something BTreeMap handles well. It looks like the kvlog structure you're working on doesn't provide the ordering constraint on the keys that would make this possible.

Another operation would be to "scan" over an ordered collection, producing another collection that effectively has dependencies from each value to the one preceding it. Again this relies on the collections being ordered.

A more mundane operation would be creating a new collection by mapping over another one.

The "source" collections (not the product of a scan, map, or other iterative process) would be modified by random access insertion and replacement. If deletion were to happen (not an absolute necessity) it could be restricted to granularity of blocks of keys.

The keys in question are in practice i64, representing timestamps.

Sorry that wasn't pseudocode, but hopefully that gives you the gist of what I'm after.

Regardless of whether Adapton ends up suitable for this use case, I'm still interested in using it in the future, as it looks to be filling an unclaimed niche in the Rust ecosystem. Good work!

[matthewhammer]

Ah, I see. Thanks for clarifying how you want to use the BTreeMap. I see what you mean about the ordering being important for many of those use cases, and how the key-value log wouldn't give you want you want there.

Folds over sorted sequences: We have a random access sequence (represented as a balanced "level tree", or a focused "zipper"), which also permits sequential folds (from left to right, or right to left). If this sequence were sorted, you would have the fold that you wanted in some of the use cases you described above.

Finding nearby keys in sorted sequences: With a bit more work, we may be able to permit random lookup by key on a sorted level tree, but we haven't done that yet. I don't foresee a technical problem with implementing that, though. We have a good representation of finite sets that we can use to cache which sub-trees have which keys, to help a recursive walk from the room find the nearest matching key(s).

Of course, this would only work if the sequence (represented as a level tree) has sorted keys (leaf elements). In the past, we've implemented sorting for representations similar to these sequences, and we plan to do so for the latest implementation here, but to my knowledge have not done so yet. It's on our (rather long) todo list, though.

cc @kyleheadley