Själv-join finner alla objekt i en datauppsättning inom en tröskel för varandra som definieras av en likhetsmått. Som sådan, själv-join är en byggsten för området databaser och data mining, och är anställd i Big Data applikationer. I detta dokument, vi avancerar en GPU-effektiv algoritm för likhet själv-join som använder Euclidean avstånd metrisk. Sök-och-raffinaderistrategin är ett effektivt tillvägagångssätt för datauppsättningar med låga dimensioner, eftersom indexsökningar bryts ned med ökande dimension (dvs. dimensionalitetens förbannelse). Således inriktar vi oss på problemet med låg dimension, och jämför vår GPU själv-join med en sök-och-raffinaderi genomförande, och en toppmodern parallellalgoritm. I låg dimensionalitet finns det flera unika utmaningar i samband med att effektivt lösa själv-join-problemet på GPU. Lågdimensionella data resulterar ofta i högre datatätheter, vilket orsakar ett betydande antal avståndsberäkningar och en stor resultatuppsättning. I takt med att dimensionaliteten ökar blir indexsökningen allt mer omfattande, vilket skapar en performance flaskhals. Vi avancerar flera tekniker för att övervinna dessa utmaningar med hjälp av GPU. De tekniker vi föreslår inkluderar en GPU-effektiv index som använder en begränsad sökning, en batching system för att rymma stora resultat inställda storlekar, och en minskning av avstånd beräkningar genom dubbla sökning borttagning. Vårt GPU-självspel överträffar både sök-och-raffinaderi- och toppmoderna algoritmer.
En GPU själv-join presenterades i REF som visade sig vara effektiv på lågdimensionella data.
GPU Accelerated Self-Join for the Distance Similarity Metric
{'venue': '2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)', 'journal': '2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)', 'mag_field_of_study': ['Computer Science']}