Direkt zum Inhalt
Login erforderlich
Dieser Artikel ist Abonnenten mit Zugriffsrechten für diese Ausgabe frei zugänglich.

Computerwissenschaft: Wer ist der nächste Nachbar?

Diese Frage taucht in der Informatik häufig auf – und zwar immer dann, wenn man neue Daten mit einem bestehenden Datensatz vergleicht. Eigentlich wollten fünf Computer­wissenschaftler beweisen, dass es keine universelle Methode gibt, die sie schnell beantwortet. Stattdessen fanden sie einen Algorithmus, der es kann.
Kevin Hartnett
Wer ist der nächste Nachbar?
© Ani_Ka / Getty Images / iStock (Ausschnitt)

Bevor man ein Café eröffnet, informiert man sich normalerweise darüber, wo sich der nächste Konkurrent befindet. Dieses Szenario ist ein Beispiel für ein in der Informatik weit verbreitetes Problem: die Suche nach einem »nächsten Nachbarn«. Allgemein möchte man dabei bestimmen, welcher Punkt in einem vorhandenen Datensatz einem neu hinzugefügten Punkt am nächsten liegt. Diese Aufgabe taucht in den verschiedensten Bereichen auf, von der Genforschung über die digitale Bildersuche bis hin zu Filmempfehlungen von Netflix.

Allerdings gestaltet sich die Suche nach einem nächsten Nachbarn häufig schwierig. In den letzten Jahrzehnten haben führende Computerwissenschaftler versucht, eine allgemeine Lösung zu diesem Problem zu finden. Doch sie scheiterten ...

Download (Abo)

Kennen Sie schon …

Spektrum Kompakt – KI-Sprachmodelle

Mit ChatGPT, Claude oder Gemini lässt es sich gut reden: Sie wirken menschlich und scheinen uns zu verstehen. Manche Menschen bauen sogar eine romantische Beziehung zum Chatbot auf. Doch die ständige Bestätigung macht uns auch anfällig für Manipulation und kann sogar wahnhaftes Denken verursachen.

Spektrum Dossier – Menschen im Gespräch – Wie wir kommunizieren

Kommunikation kann verbinden – oder entzweien. Denn sie ist so viel mehr als die reine Wortbedeutung. Erfahren Sie, was im Gehirn passiert, wenn wir »auf einer Wellenlänge« sind, warum Gespräche scheitern und was erfolgreiche Konfliktlösung und eine gute Unterhaltung ausmacht und mehr.

Spektrum - Die Woche – Selbsthilfe aus dem Schädelknochen

Immuntherapien haben Fortschritte bei der Behandlung verschiedener Krebsarten erzielt, Hirntumoren blieben jedoch weitgehend resistent. Neue Forschungsergebnisse zeigen, dass unser Gehirn über Immunzellen zu verfügen scheint, die sich im Knochenmark der Schädeldecke ansammeln und Tumoren bekämpfen.

  • Quellen

Andoni, A. et al.:Data-Dependent hashing via Nonlinear Spectral Gaps. In: Symposium on Theory of Computing, S. 787–800, 2018

Andoni, A. et al.:Hölder Homeomorphisms and Approximate Nearest Neighbours. In: Symposium on Foundations of Computer Science, S. 159–169, 2018

Translation from »Quanta Magazine«: »Universal Method to Sort Complex Information Found«.

Schreiben Sie uns!

Beitrag schreiben

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Zuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Zuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmende sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Zuschriften können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!

Artikel zum Thema

Themenkanäle

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.