Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  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

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-164E-F Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-28AC-7
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Farzan, Arash1, Autor           
Gagie, Travis2, Autor
Navarro, Gonzalo2, Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 20102010
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 536765
DOI: 10.1007/978-3-642-17514-5_28
URI: http://dx.doi.org/10.1007/978-3-642-17514-5_28
Anderer: Local-ID: C1256428004B93B8-1D263E7FF89D9A3AC125781600011E81-Farzan2010
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: 21st International Symposium on Algorithms and Computation
Veranstaltungsort: Jeju Island, Korea
Start-/Enddatum: 2010-01-12 - 2010-01-12

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Algorithms and Computation
  Kurztitel : ISAAC 2010
  Untertitel : 21st International Symposium, ISAAC 2010 ; Pt. II
Genre der Quelle: Konferenzband
 Urheber:
Cheong, Otfried1, Herausgeber
Chwa, Kyung-Yong1, Herausgeber
Park, Kunsoo1, Herausgeber
Affiliations:
1 External Organizations, ou_persistent22            
Ort, Verlag, Ausgabe: Berlin : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 327 - 338 Identifikator: ISBN: 978-3-642-17513-8

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
  Kurztitel : LNCS
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 6507 Artikelnummer: - Start- / Endseite: - Identifikator: -