Faster Dynamic Compressed d-ary Relations
Diego Arroyuelo, Guillermo de Bernardo, Travis Gagie, and Gonzalo
Navarro
The k^2-tree is a successful compact representation of binary relations that
exhibit sparseness and/or clustering properties. It can be extended to
d
dimensions, where it is called a k^d-tree. The representation boils
down to a long
bitvector. We show that interpreting the k^d-tree as a dynamic trie on the
Morton codes of the points, instead of as a dynamic representation of the
bitvector as done in previous work, yields operation times that are below the
lower bound of dynamic bitvectors and offers improved time performance in
practice.