Randomized Jumplists With Several Jump Pointers

  • In 2003, a dictionary data structure called jumplist has been introduced by Brönnimann, Cazals and Durand. It is based on a circularly closed (singly) linked list, but additional jump-pointers are added to provide shortcuts to parts further ahead in the list. The original jump-and-walk data structure by Brönnimann, Cazals and Durand only introduces one jump-pointer per node. In this thesis, I add one more-jump pointer to each node and present algorithms for generation, insertion and search for the resulting data structure. Furthermore, I try to evaluate the effects on the expected search costs and the complexity of the generation and insertion. It turns out that the two-jump-pointer variant of the jumplist has a slightly better prefactor (1.2 vs. 2) in the leading term of the expected internal path length than the original version and despite the more complex structure of the two-jump-pointer variant compared to the regular jumplist, the complexity of generation and insertion remains linearithmic.

Volltext Dateien herunterladen

Metadaten exportieren

  • Export nach Bibtex
  • Export nach RIS

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Elisabeth Neumann
URN (Permalink):urn:nbn:de:hbz:386-kluedo-41642
Betreuer:Markus Nebel
Dokumentart:Bachelorarbeit
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):25.08.2015
Jahr der Veröffentlichung:2015
Veröffentlichende Institution:Technische Universität Kaiserslautern
Titel verleihende Institution:Technische Universität Kaiserslautern
Datum der Annahme der Abschlussarbeit:31.03.2015
Datum der Publikation (Server):25.08.2015
Seitenzahl:IV, 67
Fachbereiche / Organisatorische Einheiten:Fachbereich Informatik
DDC-Sachgruppen:0 Allgemeines, Informatik, Informationswissenschaft / 004 Informatik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vom 30.07.2015

$Rev: 13581 $