Einführung der ANN-Suche (Approximate Nearest Neighbor) in Elasticsearch 8.0

Das Interesse an der Vektorsuche ist dank einer neuen Generation von Machine-Learning-Modellen, die alle Arten von Inhalten – einschließlich Text, Bildern, Ereignissen und mehr – als Vektoren darstellen können, stark gestiegen. Diese leistungsfähigen Repräsentationen, die oft als „Embedding-Modelle“ bezeichnet werden, können Ähnlichkeiten zwischen zwei Inhalten erfassen, die über deren oberflächliche Merkmale hinausgehen.

k-Nearest-Neighbor-Algorithmen zum Suchen (kNN) finden die Vektoren in einem Datensatz, die einem Abfragevektor am ähnlichsten sind. In Verbindung mit diesen Vektordarstellungen eröffnet die kNN-Suchen spannende Möglichkeiten für den Abruf:

• Passagen finden, die wahrscheinlich die Antwort auf eine Frage enthalten
• Erkennung von nahezu identischen Bildern in einem großen Datensatz
• Lieder finden, die einem bestimmten Lied ähnlich klingen

Die Vektorsuche ist auf dem besten Weg, neben traditionellen Verfahren wie der begriffsbasierten Bewertung zu einem wichtigen Bestandteil des Such-Toolkits zu werden.

Elasticsearch unterstützt derzeit das Speichern von Vektoren über den Feldtyp dense_vector und deren Verwendung zur Berechnung von Dokument-Scores. Dies ermöglicht es Nutzern, ein exaktes kNN-Suchen durch das Scannen aller Dokumente durchzuführen. Elasticsearch 8.0 baut auf dieser Funktionalität auf, um eine schnelle, approximative Suche nach nächsten Nachbarn (ANN) zu unterstützen. Dies stellt einen Ansatz mit wesentlich höherer Skalierbarkeit dar, der es ermöglicht, das Suchen nach Vektoren effizient auf großen Datensätzen auszuführen.

ANN in Elasticsearch

Was ist die Approximate Nearest Neighbor-suchen?

Es gibt bewährte Datenstrukturen für kNN bei niedrigdimensionalen Vektoren, wie z. B. KD-Bäume. Tatsächlich integriert Elasticsearch KD-Bäume, um Suchen auf Geodaten und numerischen Daten zu unterstützen. Moderne Einbettungsmodelle für Text und Bilder erzeugen jedoch typischerweise hochdimensionale Vektoren mit 100 – 1.000 Elementen oder sogar mehr. Diese Vektordarstellungen stellen eine einzigartige Herausforderung dar, da es sehr schwierig ist, in hohen Dimensionen effizient die nächsten Nachbarn zu finden.

Angesichts dieser Schwierigkeit opfern Algorithmen für die Suche nach nächsten Nachbarn normalerweise die perfekte Genauigkeit, um ihre Geschwindigkeit zu verbessern. Diese Algorithmen für ungefähre nächste Nachbarn (ANN) geben möglicherweise nicht immer die tatsächlichen k nächsten Vektoren zurück. Sie werden jedoch effizient ausgeführt, lassen sich auf große Datensätze skalieren und pflegen dabei eine gute Leistung.

Auswahl eines ANN-Algorithmus

Die Entwicklung von ANN-Algorithmen ist ein aktives akademisches Flächendiagramm, und es gibt viele vielversprechende Algorithmen, aus denen man wählen kann. Sie bieten oft unterschiedliche Kompromisse in Bezug auf Suchgeschwindigkeit, Implementierungskomplexität und Kosten für das Indexieren. Glücklicherweise gibt es ein großartiges Open-Source-Projekt namens ann-benchmarks, das die führenden Algorithmen anhand verschiedener Datensätze testet und Vergleiche veröffentlicht.

Elasticsearch 8.0 verwendet einen ANN-Algorithmus namens Hierarchical Navigable Small World (HNSW)-Graphen, der Vektoren basierend auf ihrer Ähnlichkeit zueinander in einem Graphen organisiert. HNSW zeigt eine starke Suchleistung bei einer Vielzahl von ann-benchmarks-Datensätzen und hat auch in unseren eigenen Tests gut abgeschnitten. Ein weiterer Vorteil von HNSW ist, dass es in der Industrie weit verbreitet ist und bereits in mehreren verschiedenen Systemen implementiert wurde. Neben dem wissenschaftlichen Originalpapier gibt es viele hilfreiche Ressourcen, um mehr über die Details des Algorithmus zu erfahren. Obwohl Elasticsearch ANN derzeit auf HNSW basiert, ist das Feature flexibel konzipiert, sodass wir in Zukunft verschiedene Ansätze integrieren können.

Zeigen Sie mir den Code!

Um Vektoren für die ANN-Suchen zu indexieren, müssen wir index: true setzen und die Ähnlichkeitsmetrik angeben, die wir für den Vergleich verwenden:

In diesem Beispiel ist die ANN-suchen um Größenordnungen schneller als der exakte Ansatz. Der Recall liegt bei etwa 95 %, sodass im Durchschnitt über 9 von 10 tatsächlichen nächsten Nachbarn gefunden werden.

Sie können die Leistung beim kNN-Suchen in den nächtlichen Elasticsearch-Benchmarks überprüfen. Diese Benchmarks werden durch es-rally unterstützt, ein Tool für Elasticsearch-Benchmarking, insbesondere durch den neuen dense_vector Rally-Track. Wir planen, Rally zukünftig so zu erweitern, dass neben der Latenz auch über den Recall Bericht erstattet wird, da es ebenfalls wichtig ist, die Genauigkeit des Algorithmus zu verfolgen. Derzeit testen diese Benchmarks einen Datensatz von einigen Millionen Vektoren, aber die ANN-Suche kann mit einer längeren Indexierungszeit oder durch das Hinzufügen von Hardwareressourcen sicherlich darüber hinaus skaliert werden.

Unterstützt durch Apache Lucene

Viele der Kern-Suchfunktionen von Elasticsearch werden von der Lucene-Bibliothek bereitgestellt, einem Open-Source-Projekt, das von der Apache Software Foundation verwaltet wird. Elasticsearch ANN bildet hier keine Ausnahme und basiert auf einem spannenden neuen Lucene-Feature zum Speichern und Suchen von numerischen Vektoren. Dieses Feature ist das Ergebnis einer großartigen Zusammenarbeit, an der mehrere Entwickler aus verschiedenen Organisationen beteiligt waren. Was als mutiger Vorschlag begann, entwickelte sich schnell zu einer funktionierenden (und schnellen) Implementierung. Dann kam die Herausforderung, die API zu entwerfen und das Feature abzurunden.

Seitdem arbeitet die Lucene-Community weiterhin zusammen, um das Feature voranzubringen. Mehrere Entwickler zeigten Interesse und leisteten Beiträge, von der Neugestaltung von Namen über Algorithmus-Updates und Performance - Verbesserungen bis hin zu vielem mehr. Die Vektorsuchfunktionen von Lucene erweitern sich dank der Bemühungen aller Beteiligten schnell.

Neben der fruchtbaren Zusammenarbeit bringt die Entwicklung von ANN in Lucene weitere wesentliche Vorteile mit sich. Die Implementierung von Lucene ist auf Low-Level-Ebene so konzipiert, dass sie sich korrekt in bestehende Funktionen integrieren lässt, wodurch die ANN-Suche nahtlos mit anderen Elasticsearch-Features interagieren kann. Eine solch tiefe Integration wäre nicht wirklich möglich, wenn wir von einer externen ANN-Bibliothek abhängig wären. Zum Beispiel handhabt Lucene ANN gelöschte Dokumente transparent, indem es während des Graph-Suchens „Tombstones“ überspringt. Sie respektiert zudem alle Datenkompatibilitätsgarantien von Lucene, sodass Sie sicher sein können, dass Vektordaten auch nach einem Upgrade weiterhin funktionieren. Schließlich ist die Implementierung genau wie Elasticsearch in Java geschrieben, was es uns ermöglicht, deren Sicherheit zu gewährleisten und die Speicherverwaltung zu vereinfachen.

Was kommt als Nächstes?

In 8.0 wird der _knn_search-Endpoint für eine effiziente ANN-Suche als „Technical Preview“ veröffentlicht. Die ANN-Suche ist ein relativ neues Thema, nicht nur für Elastic, sondern für die gesamte Branche, und es gibt noch bedeutende offene Fragen dazu, wie sie sich verhalten sollte. Was ist der beste Weg, um Vektorähnlichkeitsbewertungen mit herkömmlichen BM25-Scores zu kombinieren? Sollte die kNN-Suchen Paginierung unterstützen? Die Entwicklung von ANN als eigenen experimentellen Endpoint ermöglicht es uns, schnell zu iterieren und dessen Verhalten zu testen. Wir planen, ANN letztendlich in die _search-API zu integrieren, sobald wir fundierte Antworten auf diese Fragen haben. (Obwohl _knn_search noch nicht allgemein verfügbar [GA] ist, wurde der Feldtyp „dense_vector“ in Version 7.6 allgemein verfügbar gemacht und verfügt weiterhin über eine stabile API.)

Zu den wichtigsten Funktionen, die wir unterstützen wollen, gehören ANN mit Filtern sowie die „hybride“ Suche, bei der ANN-Ergebnisse mit denen einer herkömmlichen Abfrage kombiniert werden. Wir arbeiten auch an der Verbesserung der Geschwindigkeit des Indexierens, da das Erstellen von HNSW-Graphen ein aufwändiger Vorgang sein kann. Wir betrachten diese Version nur als einen Anfang und freuen uns darauf, das ANN-Suchen in den kommenden Versionen zu verbessern. Ihr Feedback ist sehr wertvoll und hilft uns, die Ausrichtung des Features zu bestimmen. Wir würden uns freuen, von Ihnen auf GitHub und in unseren Discuss-Foren (und auch in Lucene) zu hören!

Probieren Sie die ANN-Suchen in Elastic Cloud aus, indem Sie sich bei der Elastic Cloud-Konsole logging oder sich für eine kostenlose 14-tägige Testversion.registrieren.