GPU parallel algorithms for reporting movement behaviour patterns in spatiotemporal databases

Abstract

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. Then, we study the problem of reporting all subtrajectory clusters of a trajectory. To measure similarity between curves we choose the Fréchet distance. Finally we solve the ’Flock pattern’. 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

En aquesta tesi tractem i resolem varis problemes relacionats amb el càlcul de patrons de moviment en bases de dades espai-temporals, dissenyant i implementant algoritmes paral·lels utilitzant GPUs. Primer, proposem un algoritme que utilitza els processos gràfics de la GPU per reportar el patró ‘Llocs Populars’. Després estudiem el problema de reportar tots els grups de subtrajectories d’una trajectòria. Per mesurar la similitud entre corbes hem triat la distancia de Fréchet. Finalment resolem el problema del patró ‘Ramat’. Amb aquest objectiu, presentem dos algorismes per resoldre dos problemes relacionats amb el patró ‘Ramat’: El problema de trobar tots els conjunts maximals de una família, i el problema de intersecar dos famílies de conjunts. Proposem algorismes paral·lels per resoldre els dos problemes que després s’utilitzen per reportar patrons ’Ramat’