Grouping Heuristics, Online Algorithms, and Ordering

[l-monninger]

Summary

There have been a series of questions about grouping heuristics generally and how they contribute to node performance in their application against Celestia. I think there are a fair number of things we can do to improve the API and potentially get some additional performance bumps.

Questions

Ownership

I've been thinking about the grouping heuristics and problems with cloning vs. moves. Have you considered passing the items by reference and only letting the grouping heuristics morph indexing information?

Streaming and Online Algorithms

Should there be design space for grouping on a stream: if new items become available while the operation is performed, should they be somehow mixed in with the intermediate grouping data, or would that make it too complex?

Ordering

Are grouping heuristics generally allowed to arbitrarily reorder blobs between groups, or should the groups be non-overlapping subsequences of the original sequence?

[l-monninger]

Streaming and Online Algorithms in Current Application

So, yes, the usage of our current grouping heuristics is actually over a stream of transactions. We read--up to a certain max duration and max size--these transactions to form a block and likewise construct blocks for a max duration before forming our "point." We then apply our group heuristics to this "point."

Notably however, the most important of our heuristics is the First Fit Bin Packing--which is in fact an online algorithm. However, when operating over a stream, we have to make a tradeoff between latency and this true online-ness. That is, we have to manufacture points or risk undefined latency.

Ideally, we would model this a little bit with a cost function for our users to decide what an ideal algorithm could be here.

[l-monninger]

Streaming and Online Algorithms and the Grouping Heuristic API

At the moment, I believe that we should be using the Grouping Heuristic API independently. It's intersection with common streaming and online algorithms should be in its application to computing over points.

[l-monninger]

Ordering

It would be nice to wrap grouping heuristic algs that respect order in some kind of type-state or trait. That way, the ordering safety or not is always known expressively.

[mzabaluev]

Ordering

It would be nice to wrap grouping heuristic algs that respect order in some kind of type-state or trait. That way, the ordering safety or not is always known expressively.

We can develop the abstract framework further, but if the implementation consuming these heuristics only needs order-preserving algorithms, traits and types for more general grouping would effectively be dead code. The data structure to optimally represent segmentation of a sequence is different, and processing it can be much more efficient (as you can just take slices out of the original sequence instead of random access extractions).

[l-monninger]

The data structure to optimally represent segmentation of a sequence is different, and processing it can be much more efficient (as you can just take slices out of the original sequence instead of random access extractions).

So, this would primarily concern changing what we currently refer to as the distribution, a Vec<GroupingOutcome> and likewise GroupingOutcome a Vec<Elemental> outcome to something like one of the following:

• Linked List
• Rope (B-tree Rope)

Any other candidates?

Currently, the grouping heuristic is being used in places where our $n$ is small and the primary cost is actually the function.

[l-monninger]

Ownership

We can accept and return references. This will push cloning down to the developer against the API. If this is reasonable, I say we go ahead.