Top-k Spatial Join on GPU

Abstract

Gitt to sett med romlige objekter der hvert objekt har en rangering, et romlig sammenslåingspredikat (f.eks. en punktdistanse-begrensning), og en summeringsfunksjon som sammenslår rangeringen til et par av objekter (f.eks. en vektet sum), slår top-k spatial join-operasjonen sammen settene med det romlige sammenslåingspredikatet og returnerer de \(k\) parene som har best sammenslått rangering. Romlige datasett kan være komplekse og store, som gjør det nødvendig å benytte datastrukturer for romlig indeksering slik som R-treet for å øke ytelsen på spatial join og romlige spørringer. Det finnes algoritmer for top-k spatial join basert på R-trær, men de er sekvensielle algoritmer med begrenset ytelse grunnet bruk av kun én tråd. For å øke ytelsen på top-k spatial join videre kan parallelle algoritmer anvendes, men forskning på dette området er begrenset.

Grafikkprosessorer er i ferd med å bli prisgunstig og utbredt maskinvare, og deres evne for massivt parallell prosessering kan benyttes for å oppnå høy ytelse. APIer som CUDA har muliggjort trenden ``general-purpose computing on graphics processors'' (GPGPU), som har blitt en populær måte å øke ytelsen til applikasjoner i visse felt. Det kreves spesiell design for å effektivt anvende grafikkprosessorer, derfor kreves det ny forskning for å tilpassse metoder til det nye databehandlingsparadigmet. Forskning viser at ytelsen for parallelle romlige spørringer på R-trær kan økes med GPGPU, men det finnes lite forskning på prosessering av spatial joins og top-k-spørringer generelt med GPGPU.

I denne oppgaven har hovedmålet vært å fastslå hvordan GPGPU kan anvendes for top-k spatial join-spørringer og hvorvidt/hvordan dette kan oppnå økt ytelse. Et sekundærmål angår det samme men ved bruk av flere tråder. For å fastsette dette har vi undersøkt GPGPU, R-treet og relaterte algoritmer, ranked joins, sorteringsalgoritmer og heaps og utviklet en enkelttråds-versjon, en flertråds-versjon og en CUDA-versjon av den Blokkbaserte Algoritmen, og konkludert med en eksperimentell evaluering. Evalueringen viser at GPGPU kan effektivt anvendes for top-k spatial joins, men vår implementasjon oppnår kun betydelig økt ytelse for særlig store inndata med få returverdier. Generelt er bruk av flere tråder et mer effektivt alternativ, da flertråds-versjonen har bedre ytelse enn enkelttråds-versjonen i alle eksperimenter utenom de med de minste inndataene.

Given two sets of spatial objects where each object is assigned a score, a spatial join predicate (such as a point distance threshold), and an aggregate function that combines scores for pairs of objects (such as a weighted sum), the top-k spatial join query joins the sets by the spatial join predicate and returns the \(k\) pairs with the best scores. Spatial data sets can be complex and large, requiring the use of spatial indexing data structures such as the R-tree to accelerate spatial queries and spatial joins. A number of top-k spatial join algorithms based on R-trees exist, but they are sequential algorithms whose performance is limited by the use of a single thread. To accelerate top-k spatial joins further, parallel algorithms could be applied, but research on this particular subject is limited.

Graphics processors are becoming commodity hardware, and their massively parallel processing capabilities can be used to achieve high performance. APIs such as CUDA have enabled the trend of general-purpose computing on graphics processors (GPGPU), which has become a popular way to accelerate applications in certain domains. Special application design is required to efficiently utilize graphics hardware, which requires new research to adapt to this new computing paradigm. Research shows that parallel spatial queries and spatial joins on R-trees can be sped up significantly with GPGPU, but little research has been made into processing top-k spatial joins and top-k queries in general with GPGPU.

In this thesis, the primary goal has been to determine how to perform top-k spatial joins using GPGPU and determine if or how it can be used to achieve speedups. A secondary goal applies similarly to parallel top-k spatial joins using multi-threading. To achieve this, we researched GPGPU, the R-tree and related algorithms, ranked joins, sorting algorithms and heaps and developed a single-threaded, a multi-threaded and a CUDA implementation of the Block-based Algorithm, and finally performed an experimental evaluation. The experimental evaluation shows that top-k spatial joins can be performed efficiently using GPGPU, but the implementation only achieves significant speedups for particularly large inputs and small outputs. Multi-threaded top-k spatial joins is a more viable alternative in general, where the multi-threaded implementation outperforms the single-threaded implementation in all experiments except for the ones with the smallest inputs.