DATOS DEL INVESTIGADOR PRINCIPAL |
|
Nombre |
Pablo Montes Arango
|
Nombre del perfíl |
Investigador Tiempo Completo
|
Grupo de investigación |
Sistemas y Computación
|
Línea de investigación |
Bioinformática e Informática teórica (BIT)
|
Equipo del proyecto |
|
TÍTULO DEL PROYECTO |
Algoritmos y Estructuras de Datos para el Manejo de Grandes Cantidades de Información
|
PALABRAS CLAVE |
Análisis y diseño de algoritmos, Estructuras de datos, Memoria principal / Memoria secundaria, Entrada / Salida de datos, Ordenamiento, Cota inferior
|
OBJETIVOS DEL PROYECTO |
Análisis, diseño e implementación de algoritmos y estructuras de datos asintóticamente óptimos bajo el modelo DAM. Esto incluye (1) el análisis de algoritmos y estructuras de datos existentes, (2) el diseño y análisis de modificaciones a los algoritmos y estructuras de datos existentes buscando mejorar su eficiencia, (3) el diseño y análisis de nuevos algoritmos y estructuras de datos para resolver problemas prácticos que requieren el procesamiento de grandes cantidades de información, y (4) el estudio de detalles de implementación de los algoritmos y las estructuras de datos estudiados y propuestos.
|
PERTINENCIA ESPISTEMOLÓGICA DEL PROYECTO |
En años recientes la cantidad de información almacenada por los sistemas ha ido incrementado en medidas desproporcionadas. El sistema observación de la tierra de la NASA, por ejemplo, produce petabytes de datos por año. De igual forma, las bodegas de datos de ventas de empresas como Walmart ocupan más de medio petabyte.
El gran reto actual es, entonces, la manipulación y el procesamiento eficiente de todos estos datos. De lo contrario, la mayoría de la información recopilada sería inútil.
Ahora bien, por restricciones de hardware, no es posible almacenar toda la información en memoria principal para su procesamiento. Se hace necesario, entonces, traer la información de memoria secundaria por fragmentos. Cuando el programa necesita algún dato, la información debe ser transportada desde la memoria secundaria, procesada, y transportada de vuelta para hacer espacio para nueva información. Cada operación de entrada / salida entre la memoria principal y la memoria secundaria tiene un alto costo en cuanto a tiempo. Mientras está esperando por la información, el procesador no está realizando ninguna actividad productiva, lo que afecta el tiempo de ejecución de el programa como un todo.
El análisis de algoritmos tradicional asume que todos los datos pueden ser accedidos en tiempo constante y, por lo tanto, un programa que en teoría es eficiente bajo este modelo, puede no desempeñarse bien ante la presencia de grandes cantidades de información. Se hace necesario, entonces, utilizar un modelo de análisis diferente que tenga en consideración el efecto de la entrada / salida de datos. El modelo de ``Acceso Aleatorio a Disco'' (DAM por sus siglas en inglés) es comúnmente utilizado para este fin.
|
RELEVANCIA DEL PROYECTO PARA LA INSTITUCIÓN Y PARA LOS BENEFICIARIOS DEL PROYECTO |
El proyecto se propone como parte de los estudios doctorales del profesor Pablo Montes Arango y se encuentra estrechamente relacionado con las materias de la línea de métodos formales y, específicamente, con la materia Análisis y Verificación de Algoritmos.
|
PROBLEMA DE INVESTIGACIÓN |
Actualmente el proyecto se centra en dos problemas de investigación. El primero, de naturaleza completamente teórica, trata el problema de ordenamiento de llaves atómicas de longitud variable en memoria externa. El segundo, con un fuerte componente práctico, trata el problema de consultas de pertenencia aproximada en conjuntos extremadamente grandes.
|
METODOLOGÍA |
El proyecto puede ser clasificado dentro de la investigación científica por cuanto se basa en la revisión de artículos recientes relacionados y la propuesta teórica de avances en el área. El proceso se realiza de forma conjunta con el asesor y los otros integrantes del grupo de investigación en algoritmos dn Stony Brook University.
|
RESULTADOS ESPERADOS |
Demostración de una cota inferior estrecha así como el diseño y análisis de un algoritmo asintóticamente óptimo para el problema de ordenamiento de llaves atómicas de longitud variable en memoria externa.
Diseño e implementación de una estructura de datos probabilística para solucionar el problema de consulta de pertenencia aproximada en conjuntos, con énfasis en la optimización de su desempeño en memoria secundaria.
|
DURACIÓN DEL PROYECTO |
|
POSIBLES FUENTES DE FINANCIACIÓN EXTERNA |
|
REVISIÓN BIBLIOGRÁFICA |
|
ENTREGABLES |
|
CRONOGRAMA |
TIPO |
DESCRIPCIÓN |
F.INICIO |
F.FINAL |
Entregable
|
Artículo Divulgativo
|
01/01/2012
|
01/04/2012
|
Entregable
|
Software
|
01/01/2012
|
01/06/2012
|
Entregable
|
Articulo de Investigación
|
01/01/2012
|
01/06/2012
|
Entregable
|
Articulo de Investigación
|
01/01/2012
|
01/12/2012
|
Seleccione...
|
|
|
|
|
PEDIDO DE BIBLIOGRAFÍA |
|
ANEXOS | |