Top-k Spatial Join on GPU

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