Differences
This shows you the differences between two versions of the page.
|
fischer:abschlussarbeiten:distwt-hybrid [2019-12-11 08:21] |
fischer:abschlussarbeiten:distwt-hybrid [2019-12-11 08:50] |
||
|---|---|---|---|
| Line 4: | Line 4: | ||
| Wavelet Trees sind eine Datenstruktur, die einen Eingabestring so kodieren, dass effizient die Vorkommen eines Zeichens bis zu einer beliebigen Position gezählt (//rank//) sowie ein beliebiges Vorkommens im String lokalisiert werden kann (//select//). Überdies kann der Eingabestring für alle Positionen wiederhergestellt werden, so dass dieser nicht mehr explizit gespeichert werden muss. | Wavelet Trees sind eine Datenstruktur, die einen Eingabestring so kodieren, dass effizient die Vorkommen eines Zeichens bis zu einer beliebigen Position gezählt (//rank//) sowie ein beliebiges Vorkommens im String lokalisiert werden kann (//select//). Überdies kann der Eingabestring für alle Positionen wiederhergestellt werden, so dass dieser nicht mehr explizit gespeichert werden muss. | ||
| - | Die Konstruktion eines Wavelet Trees kann effizient mit einem Divide-and-Conquer-Verfahren (//Domain Decomposition//) parallelisiert werden, wobei jede Einheit zunächst den Wavelet Tree für ihren Teil des Eingabestrings konstruiert und die Ergebnisse anschließend zusammengeführt werden (merge). Neuere Forschung befasst sich mit der Konstruktion in den Modellen | + | Die Konstruktion eines Wavelet Trees kann effizient mit einem Divide-and-Conquer-Verfahren (//Domain Decomposition//) parallelisiert werden, wobei jede Einheit (z.B. ein Prozessorkern) zunächst den Wavelet Tree für ihren Teil des Eingabestrings konstruiert und die Ergebnisse anschließend zusammengeführt werden (merge). Neuere Forschung befasst sich mit der Konstruktion in den Modellen |
| * //shared memory//, wo jeder Prozessorkern einen Teil der Eingabe erhält und der Merge-Schritt über //geteilten Speicher// durchgeführt wird, sowie | * //shared memory//, wo jeder Prozessorkern einen Teil der Eingabe erhält und der Merge-Schritt über //geteilten Speicher// durchgeführt wird, sowie | ||
| Line 20: | Line 20: | ||
| ==== Betreuer ==== | ==== Betreuer ==== | ||
| - | Dir Arbeit wird betreut von [[staff:fischer|Johannes Fischer]] und [[staff:dinklage|Patrick Dinklage]]. | + | Die Arbeit wird betreut von [[staff:fischer|Johannes Fischer]] und [[staff:dinklage|Patrick Dinklage]]. |