Scalable Techniques for Trajectory Outlier Detection
2019-06
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Scalable Techniques for Trajectory Outlier Detection
Authors
Published Date
2019-06
Publisher
Type
Thesis or Dissertation
Abstract
The recent improvements in tracking devices and positioning satellites have led to an increased availability of spatial data describing the movement of objects such as vehicles, animals, etc. Such data is obtained by recording the positions of the objects at regular intervals and then arranging the collected positions of each object into a time-ordered sequence called trajectory. The high availability of trajectory data has permitted the execution of data analysis operations such as trajectory outlier detection, which consists in the identification of those trajectories that behave much differently from the rest of the trajectories in a database. There are several time-critical applications such as traffic management systems, security surveillance systems and real-time stock monitoring, etc. which can be solved through trajectory outlier detection. However, the time-critical nature of such applications imposes tight constraints on the execution time of trajectory outlier detection algorithms. To deal with these constraints, we propose three strategies to accelerate the performance of the existing trajectory outlier detection algorithm ODMTS. First, we consider using spatial data structures such as k-d trees and R-trees to improve the running time performance of the ODMTS algorithm for trajectory outlier detection. Our results showed that by using R-trees we can improve the execution time of ODMTS by a factor of 10X. Our second strategy consists in harnessing the power of multiple CPUs to parallelize the ODMTS algorithm. This strategy yielded an execution time improvement that scales linearly with the number of cores, which in our case achieved 32X. The third strategy consists in a new partitioning-based streaming algorithm, called PDMTS, for trajectory outlier detection that leverages data streams in order to find trajectory outliers. Our experiments on real-life datasets showed that our proposed algorithm detected almost 45% outliers more than ODMTS, but is almost 18% slower than compared to ODMTS due to the partitioning step.
Keywords
Description
University of Minnesota M.S. thesis. June 2019. Major: Computer Science. Advisor: Eleazar Leal. 1 computer file (PDF); viii, 52 pages.
Related to
Replaces
License
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Gohar, Usman. (2019). Scalable Techniques for Trajectory Outlier Detection. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/206183.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.