90. matematické kolokvium KAM - Peter van Emde Boas (Universiteit van Amsterdam): The history of the van Emde Boas trees

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.

CV

Peter van Emde Boas studoval matematiku na Amsterdamské univerzitě v letech 1962 až 1969, tam také obhájil Ph.D. práci v roce 1974 na téma z teoretické informatiky. Na jeho příklon k teoretické informatice mely zásadní vliv pobyty na univerzitě Cornell v Ithace, NY, kde se seznámil s prací Jurise Hartmanise a kde také objevil datovou strukturu dnes známou pod jeho jménem. Od roku 1964 do 1977 působil v Matematickém centru v Amsterdamu (nyní CWI). Od roku 1969 působil na Amsterdamské univerzitě, kde je profesorem od roku 1977 (od roku 2009 emeritním profesorem). Kromě datových struktur se zabýval sémantikou programovacích i přirozených jazyků, teorií databází, umělou inteligencí, logikou a teorií her. Významná je například jeho role při nalezení 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). Školil 22 studentů, mezi nimi jsou Arjen Lenstra nebo Harry Buhrman. Prof. Emde Boas je dlouholetým organizátorem evropské informatiky, byl členem mnoha programových výborů informatických konferencí. O jeho vztahu k české komunitě svědčí i to, že byl předsedou programového výboru ICALP 1999 v Praze a konferenci SOFSEM 2004 a 2013, účastnil se a byl v programovém výboru řady konferencí MFCS.

utery 18. listopadu 2014 v 11:00, refektar (aula), prvni patro