caa a22 4500 445804440 CHVBK 20180317145152.0 cr unu---uuuuu 170323e20110801xx s 000 0 eng 10.1007/s00453-009-9376-2 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9376-2 Detecting Regular Visit Patterns [Elektronische Daten] [Bojan Djordjevic, Joachim Gudmundsson, Anh Pham, Thomas Wolle] We are given a trajectory $\mathcal{T}$ and an area $\mathcal{A}$ . $\mathcal{T}$ might intersect $\mathcal{A}$ several times, and our aim is to detect whether $\mathcal{T}$ visits $\mathcal{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 if and only if the trajectory $\mathcal {T}$ intersects the area $\mathcal{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 $\mathcal{T}$ intersecting $\mathcal{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. Springer Science+Business Media, LLC, 2009 Data structures nationallicence Approximation algorithms nationallicence Algorithms nationallicence Computational geometry nationallicence Djordjevic Bojan School of Information Technologies, University of Sydney, Sydney, Australia aut Gudmundsson Joachim NICTA Sydney, Locked Bag 9013, 1435, Alexandria, NSW, Australia aut Pham Anh School of Information Technologies, University of Sydney, Sydney, Australia aut Wolle Thomas NICTA Sydney, Locked Bag 9013, 1435, Alexandria, NSW, Australia aut Algorithmica Springer-Verlag 60/4(2011-08-01), 829-852 0178-4617 60:4<829 2011 60 453 https://doi.org/10.1007/s00453-009-9376-2 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9376-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Djordjevic Bojan School of Information Technologies, University of Sydney, Sydney, Australia aut NATIONALLICENCE 700 1- Gudmundsson Joachim NICTA Sydney, Locked Bag 9013, 1435, Alexandria, NSW, Australia aut NATIONALLICENCE 700 1- Pham Anh School of Information Technologies, University of Sydney, Sydney, Australia aut NATIONALLICENCE 700 1- Wolle Thomas NICTA Sydney, Locked Bag 9013, 1435, Alexandria, NSW, Australia aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/4(2011-08-01), 829-852 0178-4617 60:4<829 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer