Graphos

Dentro de esta area, podemos identificar dos tipos de sistemas:

- Las bases de datos orientadas a grafos (graph databases): Son sistemas desarrollados para
el almacenamiento y consulta de grafos siguiendo las tecnicas tradicionales de base de
datos, es decir, son muy similares a las bases de datos relacionales.

- Los sistemas de procesamiento para grafos (graph processing frameworks). Son

frameworks enfocados en el procesamiento y analisis de grandes grafos a traves de
múltiples computadores, con el objetivo de disminuir el tiempo de ejecucion de los
algoritmos involucrados
 Estos tipos de sistemas representan dos enfoques distintos para la gestión de grafos, cada uno con
sus propias ventajas y desventajas.

Los sistemas de procesamiento para grafos surgieron debido a la necesidad de procesar grandes y
complejas colecciones de datos, las cuales son difíciles – por no decir imposibles – de almacenar y
procesar en un solo computador.

En consecuencia, estos sistemas se caracterizan por realizar procesamiento por lotes en memoria (in-
memory batch processing) sobre una plataforma computacional de procesamiento paralelo y/o
distribuido.

Cabe mencionar que el uso de un sistema distribuido con mayores recursos computacionales –
basicamente, procesador y memoria– abre la posibilidad de procesar muchos datos; sin embargo,
este sistema puede entregar peor desempeño que un único computador cuando se ejecutan ciertos
tipos de algoritmos.

* Una consulta toca la mayoría de un archivo, mientras que las bases de datos de gráficos solo tocan
datos relevantes, por lo que un escaneo secuencial no es una suposición de optimización.
 Las ventajas y desventajas de las Graph Databases

VENTAJAS

- La velocidad de búsqueda depende únicamente del número de

relaciones concretas, no del conjunto de datos

- Resultados en tiempo real

DESVENTAJAS

- Es difícil de escalar, por estar diseñado para arquitecturas con un

solo servidor

- Sin lenguaje de consulta consistente

 A considerar

Los sistemas de procesamiento para grafos se pueden dividir en dos grupos, dependiendo de su
forma de implementacion.

A) Se encuentran los sistemas genéricos de procesamiento masivo

que han sido adaptados para procesar grafos, la mayoría de ellos
basados en el modelo de programación MapReduce. Dentro de este
grupo encontramos a Hadoop, YARN, y Stratosphere. Aunque estos
sistemas mejoran el tiempo de computación, los usuarios necesitan
traducir sus consultas de grafos al modelo de trabajo de
MapReduce. De hecho, se ha comprobado que expresar algoritmos
sencillos para grafos en dicho modelo resulta ser un gran desafío.
Adicionalmente, estos sistemas no pueden tomar ventaja de las
características de los grafos, y la implementación de algoritmos
iterativos frecuentemente resulta en complejas cadenas de trabajo
y un movimiento excesivo de datos entre los componentes de la
plataforma.
 A considerar continuación …..

B) Los sistemas de procesamiento offline para análisis de

grafos (offline graph analytic systems), se basan en un
procesamiento iterativo por lotes sobre el total de los datos,
hasta que el método de computación alcanza un punto fijo
(fixed-point) o un criterio de termino. De esta manera, estos
sistemas están capacitados para ejecutar algoritmos para
grafos que requieren una exploración total de los datos y el
uso intensivo de los recursos computacionales, como por
ejemplo el algoritmo de PageRank, consultas recursivas como
la búsqueda de shortest-paths, y algoritmos de clustering.
 USOS - APLICACIÓN
Las bases de datos no relacionales han surgido como respuesta a las necesidades de gestión de datos en
dominios de aplicación de gran relevancia como:

- World Wide Web (contiene mas de 50 billones de paginas web sobre las cuales el algoritmo de page
rank es ejecutado)

- Las redes sociales (Facebook tiene mas de 1.65 billones de usuarios, cada uno con cientos de
relaciones es un framework para el procesamiento de grafos de gran tamaño sobre una plataforma
distribuida, con una alta tolerancia a fallas ampliamente utilizado para el análisis de Big Data.)

- La Bioinformática (Protein Data Bank (PDB) registra un poco mas de cien mil proteínas–de un posible
universo de 1012 cada una de las cuales contiene cientos de aminoácidos y átomos cuyas miles de
relaciones son estudiadas por biólogos y bioinformáticos en busca de tratamientos para las
enfermedades).

- entre otros

Los datos generados por muchos de estos dominios de aplicación pueden ser fácilmente modelados y
analizados como grafos, caracterizados por su estructura irregular, su alta interconexión, y su gran tamaño.
 CASSOVARY

Cassovary es una biblioteca simple de procesamiento de "gráfico grande" para

la JVM. La mayoría de las bibliotecas de gráficos alojadas en JVM son flexibles
pero no ahorran espacio. Cassovary está diseñado desde cero para ser capaz de
manejar gráficas de manera eficiente con miles de millones de nodos y
bordes. Un ejemplo típico de uso es hacer minería de gráficos a gran escala y
análisis de una gran red. 

Cassovary pretende ser fácil de usar en un entorno alojado en JVM y,

sin embargo, ser lo suficientemente eficiente como para escalar a miles
de millones de bordes. Deliberadamente no está diseñado para
proporcionar persistencia o funcionalidad de base de datos, el
tamaño del gráfico con el que trabaja está limitado por la memoria
disponible en una máquina
 El lenguaje que utiliza Cassovary es el SCALA.

Scala es un lenguaje multi-paradigma

diseñado para expresar patrones comunes de
programación en forma concisa, elegante y
con tipos seguros. Sin embargo, estas
características se tienen por todos lados y no
son atractivas para que un programador Java,
C++, o programador en cualquier otro
lenguaje piense en aprender Scala. Hay otras características que tal vez podrían
ser atractivas para programadores, ya que
hoy Scala se ejecuta en el sistema operativo
Android para teléfonos inteligentes y es
compatible desde su concepción con todos
los ambientes Java y se ejecuta en una
Máquina Virtual Java (JVM).
Hoy en día es un lenguaje necesario para la instrumentación de mecanismos para
el manejo de grandes volúmenes de datos. En el lenguaje Scala una gran
característica es su manejo eficiente de Colecciones y así mismo sus directivas para
PARALELIZAR tareas, además de sus mecanismos para crear sistemas concurrentes
con el Modelo de Actores de Akka

* Una de las dificultades en la aplicación de paralelismo en

aplicaciones que utilizan las colecciones es que las colecciones
no son seguros para subprocesos con hilos (not thread-safe),
lo que significa que varios subprocesos no pueden manipular
una colección sin introducir interferencias de hilos (thread
interference) o errores de coherencia de memoria (memory
consistency errors)
Dentro de las características que promueven hoy el uso de Scala es el soporte
en los procesos distribuidos tolerantes a fallas con grandes volúmenes de
datos (BigData).

En Scala la concurrencia se ofrece por medio del Modelo de Actores (Actor Model).
Este modelo ofrece un enfoque de la concurrencia basada completamente en
intercambio de mensajes entre los procesos. El Modelo basado en Actores es una
idea exitosa ya instrumentada en otros lenguajes por ejemplo en el lenguaje Erlang.
 GIRAPH

Para el procesamiento de grandes grafos (Big Grafis).

Se basan en el modelo Paralelo Síncrono a Granel (Bulk Synchronous Parallel - BSP)

Giraph presenta una eficiencia 4 veces superior sobre Hadoop a lo que se refiere al
tiempo de cómputo del algoritmo de PageRank. Esta ventaja aumenta a casi a 8
veces cuando se trata de un algoritmo para encontrar el árbol de expansión mínima.
Esto se debe principalmente a la ventaja que posee Giraph al poder mantener una
comunicación global entre cada superpaso sin requerir entradas y salidas E/S a disco.

Una buena prueba de la capacidad de Giraph para procesar grafos de gran tamaño es
su uso en Facebook
 Funcionamiento
Su uso no es tan sencillo como se argumenta. Solo la instalación y configuración inicial de Giraph,
considerando las bibliotecas involucradas y la plataforma distribuida, toma como mínimo 25 minutos
(requiere de conocimientos intermedios de administración de sistemas)

La ejecución de un algoritmo se puede resumir en tres pasos:

1- Carga de datos:

• La carga de datos implica transformar los datos originales a alguno de los

formatos de texto soportados por Giraph, tarea que puede tomar bastante
tiempo dependiendo de la estructura de los datos y el formato elegido

2- Ejecución del algoritmo:

• Los algoritmos deben ser programados centrándose en los vértices. Esto

puede parecer sencillo, sin embargo es un gran desafío adaptarse a este
nuevo paradigma de programación ya que es muy distinto a la forma
tradicional de diseñar algoritmos para grafos.
• Si bien las funciones básicas del API de Giraph son fáciles de entender,
existen algunas funciones que no son intuitivas y para las cuales existe poca
documentación.
1- Procesamiento del resultado:

• El resultado de ejecutar Giraph se traduce en un archivo plano

que contiene una línea de texto para cada nodo/etiqueta en el
grafo. Claramente, este tipo de resultado implica un
procesamiento y análisis adicional.

• Cabe destacar que el modelo de datos de Giraph se basa en

multigrafos dirigidos y etiquetados, es decir, cada nodo o arista
tiene una etiqueta o valor, las aristas son dirigidas, y pueden
existir múltiples aristas entre un mismo par de nodos.

• Tiene también varias limitantes. En particular, los vértices y 

aristas no tienen tipos, y no es posible asociar datos complejos
–como propiedades– a vértices y aristas, pues estos elementos 
tienen únicamente un valor asociado.
 PageRank
PageRank

PageRank es un algoritmo de análisis de enlaces que se utiliza para determinar la importancia de un

documento basado en el número de referencias y en la importancia de los documentos fuente. Su función
es la de medir la importancia y la calidad de una página web en un rango de 0 a 10.

El valor de una página web –llamémosle X– es determinado a través de los enlaces que le son otorgados por un sitio
Web Y, teniendo en cuenta, además, otros factores como la calidad y la importancia del sitio web que otorga el
enlace. Por consiguiente, tener muchos enlaces no quería decir tener un PageRank de 10, sino que su calidad
también era un factor más que importante en el cálculo de cuan influyente era un portal o sus diferentes páginas.
 GRAPH COMPUTE ENGINE

• Son una solución excelente para consultas analíticas de big data en tiempo real donde el tamaño de
los datos crece rápidamente.
• Mejor resolución de problemas
• Las bases de datos de gráficos resuelven problemas que son poco prácticos para consultas
relacionales, por ejemplo: algoritmos iterativos como PageRank, descenso de gradiente y otros
algoritmos de minería de datos y aprendizaje automático
• Las bases de datos de gráficos pueden realizar actualizaciones en tiempo real en big data y, al
mismo tiempo, admitir consultas.
• Este es un inconveniente importante de los sistemas de gestión de big data existentes, como
Hadoop HDFS, ya que fue diseñado para lagos de datos, donde los escaneos secuenciales y la
incorporación de nuevos datos (sin búsqueda aleatoria) son las características de la carga de trabajo
prevista, y es una opción de diseño de arquitectura para garantizar una exploración rápida de E / S
de un archivo completo.
Combina múltiples dimensiones para administrar grandes datos, incluidas series de
tiempo, demográficas, geo-dimensiones, etc. con una jerarquía de granularidad en
diferentes dimensiones

Con un esquema gráfico cuidadosamente diseñado, los científicos de datos y

analistas de negocios pueden realizar prácticamente cualquier consulta analítica
en una base de datos gráfica.

Las bases de datos de gráficos sirven como una gran infraestructura de inteligencia
artificial debido a la información relacional bien estructurada entre entidades, lo
que permite interferir aún más hechos y conocimientos indirectos. Ejemplo:
Google Expander lo ha utilizado para la tecnología de mensajería inteligente.

El gráfico de conocimiento fue creado por Google para comprender mejor a los
humanos y se están haciendo mucho más avances en la inferencia de
conocimiento que enfatiza los datos dela estructura gráfica como una
configuración de optimización de redes neuronales.

Las claves para una base de datos gráfica exitosa para servir como una
infraestructura de datos de IA en tiempo real son: Soporte para actualizaciones en
tiempo real como flujos de datos nuevos en un lenguaje de consulta declarativa
altamente expresivo y fácil de usar para dar control total a los científicos de datos.
 Pregel

Sistema para el procesamiento de gráficos a gran escala

Pregel es el sistema de Google que impulsa el PageRank es la inspiración para Apache Giraph , que
Facebook usa para analizar su gráfico social.

El procesamiento eficiente de gráficos grandes es un desafío. Los algoritmos de gráficos a menudo exhiben

una localidad pobre de acceso a la memoria, muy poco trabajo por vértice y un grado de paralelismo
cambiante en el transcurso de la ejecución. La distribución en muchas máquinas exacerba el problema de
la localidad y aumenta la probabilidad de que una máquina falle durante el cálculo.

Los cálculos de Pregel consisten en una secuencia de iteraciones, llamadas superpasos. Durante un

superpaso, el marco invoca una función definida por el usuario para cada vértice, conceptualmente en
paralelo
 GRAPH ENGINE (GE)

Es un motor de procesamiento de datos distribuido en memoria, respaldado por un almacén de RAM

fuertemente tipado y un motor de cómputo distribuido general.

La capacidad de exploración rápida de datos y computación paralela distribuida hace de GE una

plataforma de procesamiento de gráficos grandes y naturales.
 
GE admite tanto el procesamiento de consultas en línea de baja latencia como el análisis fuera de línea
de alto rendimiento en gráficos grandes de mil millones de nodos

GE es bueno en la gestión de miles de millones de objetos en tiempo de ejecución de diversos

tamaños. Un byte cuenta a medida que aumenta el número de objetos. GE proporciona una asignación
de memoria rápida y una reasignación de memoria eficiente con altos índices de utilización de
memoria.
 GE encaja donde el caché no es suficientemente bueno

GE utiliza la RAM para acelerar el acceso a los datos, así como el cálculo, La RAM se usa
directamente como almacenamiento en tiempo de ejecución en lugar de solo usarse para servir
recursos estáticos.

GE también es un motor de cálculo flexible impulsado por el paso de mensajes declarativos.

Desde la perspectiva del cálculo gráfico, GE no es un sistema gráfico optimizado específicamente

para una determinada operación gráfica. En cambio, con su capacidad integrada de modelado de
datos y computación, podemos desarrollar módulos de computación gráfica con facilidad. En
otras palabras, GE puede transformarse fácilmente en un sistema que admita un cálculo gráfico
específico.
Ge es un sistema de gestión de gráficos. Está diseñado para administrar gráficos de la vida
real con datos asociados ricos en lugar de solo la topología de gráficos
 Pegasus

Pegasus es un sistema configurable para mapear y ejecutar flujos de trabajo de

aplicaciones abstractas en una amplia gama de entornos de ejecución que incluyen
una computadora portátil, un clúster de campus, una cuadrícula o un comercial o
nube académica

Hoy, Pegasus ejecuta flujos de trabajo en Amazon EC2, Nimbus, Open Science Grid,
TeraGrid y muchos grupos de campos.

Pegaso puede ejecutar flujos de trabajo que van desde unas pocas tareas
computacionales hasta 1 millón.

La entrada a Pegaso es una descripción del flujo de trabajo abstracto en formato XML
Pegasus permite a los investigadores traducir tareas computacionales complejas en flujos de
trabajo que vinculan y gestionan conjuntos de tareas dependientes y archivos de datos
relacionados

Pegasus encadena automáticamente las tareas dependientes juntas, de modo que una sola
los científicos pueden completar cálculos complejos que alguna vez requirieron muchas
personas diferentes.
 Características
- Portabilidad / Reutilización: Los flujos de trabajo creados por el usuario pueden ejecutarse fácilmente
en diferentes entornos sin alteración. Pegasus actualmente ejecuta flujos de trabajo además de Condor,
infraestructuras de Grid como Open Science Grid y TeraGrid, Amazon EC2, Nimbus y muchos grupos de
campos. El mismo flujo de trabajo puede ejecutarse en un solo sistema o en un conjunto heterogéneo de
recursos

- Actuación: El mapeador Pegasus puede reordenar, agrupar y priorizar tareas para aumentar el
rendimiento general del flujo de trabajo

- Escalabilidad: Pegasus puede escalar fácilmente tanto el tamaño del flujo de trabajo como los recursos
sobre los que se distribuye el flujo de trabajo. Ejecuta flujos de trabajo que van desde unas pocas tareas
computacionales hasta 1 millón. La cantidad de recursos a participar en la ejecución de un flujo de trabajo
puede escalar según sea necesario sin ningún impedimento para el rendimiento

- Procedencia: Los datos de procedencia se recopilan en una base de datos, y los datos se pueden resumir
con herramientas tales como pegasus-statistics, pegasus-plot, o directamente con consultas SQL
- Gestión de datos: Pegasus maneja la selección de réplicas, transferencias de datos y registros de
salida en catálogos de datos. Estas tareas se agregan a un flujo de trabajo como trabajos auxiliares
por el planificador de Pegasus.

- Ejecución local: Pegasus puede ejecutar un flujo de trabajo en una sola computadora con acceso a
Internet. Correr en un entorno local es más rápido para implementar, ya que el usuario no necesita
obtener acceso a múltiples recursos para ejecutar un flujo de trabajo.