Mostrar o rexistro simple do ítem

Faster compressed quadtrees

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.issued2023-02
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.urihttp://hdl.handle.net/2183/37832
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.language.isoenges_ES
dc.publisherElsevier B.V.es_ES
dc.relationinfo:eu-repo/grantAgreement/EC/H2020/690941es_ES
dc.relationinfo: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.relationinfo: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.relationinfo: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.relationinfo: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.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.typeinfo:eu-repo/semantics/articlees_ES
dc.rights.accessinfo:eu-repo/semantics/embargoedAccesses_ES
dc.date.embargoEndDate2025-02-01es_ES
dc.date.embargoLift2025-02-01
UDC.journalTitleJournal of Computer and System Scienceses_ES
UDC.volume131es_ES
UDC.startPage86es_ES
UDC.endPage104es_ES
dc.identifier.doi10.1016/j.jcss.2022.09.001


Ficheiros no ítem

Thumbnail
Nome:
Bernardo_Guillermode_2023_Fast ...
Tamaño:
795.7Kb
Formato:
PDF
Descrición:
Versión aceptada
Ver/abrir
Thumbnail
Nome:
license_rdf
Tamaño:
1.203Kb
Formato:
application/rdf+xml
Ver/abrir

Este ítem aparece na(s) seguinte(s) colección(s)

Mostrar o rexistro simple do ítem