Marcel Ehrhardt:

An In-Depth Analysis of Data Structures Derived from van-Emde-Boas-Trees


IP-packet routing is one of the most practical solved problems in computer science with millions of routed packets per second. The algorithmic problem behind it is the so-called predecessor problem. Assuming a universe U, in this problem one can query a set S ⊆ U for the *predecessor* of an element q within the set S, i.e. max{x ∈ S | x < q}. If the set S can be manipulated, the problem is called the *dynamic* predecessor problem, otherwise it is called the *static* predecessor problem.

I give an overview of several different data structures for the w-bit word RAM on *bounded integer universes*, i.e. U = {0, ..., 2^w − 1}. Those data structures are based on the van-Emde-Boas-Tree [BKZ76]. For each data structure I work out the details of the algorithms by giving pseudo-code and for some of them I present new techniques, which give an easier and clearer presentation of the data structure and the algorithms. Last but not least, I answer an open problem concerning the space usage stated by Bose et al [Bos+13].

Master of Science (M.Sc.)