UNIVERSITÄTSBIBLIOTHEK
  • search hit 8 of 9
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

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