Skip navigation
  •  Home
  • UDC 
    • Getting started
    • RUC Policies
    • FAQ
    • FAQ on Copyright
    • More information at INFOguias UDC
  • Browse 
    • Communities
    • Browse by:
    • Issue Date
    • Author
    • Title
    • Subject
  • Help
    • español
    • Gallegan
    • English
  • Login
  •  English 
    • Español
    • Galego
    • English
  
View Item 
  •   DSpace Home
  • 1. Investigación
  • Grupos de investigación
  • Laboratorio de Bases de Datos (LBD)
  • GI-LBD - Artigos
  • View Item
  •   DSpace Home
  • 1. Investigación
  • Grupos de investigación
  • Laboratorio de Bases de Datos (LBD)
  • GI-LBD - Artigos
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Compressed Data Structures for Binary Relations in Practice

Thumbnail
View/Open
C.Quijada_Compressed_Data_Structures_for_Binary_Relations_in_Practice_2020.pdf (7.753Mb)
Use this link to cite
http://hdl.handle.net/2183/25445
Collections
  • OpenAIRE [148]
  • GI-LBD - Artigos [22]
Metadata
Show full item record
Title
Compressed Data Structures for Binary Relations in Practice
Author(s)
Quijada Fuentes, Carlos
Penabad, Miguel R.
Ladra, Susana
Gutiérrez Retamal, Gilberto
Date
2020-01-31
Citation
C. Quijada Fuentes, M. R. Penabad, S. Ladra and G. Gutiérrez Retamal, "Compressed Data Structures for Binary Relations in Practice," in IEEE Access, vol. 8, pp. 25949-25963, 2020.
Abstract
[Abstract] Binary relations are commonly used in Computer Science for modeling data. In addition to classical representations using matrices or lists, some compressed data structures have recently been proposed to represent binary relations in compact space, such as the k 2 -tree and the Binary Relation Wavelet Tree (BRWT). Knowing their storage needs, supported operations and time performance is key for enabling an appropriate choice of data representation given a domain or application, its data distribution and typical operations that are computed over the data. In this work, we present an empirical comparison among several compressed representations for binary relations. We analyze their space usage and the speed of their operations using different (synthetic and real) data distributions. We include both neighborhood and set operations, also proposing algorithms for set operations for the BRWT, which were not presented before in the literature. We conclude that there is not a clear choice that outperforms the rest, but we give some recommendations of usage of each compact representation depending on the data distribution and types of operations performed over the data. We also include a scalability study of the data representations.
Keywords
Computational complexity
Data compression
Data structures
Matrix algebra
Trees (mathematics)
 
Editor version
https://doi.org/10.1109/ACCESS.2020.2970983
Rights
Atribución 4.0 España
 
http://creativecommons.org/licenses/by/4.0/
 
ISSN
2169-3536

Browse

All of DSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

My Account

LoginRegister

Statistics

View Usage Statistics
Sherpa
OpenArchives
OAIster
Scholar Google
UNIVERSIDADE DA CORUÑA. Servizo de Biblioteca.    DSpace Software Copyright © 2002-2013 Duraspace - Send Feedback