92 KAM Mathematical Colloquium
Peter van Emde Boas
Universiteit van Amsterdam
THE HISTORY OF THE VAN EMDE BOAS TREES
Tuesday November 18 2014 at 11:00, refektář room, first floor
KAM MFF UK
Malostranské nám. 25
118 00 Praha 1
Abstract
The stratified tree, also called van Emde Boas tree, is a data structure implementing the full
repertoire of instructions manipulating a single subset of a finite ordered universe of size $u$
with the processing time per instruction $O(\log\log(u))$. Hence it improves upon the traditional
comparison based tree structures for dense subsets. Examples exist where this improvement helps to
speed-up algorithmic solutions of real problems; such applications can be found for example in graph
algorithms, computational geometry and forwarding of packets on the internet.
This data structure was invented during a three months postdoc residence at Cornell University in the fall of 1974.
In my talk I want to describe the historical backgrounds against which the
stratified trees were discovered and implemented.
In the literature today, the data structure is usually described by a direct
recursive approach. However, this requires address calculations on the arguments
which use multiplicative arithmetical instructions. These instructions were not allowed in
the Random Access Machine model (RAM) which was the standard model in 1974. Therefore my early
implementations of the stratified trees were based on a different approach which is best described as
a binary-search-on-levels strategy. In this approach the address calculations were not required,
and the structure could be implemented using pointers. The downside of this approach is that it
leads to rather complex algorithms, which are still hard to present correctly even today. Another
bad consequence was the super linear space consumption of the data structure, which was only
eliminated three years later.
O přednášejícím
Peter van Emde Boas studoval matematiku na Amsterdamske univerzite v
letech 1962 až 1969, tam take obhajil Ph.D. praci v roce 1974 na tema z
teoreticke informatiky. Na jeho priklon k teoreticke informatice mely zasadni
vliv pobyty na univerzite Cornell v Ithace, NY, kde se seznamil s praci Jurise
Hartmanise a kde take objevil datovou strukturu dnes znamou pod jeho jmenem.
Od roku 1964 do 1977 pusobil v Matematickem centru v Amsterdamu (nyni CWI).
Od roku 1969 pusobil na Amsterdamske univerzite, kde je profesorem od roku 1977
(od roku 2009 emeritnim profesorem). Krome datovych struktur se zabyval semantikou
programovacich i prirozenych jazyku, teorii databazi, umelou inteligenci,
logikou a teorii her. Vyznamna je napriklad jeho role pri nalezeni LLL algoritmu
(viz I. Smets, A. Lenstra, H. Lenstra, L. Lovasz, P. van Emde Boas:
The History of the LLL-Algorithm. In: The LLL Algorithm, Springer 2010, pp.1-17).
Skolil 22 studentu, mezi nimi jsou Arjen Lenstra nebo Harry Buhrman.
Prof. Emde Boas je dlouholetym organizatorem evropske informatiky, byl clenem mnoha programovych vyboru
informatickych konferenci. O jeho vztahu k ceske komunite svedci i to, že byl predsedou programoveho
vyboru ICALP 1999 v Praze a konferenci SOFSEM 2004 a 2013, ucastnil se a byl v programovem vyboru rady konferenci MFCS.