Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Conference Paper

Entropy-bounded Representation of Point Grids


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

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

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