Metraipolis › archive › dc_8a515a48aaf0

External Memory Minimaler Spannbaum — Wikipedia (de)

Source
Wikipedia (de)
Original
https://de.wikipedia.org/wiki/External_Memory_Minimaler_Spannbaum
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-06T17:59:19.050Z
SHA-256 of the archived text
e2624bc8618170f3e4a97ef70e50b4cb0a4ffb4e58eec0ae68d8ae1743c3acd1
Stable URL of this page
https://metraipolis.com/documento/dc_8a515a48aaf0

How to cite

External Memory Minimaler Spannbaum — Wikipedia (de) — Wikipedia (de), https://de.wikipedia.org/wiki/External_Memory_Minimaler_Spannbaum (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_8a515a48aaf0 (Metraipolis archive dc_8a515a48aaf0, sha256 e2624bc8618170f3e4a97ef70e50b4cb0a4ffb4e58eec0ae68d8ae1743c3acd1)
BibTeX
@misc{dc8a515a48aaf0,
  title = {External Memory Minimaler Spannbaum — Wikipedia (de)},
  howpublished = {Wikipedia (de)},
  url = {https://de.wikipedia.org/wiki/External_Memory_Minimaler_Spannbaum},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_8a515a48aaf0; sha256 e2624bc8618170f3e4a97ef70e50b4cb0a4ffb4e58eec0ae68d8ae1743c3acd1},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (de), https://de.wikipedia.org/wiki/External_Memory_Minimaler_Spannbaum. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Ein externer minimaler Spannbaum bezeichnet in der Informatik einen minimalen Spannbaum, der für einen in den Sekundärspeicher ausgelagerten Graphen G=(V,E) berechnet wurde. Letzteres ist für Graphen nötig, deren Anzahl Knoten und Kanten zu groß ist, als das sie gleichzeitig vollständig in den Hauptspeicher passen. Als Anwendungsbeispiel kann man einen Crawl des sozialen Netzwerkes Twitter aus dem Jahre 2010 heranziehen. Wenn man das Kantengewicht vernachlässigt und eine Kante als Paar von Knotenindizes speichert, so ergibt sich für den Graphen eine Größe von (2⋅⌈log2(41652230)⌉)⋅14683651828Bytes≈9,55⋅109Bytes, was 9,55 Gigabytes entspricht. Wenn man davon ausgeht, dass ein Desktop-PC für gewöhnlich über 8 GB Hauptspeicher verfügt, so würden diese nicht ausreichen, um auf dem Graphen einen minimalen Spannbaum vollständig intern zu berechnen. Für externe Algorithmen verwendet man als Berechnungsmodell das External Memory Modell. Es besteht aus Hauptspeicher der Größe M und Sekundärspeicher und man kann Datenblöcke der Größe B zwischen ersterem und letzterem übertragen. Das Lesen (Schreiben) eines Blocks vom (in den) Sekundärspeicher in den (vom) Hauptspeicher, bezeichnet man als I/O (= Input/Output). Letzteres ist die Kerngröße in diesem Modell, die es zu minimieren gilt. Im Gegensatz zu Modellen wie der Random Access Machine steht hier nicht die asymptotische Laufzeit im Vordergrund, sondern die Anzahl I/Os. Aufgrund der deutlich erhöhten Zugriffszeit des Sekundärspeichers, relativ zu der des Hauptspeichers, werden die I/Os oft zum Flaschenhals des Systems.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in tedesco, in ordine alfabetico).
Fonte: Wikipedia in tedesco, voce «External Memory Minimaler Spannbaum» — https://de.wikipedia.org/wiki/External_Memory_Minimaler_Spannbaum
Wikidata Q97381210: «type of minimal spanning tree in computer science» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q97381210
Autori: i contributori di Wikipedia (cronologia: https://de.wikipedia.org/wiki/External_Memory_Minimaler_Spannbaum?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 264050893, consultata il 2026-11-06T17:55:36.354Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 79b46839ad03473ec52a41f15ff33f151bba794c6089ae2ba36a2553a917b7db