Comparing to Implicit Interval Tree with Interpolation Index (iitii) about coitrees HOT 3 OPEN

Specifically on van Emde Boas indexing, given the overall tree geometry, can one figure in constant time, the array index of the i'th node (from the left) on tree level L?

@mlin #2 has some related discussions.

from coitrees.

iitii is sensitive ("adaptive", if I'm spinning it) to the data; it's easy to come up with scenarios that revert it to cgranges equivalence. Though those may be rare in practice, coitrees has a constant factor advantage in the worst case.

If the data are compliant then iitii potentially has an asymptotic (in dataset size) advantage in the average case, since it skips search iterations. But the predicate is a strong one, so it's not a clear win. I've spent a little time trying to come up with a way to combine the ideas in iitii and coitrees, but nothing to speak of yet. It would help if it were possible to write closed or more-closed formulae for the van Emde Boas indices.

I don't know if I'd recommend iitii for practical usage anytime soon, it's more of an exploratory side-project for me. The indexing scheme in GenomicSQLite is not as fast, but has many other (overwhelming?) practical utilities.

from coitrees.

Specifically on van Emde Boas indexing, given the overall tree geometry, can one figure in constant time, the array index of the i'th node (from the left) on tree level L? iitii is just regressing the interval positions on that.

from coitrees.