22 September 2011

Mikkel Thorup is new professor at DIKU - in algorithmics and data structures

As of 1. august 2011 Mikkel Thorup is appointed professor in algorithms and data structures at the Department of Computer Science (DIKU).

This is celebrated through an inaugural lecture on 29th September 2011. More info under events.

Hash-tables - or how a computer looks things up

Abstract:

Not too long ago we had to look up words in printed dictionaries with words sorted in alphabetical order. For many people this could be rater time consuming. Computers can look up in dictionaries much faster, but they have to do it many more times. This is often a computational bottle-neck, so if we could get better dictionaries, then this would help computers perform better in many contexts.

At AT&T I have paid special interest to the traffic on the Internet. When Internet users download, say music the music file is split into many packets which are transmitted separately. When you want to find out which packets belong together, you have to look them up based on header information like source and destination IP addresses. Those look-ups have to be very fast to keep up with the Internet traffic.

On computers we often refer to this kind of dictionaries as hash tables. Here 'hash' refers to implementations based on randomized hash functions that shuffle the tables in a random looking order. The point here is that the tables are not sorted like a traditional alphabetically ordered dictionary. The randomization gives a nice even spread facilitating very fast lookups.

We have studied and used hash tables since the 50'ies, but recently the field has been revolutionized thanks to better hash functions. It turned out that that the commonly used hash tables were not random enough. This made them very vulnerable in connection with "Denial-of-Service" attacks on the Internet. Thanks to our recent research we now have realistic hash functions that are provably safe against any attack: They have good expected performance no matter the input.

As mentioned, hash tables are used for almost any kind of data processing. The Internet is therefore only one of many applications of the new safe hash tables. In addition, the hash functions themselves have many applications beyond hash tables.

About Mikkel Thorup:

Mikkel Thorup has a D.Phil. from Oxford University from 1993. From 1993 to 1998 he was at the University of Copenhagen. Since then he has been at AT&T Labs-Research. He is a Fellow of the ACM and of AT&T, Member of the Royal Danish Academy of Sciences and Letters, and co-winner of the 2011 MAA Robbins Award. His main work is in algorithms and data structures and he is the editor of this area for the Journal of the ACM. One of his best-known results is a linear-time algorithm for the single-source shortest paths problem in undirected graphs. Mikkel prefers to seek his mathematical inspiration in nature, combining the quest with his hobbies of bird watching and mushroom picking.