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	AUTOR TÍTULO EDITORIAL
ANEXOS