Wie bewerten wir Datenlöschung in graphbasierten ANN-Indexen?

Die Suche nach dem nächsten Nachbarn in großen Datenmengen – das sogenannte Approximate Nearest Neighbor Search (ANNS) – hat in den letzten Jahren stark an Bedeutung gewonnen. Besonders Anwendungen wie Retrieval-Augmented Generation setzen auf ANNS-Algorithmen, die mit dynamischen Daten umgehen können. Deshalb wächst das Interesse an der Lösung des ANNS-Problems für sich verändernde Datensätze.

Ein entscheidendes Thema bleibt jedoch die effiziente Löschung von Daten aus graphbasierten ANN-Indexen. Bisher fehlt eine einheitliche Evaluationsmethode, um zu beurteilen, wie gut verschiedene Löschstrategien funktionieren. Das neue Papier aus dem arXiv-Repository adressiert dieses Problem und stellt einen umfassenden experimentellen Rahmen vor.

Die Autoren klassifizieren die Löschmethoden in graphbasierten ANN-Indexen in drei Hauptansätze und formulieren diese mathematisch. Anschließend werden die Methoden anhand von Kennzahlen wie Genauigkeit, Abfragegeschwindigkeit und weiteren relevanten Metriken bewertet. Der Fokus liegt dabei auf realistischen Anwendungsfällen, sodass die Ergebnisse unmittelbar in der Praxis anwendbar sind.

Um die Wirksamkeit des Ansatzes zu demonstrieren, wenden die Forscher ihr Framework auf den hochmodernen Index HNSW (Hierarchical Navigable Small World) an. Die Analyse zeigt, wie sich unterschiedliche Löschstrategien auf die Leistung auswirken. Darauf aufbauend schlagen sie „Deletion Control“ vor – eine Methode, die dynamisch die passende Löschstrategie auswählt, um die geforderte Suchgenauigkeit zu gewährleisten.