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.
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 |