Show simple item record

dc.contributor.authorQuijada Fuentes, Carlos
dc.contributor.authorPenabad, Miguel R.
dc.contributor.authorLadra, Susana
dc.contributor.authorGutiérrez Retamal, Gilberto
dc.date.accessioned2020-04-27T14:13:32Z
dc.date.available2020-04-27T14:13:32Z
dc.date.issued2020-01-31
dc.identifier.citationC. 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.es_ES
dc.identifier.issn2169-3536
dc.identifier.urihttp://hdl.handle.net/2183/25445
dc.description.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.es_ES
dc.description.sponsorshipMinisterio de Ciencia, Innovación y Universidades; TIN2016-77158-C4-3-Res_ES
dc.description.sponsorshipMinisterio de Ciencia, Innovación y Universidades; TIN2016-78011-C4-1-Res_ES
dc.description.sponsorshipMinisterio de Ciencia, Innovación y Universidades; RTC-2017-5908-7es_ES
dc.description.sponsorshipConsellería de Economía e Industria; IN852A 2018/14es_ES
dc.description.sponsorshipXunta de Galicia; ED431C 2017/58es_ES
dc.description.sponsorshipXunta de Galicia co-funded with ERDF; ED431G/01es_ES
dc.description.sponsorshipUniversity of Bío-Bío; 192119 2/Res_ES
dc.description.sponsorshipUniversity of Bío-Bío; 195119 GI/VCes_ES
dc.language.isoenges_ES
dc.publisherInstitute of Electrical and Electronics Engineerses_ES
dc.relationinfo:eu-repo/grantAgreement/EC/H2020/690941es_ES
dc.relation.urihttps://doi.org/10.1109/ACCESS.2020.2970983es_ES
dc.rightsAtribución 4.0 Españaes_ES
dc.rightshttp://creativecommons.org/licenses/by/4.0/
dc.subjectComputational complexityes_ES
dc.subjectData compressiones_ES
dc.subjectData structureses_ES
dc.subjectMatrix algebraes_ES
dc.subjectTrees (mathematics)es_ES
dc.titleCompressed Data Structures for Binary Relations in Practicees_ES
dc.typeinfo:eu-repo/semantics/articlees_ES
dc.rights.accessinfo:eu-repo/semantics/openAccesses_ES
UDC.journalTitleIEEE Accesses_ES
UDC.volume8es_ES
UDC.startPage25949es_ES
UDC.endPage25963es_ES
dc.identifier.doi10.1109/ACCESS.2020.2970983


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record