Please use this identifier to cite or link to this item:
Title: Analyzing Trajectories Using Uncertainty and Background Information
Authors: KUIJPERS, Bart 
OTHMAN, Walied 
VAISMAN, Alejandro 
Issue Date: 2009
Publisher: Springer
Source: Mamoulis, Nikos & Seidl, Thomas & Pedersen, Torben Bach & Torp, Kristian & Assent, Ira (Ed.) Proceedings of the 11th International Symposium on Advances in Spatial and Temporal Databases (SSTD2009). p. 135-152.
Series/Report: Lecture Notes in Computer Science
Series/Report no.: 5644
Abstract: A key issue in clustering data, regardless the algorithm used, is the definition of a distance function. In the case of tra jectory data, different distance functions have been proposed, with different degrees of complexity. All these measures assume that tra jectories are error-free, which is essentially not true. Uncertainty is present in tra jectory data, which is usually obtained through a series of GPS of GSM observations. Trajectories are then reconstructed, typically using linear interpolation. A first source of error in tra jectory are the GPS observations themselves, since many reported points lie outside the road network. Thus, the users position must be matched to a map, leading to the problem of map matching. A well-known model to deal with uncertainty in a trajectory sample, uses the notion of space-time prisms (also called beads ), to estimate the positions where the object could have been, given a maximum speed. Thus, we can replace a (reconstructed) trajectory by a necklace (intuitively, a a chain of prisms ), connecting consecutive trajectory sample points. When it comes to clustering, the notion of uncertainty requires appropriate distance functions. The main contribution of this paper is the definition of a distance function that accounts for uncertainty, together with the proof that this function is also a metric, and therefore it can be used in clustering. We also present an algorithm that computes the distance between the chains of prisms corresponding to two trajectory samples. Finally, we discuss some preliminary results, obtained clustering a set of trajectories of cars in the center of the city of Milan, using the distance function introduced in this paper.
Document URI:
ISBN: 978-3-642-02981-3
DOI: 10.1007/978-3-642-02982-0_11
ISI #: 000269309400011
Category: C1
Type: Proceedings Paper
Validations: ecoom 2010
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
sstd2009_submission_21.pdfPublished version1.02 MBAdobe PDFView/Open
Show full item record


checked on Sep 2, 2020


checked on May 21, 2022

Page view(s)

checked on May 20, 2022


checked on May 20, 2022

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.