Worldwide China

Big Data

Ist Rechenpower alles bei der Big-Data-Analyse?

| Autor / Redakteur: Ulrich Meyer* / Marc Platthaus

Abb.1: Auf das Thema Big Data muss man auch im Labor Antworten finden.
Bildergalerie: 1 Bild
Abb.1: Auf das Thema Big Data muss man auch im Labor Antworten finden. (Bild: © Alex011973_fotolia.com)

Bei der Verarbeitung großer Datenmengen werden typischerweise sehr leistungsfähige Rechner eingesetzt. Aber ohne geeignete Algorithmen stoßen auch diese schnell an ihre Grenzen. Verbesserte Graphalgorithmen sind der Schlüssel, viele praxisrelevante Big-Data-Berechnungsprobleme effizient zu lösen.

Big Data ist inzwischen in aller Munde und eine Vielzahl von Artikeln in diversen Printmedien widmet sich diesem Thema. Dabei werden wahlweise die Vorteile oder die Risiken und Nebenwirkungen von „Big Data Algorithmen“ in den Vordergrund gestellt. Meist geht es darum, verschiedenste Daten miteinander zu verknüpfen, um so bisher unbekannte (statistische) Zusammenhänge zu sehen. Es ist anfangs oft gar nicht klar, auf welche Fragen man eigentlich Antworten sucht. Die dafür benutzten Algorithmen sind dementsprechend sehr allgemein und nicht auf ein konkretes Anwendungsproblem hin programmiert. Etliche Anwendungen sind aber ganz anders gestrickt und obwohl sehr klar ist, wonach man sucht, bedeutet die schiere Größe der Daten eine enorme Herausforderung. Selbst einfache klassische Probleme lassen sich für Big Data ohne bessere Algorithmen nur noch mit sehr hohem Aufwand lösen.

Im neu eingerichteten Schwerpunktprogramm SPP 1736 „Algorithms for Big Data“ (www.big-data-spp.de) der Deutschen Forschungsgemeinschaft (DFG) geht es um solche Fragestellungen der theoretischen Informatik. Gleich mehrere Projekte beschäftigen sich mit so genannten „Graphalgorithmen“.

Wozu werden Graphalgorithmen verwendet?

Ein bekanntes Beispiel: Wer heutzutage eine Adresse in einer fremden Stadt anfahren will, benutzt dazu höchstwahrscheinlich ein Navigationsgerät oder Smartphone mit entsprechender Software. Beide suchen eine gute oder sogar optimale Route mittels Algorithmen zur kombinatorischen Optimierung. Die Straßenkarte wird intern als Graph abgespeichert, das ist eine Datenstruktur aus Knoten und Kanten. Ein Knoten v entspricht einer Abzweigung oder Straßenkreuzung, eine Kante e={v,w} repräsentiert den Straßenabschnitt zwischen den Knoten v und w. Jede Kante besitzt außerdem ein Kantengewicht c(e), welches z.B. die Länge (oder Reisezeit) des zur Kante gehörenden Straßenabschnitts kodiert. Dementsprechend besteht eine Route vom Startknoten s zum Zielknoten t aus einer Abfolge von Kanten{s,v1}, {v1,v2}, …, {vi-1,vi}, {vi,t} und die Gesamtlänge der Route ergibt sich aus der Summe der entsprechenden Kantengewichte.

Wie findet ein Algorithmus in einem Graphen schnell eine kürzeste Route vom Start zum Ziel? Naiv könnte man hoffen, dass heutige Computer leistungsstark genug sind, einfach alle möglichen Pfade durchzuprobieren und den besten auszugeben. Ein Blick auf den Beispielgraph (siehe S. 24) zeigt jedoch, dass die Anzahl möglicher Pfade im Extremfall viel zu schnell aus dem Ruder läuft: Vom Startknoten s = 0 zum Knoten 3 gibt es zwei Möglichkeiten (entweder über Knoten 1 oder über Knoten 2), dann vom Knoten 3 zum Knoten 6 wiederum zwei Möglichkeiten, das heißt insgesamt also schon 2*2 = 4 verschiedene Routen um von s nach 6 zu gelangen. Weiterhin 2*2*2=23 = 8 Varianten für die Reise von s nach 9 und somit 24 = 16 mögliche Pfade von s nach Knoten 12, sowie allgemein 2(i/3) unterschiedliche Routen von s nach Knoten i, falls i durch 3 teilbar ist.

Erweitert man den Beispielgraphen in analoger Form, dann kommen für den Abschnitt von s bis Knoten 99 schon 233 = 8 589 935 592 Möglichkeiten zusammen und bis Knoten 999 eine rund hundertstellige Zahl verschiedener Routen (das ist deutlich mehr als die Anzahl der Atome im gesamten Universum).

Nun sehen Straßengraphen natürlich etwas anders aus als unser kleines Beispiel, aber auch in ihnen gibt es viel zu viele Möglichkeiten um von A nach B zu gelangen, und die Anzahl der Knoten für gebräuchliche Graphen Westeuropas liegen eher in der Größenordnung von 20 Millionen statt nur 1000. Es braucht also deutlich bessere Methoden als das triviale Aufzählen und Austesten aller Alternativen.

Inhalt des Artikels:

Kommentare werden geladen....

Kommentar zu diesem Artikel abgeben

Der Kommentar wird durch einen Redakteur geprüft und in Kürze freigeschaltet.

  1. Avatar
    Avatar
    Bearbeitet von am
    Bearbeitet von am
    1. Avatar
      Avatar
      Bearbeitet von am
      Bearbeitet von am

Kommentare werden geladen....

Kommentar melden

Melden Sie diesen Kommentar, wenn dieser nicht den Richtlinien entspricht.

Kommentar Freigeben

Der untenstehende Text wird an den Kommentator gesendet, falls dieser eine Email-hinterlegt hat.

Freigabe entfernen

Der untenstehende Text wird an den Kommentator gesendet, falls dieser eine Email-hinterlegt hat.

copyright

Dieser Beitrag ist urheberrechtlich geschützt. Sie wollen ihn für Ihre Zwecke verwenden? Infos finden Sie unter www.mycontentfactory.de (ID: 42957628 / Wissenschaft & Forschung)