Entropy-bounded Representation of Point Grids

Farzan, Arash; Gagie, Travis; Navarro, Gonzalo

doi:10.1007/978-3-642-17514-5_28

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Entropy-bounded Representation of Point Grids

MPS-Authors

/persons/resource/persons44403

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

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: https://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.