A succinct data structure for self-indexing ternary relations

DOI10.1016/J.JDA.2016.10.002MaRDI QIDQ2397150zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(5)

• Compact binary relation representations with rich functionality
• A holistic approach to the composition of ternary relations
• ASA-graphs for efficient data representation and processing
• Faster dynamic compressed \(d\)-ary relations
• Compact rich-functional binary relation representations

Describes a project that uses

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)