DUGi

IDELabRoute: librería para la gestión de grafos escalable

http://dugi.udg.edu/item/http:@@@@hdl.handle.net@@10256@@3511

Las redes son un importante elemento topológico que tiene poco soporte en el software libre. Hay redes que cuentan con millones de nodos, lo que conlleva la necesidad de manejarlas de forma cuidadosa para optimizar los recursos. Consultando el estado del arte, hemos concluido que existe cierta cantidad de librerías de código abierto disponible, que generalmente emplean un modelo de gestión de los grafos que genera una estructura mallada de objetos en memoria precisando grandes cantidades de memoria y tiempos de puesta en marcha elevados. Estas carencias adquieren especial relevancia cuando se trata de manejar grandes redes. Además las librerías analizadas no suelen ser aptas para procesado multihilo por lo que no pueden usarse en entornos de servidores. Para estos casos hemos puesto en marcha el proyecto IDELabRoute la solución propuesta consiste en una librería genérica de análisis de redes “thread-safe” con gestión dinámica de memoria; para lo cual, se usa una arquitectura modular con gestores de memoria intercambiables, que desde distintas fuentes de almacenamiento persistente (i.e. bases de datos o sistemas de ficheros), maneja grafos de forma dinámica atendiendo a criterios espaciales y/o topológicos. Se trata de una solución de compromiso, puesto que el precio a pagar por la reducción del tamaño de los objetos en memoria es un incremento en el tiempo de respuesta, debido a la gestión de memorias con diversos tiempos de respuesta. Se trata, por tanto, de un sistema de gestión de grafos dinámico que permite manejar grandes modelos de redes de forma escalable, por lo que puede resultar adecuado en entornos con pocos recursos en relación al tamaño total de la red. El primer objetivo práctico del proyecto es proporcionar a la comunidad del GIS libre un servicio WPS para el cálculo de rutas

Universitat de Girona. Servei de Sistemes d’Informació Geogràfica i Teledetecció