Beschleunigung von Hash-Tabellen mittels GPUs

- Bachelor-/Masterarbeit -


Beschreibung:

Da der Indexzugriff Ausgangspunkt für alle nachfolgenden Verarbeitungsschritte von Anfragen eines DBMS ist, ist ein schneller Indexzugriff wesentlich für die Gesamtperformanz der DBMS. Würden Datenzugriffe ohne die Verwendung von Indexen erfolgen, so müssten die gesamten Daten eingelesen werden, auch wenn das Zugriffsergebnis nur einen kleinen Teil der Daten beinhalten soll. In der Literatur existieren eine Vielzahl von Indexstrukturen, welche hinsichtlich unterschiedliche Eigenschaften wie Speicherbedarf [2, 3, 4, 7], Zugriffszeiten für Einfügen [5, 6], Suchen von einzelnen Einträgen [3, 6] oder Bereichssuche [1, 3] optimiert sind.

 

In dieser Bachelor-/Masterthesis wollen wir verschiedene Ansätze für Hashing untersuchen, welche durch GPUs beschleunigt werden. Eine Auswahl an Hashing-Ansätzen sind: Bloom-Filter [9], Cuckoo [10], Morton filters [11] und Vacuum filters [12].

 

[1] D. Comer. Ubiquitous B-Tree. ACM Comput. Surv., 11(2):121–137, June 1979.

[2] V. Leis, A. Kemper, and T. Neumann. The adaptive radix tree: Artful indexing for main-memory databases. In ICDE, 2013.

[3] Y. Mao, E. Kohler, and R. T. Morris. Cache craftiness for fast multicore key-value storage. In Proceedings of the 7th ACM European Conference on Computer Systems, EuroSys ’12, pages 183–196, 2012.

[4] D. R. Morrison. Patricia - practical algorithm to retrieve information coded in alphanumeric. J. ACM, 15(4):514–534, Oct. 1968.

[5] P. O’Neil et al. The log-structured merge-tree (LSM-tree). Acta Informatica, 33(4):351–385, 1996.

[6] R. Pagh and F. Rodler. Cuckoo hashing. J. Algorithms, 51(2):122–144, 2004.

[7] J. Rao and K. A. Ross. Making b+- trees cache conscious in main memory. In SIGMOD, 2000.

[8] H. Zhang, D. G. Andersen, A. Pavlo, M. Kaminsky, L. Ma, and R. Shen. Reducing the storage overhead of main-memory oltp databases with hybrid indexes. In Proceedings of the 2016 International Conference on Management of Data (SIGMOD), pages 1567–1581, 2016.

[9] B. H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422–426, 1970.

[10] B. Fan, D. G. Andersen, M. Kaminsky, and M. D. Mitzenmacher. Cuckoo filter: Practically better than Bloom. In Proc. of the ACM CoNEXT, 2014.

[11] Alex D. Breslow, Nuwan S. Jayasena, Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity, VLDB, 2018.

[12] Minmei Wang, Mingxun Zhou, Chen Qian, Shouqian Shi, Vacuum Filters: More Space-Efficient and Faster Replacement for Bloom and Cuckoo Filters, VLDB, 2019

 

Anforderungen/Kenntnisse:
OpenCL, GPU-Programmierung, Hashtabellen ...

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