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 para el manejo de grandes cantidades de información
PALABRAS CLAVE	Análisis y diseño de algoritmos, memoria principal, memoria secundaria, entrada / salida de datos
OBJETIVOS DEL PROYECTO	El proyecto busca analizar algoritmos existentes bajo el modelo DAM y proponer modificaciones para mejorar su eficiencia bajo este modelo, diseñar y analizar nuevos algoritmos bajo el modelo DAM para resolver problemas prácticos que requieren el procesamiento de grandes cantidades de datos, y estudiar detalles de implementación de los algoritmos estudiados y propuestos.
PERTINENCIA ESPISTEMOLÓGICA DEL PROYECTO	En la actualidad, las aplicaciones se ven enfrentadas al reto de manipular eficientemente grandes cantidades de información. 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, 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. En el modelo DAM se asume que la memoria principal tiene un tamaño total de $M$, la información entre memoria principal y memoria secundaria es transportada en bloques de tamaño $B$ y el número total de datos de entrada es $N$. Bajo este modelo, la eficiencia de un algoritmo se mide en términos de el número de bloques que se transportan entre memoria principal y memoria segundaria durante su ejecución. Para tal fin, el algoritmo debe ser diseñado teniendo en cuenta las siguientes consideraciones: 1. Localidad espacial: Cuando un bloque es traído a memoria principal debe contener tanta información útil como sea posible. Dado que un bloque contiene por lo general más de un único dato, el algoritmo debe almacenar la información de tal forma que la mayor cantidad de datos dentro del bloque sean utilizados y no únicamente el que era requerido. 2. Localidad temporal: Una vez que un dato está en memoria principal, debe realizarse la mayor cantidad de procesamiento con él como sea posible antes de ser escrito de nuevo en memoria secundaria. Dado que el transporte de bloques es tan costoso, el algoritmo debe propender por que la información contenida en el bloque sea utilizada por la mayor cantidad de tiempo posible y que una vez que se devuelva el bloque a memoria secundaria no vuelva a ser requerido en el futuro cercano. 3. Eficiencia interna: El trabajo interno realizado por el algoritmo, asumiendo que todos los datos caben en memoria principal, debe ser comparable con lo algoritmos más eficientes para resolver el mismo problema. Algunos de los problemas específicos que se estudiarán a corto plazo incluyen: 1. El estudio de algoritmos de ordenamiento bajo el modelo DAM en donde las llaves son consideradas atómicas, pero de diferentes tamaños. Aunque es bien sabido que se requieren $\Omega ((N / B) \log_{M / B} (N / B))$ transferencias de bloques para ordernar un arreglo de $N$ elementos, este límite asume que todas las llaves tienen el mismo tamaño y, más aún, que un bloque está compuesto de una o más llaves. Sin embargo, si las llaves son extremadamente grandes ($\Theta (M)$) no es posible ordernar el arreglo en menos de $O ((N / B) \log_{2} (N / B))$. El proyecto propone el diseño de algoritmos de ordenamiento que se comporten bien ante la presencia de llaves de atómicas de diferentes tamaños. 2. El estudio de estructuras de dato eficientes en espacio para el modelado de conjuntos dinámicos extremadamente largos a través de índices probabilísticos. En particular se propone el diseño de una estructura de datos eficiente en espacio, independiente de la historia y dinámica que permita reducir el número de ``búsquedas ocultas'' innecesarias en la inserción / eliminación de elementos en bases de datos mediante la solución del problema de preguntas de pertenencia aproximada en conjuntos. 3. El estudio de órdenes óptimos de almacenamiento para mallas dinámicas en el modelo cache-ignorante. Aunque se han propuesto varios órdenes para almacenamiento de mallas en el modelo DAM y en el modelo cache-ignorante que permiten actualizaciones eficientes, estos órdenes no tienen en cuenta mallas dinámicas. En particular se propone el estudio de un algoritmo propuesto por [Bender, Kuszmaul, Teng y Wang en 2007] que preprocesa una malla dada y la almacena en tiempo $O (|G| \log^{2} |G|)$ y con $O (1 + |G| \log^{2} (|G| / M) / B)$ transferencias de memoria para permitir inserciones y eliminaciones eficientes.
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. Con respecto a la pertinencia empresarial, la necesidad de algoritmos que procesen gran cantidad de datos de una manera eficiente es obvia en la industria de software en la actualidad.
PROBLEMA DE INVESTIGACIÓN	Análisis, diseño e implementación de algoritmos nuevos y existentes bajo el modelo DAM.
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. La información requerida se encuentra publicada en librerías digitales como ACM y IEEE. El proceso de información se realiza de forma conjunta con el asesor y los otros integrantes del grupo de investigación en Algoritmos en Stony Brook University.
RESULTADOS ESPERADOS	Se espera la publicación de artículos de investigación en congresos reconocidos a nivel internacional en las áreas de análisis y diseño de algoritmos y sistemas, así como la implementación de las estructuras de datos diseñadas.
DURACIÓN DEL PROYECTO
POSIBLES FUENTES DE FINANCIACIÓN EXTERNA
REVISIÓN BIBLIOGRÁFICA
ENTREGABLES
CRONOGRAMA	TIPO DESCRIPCIÓN F.INICIO F.FINAL Entregable Software 01/01/2011 15/10/2011 Entregable Software 01/01/2011 15/10/2011 Entregable Artículo 01/01/2011 14/06/2011 Seleccione... Seleccione... Seleccione... Seleccione... Seleccione... Seleccione... Seleccione...
PEDIDO DE BIBLIOGRAFÍA	AUTOR TÍTULO EDITORIAL
ANEXOS