Interleaved K2-tree: Indexing and Navigating Ternary Relations

Authors: Sandra, Álvarez-García; Nieves, R. Brisaboa; Guillermo, de Bernardo; Gonzalo,Navarro;
Year: 2014
Venue: Proceedings of the 2014 Data Compression Conference (DCC 2014)
Link: http://dx.doi.org/10.1109/DCC.2014.56
Product of the Action: No

Abstract:
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.