Similarity Search on Uncertain Spatio-temporal Data
Johannes Niedermayer, Andreas Zuefle, Tobias Emrich, Matthias Renz, Nikos Mamoulis, Lei Chen, Hans‐Peter Kriegel · 2013
Abstract: In this work, we address the problem of similarity search in a database of uncertain spatio-temporal objects. Each object is defined by a set of observations ((time,location)-tuples) and a Markov chain which describes the objects uncertain mo-tion in space and time. To model similarity- which is an important building block for many applications such as identifying frequent motion patterns or trajectory clus-tering- we employ the well-known Longest Common Subsequence (LCSS) measure, which becomes a distribution on uncertain spatio-temporal data (ULCSS). We show how the aligned version (without time shifting) of the ULCSS can be exactly computed in PTIME, which is also verified by extensive experiments. 1