# Research Publications

Detecting Regular Visit Patterns
Bojan Djordjevic, (Hans) Joachim Gudmundsson, Anh Pham, 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 {\em most} of the days (weeks or years), but not necessarily on {\em every} day (week or year). During the modelling of such applications, we encountered an elementary problem on bitstrings, that we call {\sc 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.

## Details

 Status: published Type: Conference Paper Conference Name: Algorithms - ESA 2008 Pages: 344-355 City/Country: Karlsruhe/Germany Conference URL: dx.doi.org/10.1007/978-3-540-87744-8_29 Publisher: Springer-Verlag, LNCS Volume 5193