A succinct data structure for self-indexing ternary relations

DOI10.1016/J.JDA.2016.10.002zbMATH Open1407.68104arXiv1707.02759OpenAlexW2540110816MaRDI QIDQ2397150FDOQ2397150

Authors: Sandra Alvarez-Garcia, Guillermo de Bernardo, Nieves R. Brisaboa, Gonzalo Navarro 

Publication date: 29 May 2017

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Abstract: The representation of binary relations has been intensively studied and many different theoretical and practical representations have been proposed to answer the usual queries in multiple domains. However, ternary relations have not received as much attention, even though many real-world applications require the processing of ternary relations. In this paper we present a new compressed and self-indexed data structure that we call Interleaved $K^2$-tree (I$K^2$-tree), designed to compactly represent and efficiently query general ternary relations. The I$K^2$-tree is an evolution of an existing data structure, the $K^2$-tree, initially designed to represent Web graphs and later applied to other domains. The I$K^2$-tree is able to extend the $K^2$-tree to represent a ternary relation, based on the idea of decomposing it into a collection of binary relations but providing indexing capabilities in all the three dimensions. We present different ways to use I$K^2$-tree to model different types of ternary relations using as reference two typical domains: RDF and Temporal Graphs. We also experimentally evaluate our representations comparing them in space usage and performance with other solutions of the state of the art.

Full work available at URL: https://arxiv.org/abs/1707.02759

Recommendations

• Compact rich-functional binary relation representations
• Compact binary relation representations with rich functionality
• Adaptive Searching in Succinctly Encoded Binary Relations and Tree-Structured Documents
• Succinct indexes for strings, binary relations and multilabeled trees
• An Improved Succinct Representation for Dynamic k-ary Trees

zbMATH Keywords

RDFcompressed data structurestemporal graphsternary relations\(K^2\)-tree

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Cites Work

• Compact binary relation representations with rich functionality
• Succinct representation of labeled graphs

Cited In (3)

• Compact rich-functional binary relation representations
• A holistic approach to the composition of ternary relations
• Faster dynamic compressed \(d\)-ary relations

Uses Software

• SPARQL

This page was built for publication: A succinct data structure for self-indexing ternary relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2397150)