Can we speed up the median calculation?

[joshuak94]

Current median calculation:

• Take a list of records
• Add the start/end to a new list.
• Sort the new list.
• Get the median. This is done for each node.

Instead, we could do something like this:

• Pre-make the sorted vector with starts/ends.
• Recursively get all of the medians.
• In construction, keep track of which median to use for which node. In theory, this only requires sorting n records one time, whereas the original method sorts n records logn times.

[joshuak94]

This probably isn't possible, because you can't know in advance which records will be removed from the list...

[joshuak94]

Use merge instead of adding to a new list and then sorting...

[joshuak94]

Another thing to consider is we might be fine to use the mean instead of the median, since we wouldn't really expect any "outlier" intervals...