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’?
Monday, September 29, 2008
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.
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?
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?
Subscribe to:
Posts (Atom)
