GPU Parallel Algorithms for Reporting Movement Behaviour Patterns in Spatiotemporal Databases

Nacho Valladares Cereceda
University of Girona
University of Girona, 2013

   title={GPU parallel algorithms for reporting movement behaviour patterns in spatiotemporal databases},

   author={Valladares Cereceda, Ignacio and others},


   publisher={Universitat de Girona}


Download Download (PDF)   View View   Source Source   



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.
VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)

* * *

* * *

Follow us on Twitter

HGPU group

1666 peoples are following HGPU @twitter

Like us on Facebook

HGPU group

338 people like HGPU on Facebook

* * *

Free GPU computing nodes at hgpu.org

Registered users can now run their OpenCL application at hgpu.org. We provide 1 minute of computer time per each run on two nodes with two AMD and one nVidia graphics processing units, correspondingly. There are no restrictions on the number of starts.

The platforms are

Node 1
  • GPU device 0: nVidia GeForce GTX 560 Ti 2GB, 822MHz
  • GPU device 1: AMD/ATI Radeon HD 6970 2GB, 880MHz
  • CPU: AMD Phenom II X6 @ 2.8GHz 1055T
  • RAM: 12GB
  • OS: OpenSUSE 13.1
  • SDK: nVidia CUDA Toolkit 6.5.14, AMD APP SDK 3.0
Node 2
  • GPU device 0: AMD/ATI Radeon HD 7970 3GB, 1000MHz
  • GPU device 1: AMD/ATI Radeon HD 5870 2GB, 850MHz
  • CPU: Intel Core i7-2600 @ 3.4GHz
  • RAM: 16GB
  • OS: OpenSUSE 12.3
  • SDK: AMD APP SDK 3.0

Completed OpenCL project should be uploaded via User dashboard (see instructions and example there), compilation and execution terminal output logs will be provided to the user.

The information send to hgpu.org will be treated according to our Privacy Policy

HGPU group © 2010-2015 hgpu.org

All rights belong to the respective authors

Contact us: