Sunday, December 23, 2007

ISAAC - Day 3

Today I gave my two presentations. Both papers are about trajectories, or what is sometime called geospatial lifelines, which is the the research topic of our project in Sydney. In the first paper we consider the problem of compressing, or simplifying, trajectories such that both the spatial and temporal information is preserved. The problem has been studied earlier in the database community, however, we gave a first method that guarantees that approximate versions of standard operations such as where_at, when_at and nearest neighbour are "sound". We also showed how the simplification can be done in O(n log^3 n) time (in practice the standard Douglas-Peucker algorithm in 3D works like a charm).

The second paper considered the problem of computing a "popular place" in a set of trajectories. A popular place is just a region, in our case a square of given side length, that is "visited" by at least k different trajectories. Our main result is a quadratic time algorithm with a "matching" 3-SUM hardness proof.

Both presentations went okay and hopefully some of the participants now have an idea of the existing problems in the area.

Finally I had sushi!

Tomorrow I'm going back to Sydney and my new office which is on the top floor of the School of IT building at University of Sydney.

No comments:

Post a Comment