Procházení grafu externí paměti - External memory graph traversal

Procházení grafu externí paměti je typ přechod grafu optimalizováno pro přístup k externě uložené paměti.

Pozadí

Traversal graph is a subrutine in most graph algorithms. Cílem algoritmu pro procházení grafu je navštívit (a / nebo zpracovat) každý uzel grafu. Algoritmy pro procházení grafů vyhledávání na šířku a hloubkové vyhledávání, jsou analyzovány pomocí von Neumann model, který předpokládá jednotné náklady na přístup do paměti. Toto zobrazení zanedbává skutečnost, že pro velké instance je část grafu umístěna na disku, nikoli ve vnitřní paměti. Vzhledem k tomu, že přístup k disku je o poznání pomalejší než přístup k vnitřní paměti, je potřeba efektivního procházení externí paměť existuje.

Model externí paměti

Pro algoritmy externí paměti model externí paměti od Aggarwala a Vittera^[1] se používá pro analýzu. Stroj je určen třemi parametry: M, B a D.M je velikost vnitřní paměti, B je velikost bloku disku a D je počet paralelních disků. Míra výkonu pro algoritmus externí paměti je počet I / O, které provádí.

Prohledávání do šířky první paměti externí paměti

Šířka prvního vyhledávacího algoritmu začíná v kořenovém uzlu a prochází každý uzel s hloubkou jedna. Pokud v aktuální hloubce již nejsou žádné nenavštívené uzly, procházejí se uzly ve vyšší hloubce. Nakonec byl každý uzel grafu navštíven.

Munagala a Ranade

Vizualizace pro výpočet L (t) v Munagala-Ranade-vyhledávání na šířku algoritmus.

Pro neorientovaný graf ${ displaystyle G}$, Munagala a Ranade^[2] navrhl následující algoritmus externí paměti:

Nechat ${ displaystyle L (t)}$ označte uzly v první vyhledávací úrovni t a nechte ${ displaystyle A (t): = N (L (t-1))}$ být množinou sousedů úrovně t-1. Za každé t ${ displaystyle L (t)}$ lze postavit z ${ displaystyle A (t)}$ transformací do sady a vyloučením dříve navštívených uzlů z ní.

1. Vytvořit ${ displaystyle A (t)}$ přístupem k seznamu sousedství každého vrcholu v ${ displaystyle L (t-1)}$. Tento krok vyžaduje ${ displaystyle O (| L (t-1) | + | A (t) | / (D cdot B))}$ I / O.
2. další ${ displaystyle A '(t)}$ je vytvořen z ${ displaystyle A (t)}$ odstraněním duplikátů. Toho lze dosáhnout tříděním ${ displaystyle A (t)}$, následuje fáze skenování a zhutňování ${ displaystyle O ( operatorname {druh} (| A |))}$ I / O.
3. ${ displaystyle L (t): = A '(t) zpětné lomítko {L (t-1) pohár L (t-2) }}$ se vypočítá paralelním skenováním ${ displaystyle L (t-1)}$ a ${ displaystyle L (t-2)}$ a vyžaduje ${ displaystyle O ((| A (t) | + | L (t-1) | + | L (t-2) |) / (D cdot B))}$ I / O.

Celkový počet I / O tohoto algoritmu následuje s ohledem na to ${ displaystyle sum _ {t} | A (t) | = O (m)}$ a ${ displaystyle sum _ {t} | L (t) | = O (n)}$ a je ${ displaystyle O (n + operatorname {sort} (n + m))}$.

Vizualizace tří popsaných kroků nezbytných k výpočtu L(t) je znázorněn na obrázku vpravo.

Mehlhorn a Meyer

Mehlhorn a Meyer^[3] navrhl algoritmus, který je založen na algoritmu Munagala a Ranade (MR) a zlepšuje jejich výsledek.

Skládá se ze dvou fází. V první fázi je graf předzpracován, druhá fáze provádí vyhledávání na šířku pomocí informací shromážděných v první fázi.

Během fáze předzpracování je graf rozdělen do nesouvislých podgrafů ${ displaystyle S_ {i}, , 0 leq i leq K}$ s malým průměrem. Podle toho dále rozděluje seznamy sousedství vytvořením externího souboru ${ displaystyle F = F_ {0} F_ {1} tečky F_ {K-1}}$, kde ${ displaystyle F_ {i}}$ obsahuje seznam sousedství pro všechny uzly v ${ displaystyle S_ {i}}$.

Fáze vyhledávání na šířku je podobná algoritmu MR. Algoritmus navíc udržuje seřazený externí soubor ${ displaystyle H}$. Tento soubor je inicializován pomocí ${ displaystyle F_ {0}}$. Dále uzly jakékoli vytvořené úrovně vyhledávání v první šíři nesou identifikátory souborů ${ displaystyle F_ {i}}$ jejich příslušných podgrafů ${ displaystyle S_ {i}}$. Místo použití náhodných přístupů ke konstrukci ${ displaystyle L (t)}$ soubor ${ displaystyle H}$ se používá.

1. Proveďte paralelní skenování seřazeného seznamu ${ displaystyle L (t-1)}$ a ${ displaystyle H}$. Extrahujte seznamy sousedství pro uzly ${ displaystyle v v L (t-1)}$, které lze najít v ${ displaystyle H}$.
2. Seznamy sousedství pro zbývající uzly, které nelze najít v ${ displaystyle H}$ je třeba vyzvednout. Skenování ${ displaystyle L (t-1)}$ získá identifikátory oddílu. Po seřazení a odstranění duplikátů příslušné soubory ${ displaystyle F_ {i}}$ lze zřetězit do dočasného souboru ${ displaystyle F '}$.
3. Chybějící seznamy sousedství lze extrahovat z ${ displaystyle F '}$ se skenováním. Dále jsou sloučeny zbývající seznamy sousedství ${ displaystyle H}$ jediným průchodem.
4. ${ displaystyle A (t)}$ je vytvořen jednoduchým skenováním. Informace o oddílu jsou připojeny ke každému uzlu v ${ displaystyle A (t)}$.
5. Algoritmus probíhá jako algoritmus MR.

Okraje mohou být skenovány častěji v ${ displaystyle H}$, ale nestrukturované I / O za účelem načtení seznamů sousedství jsou sníženy.

Celkový počet I / O pro tento algoritmus je ${ displaystyle O ({ sqrt {n cdot (n + m) / (D cdot B)}} + operatorname {sort} (n + m))}$

Vyhledávání hloubky první paměti externí paměti

Algoritmus vyhledávání do hloubky prozkoumá graf podél každé větve tak hluboko, jak je to možné, před zpětným sledováním.

Pro režie grafy Buchsbaum, Goldwasser, Venkatasubramanian a Westbrook^[4] navrhl algoritmus s ${ displaystyle O ((V + E / B) log _ {2} (V / B) + operatorname {sort} (E))}$ I / O.

Tento algoritmus je založen na datové struktuře s názvem strom úložiště s vyrovnávací pamětí (BRT). Ukládá více položek z objednaného vesmíru. Položky jsou identifikovány podle klíče. BTR nabízí dvě operace:

• vložka (T, x), který přidává položku X na T a potřeby ${ displaystyle O (1 / B log _ {2} (N / B))}$ amortizované I / O. N je počet položek přidaných do BTR.
• extrakt (T, k), který hlásí a odstraňuje z T všechny položky s klíčem k. To vyžaduje ${ displaystyle O ( log _ {2} (N / B) + S / B)}$ I / O, kde S je velikost sady vrácená výpis.

Algoritmus simuluje interní hloubkový první vyhledávací algoritmus. Stoh S uzlů je pozastaveno. Během iterace uzlu proti na vrcholu S tlačit na nenavštíveného souseda S a iterovat. Pokud neexistují žádní nevítaní sousedé, pop proti.

Obtíž je určit, zda je uzel neviditelný, aniž by to udělal ${ displaystyle Omega (1)}$ I / O na hranu. Chcete-li to udělat pro uzel proti příchozí hrany (x, v) jsou vloženy do BRT D, když proti je poprvé objeven. Dále odchozí hrany (proti,X) jsou zařazeny do prioritní fronty P(proti), zadaný hodností v seznamu sousedů.

Pro vrchol u na vrcholu S všechny hrany (u,X) jsou extrahovány z D. Takové hrany existují, pouze pokud X byl objeven od poslední doby u byl na vrcholu S (nebo od začátku algoritmu, pokud u je poprvé na vrcholu S). Pro každou hranu (u,X) smazat (X) operace se provádí na P(u). Nakonec a operace mazání min na P (u) získá další nenavštívený uzel. Li P(u) je prázdný, u je vyskočeno z S.

Pseudokód pro tento algoritmus je uveden níže.

1  postup BGVW-hloubka-první-vyhledávání (G,proti): 2 let S být hromádka, P[] prioritní fronta pro každý uzel a D BRT3 S.tlačit(proti)4      zatímco S není prázdný5 proti = S.top () 6 -li proti není označeno: 7 bodů (proti) 8 extrahujte všechny hrany (v, x) z D, ${ displaystyle  forall}$X: P[proti].vymazat(X)9          -li u=P[proti] .delete-min () není null10 S.tlačit(u)11         jiný12             S.pop () 13 postup označit(proti) 14 položte všechny hrany (X,proti) do D15      ${ displaystyle  forall}$ (proti,X): dát X do P[proti]

Reference