Novel Data Structures for Advanced Computational Movement Analysis

Abstract

In this work we present novel data structures and algorithms that answer queries on movement data, which is defined as the recording of an object's spatial location over a set of discrete time intervals. Specifically, we describe three extensive studies that propose new solutions to the problem of proximity searches on trajectory data under the continuous Fréchet distance. We provide both theoretical analysis and experimental results that improve over previous work. The first study discusses a scalable approach for range and k-nearest-neighbor trajectory queries on an input trajectory data set. We introduce a novel metric index tree structure whose size is linear in the number of input trajectories, improve on or introduce new upper and lower bound algorithms for computing the continuous Fréchet distance, and give search heuristics that reduce computations. The second study researches the problem of searching for the nearest sub-trajectory within a large input trajectory, given a query trajectory. A new linear size simplification tree structure and adaptive clustering-based query algorithm are described, and experiments on real and synthetic data sets show effective search space pruning compared to baseline approaches. The final study explores the problem of accurately recognizing human sign language words by mining and constructing geometric feature space trajectories from human body movement. Nearest-neighbor classification applies speed-invariant distance measures to trajectories, which improve sign recognition accuracy over recent state-of-the-art neural network approaches. Our research focuses on practical and scalable solutions which give exact or approximate results, and can be implemented in industrial applications. Moreover, we strive for interpretable algorithms where it is easy follow the steps and precisely understand how an answer is computed.