Mining Regions of Interest from trajectory data

The number of location-tracking devices is constantly increasing and so does the amount of captured trajectory data. There is hence an emerging need for scalable trajectory mining tools to extract knowledge from mobility data. In this work we focus on the problem of partitioning a space into meaningful regions of interest (ROIs) that are most frequently crossed by trajectories. This problem is of great importance as it constitutes the first step of the possible subsequent analysis of trajectories. Our contribution is that we formulate the task of discovering ROIs as a discrete optimization problem aiming to compress the dense regions with a given number simple parameterized shapes, such as rectangles. We give a linear program for solving this optimization problem assuming a given fixed number of ROIs. We then extend the approach to discover the best number of ROIs automatically by relying on the Minimum Description Length Principle. Our experiments on real and synthetic data show that the approach is scalable and able to retrieve ROIs of higher quality than those extracted with the well-known PopularRegion algorithm.