MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Farzan, Arash
Gagie, Travis
Navarro, Gonzalo		dblp
dblp
dblp
Not MPG Author(s):
Gagie, Travis
Navarro, Gonzalo
Editor(s):
Cheong, Otfried
Chwa, Kyung-Yong
Park, Kunsoo		dblp
dblp
dblp
Not MPII Editor(s):
Cheong, Otfried
Chwa, Kyung-Yong
Park, Kunsoo
BibTeX cite key*:
Farzan2010
Title, Booktitle
Title*:
Entropy-Bounded Representation of Point Grids
Booktitle*:
Algorithms and Computation : 21st International Symposium, ISAAC 2010. - Pt. II
Event, URLs
Conference URL::
http://tclab.kaist.ac.kr/~isaac10/home.html
Downloading URL:
http://dx.doi.org/10.1007/978-3-642-17514-5_28
Event Address*:
Jeju Island, Korea
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
12 January 2010
Event End Date:
12 January 2010
Publisher
Name*:
Springer
URL:
Address*:
Berlin
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
6507
Number:
Month:
Pages:
327-338
Year*:
2010
VG Wort Pages:
ISBN/ISSN:
978-3-642-17513-8
Sequence Number:
DOI:
10.1007/978-3-642-17514-5_28
Note, Abstract, ©
(LaTeX) 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.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Farzan2010,
AUTHOR = {Farzan, Arash and Gagie, Travis and Navarro, Gonzalo},
 EDITOR = {Cheong, Otfried and Chwa, Kyung-Yong and Park, Kunsoo},
 TITLE = {Entropy-Bounded Representation of Point Grids},
 BOOKTITLE = {Algorithms and Computation : 21st International Symposium, ISAAC 2010. - Pt. II},
 PUBLISHER = {Springer},
 YEAR = {2010},
 VOLUME = {6507},
 PAGES = {327--338},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Jeju Island, Korea},
 ISBN = {978-3-642-17513-8},
 DOI = {10.1007/978-3-642-17514-5_28},
}

Entry last modified by Anja Becker, 01/13/2011
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]		Created
01/12/2011 01:12:13 AM
Revision
1.
0.


Editor
Anja Becker
Arash Farzan


Edit Date
13.01.2011 13:17:37
01/12/2011 01:12:13 AM