We propose a model for subtrajectory clustering ---the clustering of subsequences of trajectories; each cluster of subtrajectories is represented as a pathlet, a sequence of points that is not necessarily a subsequence of an input trajectory. Given a set of trajectories, our clustering model attempts to capture the shared portions between them by assuming each trajectory is a concatenation of a small set of pathlets, with possible gaps in between. We present a single objective function for finding the optimal collection of pathlets that best represents the trajectories taking into account noise and other artifacts of the data. We show that the subtrajectory clustering problem is NP-Hard and present fast approximation algorithms for subtrajectory clustering. We further improve the running time of our algorithm if the input trajectories are "well-behaved." Finally, we present experimental results on both real and synthetic data sets. We show via visualization and quantitative analysis that the algorithm indeed handles the desiderata of being robust to variations, being efficient and accurate, and being data-driven.

The Gromov-Hausdorff (GH) distance is a natural way to measure distance between two metric spaces. We prove that it is NP-hard to approximate the GH distance better than a factor of 3 for geodesic metrics on a pair of trees. We complement this result by providing a polynomial time O (min n , √ rn )-approximation algorithm for computing the GH distance between a pair of metric trees, where r is the ratio of the longest edge length in both trees to the shortest edge length. For metric trees with unit length edges, this yields an O (√ n )-approximation algorithm 1 .

Let M be a triangulated, orientable 2-manifold of genus g without boundary, and let h be a height function over M that is linear within each triangle. We present a kinetic data structure (KDS) for maintaining the Reeb graph R of h as the heights of M's vertices vary continuously with time. Assuming the heights of two vertices of M become equal only O(1) times, the KDS processes O((k + g) n \polylog n) events; n is the number of vertices in M, and k is the number of external events which change the combinatorial structure of R. Each event is processed in O(\log^2 n) time, and the total size of our KDS is O(gn). The KDS can be extended to maintain an augmented Reeb graph as well.

We propose parallel algorithms in the massively parallel communication (MPC) model (e.g. MapReduce) for processing large terrain elevation data (represented as a 3D point cloud) that are too big to fit on one machine. In particular, given a set S of 3D points that is distributed across multiple machines, we present a simple randomized algorithm to construct a TIN DEM of S by computing the Delaunay triangulation of the xy-projections of points in S, which is also stored across multiple machines. With high probability, the algorithm works in O(1) rounds and the total work performed is O(n log n). Next, we describe an efficient algorithm in the MPC model for computing the contour tree of the resulting DEM. Under some assumptions on the input, the algorithm works in O(1) rounds and the total work performed is O(n log n).

With the massive amounts of data available today, it is common to store and process data using multiple machines. Parallel programming platforms such as MapReduce and its variants are popular frameworks for handling such large data. We present the first provably efficient algorithms to compute, store, and query data structures for range queries and approximate nearest neighbor queries in a popular parallel computing abstraction that captures the salient features of MapReduce and other massively parallel communication (MPC) models. In particular, we describe algorithms for $kd$-trees, range trees, and BBD-trees that only require O(1) rounds of communication for both preprocessing and querying while staying competitive in terms of running time and workload to their classical counterparts. Our algorithms are randomized, but they can be made deterministic at some increase in their running time and workload while keeping the number of rounds of communication to be constant.