Publications

Möchte man eine Menge S von Strings effzient abspeichern und Operationen auf S wie das Einfügen, Suchen oder Entfernen von Strings definieren, werden üblicherweise Suchbäume verwendet. J. Bentley und R. Sedgewick haben sich in den 1990er Jahren mit diesem Problem beschäftigt und den ternären Suchbaum vorgestellt. M. Dietzfelbinger, P. Schlag und S. Walzer haben 2018 für ein anderes Problem eine neue spezielle Suchbaumstruktur für Bitstrings fester Länge entwickelt. In dieser Arbeit werden die beiden Suchbaumstrukturen verglichen und die Suchbaumstruktur für Bitstrings fester Länge verallgemeinern, so dass sie mit beliebigen Strings umgehen kann.

Diese Arbeit besteht grundsätzlich aus zwei Teilen. Der erste Teil ist beschäftigt mit der Datenstruktur Wörterbuch und ihren Konstruktionsverfahren. Um ein Wörterbuch mit sowohl einer konstanten Zugriffszeit als auch einer hohen Speicherauslastung zu konstruieren, wird Cuckoo-Hashing als eine effiziente Technik zur Erstellung von Hashtabellen verwendet. In der Arbeit werden zwei Verallgemeinerungsschemata des Cuckoo-Hashings betrachtet. Dabei werden verschiedene Zuordnungsalgorithmen systematisch beschrieben und analysiert. Im zweiten Teil der Arbeit werden Retrieval-Datenstrukturen behandelt. Zur effizienteren Konstruktion von Retrieval-Datenstrukturen in Bezug auf den verwendeten Speicherplatz werden Lazy-Gauss-Elimination (LGE) und Broadword-Programmierung eingesetzt. Damit kann ein großes lineares Gleichungssystem schneller gelöst werden. Zum Ende des zweiten Teils werden zusätzlich konkrete Implementierungen sowie experimentelle Ergebnisse des LGE und der Broadword-Programmierung präsentiert.