Schnelle ungefähre nächste Nachbarn mit automatischer Algorithmus-Konfiguration

Nächste-Nachbarn-Suche, randomisierte kd-Bäume, hierarchischer k-means-Baum, Clustering. Bei vielen Problemen der Computer Vision besteht die zeitaufwändigste Komponente in der Übereinstimmungsfindung nächster Nachbarn in hochdimensionalen Räumen. Es sind keine exakten Algorithmen bekannt, die diese hochdimensionalen Probleme schneller als die lineare Suche lösen. Ungefähre Algorithmen sind bekannt dafür, große Geschwindigkeitssteigerungen mit nur geringfügigem Genauigkeitsverlust zu bieten, aber viele dieser Algorithmen wurden mit nur minimaler Anleitung zur Auswahl eines Algorithmus und seiner Parameter für ein gegebenes Problem veröffentlicht. In diesem Papier beschreiben wir ein System, das die Frage beantwortet: „Welcher ist der schnellste ungefähre nächster-Nachbar-Algorithmus für meine Daten?“ Unser System nimmt einen gegebenen Datensatz und ein gewünschtes Genauigkeitsmaß und bestimmt damit automatisch den besten Algorithmus und die besten Parameterwerte. Wir beschreiben auch einen neuen Algorithmus, der Prioritätssuche auf hierarchischen k-means-Bäumen anwendet, der sich als mit Abstand leistungsfähigster auf vielen Datensätzen erwiesen hat. Nach der Prüfung verschiedener Alternativen haben wir festgestellt, dass mehrere randomisierte k-d Bäume für andere Datensätze die beste Leistung erbringen. Wir veröffentlichen öffentlich zugänglichen Code, der diese Ansätze implementiert. Diese Bibliothek bietet etwa eine Größenordnung Verbesserung bei der Abfragezeit gegenüber der besten bisher verfügbaren Software und stellt eine vollautomatische Parameterauswahl bereit.