RUC. Repositorio da Universidade da Coruña
Publicación
Artículo científico (JournalArticle)
Set operations over compressed binary relations
[Abstract]: Binary relations are commonly used to represent relationships between real-world objects. Classical representations for binary relations can be very space-consuming when the set of elements is large. In these cases, compressed representations, such as the -tree, have proven to be a competitive solution, as they are efficient in time while consuming very little space. Moreover,
-trees can successfully represent both sparse and dense binary relations, using different variants of the technique. In this paper, we propose and evaluate algorithms to efficiently perform set operations over binary relations represented using
-trees. More specifically, we present algorithms for computing the union, intersection, difference, symmetric difference, and complement of binary relations. Thus, this work extends the functionality of the different variants of the
-tree representation for binary relations. Our algorithms are computed directly over the compressed representation, without requiring previous decompression, and generate the result in compressed form. The experimental evaluation shows that they are efficient in terms of space and time, compared with different baselines where the binary relations are represented in plain form or require a previous decompression to perform the set operation., Gilberto Gutiérrez was supported by the research group ALgoritmos y BAses de Datos (ALBA) 160119 GI/EF and the research project 171319 4/R, both funded by Universidad del Bío-Bío (Chile).
Susana Ladra was supported by Ministerio de Economía y Competitividad, Spain (PGE and FEDER) [grant number TIN2016-77158-C4-3-R], Centro para el desarrollo Tecnológico e Industrial, Spain (co-founded with FEDER) [ITC-20161074]; Xunta de Galicia, Spain (co-founded with FEDER) [grant number ED431C 2017/58]; and support from Xunta de Galicia (Centro singular de investigación de Galicia accreditation 2016–2019), Spain and the European Union (European Regional Development Fund — ERDF), Spain.
Miguel R. Penabad was supported by Ministerio de Economía y Competitividad, Spain (PGE and FEDER) [grant number TIN2016-78011-C4-1-R], Xunta de Galicia, Spain (co-founded with FEDER) [grant number ED431C 2017/58]; and support from Xunta de Galicia (Centro singular de investigación de Galicia accreditation 2016–2019) and the European Union (European Regional Development Fund — ERDF).
Carlos Quijada-Fuentes was supported by CONICYT-PCHA/MagisterNacional/2015-22150776, Chile and by the research group ALgoritmos y BAses de Datos (ALBA) 160119 GI/EF funded by Universidad del Bío-Bío (Chile)., Xunta de Galicia; ED431C 2017/58, Chile. Comisión Nacional de Investigación Científica y Tecnológica; 2015-22150776, University of Bío-Bío; 160119 GI/EF, University of Bío-Bío; 171319 4/R
Proyecto:
MINECO / Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016 TIN2016-77158-C4-1-R
,
MINECO / Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016 ITC-20161074
,
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016 TIN2016-78011-C4-1-R
HANDLE: http://hdl.handle.net/2183/40137
Ver en: http://hdl.handle.net/2183/40137