MPI-INF D1 Publications: Proceedings Article: Entropy-Bounded Representation of Point Grids

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

Options:

Library locked

Goto entry point

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

URL of the conference:	http://tclab.kaist.ac.kr/~isaac10/home.html
URL for downloading the paper:	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


(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

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

Attachment Section