Approximate Nearest Neighbour
Approximate Nearest Neighbour ist ein Suchverfahren, das in riesigen Datenmengen sehr schnell Einträge findet, die einem gesuchten Eintrag ähnlich sind. Es verzichtet bewusst auf die Garantie, den allerbesten Treffer zu finden, und wird dadurch hunderte Male schneller.
Computer stellen Dinge wie Texte, Bilder oder Lieder oft als lange Zahlenlisten dar. Zwei solche Zahlenlisten kann man vergleichen: liegen sie nahe beieinander, sind sich die beiden Dinge ähnlich. Sucht man zu einem Bild das ähnlichste aus einer Sammlung, sucht man also die Zahlenliste mit dem geringsten Abstand. Bei einer Milliarde gespeicherter Einträge dauert es zu lange, jeden einzelnen durchzurechnen. Approximate Nearest Neighbour, kurz ANN, löst das Problem mit einem Kompromiss: Das Verfahren prüft nur einen kleinen, klug ausgewählten Teil der Sammlung. Es findet dadurch meist, aber nicht garantiert, den wirklich besten Treffer.
Warum ein bisschen Ungenauigkeit sich lohnt
Die exakte Suche nennt man Brute Force: Man vergleicht die Anfrage mit jedem einzelnen Eintrag. Das Ergebnis ist perfekt, die Rechenzeit aber wächst direkt mit der Datenmenge. Bei zehn Millionen Einträgen dauert eine solche Suche schnell mehrere Sekunden. Für eine Websuche oder einen Chatbot ist das unbrauchbar.
ANN dreht dieses Verhältnis um. Typische Verfahren liefern Antworten in wenigen Millisekunden, auch bei Milliarden Einträgen. Der Preis ist die sogenannte Recall-Rate: Sie gibt an, wie viel Prozent der wirklich besten Treffer gefunden wurden. Übliche Systeme arbeiten mit 95 bis 99 Prozent Recall.
In der Praxis fällt dieser Verlust kaum auf. Wenn eine Musik-App statt des zweitähnlichsten Songs den drittähnlichsten vorschlägt, merkt das niemand. Anders sieht es aus, wenn Vollständigkeit rechtlich gefordert ist, etwa bei einer Recherche in Gerichtsakten. Dort bleibt die exakte Suche die richtige Wahl.
Wie die Abkürzung durch den Datenberg entsteht
Alle ANN-Verfahren beruhen auf derselben Idee: Man ordnet die Daten vorher, damit man später große Teile überspringen kann. Diese Vorbereitung heißt Index-Aufbau und passiert einmalig. Sie kann Stunden dauern, spart danach aber bei jeder einzelnen Anfrage Zeit.
Ein verbreiteter Ansatz teilt die Daten in Gruppen ähnlicher Einträge auf. Zu jeder Gruppe merkt sich das System einen Mittelpunkt. Bei einer Anfrage vergleicht man zuerst nur die wenigen Mittelpunkte. Dann durchsucht man ausschließlich die zwei oder drei nächstliegenden Gruppen gründlich. Der Rest der Sammlung wird gar nicht erst angefasst.
Der heute wichtigste Ansatz heißt HNSW und arbeitet mit einem Netz aus Verbindungen. Jeder Eintrag ist mit einigen ähnlichen Einträgen verknüpft, wie Freunde in einem sozialen Netzwerk. Die Suche startet an einem beliebigen Punkt und hangelt sich immer zum nächstbesseren Nachbarn weiter. Zusätzlich gibt es eine grobe obere Ebene für weite Sprünge, ähnlich einem Autobahnnetz über den Landstraßen. So erreicht man die richtige Region in wenigen Schritten.
ANN in Suchfeldern und KI-Chatbots
Am häufigsten steckt ANN in Empfehlungssystemen. Streaming-Dienste und Online-Shops speichern für jeden Nutzer und jedes Produkt eine Zahlenliste. Der Vorschlag « Das könnte dir auch gefallen » ist im Kern eine ANN-Suche. Auch die Bildersuche des Smartphones funktioniert so, wenn sie auf Eingabe von « Hund » die passenden Fotos zeigt.
In KI-News taucht der Begriff meist im Zusammenhang mit Vektordatenbanken auf. Das sind Datenbanken, die genau für solche Ähnlichkeitssuchen gebaut sind. Anbieter wie Pinecone, Weaviate oder Qdrant verkaufen im Wesentlichen einen gut betriebenen ANN-Index.
Besonders wichtig ist das für Chatbots, die auf Firmendokumente zugreifen. Dieses Verfahren heißt RAG: Vor der Antwort sucht das System die passenden Textabschnitte heraus und legt sie dem Sprachmodell vor. Dieser Suchschritt ist eine ANN-Abfrage. Ein häufiger Irrtum ist deshalb, ANN für einen Teil des KI-Modells zu halten. Es ist reine Suchtechnik und funktioniert völlig ohne neuronale Netze.