Entropy-bounded Representation of Point Grids

Farzan, Arash; Gagie, Travis; Navarro, Gonzalo

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

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

会議論文

Entropy-bounded Representation of Point Grids

MPS-Authors

/persons/resource/persons44403

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

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

公開されているフルテキストはありません

付随資料 (公開)

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.

引用: 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.