Wednesday, September 15, 2010

ESA 2010

I went to ESA in Liverpool two weeks ago (yes, this is late). It was an excellent conference all around (despite it's somewhat impossible to get to from the US location). Here is my biased take on the highlights:

  • Median Trajectories by K. Buchin, M. Buchin, M. van Kreveld, M. Löffler, R. Silveira, C. Wenk and L. Wiratma - An exciting paper defining and creating algorithms for a median trajectory. The idea of the problem is: Suppose that you know trajectories along which points were moving and want to define some "median" path, for example signifying a good walking route. What is an appropriate definition of such a common trajectory and how can it be calculated? This is a nice, and to my mind obviously important, problem statement. Worth a read of the paper. (Plus, it should be noted that this paper wins the award for shortest title and, as Mark de Berg pointed out during the business meeting, all papers with 2 word titles were accepted.)
  • Folks from Google Zurich (with paper Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns by H. Bast, E. Carlsson, A. Eigenwillig, R. Geisberger, C. Harrelson, V. Raychev and F. Viger) talked about the ways in which they solved the problem of routing in public transportation networks and how that's different than routing in street networks. One example they gave that was emblematic of this type of problem was suppose that all buses leaving from a given location have stopped for the evening, but intercity planes or trains have not, then the route needs to return a wait time, not a detour out of the country and back in to approach the location in a very circuitous and more expensive way.
  • Paolo Ferragina was one of the invited speakers. I'm particularly interested in his work, so I was excited about his talk already, but I wasn't sure if he was a good speaker or not. He is. He structured his talk as a history of data storage issues and trends and even though I had read many of the books/papers previously, everything made much more sense as he explained it. Unfortunately, I had to leave the talk a few minutes early (due to the impossible to get to nature of Liverpool and my correspondingly annoying flight plans) and so I missed his descriptions of the future of practical storage/retrieval algorithms and analysis. According to the title, they have something to do with joules, but I'll have to read the corresponding paper for the result of this cliffhanger. If it's anything like the talk, I recommend you do the same.

Also, the food at the banquet was really good. Credit where credit is due.