Skip lists and probabilistic analysis of algorithms

Thomas Papadakis

1993 · 26 citations · 26 references

Concepts

Abstract

This thesis is concerned with various forms of skip lists, and with probabilistic analyses of algorithms. We investigate three topics; one topic from each of these two areas, and another topic common to both of them. First, we consider Pugh's skip list. We derive exact and asymptotic expressions for the average search cost of a fixed key and of an average key. Our results improve previously known upper bounds of these two average search costs. We also derive exact and asymptotic expressions for the variance of the search cost for the largest key. Next, we propose several versions of deterministic skip lists. They all have guaranteed logarithmic search and update costs per operation, they lead to an interesting bridge structure between the original skip list and standard search trees, they are simpler to implement than standard balanced search trees, and our experimental results suggest that they are also competitive in terms of space and time. Finally, we consider the elastic-budget trie, a variant of the standard trie, in which each external node (bucket) has precisely as many key slots as the number of keys stored in it. We examine the number of buckets of each size, and we derive exact and asymptotic expressions for their average values, as well as asymptotic expressions for their variances and covariances under the closely related Poisson model of randomness. Our experimental results suggest that maintaining only two bucket sizes may be a very reasonable practical choice.

References

26