Interleaved K2-tree: Indexing and Navigating Ternary Relations
Sandra Álvarez-García, Nieves Brisaboa, Guillermo de
Bernardo, and Gonzalo Navarro
We propose a new compressed and self-indexed data structure that we call
Interleaved K2-tree (IK2-tree), designed to compactly represent and
efficiently query general ternary relations. The IK2-tree is an evolution
of the K2-tree initially designed to represent Web graphs
but later used to represent general binary relations. The IK2-tree
represents at the same time the three dimensions in the ternary relation and
provides indexing capabilities over the three of them, but it also offers
other interesting features to improve some types of queries over one of the
three dimensions, the dimension used in the nodes of the trees instead of in
the organization of the branches.