English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Entropy-bounded Representation of Point Grids

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.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Farzan, Arash1, Author           
Gagie, Travis2, Author
Navarro, Gonzalo2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 20102010
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 536765
DOI: 10.1007/978-3-642-17514-5_28
URI: http://dx.doi.org/10.1007/978-3-642-17514-5_28
Other: Local-ID: C1256428004B93B8-1D263E7FF89D9A3AC125781600011E81-Farzan2010
 Degree: -

Event

show
hide
Title: 21st International Symposium on Algorithms and Computation
Place of Event: Jeju Island, Korea
Start-/End Date: 2010-01-12 - 2010-01-12

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithms and Computation
  Abbreviation : ISAAC 2010
  Subtitle : 21st International Symposium, ISAAC 2010 ; Pt. II
Source Genre: Proceedings
 Creator(s):
Cheong, Otfried1, Editor
Chwa, Kyung-Yong1, Editor
Park, Kunsoo1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 327 - 338 Identifier: ISBN: 978-3-642-17513-8

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 6507 Sequence Number: - Start / End Page: - Identifier: -