de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Entropy-bounded Representation of Point Grids

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44403

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

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

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.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-164E-F
Abstract
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.