Nuevo modelo algorítmico que acelera las búsquedas en redes

Investigadores de la Universidad CEU San Pablo y otros centros españoles han desarrollado un modelo de búsqueda de recursos en red basado en ‘paseos o caminos aleatorios’ que obtiene los resultados de forma más rápida. Cuando hacemos una búsqueda en internet casi nunca nos paramos a pensar en el proceso técnico que nos facilita el resultado deseado. Más allá de la aparente sencillez, cada búsqueda que un internauta realiza en la red implica el uso de toda una serie de algoritmos informáticos y matemáticos para guiar la búsqueda. Aun así, la eficacia de estos algoritmos, medibles mediante magnitudes como el tiempo que dura la búsqueda, la longitud de la búsqueda o el ancho de banda utilizado, depende de la cantidad de información proporcionada.

Ahora, el profesor Víctor López Millán de la Universidad CEU San Pablo, junto a Vicent Cholvi (Universitat Jaume I), Luis López (Universidad Rey Juan Carlos) y Antonio Fernández Anta (Institute IMDEA Networks), han presentado un modelo de búsqueda de recursos basado en los llamados caminos o paseos aleatorios (random walks).

Con este modelo se han diseñado mecanismos eficientes de búsqueda de recursos en una red en la que no se dispone de información centralizada de sus recursos. Los detalles se han publicado en la revista Computing. Según los autores, los resultados poseen importantes implicaciones prácticas para los internautas que cada día utilizan la red.

Cuando un usuario realiza una búsqueda en internet, consulta por lo general plataformas como Google o buscadores similares, que se encargan de recorrer la web para almacenar información sobre su contenido en una base de datos. Pero, ¿qué pasa si no contamos con esos buscadores centralizados o no podemos disponer de ellos en algún momento determinado?

En ese escenario o en redes P2P que no cuenten con una centralización de enlaces a los contenidos, el modelo tendría utilidad. Permitiría escrutar la red sin necesidad de recurrir a espacios de compartición de ficheros o a los buscadores, con una longitud media de las búsquedas considerablemente menor que si estuvieran basadas sólo en caminos aleatorios.

López Millán incide sobre la relevancia práctica de su investigación: “Los mecanismos de búsqueda propuestos constituyen una aportación a la descentralización de internet, reduciendo la dependencia de servicios centralizados, como pueden ser los buscadores que utilizamos diariamente”.

Los caminos aleatorios se han estudiado extensamente en matemáticas y utilizado en una amplia variedad de campos como la física estadística, la dinámica de poblaciones o la bioinformática. Los investigadores emplearon los de tipo self-avoiding walks (SAW) en lugar de los normales, junto a algunos parciales para ser más eficientes. De esta forma se mejora el rendimiento de los caminos aleatorios normales para no revisitar nodos ya recorridos, elevando la probabilidad de localizar el nodo que posee el recurso deseado.

Suma de reducciones

Los SAW consiguen reducciones de la longitud media de las búsquedas con respecto a los caminos aleatorios normales de entre el 50% y el 75% en los experimentos realizados, dependiendo del tipo de red y de su grado medio. Con los arciales se consiguen reducciones mayores de sus longitudes, lo que supone unas reducciones temporales en las búsquedas de entre el 88% y el 98%, sin una dependencia importante del tipo de red.

Además, al combinar los caminos parciales con los caminos SAW se obtienen reducciones adicionales de entre un 5% y un 12%. Y cuando se adaptan los mecanismos basados en caminos aleatorios parciales a redes con recursos dinámicos se observan también importantes reducciones de la longitud media de las búsquedas.

Este estudio ha demostrado que en mecanismos basados en caminos aleatorios SAW y en caminos aleatorios parciales, y aplicados a redes construidas aleatoriamente y en las que se cumple que cualquier punto de conexión de un nodo puede estar conectado mediante un enlace a cualquier otro punto de conexión de la red con probabilidad uniforme puede obtenerse un rendimiento que supera al de las búsquedas basadas en caminos aleatorios normales.

Acceda a la versión completa del contenido