Deutsch
 
Benutzerhandbuch Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Entropy-bounded Representation of Point Grids

MPG-Autoren
/persons/resource/persons44403

Farzan,  Arash
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Farzan, A., Gagie, T., & Navarro, G. (2010). Entropy-bounded Representation of Point Grids. In O. Cheong, K.-Y. Chwa, & K. Park (Eds.), Algorithms and Computation (pp. 327-338). Berlin: Springer. doi:10.1007/978-3-642-17514-5_28.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-164E-F
Zusammenfassung
We give the first fully compressed representation of a set of $m$ points on an $n \times n$ grid, taking $H+o(H)$ bits of space, where $H=\lg {n^2 \choose m}$ is the entropy of the set. This representation supports range counting, range reporting, and point selection queries, with a performance that is comparable to that of uncompressed structures and that improves upon the only previous compressed structure. Operating within entropy-bounded space opens a new line of research on an otherwise well-studied area, and is becoming extremely important for handling large datasets.