- Masterarbeit -

Beschreibung:

B⁺-Bäume sind eine effiziente Datenstruktur zum Suchen von Elementen. Die Daten werden nur in den Blättern gespeichert und es gibt zusätzliche Verbindungen zwischen den Blättern für eine Bereichssuche.

In dieser Bachelor-/Masterthesis sollen verschiedene Ansätze für hybride Beschleunigung von B⁺-Bäume untersucht werden, um eine optimale Lastverteilung zwischen CPU und GPU zu erreichen.

Eine Auswahl von B⁺-Baum Implementierungen sind: Palmtree [1][2], B⁺-Baum in der Rodinia Benchmark Suite [3] und eine verbesserte Version des stx-btree in der TLX Library

[1] J. Sewall, J. Chhugani, C. Kim, N. Satish, and P. Dubey. PALM: Parallel architecture-friendly latch-free modifications to B+ trees on many-core processors. Proc. VLDB Endowment, 4(11):795--806, August 2011.

[2] David B. Lomet, Sudipta Sengupta, and Justin J. Levandoski. 2013. The Bw-Tree: A B-tree for new hardware platforms. In Proceedings of the 2013 IEEE International Conference on Data Engineering (ICDE 2013) (ICDE '13). IEEE Computer Society, Washington, DC, USA, 302-313.

[3] J. Fix, A. Wilkes and K. Skadron. “Accelerating Braided B+ Tree Searches on a GPU with CUDA.” ACM Transactions on Database Systems. 2009

Anforderungen/Kenntnisse:
OpenCL, GPU-Programmierung, B⁺-Bäume ...

Bearbeitung:
Jan Henrik Schröder

Ergebnis:
Die Ausarbeitung kann im Institut für Informationssysteme angefordert werden.

Betreuung:

Prof. Dr. rer.nat. habil. Sven Groppe
Institut für Informationssysteme
Ratzeburger Allee 160 ( Gebäude 64 - 2. OG)
23562 Lübeck
Telefon: 0451 / 3101 5706