Post on 05-Apr-2015
transcript
Konstruktion sehr großer Suffixbäume
Michael Höhndorf
Steffen Andre
Übersicht
Probleme mit Suffixbäumen Lösungsansätze Verschiedene Algorithmen
Hunt
Top-Q
TDD
Vergleich
Problem Suffixbaum
Hoher Speicherbedarf Zeitaufwendige Konstruktion bei großen
Eingabestrings, da Konstruktion im RAM nicht möglich
Häufige Sprünge im Speicher Memory Bottleneck
Lösungsansätze
Suffixbaumkonstruktionen plattenfreundlich gestalten
Hunt
TDD
Bufferstrategie ändern Top-Q
TDD
Hunt/ Atkinson/ Irving
Konstruktion per Platte Vorher nur Suffixbäume kleiner als RAM Tausch von O(n) gegen locality of access Verzichtet auf Suffixlinks O(n2) Durchschnitt: O(n*logn)
Top-Q (Bedathur/ Haritsa)
Benutzt Ukkonnen-Algorithmus Neue Pagingstartegie
TDD
Von Tata/Hankins/Patel Top down disk based Besonderheit: “locality of reference” Übertrifft alle bisherigen Ansätze Unterteilung in zwei Phasen
PWOTD (Konstruktion des Suffixbaumes) Bufferstrategie
PWOTD
Partition and Write Only Top Down Unterteilung in zwei Schritte
Partitionierung Wotdeager
Komplexität: Worst Case: O(n2) Average Case O(n*logn)
Repräsentation
String: ATTAGTACA
Partitionierung
Alphabet: Σ Prefixlen: Tiefe der Partitionierung Suffixe in |Σ|prefixlen Partitionen teilen Für jede Partition Suffixbaum erstellen Suffixbäume zusammenfügen Im Beispiel:
T={2,3,6}
Wotdeager
Benutzt 4 Datenstrukturen Input String Array Suffixes Array Temp Array Tree Array
Algorithmus
Bufferstrategie
Optimale Ersetzungsstrategie für die vier Datenstrukturen finden
verfügbaren RAM zwischen den vier
Datenstrukturen aufteilen, um den
größtmöglichen Gewinn zu erreichen
Bufferstrategie
Bufferstrategie
String Größe: n Ersetzungsstrategie: LRU Schlechteste „locality of reference“
Suffixes-Array Größe: 4n Ersetzungsstrategie: LRU
Bufferstrategie
Temp Array Größe: 4n Ersetzungsstrategie: MRU
Tree-Array Größte von allen Größe: 8-12n Ersetzungsstrategie: LRU Hohe „locality of reference“
Buffermanagement
Bufferstrategie
Aufteilung des Hauptspeichers Suffixes/Temp benötigt mindestens |Σ| Seiten Tree benötigt mindestens 2 Seiten Eingabestring wird wenn möglich komplett in
den Speicher übernommen Wenn noch Platz im Hauptspeicher ist wird
dieser an Suffixes, Temp, Tree vergeben
Bufferstrategie
TDD vs. Ukkonen
TDD vs. Ukkonen
TDD bei größeren Alphabeten zunehmend besser als Ukkonen
Bei kleinen Alphabeten (demelano) Faktor 2.5 Bei mittleren Alphabeten (swp20) Faktor 4.5 Bei großen Alphabeten (unif40) Faktor 10
Trotz O(n2) meist besser, da locality of reference
Ukkonen’s Algorithmus hat viele cache misses (Bei modernen Rechnern)
TDD vs. Hunt
TDD vs Hunt
TDD in jedem Fall bedeutend besser Bei kleinen Alphabeten (H Chr1) Faktor 5.5
Bei mittleren Alphabeten (TrEMBL) Faktor 7.4
Bei großen Alphabeten (guten) Faktor 9.9
Hunt viele Sprünge bei Konstruktion
TDD berührt jeden Knoten nur einmal
TDD vs. TopQ
Test mit 50Mbp de Human Chromosom-I TopQ 78min TDD unetr gleichen Umständen nur 2,1min
TDD um Faktor 37 schneller Test auf gesamtem Chromosom
TopQ 5800min TDD 18min
FRAGEN???