Publicación: AN EFFICIENT ALGORITHM TO COUNT THE RELATIONS IN A RANGE OF BINARY RELATIONS REPRESENTED BY A K(2)-TREE
| dc.creator | MARTITA PAULINA MUÑOZ CANDIA | |
| dc.creator | RODRIGO ARIEL TORRES AVILÉS | |
| dc.creator | GILBERTO ANTONIO GUTIÉRREZ RETAMAL | |
| dc.date | 2021 | |
| dc.date.accessioned | 2025-01-10T15:18:37Z | |
| dc.date.available | 2025-01-10T15:18:37Z | |
| dc.date.issued | 2021 | |
| dc.description.abstract | TWO SETS A AND B , WHOSE ELEMENTS FULFILL A TOTAL ORDER ON OPERATOR ? , CAN HAVE A BINARY RELATION R?A×B REPRESENTED BY THE K 2 -TREE COMPACT DATA STRUCTURE, WHICH GREATLY IMPROVES STORAGE SPACE. CURRENTLY, COUNT QUERY IS MANAGED BY EITHER USING RANGE QUERY OR TO MODIFY THE STRUCTURE TO HAVE AGGREGATE INFORMATION, IMPLYING ADDITIONAL TIME OR SPACE IN ORDER TO PERFORM THE QUERY. THIS ARTICLE PRESENTS COMPACT COUNT , WHICH EXPLOITS THE K 2 -TREE PROPERTIES TO REDUCE THE PATHS TO BE SCANNED TO COUNT THE NUMBERS IN A RANGE R , THUS ENSURING AN EXPECTED RUNTIME OF O(LOGKRLOGKN) AND STORAGE OF O(LOGKR) WITH THE K 2 -TREE PARAMETERS N AND K . OUR ALGORITHM WAS COMPARED THROUGH A SERIES OF EXPERIMENTS THAT CONSIDER BOTH SYNTHETIC DATA WITH DIFFERENT DISTRIBUTIONS AND REAL DATA, WITH A SOLUTION BASED ON THE RANGE ALGORITHM. EXPERIMENTAL RESULTS SHOW THAT COMPACT COUNT IS 250 TO 1,000 TIMES FASTER THAN RANGE ON SYNTHETIC AND REAL DATA, RESPECTIVELY, WITH A SMALL ADDITIONAL STORAGE COST, AS EXPECTED BY THE THEORETICAL ANALYSIS. | |
| dc.format | application/pdf | |
| dc.identifier.doi | 10.1109/ACCESS.2021.3050081 | |
| dc.identifier.issn | 2169-3536 | |
| dc.identifier.issn | 2169-3536 | |
| dc.identifier.uri | https://repositorio.ubiobio.cl/handle/123456789/11405 | |
| dc.language | spa | |
| dc.publisher | IEEE ACCESS | |
| dc.relation.uri | 10.1109/ACCESS.2021.3050081 | |
| dc.rights | PUBLICADA | |
| dc.title | AN EFFICIENT ALGORITHM TO COUNT THE RELATIONS IN A RANGE OF BINARY RELATIONS REPRESENTED BY A K(2)-TREE | |
| dc.title.alternative | UN ALGORITMO EFICIENTE PARA CONTAR LAS RELACIONES EN UN RANGO DE RELACIONES BINARIAS REPRESENTADAS POR UN ÁRBOL K(2) | |
| dc.type | ARTÍCULO | |
| dspace.entity.type | Publication | |
| ubb.Estado | PUBLICADA | |
| ubb.Otra Reparticion | RECTORIA | |
| ubb.Otra Reparticion | DEPARTAMENTO DE SISTEMAS DE INFORMACION | |
| ubb.Otra Reparticion | DEPARTAMENTO DE CIENCIAS DE LA COMPUTACION Y TECNOLOGIA DE LA INFORMACION. | |
| ubb.Sede | CONCEPCIÓN | |
| ubb.Sede | CONCEPCIÓN | |
| ubb.Sede | CHILLÁN |
