Komprimierte Grafikdarstellung?

Question

Ich arbeite an einem Nebenprojekt, bei dem nun alle Links zwischen Wikipedia-Seiten codiert werden. Ich habe diese Informationen auf die Festplatte geschrieben, aber die Speicherbelegung, die für die Kodierung der Struktur dieses Graphen benötigt wird, ist ziemlich lächerlich - es gibt Millionen von Knoten und Dutzende von Millionen von Links. Während diese Struktur in die Erinnerung passt, bin ich mir nicht sicher, was ich tun würde, wenn es, sagen wir, eine Milliarde Links oder eine Milliarde Seiten gäbe.

Meine Frage ist - gibt es eine Möglichkeit, eine Grafik zu verlustfrei zu groß zu komprimieren, um in den Speicher zu passen, so dass es in den Speicher passt? Wenn nicht, gibt es einen guten verlustbehafteten Algorithmus, der für einige Definition von "Struktur" nicht zu viel Struktur von der ursprünglichen Grafik verliert?

Answer 1

Graphen wie Links Graphen und soziale Graphen sind sehr gut untersucht und sie haben normalerweise statistische Eigenschaften, die effiziente komprimierte Darstellungen ermöglichen.

Eine dieser Eigenschaften ist zum Beispiel, dass für ausgehende Kanten die differenzielle Kodierung der Adjazenzliste eine geringe Leistungsverteilung hat, dh es gibt viele sehr kleine Werte und sehr wenige große Werte, so dass die meisten universal codes funktionieren Gut. Insbesondere die Klasse zeta codes ist in dieser Einstellung nachweislich optimal, und in der Arbeit haben die Autoren den Link-Graphen eines kleinen Web-Crawls mit ungefähr 3 Bits pro Link komprimiert.

Ihr Code (für Java, Python und C++) ist available in their webpage als ein Graph-Komprimierungs-Framework, so dass Sie in der Lage sein sollten, damit zu experimentieren, ohne viel zu programmieren.

Dieser Algorithmus ist eine Art von alt (2005) und es gab Entwicklungen auf dem Gebiet, aber ich habe keine Hinweise auf die Papiere im Moment, die Verbesserungen sind sowieso nicht signifikant und ich glaube nicht, dass es irgendwelche gibt verfügbarer und getesteter Code, der sie implementiert.

Answer 2

Wie wäre es mit dem Schreiben Ihrer Knoten, Links und Verknüpfungen zu einem vorhandenen skalierbaren Datenbanksystem (MySQL, SQL Server, Oracle usw.)? Sie können bei Bedarf Indizes und gespeicherte Prozeduren für eine schnellere DB-Level-Verarbeitung erstellen.

Wenn Sie diese Route aus irgendeinem Grund nicht gehen können, müssen Sie Daten ein- und auslagern (genau wie bei DB-Systemen!). Die Komprimierung der Daten ist in vielen Fällen eine kurzfristige Hilfe. Wenn Sie das RAM-Dach aus irgendeinem Grund nicht erhöhen können, kaufen Sie nur sich selbst begrenzte Zeit, also würde ich empfehlen, es zu komprimieren.

Answer 3

Ganz allgemein gesprochen, wenn Sie N Knoten und einen Durchschnitt von X ausgehenden Verbindungen pro Knoten, X viel kleiner als N haben, werden Sie XN ln N Bits der Informationen benötigen, um dies darzustellen, es sei denn, Sie können Muster finden in der Link-Struktur (die Sie dann ausnutzen können, um die Entropie zu reduzieren). XN ln N liegt in einer Größenordnung von der Komplexität Ihrer 32-Bit-Adjazenzliste.

Es gibt einige Tricks, die Sie die Größe tun könnte etwas mehr zu bringen:

• Verwenden Huffman-Codes Link-Ziele zu kodieren. Weisen Sie häufig verwendeten Seiten kürzere Codes zu und weisen Sie selteneren Seiten längere Codes zu.
• Suchen Sie nach einer Möglichkeit, die Seitengruppe in Klassen aufzuteilen. Speichern Sie jeden Link zwischen Seiten innerhalb derselben Klasse wie "0" + "# innerhalb der Klasse"; Links zwischen Seiten in verschiedenen Kategorien als "1" + "Zielklasse" + "# innerhalb der Klasse".

Links von Giuseppe sind Überprüfung wert, aber nur das Experiment wird Ihnen sagen, wie gut diese Algorithmen auf Wikipedia anwendbar sind.

Answer 4

Wenn Sie nicht benötigen, müssen Sie sich ansehen, wie BGL eine Grafik in einer compressed sparse row format darstellt. Laut den Dokumenten "minimiert es die Speicherverwendung zu O (n + m), wobei n und m die Anzahl der Scheitelpunkte bzw. Kanten sind". Boost Graph Library hat sogar an example, die Ihren Anwendungsfall widerspiegelt.

Bevor Sie zu weit gehen, sollten Sie wirklich herausfinden, wie Sie Ihre Grafik abfragen wollen. Brauchen Sie Links, die auf die Seite verweisen, sowie Links von einer Seite? Müssen Sie die Anzahl der Links auf einer bestimmten Seite effizient finden? Für eine ziemlich gut durchdachte Liste von grundlegenden Graphenoperationen, werfen Sie einen Blick auf Boost Graph Library's (BGL) concepts. Sie können dies dann den Anforderungen für verschiedene Algorithmen zuordnen. Beispielsweise benötigt Dijkstra's shortest path ein Diagramm, das "Vertex List Graph" und "Incidence Graph" modelliert.

Answer 5

Ich war Teil von a paper vor einer Weile über das Komprimieren von Webgrafiken, so dass sie in den Speicher passen würden. Wir haben es auf ungefähr 6 Bits pro Verbindung heruntergekommen.

Answer 6

In Ihrem Fall versuchen Sie, ein einzelnes Diagramm in einen Speicher statt einer allgemeinen, großen Familie von Graphen zu komprimieren. Wenn Sie nur einzelne Graphen komprimieren müssen, können Sie jede beliebige algorithmische Darstellung dafür finden. Dies wird zu einem Problem von Kolmogorov complexity. Im Allgemeinen können Sie zufällige Graphen nicht effizient komprimieren, da sie zufällig sind und daher nicht vorhergesagt werden können und wenn sie nicht vorhergesagt werden können, können sie nicht komprimiert werden. Dies ergibt sich aus der grundlegenden Informationstheorie; Es ist die gleiche Sache, dass Sie Bilder mit zufälligem Geräusch nicht komprimieren können.

Angenommen, Sie haben 2 (Milliarden) Seiten und jeder hat genau 2 ausgehende Links und dass die Verbindungen wirklich zufällig verteilt sind. Die Links auf jeder Seite repräsentieren fast 16 * 30 Bits an Information (nicht vollständig, weil die 16 Links alle verschieden sind und dies fügt eine winzige Menge an Redundanz hinzu). So haben Sie 2 * 16 * 30 = 2 * 120 = 15 GB Informationen dort, und die Informationstheorie sagt, dass Sie eine kleinere GENERAL-Darstellung nicht finden können. Sie müssen die spezielle Struktur des Wikipedia-Graphen verwenden, um unter die informationstheoretische Untergrenze zu gelangen.