high performance computing on graphics processing units: hgpu.org

Mobility is a key element of many processes and activities, and the understanding of movement is important in many areas of science and technology. 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 they record. It is necessary to develop efficient data mining algorithms and visual analytic techniques in order to extract useful and relevant information from movement data sets. There exist a well known collection of spatiotemporal patterns which can take place inside these data sets and, by detecting them, we can reveal important information. Due to the size of the input, this information can be very difficult, and sometimes impossible, to detect without using the appropriate algorithms. The increasing programmability and high computational rates of Graphics Processing Units (GPU) make them attractive as an alternative to CPUs for general-purpose computing. There exist some benefits like executing algorithms, or a part of them, in the GPU, releasing work from CPU. Although these tasks distribution considerably increases the algorithms efficiency, the most important feature of GPUs is their inherent parallelism that has been exploited in several algorithms and applications. In this thesis we treat and solve various problems related to movement pattern detection by designing and implementing parallel algorithms using the GPU. We first propose a GPU pipeline based algorithm to report the ‘Popular places’ pattern. We introduce the popularity map, that is, a measure of how many times the moving objects of a set have visited each point. Then, we study the problem of reporting all subtrajectory clusters of a trajectory, in other words, we look for similar curves within a trajectory. To measure similarity between curves we choose the Frechet distance. We show how the existing sequential algorithm can be modified exploiting parallel algorithms together with the GPU computational power showing substantial speed-ups. Finally we solve the ‘Flock pattern’. A flock refers to a large enough subset of entities that move close to each other for a given time interval. We present a parallel approach, to be run on a GPU, for reporting maximal flocks. To this aim, we present two algorithms to solve two problems related with the ‘Flock pattern’: finding the maximal sets of a family and intersecting two families of sets. The GPU parallel algorithms proposed to solve these two problems are later used for reporting flock patterns.