Anwenden von Algorithmen auf große Datenmengen

8

Gibt es ein Buch oder Tutorial, in dem wir lernen, wie wir die gängigen Algorithmen (Sortieren, Suchen usw.) auf große Datenmengen (dh Daten, die nicht vollständig in den Hauptspeicher geladen werden können) effizient anwenden und diese Algorithmen unter Berücksichtigung der Kosten von effizient anwenden können? Blockübertragung vom externen Speicher? Zum Beispiel sagen fast alle Algorithmus-Lehrbücher, dass B- und B + -Bäume zum Speichern von Daten auf der Festplatte verwendet werden können. Es wird jedoch nicht erläutert, wie dies tatsächlich getan werden kann, insbesondere wenn die Zeiger behandelt werden, bei denen die Daten auf der Festplatte vorhanden sind. Obwohl viele Bücher Suchtechniken lehren, berücksichtigen sie in ähnlicher Weise keine Daten, die im Sekundärspeicher vorhanden sind.

Ich habe Knuths Buch überprüft. Obwohl diese Ideen diskutiert werden, habe ich immer noch nicht verstanden, wie man sie tatsächlich in einer Hochsprache anwendet. Gibt es eine Referenz, die diese Details bespricht?

algorithms efficiency memory-management big-data Arani
quelle
1
Schauen Sie sich "Mining Massive Data Sets" an .
Dave Clarke
Sie können einen Blick auf die umfassende Bibliographie des STXXL werfen: die Standardvorlagenbibliothek für XXL-Datensätze .
Vor dem
In diesen Tagen mit großartigen DBs wie Oracle, DB2, SQL Server arbeitet normalerweise niemand mehr mit großen Datenmengen. Wenn Sie interessiert sind, können Sie sich verwandte Dokumente zu einem DB-Server ansehen, aber heutzutage versuchen Martin Fowler und einige andere Leute dies Wechseln Sie zu NO SQL . Sie können dies auch überprüfen. (Aber es gibt zu viele Aspekte in großen Datenbanken, wie Parallelität, Sicherheit, ... nicht nur schnelle Algorithmen).
@ Dave, Vor: Vielen Dank für Ihre Referenzen. Ich werde sie überprüfen und Sie informieren, ob sie das sind, wonach ich suche.
Arani
@SaeedAmiri: Ich verstehe das, aber soweit ich weiß, ist das Speichern von Daten in Datenbanken nur dann nützlich, wenn die Daten in irgendeiner Weise stark strukturiert sind. Daher werden Zahlenfolgen und ähnliche Daten im Allgemeinen nicht mithilfe von Datenbanken gespeichert. Darüber hinaus beschreiben Datenbanklehrbücher aus Sicht des Datenbankentwicklers nicht sehr detailliert. Während die meisten von ihnen erwähnen, dass Datenbanken B- und B + -Bäume verwenden, beschreiben die meisten nicht, wie sie diese Datenstrukturen tatsächlich implementieren.
Arani

Antworten:

2

Datenbankbücher sind ein gutes Beispiel. Schauen Sie sich jedoch die feld-E / A-effizienten Datenstrukturen (und Algorithmen) an. Meines Wissens gibt es einige Kurse zu diesem Thema, aber nur sehr wenige Bücher.

Überprüfen Sie dieses Buch: U. Meyer, P. Sanders und J. Sibeyn (Hrsg.), Algorithmen für Speicherhierarchien, Lecture Notes in Computer Science 2625, Springer, 2003.

Überprüfen Sie diese Kurse: http://www.win.tue.nl/~hermanh/teaching/2IL35/ http://www.daimi.au.dk/~large/ioS12/

und diese Folien: algo2.iti.kit.edu/sanders/courses/algen09-10/rdslides.pdf

AJed
quelle
1

Das Datenbankbuch von Ramkrishnan und Gehrke behandelt diese Dinge ausführlich.

Arani
quelle
Das Schlimmste und Langweiligste überhaupt :)! obwohl es eine gute Einführung in viele interessante Themen in Datenbanken und Datenbankoptimierung ist.
AJed
0

Heutzutage ist dieses Feld als Big Data bekannt und entwickelt sich sehr schnell und schnell, basierend auf der starken Verbindung mit Virtualisierung, und relationale Datenbanktechnologie wird nur als Teilmenge angesehen. Wie in den Kommentaren erwähnt, bewegen sich in Schlüssel- / Wertedatenbanken und NoSQL viele neue Innovationen und Impulse. Aus Ihren Kommentaren geht jedoch hervor, dass Sie mehr an den Prinzipien und Techniken des relationalen Datenbankdesigns interessiert sind . Versuchen Sie die folgenden Refs:

vzn
quelle
Ich habe nicht wirklich relationale Datenbanksysteme studiert, und das könnte eine plausible Antwort sein. Aber ich suche eigentlich nicht nach Datenbanklehrbüchern, die das Datenbankdesign beschreiben. Stattdessen wäre ein Buch sehr hilfreich, das es aus Sicht des Datenbankentwicklers beschreibt (das uns explizit erklärt, wie Datenstrukturen für die Arbeit an Datenträgern implementiert werden).
Arani
Ich hasse es, das zuzugeben, aber ich habe diese Schiedsrichter ein bisschen verpfuscht. es gibt Bücher auf Datenbank - Algorithmen , aber es gibt viele Bücher über Datenbank - Design , die wirklich sind , wie Tabellen zu organisieren, Datenmodellierung, Normalisierung, Indizes etc, Konzepte wie diese. Während diese tangential mit Ihrer Frage zusammenhängen, sind sie nicht wirklich genau miteinander verbunden. Grundsätzlich sind viele der Strategien zur Verwaltung von B-Bäumen in modernen Datenbanken eher an Geschäftsgeheimnisse gebunden. Im Allgemeinen werden die B-Bäume in "Seiten" gespeichert, die dynamisch zugeordnet und indiziert werden. Vielleicht suchen Sie irgendwann nach besseren Refs.
vzn
Ratet mal, was ihr wirklich wollt, ist das Design des physischen Datenbankspeichers (das in einigen dieser Referenzen möglicherweise lose behandelt wird oder nicht). Beispiel: Hier ist ein Whitepaper für eine Fallstudie mit verwandten Inhalten, z. B. "Interna of Physical Server Storage für SQL Server". , MS SQL Server
vzn
Siehe auch die eng verwandte Optimierung des Abfrageplans
vzn
1
Siehe auch B + -Baumindizes mit einigen Verweisen auf Speicherseiten und Apache-Derby , eine B-Baum-Abruf- / Speicherimplementierung in Java mit Implementierungsdetails
vzn