Ítem


GPU parallel algorithms for reporting movement behaviour patterns in spatiotemporal databases

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’

Universitat de Girona

Altres contribucions: Universitat de Girona. Departament d’Informàtica, Matemàtica Aplicada i Estadística
Autor: Valladares Cereceda, Ignacio
Data: 18 juliol 2013
Resum: 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’
Format: application/pdf
Altres identificadors: Gi. 1117-2013
http://hdl.handle.net/10803/119544
Accés al document: http://hdl.handle.net/10256/9868
Llenguatge: eng
Editor: Universitat de Girona
Drets: ADVERTIMENT. L’accés als continguts d’aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d’investigació i docència en els termes establerts a l’art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l’autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s’autoritza la seva reproducció o altres formes d’explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d’un lloc aliè al servei TDX. Tampoc s’autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.
Matèria: GPU
Movement patterns
Patrons de moviment
Patrones de movimiento
Parallel
Paral·lel
Paralelo
Trajectory
Trajectòria
Trayectoria
Computacional geometry
Geometria computacional
Geometría computacional
Fréchet distance
Distància de Fréchet
Distancia de Fréchet
51 - Matemàtiques
68 - Indústries, oficis i comerç d’articles acabats. Tecnologia cibernètica i automàtica
Títol: GPU parallel algorithms for reporting movement behaviour patterns in spatiotemporal databases
Tipus: info:eu-repo/semantics/doctoralThesis
Repositori: DUGiDocs

Matèries

Autors