Monday, September 29, 2008

SoCG call-for-papers

SoCG 2009 will take place on the 8-10 of June in Aarhus, Denmark. I'm sure it will be a lot of fun to visit Aarhus and Lars, especially since Sweden is playing against Denmark in the football world cup qualification on the 6th of June!

Here's the CFP.

Btw, why is Århus the city spelt with an `Å' while Aarhus University is spelt with `Aa’?

Wednesday, September 10, 2008

Algoritmics in NZ

The algorithmic activities in New Zealand continues. At the 7th Australia – New Zealand Mathematics Convention in Christchurch there will be a special algoritmics session. This special session is part of the thematic programme on Algorithmics funded by the New Zealand Institute for Mathematics and its Applications (NZIMA).

Also, Bernard Chazelle will give a series of public lectures in the period 13-22 March 2009.

Sunday, September 7, 2008

Clustering trajectories

Late last year I attended a (great) workshop in the Netherlands organised by Marc van Kreveld. From that workshop a few (!) papers came out. One of them was just accepted to ISAAC - "Detecting Commuting Patterns by Clustering Subtrajectories" by Kevin Buchin, Maike Buchin, Jun Luo, Maarten Löffler and me.

The problem of clustering trajectories is surprisingly hard. In the data mining/database community there are several papers on this problem that are fairly fast but not very accurate (useful?).

In the paper we focus on finding subtrajectories of a single trajectory that forms a cluster (can easily be extended to the general clustering problem). This is useful for detecting, e.g., commuting patterns or seasonal migration behaviour. Our approach builds on the Frechet distance and heavily makes use of the freespace diagram. This gives an accurate definition of a trajectory cluster (imho) but it is very costly to compute (both in time and space). The running time is roughly quadratic (for most settings) and a (non-optimised) implementation can handle 10K points in roughly 20 minutes.

The obvious open problem is: Is there an accurate definition of a trajectory cluster that would allow for a more efficient implementation?