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.