Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Flexible indexing of repetitive collections

Belazzougui, D., Cunial, F., Gagie, T., Prezza, N., & Raffinot, M. (2017). Flexible indexing of repetitive collections. In J. Kari (Ed.), Unveiling Dynamics and Complexity: 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017, Proceedings (pp. 162-174). Cham: Springer International Publishing.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/21.11116/0000-0002-8C01-F Versions-Permalink: https://hdl.handle.net/21.11116/0000-0002-8C02-E
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Belazzougui, Djamal, Autor
Cunial, Fabio1, Autor           
Gagie, Travis, Autor
Prezza, Nicola, Autor
Raffinot, Mathieu, Autor
Kari, Jarkko, Herausgeber
Affiliations:
1Max Planck Institute for Molecular Cell Biology and Genetics, ou_2340692              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: Highly repetitive strings are increasingly being amassed by genome sequencing experiments, and by versioned archives of source code and webpages. We describe practical data structures that support counting and locating all the exact occurrences of a pattern in a repetitive text, by combining the run-length encoded Burrows-Wheeler transform (RLBWT) with the boundaries of Lempel-Ziv 77 factors. One such variant uses an amount of space comparable to LZ77 indexes, but it answers count queries between two and four orders of magnitude faster than all LZ77 and hybrid index implementations, at the cost of slower locate queries. Combining the RLBWT with the compact directed acyclic word graph answers locate queries for short patterns between four and ten times faster than a version of the run-length compressed suffix array (RLCSA) that uses comparablememory, and with very short patterns our index achieves speedups even greater than ten with respect to RLCSA

Details

einblenden:
ausblenden:
Sprache(n):
 Datum: 2017-06-16
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: DOI: 10.1007/978-3-319-58741-7 17
Anderer: cbg-6905
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: 13th Conference on Computability in Europe, CiE 2017
Veranstaltungsort: Turku, Finland
Start-/Enddatum: 2017-06-12 - 2017-06-16

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Unveiling Dynamics and Complexity : 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017, Proceedings
Genre der Quelle: Konferenzband
 Urheber:
Kari, Jarkko, Herausgeber
Affiliations:
-
Ort, Verlag, Ausgabe: Cham : Springer International Publishing
Seiten: - Band / Heft: Unveiling Dynamics and Complexity : 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017, Proceedings Artikelnummer: - Start- / Endseite: 162 - 174 Identifikator: ISBN: 978-3-319-58740-0