Seminar within Theory Pearls: "Repetitive patterns", Joachim Gudmundsson, NICTA Sydney

Date: October 29, 2008 (Wednesday) at 14:15 to 15:00

Titel: Detecting Regular Visit Patterns
Joint work with: Bojan Djordjevic, Anh Pham and Thomas Wolle
We are given a trajectory T and an area A. T might intersect A several
times, and our aim is to detect whether T visits A with some
regularity, e.g. what is the longest time span that a GPS-GSM equipped
elephant visited a specific lake on a daily (weekly or yearly) basis,
where the elephant has to visit the lake most of the days (weeks or
years), but not necessarily on every day (week or year).

During the modelling of such applications, we encountered an
elementary problem on bitstrings, that we call LDS
(LongestDenseSubstring). The bits of the bitstring correspond to a
sequence of regular time points, in which a bit is set to 1 iff the
trajectory T intersects the area A at the corresponding time point.
For the LDS problem, we are given a string s as input and want to
output a longest substring of s, such that the ratio of 1's in the
substring is at least a certain threshold.

In our model, LDS is a core problem for many applications that aim at
detecting regularity of T intersecting A. We propose an optimal
algorithm to solve LDS, and also for related problems that are closer
to applications, we provide efficient algorithms for detecting

Room: LTH, E:2405

Last modified Dec 9, 2011 12:59 pm