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 - Die Woche – Wie Computer das Lernen lernen

Die Nobelpreise in Medizin oder Physiologie, Physik und Chemie sind vergeben! Erfahren Sie, wie bahnbrechende Forschungen zu microRNA, neuronalen Netzen und Proteinen die Welt verändern.

Spektrum der Wissenschaft – Formen der Mathematik

Die Mathematik ist ein erstaunlich vielfältiges Fach und zeigt sich in den verschiedensten Formen: Lesen Sie von den bunten Fraktalen der Mandelbrotmenge, einer Einstein-Kachel, die den Boden mit erstaunlichen, lückenlosen Mustern versieht oder den Falten eines zerknitterten Papiers. Diese unterschiedlichen Strukturen bergen spannende mathematische Eigenschaften, die Fachleute in den letzten Jahren entdeckt und zum Staunen gebracht haben. Darüber hinaus stellen wir die Frage, warum Kieselsteine oval sind und zeigen Ihnen, nach welchen Regeln die faszinierenden Sandzeichnungen auf dem südpazifischen Archipel Vanuatu entstehen.

Spektrum Kompakt – Pi ist überall - Die fabelhafte Welt der Mathematik

Häufiger als man denkt, schleicht sie sich in unseren Alltag ein: Die Kreiszahl Pi spielt nicht nur eine Rolle bei runden Flächeninhalten, sondern auch bei Lebenssimulationen, Streichhölzern oder Billardspielen - und obwohl sie seit jeher fasziniert, wirft ihr Vorkommen noch immer Fragen auf.

  • 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.