# 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

Abstrakt:

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

regularity.

Room: LTH, E:2405

*Last modified Dec 9, 2011 12:59 pm
*

0223