dcjones
commented
4 years ago Yes, this is all correct.
I do use some auxiliary arrays do do the ordering. I don't think this is strictly necessary, but it's faster than reordering things in place. So space is still linear, but larger than cgranges or some of the other algorithms.
I haven't tried computing child pointers (implicit veb). Storing pointers (explicit veb) adds space, which means more memory to fetch, potentially slowing search down, but I suspect that effect is so small that it's swamped by any non-trivial computation needed at each step when searching implicit veb.
The specific layout I use is what this paper described as "in-order veb":
Lindstrom, P., and D. Rajan. 2014. “Optimal Hierarchical Layouts for Cache-Oblivious Search Trees.” In 2014 IEEE 30th International Conference on Data Engineering, 616–27.
There they benchmark many possible tree layouts (fig. 4). In-order veb is close to their optimal, while being somewhat simpler. They find that implicit versions tend to be slower for complex layouts like veb. (On the other hand, they also claim that implicit BFS order can be faster. I have tried this and didn't find this to be the case for my implementation and computer.)
So overall, I've tried to optimize time often at the expense of space.
lh3
I would like to add more discussions on coitrees in my bedtk manuscript. I want to make sure my following understanding is correct. cgranges encodes the interval tree in the in-order layout. coitrees reorders the array into the van Emde Boas (vEB) layout. It seems that in the implementation, you are keeping the index of the left and right children for efficient access. This increases the memory of the index by two integers per element. Brodal et al (2002) seems to give a method to compute the index of a child using a precomputed table of O(log N) space instead of O(N). Have you considered something along this line? Also, I haven't read the source code to generate the vEB layout. Do you use an auxiliary array? If so, that would increase the peak memory. Is that correct? Thanks.