Masters Theses
Keywords and Phrases
Piecewise constant approximation; Shape similarity; Mahalanobis distance
Abstract
"With the rapid advances of mobile device technology and positioning techniques, more and more trajectory data from moving objects is being generated and used by location aware systems such as vehicle navigation system. There are several queries which are generally made by the users of vehicle navigation system which need to retrieve similar trajectories based on distance metrics. There have been several distance metrics proposed as similarity measures for searching patterns of interest embedded in the trajectory databases. Most of the similarity search techniques based on these metrics embed an n-point trajectory in an n-dimensional Euclidean space. Metrics proposed in the past fundamentally are the Lp-norms or their modifications, between a given trajectory and the query trajectory in this Euclidean space. These metrics do not account either for correlations inherent amongst various dimensions of the trajectory that occur due to characteristics of spatial data or the irregular scaling due to the disparity of the sources from where the trajectory data is procured. It is also found that the distance metrics that are fairly accurate for one application perform poorly for others. Dimensionality also plays a very vital role in the performance of the distance metrics. In this paper we propose a novel generalized distance metric based on a model that incorporates the time axis explicitly. The proposed metric is based fundamentally on the Mahalanobis distance metric, which eliminates the correlation and scaling errors in similarity searches on trajectory databases. We also propose the incorporation of a weight matrix in the proposed distance metric, which allows for easy manipulation of the degree of significance of the different spatial and or temporal dimensions. This renders the proposed metric more customizable for various applications. The introduction of dimensionality reduction using the popular Piecewise Constant Approximation technique, in the trajectory data set produces the approximate similar trajectory in a faster manner. But such a fast search of getting approximate similar trajectory by reducing the dimensionality of data is accompanied by loss of precision of query results. We present a discussion with real world examples on how this generalized distance metric improves accuracy of various classes of similarity search queries and its suitability for real-time applications. We implemented our algorithms in Matlab and tested them using City Simulator database containing 10,000 trajectories. We show two set of results using the proposed metric. The first set is the result of using the proposed metric for exact similarity search by processing the trajectory data in its entirety and the second set is the result of using the distance metric for fast approximate similarity search on trajectory data where dimensions have been reduced using Piecewise Constant Approximation"--Abstract, pp. iv-v
Advisor(s)
Madria, Sanjay Kumar
Committee Member(s)
McMillin, Bruce M.
Jagannathan, Sarangapani, 1965-
Department(s)
Computer Science
Degree Name
M.S. in Computer Science
Publisher
University of Missouri--Rolla
Publication Date
Summer 2004
Pagination
ix, 50 pages
Note about bibliography
Includes bibliographical references (pages 46-49)
Rights
© 2004 Garima Pathak, All rights reserved.
Document Type
Thesis - Restricted Access
File Type
text
Language
English
Subject Headings
Wireless communication systemsDistance geometryApproximation theory
Thesis Number
T 8606
Print OCLC #
62260202
Recommended Citation
Pathak, Garima, "Generalized distance metric as a robust similarity measure for mobile object trajectories" (2004). Masters Theses. 3632.
https://scholarsmine.mst.edu/masters_theses/3632
Share My Thesis If you are the author of this work and would like to grant permission to make it openly accessible to all, please click the button above.
