Entropy-bounded representation of point grids
| Author | dc.contributor.author | Farzan, Arash | |
| Author | dc.contributor.author | Gagie, Travis | es_CL |
| Author | dc.contributor.author | Navarro, Gonzalo | es_CL |
| Admission date | dc.date.accessioned | 2014-12-24T12:56:34Z | |
| Available date | dc.date.available | 2014-12-24T12:56:34Z | |
| Publication date | dc.date.issued | 2014 | |
| Cita de ítem | dc.identifier.citation | Computational Geometry Volume 47, Issue 1, January 2014, Pages 1–14 | en_US |
| Identifier | dc.identifier.other | DOI: 10.1016/j.comgeo.2013.08.002 | |
| Identifier | dc.identifier.uri | https://repositorio.uchile.cl/handle/2250/126797 | |
| General note | dc.description | Artículo de publicación ISI | en_US |
| Abstract | dc.description.abstract | We give the first fully compressed representation of a set of m points on an n×n grid, taking H+o(H) bits of space, where View the MathML source is the entropy of the set. This representation supports range counting, range reporting, and point selection queries, with complexities that go from O(1) to O(lg2n/lglgn) per answer as the entropy of the grid decreases. Operating within entropy-bounded space, as well as relating time complexity with entropy, opens a new line of research on an otherwise well-studied area. | en_US |
| Lenguage | dc.language.iso | en | en_US |
| Publisher | dc.publisher | Elsevier | en_US |
| Type of license | dc.rights | Attribution-NonCommercial-NoDerivs 3.0 Chile | * |
| Link to License | dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ | * |
| Keywords | dc.subject | Compressed data structures | en_US |
| Título | dc.title | Entropy-bounded representation of point grids | en_US |
| Document type | dc.type | Artículo de revista |
Files in this item
This item appears in the following Collection(s)
-
Artículos de revistas
Artículos de revistas
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 Chile