Faster compressed quadtrees

Simple item page
UDC.coleccionInvestigaciónes_ES
UDC.departamentoCiencias da Computación e Tecnoloxías da Informaciónes_ES
UDC.endPage104es_ES
UDC.grupoInvLaboratorio de Bases de Datos (LBD)es_ES
UDC.journalTitleJournal of Computer and System Scienceses_ES
UDC.startPage86es_ES
UDC.volume131es_ES
dc.contributor.authorBernardo, Guillermo de
dc.contributor.authorGagie, Travis
dc.contributor.authorLadra, Susana
dc.contributor.authorNavarro, Gonzalo
dc.contributor.authorSeco, Diego
dc.date.accessioned2024-07-09T12:23:36Z
dc.date.embargoEndDate2025-02-01es_ES
dc.date.embargoLift2025-02-01
dc.date.issued2023-02
dc.description©2023 Elsevier B.V. All rights reserved. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/byncnd/ 4.0/. This version of the article has been accepted for publication in Future Generation Computer Systems. The Version of Record is available online at https:// doi.org/10.1016/j.jcss.2022.09.001es_ES
dc.descriptionVersión aceptadaes_ES
dc.descriptionAn early partial version of this paper appeared in Proc. of the Data Compression Conference 2015.es_ES
dc.description.abstract[Abstract]: Real-world point sets tend to be clustered, so using a machine word for each point is wasteful. In this paper we first show how a compact representation of quadtrees using O(1) bits per node can break this bound on clustered point sets, while offering efficient range searches. We then describe a new compact quadtree representation based on heavy-path decompositions, which supports queries faster than previous compact structures. We present experimental evidence showing that our structure is competitive in practice.es_ES
dc.description.sponsorshipPartially funded by the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 690941. GdB and SL funded by MCIN/AEI/10.13039/501100011033 [grants PID2020-114635RB-I00 (EXTRACompact), PID2019-105221RB-C41 (MAGIST)], by MCIN/AEI/10.13039/501100011033, “NextGenerationEU/PRTR” [grants PDC2021-120917-C21 (SIGTRANS) , PDC2021-121239-C31 (FLATCITY-POC)], by GAIN/Xunta de Galicia [grant ED431C 2017/53 (GRC) ], and also supported by the Centro de Investigación de Galicia “CITIC”, funded by Xunta de Galicia , FEDER Galicia 2014-2020 80%, SXU 20% [grant ED431G 2019/01 (CSI) ]. TG funded by NSERC Discovery Grant RGPIN-07185-2020. GN and DS funded by ANID - Millennium Science Initiative Program - Code ICN17_002 , Chile. GN funded by FONDECYT Grant 1-200038 , Chile.es_ES
dc.description.sponsorshipXunta de Galicia; ED431C 2017/53es_ES
dc.description.sponsorshipXunta de Galicia; ED431G 2019/01es_ES
dc.description.sponsorshipNatural Sciences and Engineering Research Council of Canada; RGPIN-07185-2020es_ES
dc.description.sponsorshipChile. Agencia Nacional de Investigación y Desarrollo; ICN17_002es_ES
dc.description.sponsorshipChile. Comisión Nacional de Investigación Científica y Tecnológica; 1-200038es_ES
dc.identifier.citationG. de Bernardo, T. Gagie, S. Ladra, G. Navarro, and D. Seco, "Faster compressed quadtrees", Journal of Computer and System Sciences, Vol. 131, pp. 86 - 104, Feb. 2023, doi: 10.1016/j.jcss.2022.09.001es_ES
dc.identifier.doi10.1016/j.jcss.2022.09.001
dc.identifier.urihttp://hdl.handle.net/2183/37832
dc.language.isoenges_ES
dc.publisherElsevier B.V.es_ES
dc.relation.projectIDinfo:eu-repo/grantAgreement/EC/H2020/690941es_ES
dc.relation.projectIDinfo:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PID2020-114635RB-I00/ES/EXPLOTACIÓN ENRIQUECIDA DE TRAYECTORIAS CON ESTRUCTURAS DE DATOS COMPACTAS Y GISes_ES
dc.relation.projectIDinfo:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PID2019-105221RB-C41/ES/VISUALIZACION Y EXPLORACION BASADA EN FLUJOS Y ANALITICA DE BIG DATA ESPACIAL/es_ES
dc.relation.projectIDinfo:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023/PDC2021-120917-C21/ES/SIGTRANSes_ES
dc.relation.projectIDinfo:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023/PDC2021-121239-C31/ES/FLATCITY-POCes_ES
dc.relation.urihttps://doi.org/10.1016/j.jcss.2022.09.001es_ES
dc.rightsAtribución-NoComercial-SinDerivadas 3.0 Españaes_ES
dc.rights.accessRightsopen accesses_ES
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/es/*
dc.subjectClustered pointses_ES
dc.subjectCompact data structureses_ES
dc.subjectHeavy-path decompositiones_ES
dc.subjectQuadtreeses_ES
dc.subjectRange querieses_ES
dc.titleFaster compressed quadtreeses_ES
dc.typejournal articlees_ES
dspace.entity.typePublication
relation.isAuthorOfPublication23354397-ec74-4cbb-93ac-f85352e9fbd8
relation.isAuthorOfPublication55bfba4e-d15b-4c84-9894-ac53c2278caf
relation.isAuthorOfPublication205d0115-1d0f-46c4-8581-ea7a69642870
relation.isAuthorOfPublication.latestForDiscovery23354397-ec74-4cbb-93ac-f85352e9fbd8

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
Bernardo_Guillermode_2023_Faster_compressed_quadtrees.pdf
Size:
795.73 KB
Format:
Adobe Portable Document Format
Description:
Versión aceptada
Download

Collections

Investigación (FIC)