Node age processed data for graphical use

[jrosindell]

We will have a date on every node of the tree (high precision).

We will want dervied data though because

• the full data is too heavy for the full tree
• and because fully to scale dates will not look good in any case.

There are three concepts for this we'll want 1 for sure and 2 or 3 (I used 2 in the separate demo but suspect 3 may be better)

1. Geological age (and epoch)
2. age rounded to multiples of something (e.g. 25 My)
3. Locally weighted mean branch length
4. Sliding window mean branch length

[jrosindell]

Geological

I digitised 42 bands from the International Commission on Stratigraphy (feels like the right place) data is CC-BY

geologicalperiods.csv

https://stratigraphy.org/supplementary#data

There is also
https://github.com/i-c-stratigraphy/chart/blob/main/chart.ttl
Which would require extra pain to parse and not part of an MVP.

There are 42 bands including all those that I think would be meaningful to the public

Basic bare bones option - use geological period e.g. jurassic, triassic (15 of these)
Mid option - use epoch e.g. 'upper jurassic' (42 of these)

Beyond this is not digitised above e.g. the the Toarcian or Oxfordian ages within the Jurassic (not heard of them? nor have I) => not needed for public consumption.

42 categories means still possible to have a single character mapping to each epoch.

[jrosindell]

weighted mean

Ratio of branch length with locally weighted mean branch length - short summary of the algorithm is traverse the tree passing as you go a weighted mean branch length - each time you take the mean you have of the parent (or child depending on direction) and mean that with the next branch length but with a weighting e.g. 0.8 so that the local branch gets weight 1 in the running mean, its parent gets 0.8, its parent gets 0.8^2 and influence recedes geomaetrically. Nice because it requires one traverse of the tree down and one up to do all

Next value = (current branch length + weight * previous value ) /(1+weight)
weight < 1

[jrosindell]

Sliding window

this is harder and more computationally intensive (but still fast I think)

The idea is inspired by moving averages of differnet widths used for market technical analyses. Decisions are informed by metics such as is current price above or below the x day moving average.

Here's what our algorithm would look like

depth first (from root) traverse of the tree store for each node the sum of its branch length and that of its parent also store 2 on each node (except the root) because at this stage 2 is the denomenator needed for a moving average (except at the root where there is no parent)

repeat the depth first traverse but this time use the output of the last traverse so you get the sum of the node, parent and grandparent.

repeat depth first traverse for as many times as needed to get correct width of moving average (I suspect no more than 5 would make any sense)

optional: repeat with beadth first traverse from leaves and combine the up and doward facing moving averages. I do wonder if that would be necessary - it makes the causality messy and requires more coding. In a way it's 'neater' to let the lower branches be influenced by comparison to the higher branches but not the reverse. The same consideration would apply to the weighted mean approach as well (do we consider near branches in both directions or not)

The final calculation both for sliding window and weighted mean approaches would look something like

log(branch length / localised mean from one of the approaches)

what we do next is interesting as well but I'd be inclined to truncate at 1 so anything less than the localised mean just gets 1 whilst anything longer gets a discrete number - I don't think we need any more categories than the other sections (at most 50, but might get away with much less)

[jrosindell]

I guess we probably want to start with 2 and 3 for easiest route forwards then experiemnt with graphics using those ideas before going further with this issue.

[lentinj]

For Geological, we're essentially rounding date to the nearest geological period, would we be better off storing an approximate date and then keeping the mapping in OneZoom? Fitting the Mya range from the CSV in a 16 bit int (0 to 65535) seems not unreasonable. This would be 2 bytes per-node, but if it saves having multiple arrays to look up in then we come out even.

For weighted mean, ete4 offers helpers for this (or at least roughly the same concept). That page may be worth a browse to see if there's anything else potentially useful.

For reference, here's a list of possible array data types that we could potentially use. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Typed_arrays#typed_array_views, although Float16Array is possibly too fresh to rely on support for.

[jrosindell]

Thanks @lentinj that's really useful.

Here's what ChatGPT thinks about the load time

~500 KB – 1 MB → basically instant, nobody notices
1 – 2 MB → still feels smooth if not blocking
2 – 3 MB → acceptable if your UI shows something quickly
3 – 5 MB → now you’re relying on good UX tricks

5 MB → you’re testing people’s patience

2.3 million nodes * 2 bytes ~ 5mb (testing patience area)

Both leaves and nodes have a branch leading to them with a branch length so even though we can assume age = 0 on all leaves for the tree without extinct species that's more of a special case in the general scheme of where this is going so acutally its more like double = 10mb (unacceptable). compression might help a lot but we don't yet know how much

I guess you're in agreement that pushing the tree calculations onto the client is too much of a performance drain (and double work if we later decide it has to be on the server) even if it's convenient for experimentation. So the experimentation state should be a bank of byte arrays that are made on the server and that we choose between but don't require them at the same time for the same view.

Based on all this I think we're looking at 1 byte data types: basically Int8Array Uint8Array or Uint8ClampedArray. Looks like we want Uint8Array in pretty much every instance because individual bits can more easily be carved out.

I wonder if it might be elegant considering all the requirements to use the same byte array for leaves and nodes - remember we have an OZID from 1 to 2.3M for leaves and essentially the same number of nodes (tree is bifurcating). Hence we could use first 4 bits for leaf data and second 4 for node data on recording the discrete processed branch length data?

First step is that we build a set of Uint8Array 1 byte arrays aligned to nodes and or leaves, load one or two at a time but never more than that, do all calculations for array generation on the server, use compression, experiment with colours and geometry.

[lentinj]

2.3 million nodes * 2 bytes ~ 5mb (testing patience area)

Yes, but this is ignoring gzip or roaring bitmaps, and that we'll hopefully be still rendering in the mean time, so the user won't be twiddling thumbs (although how we manage branches suddenly exploding in length is another matter, maybe we can't).

I guess you're in agreement that pushing the tree calculations onto the client is too much of a performance drain

Not sure to be honest. But I don't think we need to tie ourselves to one or the other particularly at this point.

Hence we could use first 4 bits for leaf data and second 4 for node data on recording the discrete processed branch length data?

It's an interesting idea. It might mess with any compression scheme we use though.