Direkt zum Inhalt
Login erforderlich
Dieser Artikel ist Abonnenten von Spektrum der Wissenschaft 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.
Wer ist der nächste Nachbar?Laden...

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

März 2019

Dieser Artikel ist enthalten in Spektrum der Wissenschaft März 2019

Kennen Sie schon …

50/2018

Spektrum - Die Woche – 50/2018

In dieser Ausgabe widmen wir uns dem Prokrastinieren, dem All und Quantencomputern.

Des Rätsels Lösung - Mathematische Beweise und ihre Entdecker

Spektrum Kompakt – Des Rätsels Lösung - Mathematische Beweise und ihre Entdecker

Korrekt oder nicht? Mathematische Beweise beruhen auf Annahmen und Schlussfolgerungen. Das klingt im Prinzip einfach, es dauert aber nicht selten Jahrzehnte oder länger, bis sie gefunden werden - wenn es überhaupt gelingt. Die Geschichten und die Menschen dahinter bieten oft spannende Geschichten.

Künstliche Intelligenz - von Maschinen und Menschen

Spektrum Kompakt – Künstliche Intelligenz - von Maschinen und Menschen

Werden Maschinen irgendwann das Ruder übernehmen? Die Fortschritte in der künstlichen Intelligenz sind beeindruckend - und für manche auch Besorgnis erregend. Wo steht die Forschung, wo liegen Chancen und Risiken?

Lesermeinung

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, Leserzuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Leserzuschriften 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 Teilnehmer sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Lesermeinungen können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!

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