Global distance-based segmentation of trajectories
Authors:
Open Access
- 20 August 2006
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 34-43
Abstract
This work introduces distance-based criteria for segmentation of object trajectories. Segmentation leads to simplification of the original objects into smaller, less complex primitives that are better suited for storage and retrieval purposes. Previous work on trajectory segmentation attacked the problem locally, segmenting separately each trajectory of the database. Therefore, they did not directly optimize the inter-object separability, which is necessary for mining operations such as searching, clustering, and classification on large databases. In this paper we analyze the trajectory segmentation problem from a global perspective, utilizing data aware distance-based optimization techniques, which optimize pairwise distance estimates hence leading to more efficient object pruning. We first derive exact solutions of the distance-based formulation. Due to the intractable complexity of the exact solution, we present an approximate, greedy solution that exploits forward searching of locally optimal solutions. Since the greedy solution also imposes a prohibitive computational cost, we also put forward more lightweight variance-based segmentation techniques, which intelligently "relax" the pairwise distance only in the areas that affect the least the mining operations. Copyright 2006 ACMKeywords
This publication has 9 references indexed in Scilit:
- Modeling Multiple Time Series for Anomaly Detection2006
- Query-sensitive embeddings2005
- Indexing Large Human-Motion Databases2004
- Indexing multi-dimensional time-series with support for multiple distance measures2003
- Efficient k-NN search on vertically decomposed data2002
- Locally adaptive dimensionality reduction for indexing large time series databases2001
- Analyses of mitochondrial genomes strongly support a hippopotamus-whale cladeProceedings Of The Royal Society B-Biological Sciences, 1998
- FlyThru the Boeing 7771996
- I-COLLIDE1995