# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Entropy-bounded Representation of Point Grids

##### 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 (*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.