• search hit 13 of 22
Back to Result List

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.

Download full text files

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author:Elisabeth Neumann
URN:urn:nbn:de:hbz:386-kluedo-41642
Advisor:Markus Nebel
Document Type:Bachelor Thesis
Language of publication:English
Date of Publication (online):2015/08/25
Year of first Publication:2015
Publishing Institution:Technische Universität Kaiserslautern
Granting Institution:Technische Universität Kaiserslautern
Acceptance Date of the Thesis:2015/03/31
Date of the Publication (Server):2015/08/25
Page Number:IV, 67
Faculties / Organisational entities:Kaiserslautern - Fachbereich Informatik
DDC-Cassification:0 Allgemeines, Informatik, Informationswissenschaft / 004 Informatik
Licence (German):Standard gemäß KLUEDO-Leitlinien vom 30.07.2015