Movement Patterns Detection in Spatio-Temporal Data

Master Specialization: Visualization, Virtual Reality and Graphic Interaction
Topic Aproval date: 18/02/09
Orientation: research

Student: Ignacio Valladares
Thesis advisor(s): Joan Antoni Sellarès
Contact:

Mobility is a key element of many processes and activities, and the understanding of movement is important in many areas of science and technology such as meteorology, biology, sociology, transportation engineering, etc. With the recent advances in technologies for mobile devices, like GPS and mobile phones, we are able to generate data sets of people, animals, vehicles and other moving objects, normally available as sample points, representing a position in space in a certain instant of time. In most cases, moving object data sets are rather large in volume and complex in the structure of movement patterns that they record. Therefore, it is necessary to develop efficient data mining algorithms and visual analytics techniques in order to extract useful and relevant information, regularities and structure from massive movement data sets.

The understanding of movement is important in many areas of science and technology, for example: traffic management, surveillance and security, sport scene analysis, animal behavior and social interactions. There exist a well known collection of spatio-temporal patterns based on location and motion direction, which can occur for a subset of the moving point objects at a given time step or time interval. The flock pattern describes points moving in the same direction while  being close  to each other. The leadership pattern is similar to the flock pattern, except that one of the entities was already heading in the specified direction for some time before the flock pattern occurs. Convergence refers to moving to the  same location , given that the direction of motion does not change. The entities need not arrive at the same time. Finally, encounter refers to moving to and meeting at the same location, so it is a convergence pattern where the entities arrive at the same time.

The main aim of the Master thesis is to use Computational Geometry techniques together with the GPU power to solve problems related to movement patterns search. We will try to design more efficient algorithms for the actual solved problems that use code totally executed in the CPU. Taking into account that moving object data are approximated, the approximate solutions obtained with the GPU will be acceptable.