El recorrido de gráfico de memoria externa es un tipo de recorrido de gráfico optimizado para acceder a la memoria almacenada externamente.
Fondo
El recorrido de gráficos es una subrutina en la mayoría de los algoritmos de gráficos. El objetivo de un algoritmo de recorrido de gráfico es visitar (y / o procesar) cada nodo de un gráfico. Gráfico de algoritmos de recorrido, como búsqueda en amplitud y búsqueda en profundidad , se analizan utilizando el von Neumann modelo, que supone costes de acceso a memoria uniforme. Esta vista ignora el hecho de que, para grandes casos, parte del gráfico reside en el disco en lugar de la memoria interna. Dado que acceder al disco es mucho más lento que acceder a la memoria interna, existe la necesidad de un recorrido eficiente de la memoria externa .
Modelo de memoria externa
Para los algoritmos de memoria externa, el modelo de memoria externa de Aggarwal y Vitter [1] se utiliza para el análisis. Una máquina se especifica por tres parámetros: M , B y D . M es el tamaño de la memoria interna, B es el tamaño de bloque de un disco y D es el número de discos paralelos. La medida de rendimiento de un algoritmo de memoria externa es el número de E / S que realiza.
Búsqueda en amplitud de memoria externa
El algoritmo de búsqueda primero en amplitud comienza en un nodo raíz y atraviesa cada nodo con profundidad uno. Si no hay más nodos no visitados en la profundidad actual, se atraviesan los nodos a una profundidad mayor. Finalmente, se visitaron todos los nodos del gráfico.
Munagala y Ranade
Para un gráfico no dirigido , Munagala y Ranade [2] propusieron el siguiente algoritmo de memoria externa:
Dejar denotar los nodos en el nivel de búsqueda primero en amplitud ty dejar ser el conjunto múltiple de vecinos del nivel t-1. Por cada t, se puede construir a partir de transformándolo en un conjunto y excluyendo de él los nodos visitados anteriormente.
- Crear accediendo a la lista de adyacencia de cada vértice en . Este paso requiere E / S.
- próximo se crea a partir de eliminando duplicados. Esto se puede lograr mediante la clasificación de, seguido de una fase de escaneo y compactación que necesita E / S.
- se calcula mediante un escaneo paralelo sobre y y requiere E / S.
El número total de E / S de este algoritmo sigue teniendo en cuenta que y y es .
En la figura de la derecha se muestra una visualización de los tres pasos descritos necesarios para calcular L ( t ).
Mehlhorn y Meyer
Mehlhorn y Meyer [3] propusieron un algoritmo que se basa en el algoritmo de Munagala y Ranade (MR) y mejora su resultado.
Consta de dos fases. En la primera fase, el gráfico se procesa previamente, la segunda fase realiza una búsqueda en amplitud utilizando la información recopilada en la fase uno.
Durante la fase de preprocesamiento, el gráfico se divide en subgrafos inconexos con pequeño diámetro. Además, divide las listas de adyacencia en consecuencia, mediante la construcción de un archivo externo, dónde contiene la lista de adyacencia para todos los nodos en .
La fase de búsqueda en amplitud es similar al algoritmo MR. Además, el algoritmo mantiene un archivo externo ordenado. Este archivo se inicializa con. Además, los nodos de cualquier nivel de búsqueda creado primero en amplitud llevan identificadores para los archivos de sus respectivos subgrafos . En lugar de utilizar accesos aleatorios para construir el archivo se utiliza.
- Realizar un escaneo paralelo de la lista ordenada y . Extraiga las listas de adyacencia para los nodos, que se puede encontrar en .
- Las listas de adyacencia para los nodos restantes que no se pudieron encontrar en necesita ser recogido. Un escaneo sobreproduce los identificadores de partición. Después de ordenar y eliminar los duplicados, los archivos respectivos se puede concatenar en un archivo temporal .
- Las listas de adyacencia que faltan se pueden extraer de con un escaneo. A continuación, las listas de adyacencia restantes se fusionan en con una sola pasada.
- se crea mediante un simple escaneo. La información de la partición se adjunta a cada nodo en.
- El algoritmo procede como el algoritmo MR.
Es posible que los bordes se escaneen con más frecuencia en , pero se reducen las E / S no estructuradas para obtener listas de adyacencia.
El número total de E / S para este algoritmo es
Búsqueda en profundidad de memoria externa
El algoritmo de búsqueda en profundidad explora un gráfico a lo largo de cada rama lo más profundo posible, antes de retroceder.
Para gráficos dirigidos , Buchsbaum, Goldwasser, Venkatasubramanian y Westbrook [4] propusieron un algoritmo con E / S.
Este algoritmo se basa en una estructura de datos denominada árbol de repositorio en búfer (BRT). Almacena un conjunto múltiple de elementos de un universo ordenado. Los artículos se identifican por clave. Un BTR ofrece dos operaciones:
- inserción (t, x) , que añade elemento x de T y las necesidadesE / S amortizadas. N es el número de elementos agregados al BTR.
- extraer (T, k) , que informa y elimina de T todos los elementos con la tecla k . RequiereE / S, donde S es el tamaño del conjunto devuelto por extracción .
El algoritmo simula un algoritmo interno de búsqueda en profundidad. Se mantiene una pila S de nodos. Durante una iteración para el nodo v en la parte superior de S, empuje un vecino no visitado hacia S e itere. Si no hay vecinos no visitados, pop v .
La dificultad es determinar si un nodo no está visitado sin hacer E / S por borde. Para hacer esto para un nodo v, los bordes entrantes (x, v) se colocan en un BRT D , cuando v se descubre por primera vez. Además, los bordes salientes ( v , x ) se colocan en una cola de prioridad P ( v ), codificada por el rango en la lista de adyacencia.
Para vértice u en la parte superior de S todos los bordes ( u , x ) se extraen de D . Tales aristas solo existen si se ha descubierto x desde la última vez que u estuvo encima de S (o desde el inicio del algoritmo si u es la primera vez que está encima de S ). Para cada borde ( u , x ) se realiza una operación de eliminación ( x ) en P ( u ). Finalmente, una operación delete-min en P (u) produce el siguiente nodo no visitado. Si P ( u ) está vacío, u se extrae a partir de S .
El pseudocódigo para este algoritmo se proporciona a continuación.
1 procedimiento BGVW-profundidad-primera-búsqueda ( G , v ):2 sea S una pila, P [] una cola de prioridad para cada nodo y D un BRT3 S. Empujar ( v )4 mientras S no está vacío5 v = S. Arriba ()6 si v no está marcado:7 puntos ( v )8 extrae todos los bordes (v, x) de D ,x : P [ v ]. eliminar ( x )9 si u = P [ v ] .delete-min () no es nulo10 S. Empujar ( u )11 más 12 S .pop ()13 marca de procedimiento ( v )14 poner todos los bordes ( x , v ) en D 15 ( v , x ): ponga x en P [ v ]
Referencias
- ^ Aggarwal, Alok; Vitter, Jeffrey (1988). "La complejidad de entrada / salida de la clasificación y problemas relacionados" . Comunicaciones de la ACM . 31 (9): 1116–1127. doi : 10.1145 / 48529.48535 .
- ^ Munagala, Kameshwar; Ranade, Abhiram (1999). "E / S-complejidad de algoritmos gráficos". Actas del Décimo Simposio Anual ACM-SIAM sobre Algoritmos Discretos . SODA '99. Baltimore, Maryland, EE.UU .: Sociedad de Matemáticas Industriales y Aplicadas. págs. 687–694.
- ^ Mehlhorn, Kurt; Meyer, Ulrich (2002). "Búsqueda primero en amplitud de memoria externa con E / S sublineal". Algoritmos - ESA 2002 . ESA 2002. Roma, Italia: Springer Berlin Heidelberg. págs. 723–735.
- ^ Buchsbaum, Adam L .; Goldwasser, Michael; Venkatasubramanian, Michael; Westbrook, Suresh (2000). "Sobre el recorrido del gráfico de memoria externa". Actas del XI Simposio Anual ACM-SIAM sobre Algoritmos Discretos . SODA '00. San Francisco, California, EE.UU .: Sociedad de Matemáticas Industriales y Aplicadas. págs. 859–860.