Ein hoch-performanter (approximierter) k-Nächste-Nachbarn Algorithmus für GPUs

Abstract

In der heutigen Zeit, in der immer mehr Daten zur Verfügung stehen, gewinnt das Data-Mining zunehmendan Bedeutung. Insbesondere ist die Klassifizierung eine zentrale Methode des Data-Minings. Eine Möglichkeit Daten zu klassifizieren, stellt die Nächste-Nachbarn-Klassifikation dar. Dabei wird einem Objekt eine Klasse nur aufgrund dessen lokaler Nachbarschaft zugewiesen. Der naive Ansatz zur Lösung der Nächste-Nachbarn-Klassifikation setzt jedoch voraus, dass alle anderen Objekte in der Datenmenge betrachtet werden müssen, wodurch er eine quadratische Komplexität besitzt, was bei deren stetig wachsender Größe immer ineffizienter wird. Aufgrund dieser hohen Kosten, sind bei großen Datenmengen approximierende Verfahren attraktiv. Ein solches approximierendes Verfahren ist das in dieser Arbeit verwendete Locality Sensitive Hashing. Dieses Verfahren teilt alle Datenpunkte basierend auf deren Lokalisation durch spezielle Hash-Funktionen in Hash-Buckets auf. Mithilfe dieser Aufteilung müssen bei der Suche nach den Nächsten-Nachbarn nicht mehr alle Datenpunkte betrachtet werden. Zusätzlich zur Wahl des Algorithmus, muss jedoch auch auf eine hochperformante Implementierung für Grafikkarten geachtet werden. Dabei konnte auf NVIDIAs QUADRO GP100 Grafikkarte eine Laufzeitverbesserung um das bis zu 10-fache bei einer gleichzeitigen Genauigkeit von über 90%, gegenüber einer ebenfalls für Grafikkarten optimierten Implementierung des Naiven Algorithmus, für einen Datensatz mit 500 000 Datenpunkten in 10 Dimensionen beobachtet werden.