Datos tan importantes como los biológicos o los astronómicos crecen a una velocidad superior a la velocidad con que crece nuestra capacidad para almacenarlos y utilizarlos. Desarrollar formas más eficientes de almacenamiento y procesamiento de datos puede redundar en un menor uso de hardware, energía y ancho de banda, en la mejora de aplicaciones bioinformáticas como las necesarias para las terapias genéticas o el desarrollo de vacunas y medicamentos, e incluso favorecer saltos científicos impensables, como el que dio la inteligencia artificial. Es la contribución que pueden hacer las estructuras de datos compactas desde las ciencias de la computación.

Por Gonzalo Navarro

Nuestra siempre creciente capacidad para recoger y explotar todo tipo de datos a nuestro alrededor está dando forma a una nueva sociedad que era impensable hace unas pocas décadas y cuyo funcionamiento es ya imposible sin el manejo masivo de estos datos. Desde las ciudades inteligentes hasta la ciencia basada en datos, desde la predicción del clima hasta la inteligencia artificial, desde las sociedades digitales hasta la robótica, nuestro presente y futuro está cruzado por realidades y promesas alrededor de una capacidad extraordinaria para obtener, almacenar, procesar y utilizar datos a una escala nunca vista antes.

Estas grandes promesas traen también grandes desafíos en muchos frentes, y particularmente en el de la ciencia de la computación, la disciplina por excelencia llamada a ofrecer soluciones a los enormes problemas de eficiencia y escalabilidad que surgen y surgirán con cada vez mayor relevancia. Un par de datos para ilustrar. El primero es que hace tiempo ya que la velocidad a la que crecen los datos biológicos y astronómicos disponibles en el mundo han sobrepasado la Ley de Moore, que predice la velocidad a la que crecen nuestras capacidades de almacenamiento y procesamiento computacional. Es solo cuestión de tiempo que no podamos con ellos. El segundo es que el gran salto en la inteligencia artificial, que nació a mediados del siglo pasado y que hasta hace una década o dos se consideraba un sueño frustrado, se debe en gran parte simplemente a nuestro aumento en la capacidad de procesar más datos y a mayor velocidad. El solo hecho de mejorar la eficiencia convirtió un imposible en una realidad cuyas consecuencias recién empezamos a intuir.

Mi principal área de interés, en el Departamento de Ciencias de la Computación de la Facultad de Ciencias Físicas y Matemáticas de la Universidad de Chile, es el área llamada Estructuras de Datos Compactas. Ésta tiene que ver con un enfoque al problema de cómo procesar eficientemente datos muy masivos en forma comprimida, y se combina sinérgicamente con otros enfoques (procesamiento distribuido, paralelo, etc.). Partamos del hecho de que una cosa es el volumen de los datos y otra distinta la cantidad de información que realmente contienen. Los datos se suelen representar en una forma sencilla que permite su fácil utilización, pero eso hace que ocupen un volumen que puede ser muy superior al necesario. La compresión consiste en hallar una representación que ocupe un espacio cercano a la información que realmente tienen estos datos. La teoría de la información estudia cuánta información contienen los datos y, por lo tanto, cuánto y cómo se pueden comprimir.

Sin embargo, la compresión misma no es una respuesta a los problemas planteados, porque tradicionalmente estos datos deben ser descomprimidos nuevamente antes de poder hacer algo útil con ellos. Peor aún, en muchos casos ni siquiera con los datos descomprimidos es factible realizar operaciones complejas en forma eficiente. Es necesario crear estructuras de datos sobre ellos, que son representaciones redundantes —a veces, altamente— para agilizar su acceso y manipulación.

Las estructuras de datos compactas buscan obtener lo mejor de estos mundos. Buscan representar los datos más las estructuras de datos que se requieran para su procesamiento eficiente, en un espacio cercano a la cantidad de información que éstos contienen, es decir, cercano a lo que podrían llegar a comprimirse. Así, los datos se usan directamente en su forma comprimida, sin descomprimirse en ningún momento. Mientras con las representaciones clásicas podemos tener que agregar nuevas estructuras de datos para cada nuevo requerimiento de funcionalidad, aumentando así el espacio requerido, una estructura compacta bien diseñada puede ofrecer una funcionalidad muy amplia sobrepasando apenas el espacio que ocupan los datos comprimidos.

Las estructuras compactas permiten no solo reducir espacio, sino que procesar los datos en memorias menores y más rápidas (por ejemplo, en memoria principal en vez del disco), usar menos hardware y energía (por ejemplo, en data centers que distribuyen los datos en las memorias de muchos computadores interconectados) y usar menos ancho de banda para transferir datos y procesar mayores volúmenes (por ejemplo, en dispositivos móviles). Existe incluso una línea llamada computación comprimida, en la que el tipo de compresión usada ayuda a realizar cómputos más rápidamente que sobre los datos originales. Ésta es un área que tiene solo un par de décadas de vida, pero que ha obtenido ya importantes resultados. Me referiré a dos ejemplos de mi investigación reciente.

En el Centro de Biotecnología y Bioingeniería (CeBiB) nos hemos centrado en estructuras de datos para colecciones genómicas de una misma especie, las cuales son altamente repetitivas porque dos genomas de la colección difieren solo en un pequeño porcentaje. Almacenar estas colecciones es muy desafiante porque están creciendo rápidamente. Por ejemplo, en 2018 se completó en el Reino Unido el proyecto de secuenciar 100.000 genomas humanos, lo que suma unos 3 x 10¹⁴ pares de bases, o 300 terabytes almacenados en forma simple. Este es un caso en que una compresión adecuada permite reducir el espacio en un factor de hasta 100. Este tipo de repetitividad ocurre en otros escenarios, como software o documentos versionados (como GitHub o Wikipedia), pero es en las aplicaciones bioinformáticas donde se requieren los procesamientos más complejos de estas secuencias, con objetivos como terapias genéticas o diseño de vacunas y medicamentos. En 2020 publicamos un artículo en el Journal of the ACM, la principal revista de computación, donde describimos una nueva estructura de datos que puede realizar búsquedas complejas sobre colecciones genómicas en forma muy eficiente y usando muy poco espacio, gracias a explotar determinadas características que ofrece este tipo de colecciones repetitivas. La estructura fue recibida con interés en el mundo bioinformático también. Estamos desde entonces trabajando en integrar esta estructura a un software bioinformático de uso amplio con los creadores del conocido software de alineamiento de secuencias BowTie, pues solo herramientas de este tipo permitirán el manejo de los grandes volúmenes genómicos que enfrentamos a futuro.

En el Instituto Milenio Fundamentos de los Datos (IMFD) tomamos el problema de implementar bases de datos de grafos eficientemente. Este tipo de bases de datos permiten representar información en forma de objetos y de relaciones entre objetos, agregando atributos tanto a los objetos como a las relaciones mismas, a modo de luego poder inferir nueva información mediante encontrar patrones de conectividad y caminos dentro de estos grafos. Es un modelo que, si bien es antiguo, ha ganado mucha popularidad recientemente con el surgimiento de repositorios de información menos estructurados y con el mayor poder de cómputo que hay disponible para procesar esa información. Es el formato de Wikidata, la base de datos que provee información estructurada a Wikipedia, y un componente cada vez más frecuente en los sistemas de información modernos. Un gran desafío es que los patrones que deben encontrarse para inferir nueva información son complejos, y se necesitan algoritmos sofisticados para encontrarlos eficientemente. Para funcionar, estos algoritmos necesitan muchas estructuras de datos altamente redundantes sobre los datos, lo que multiplica varias veces el espacio que requieren estos grafos, ya voluminosos de por sí. Esto hacía que los algoritmos más eficientes fueran inaplicables en la práctica. En 2020 y 2021 publicamos dos artículos en las prestigiosas conferencias ICDT y SIGMOD donde demostramos que esta redundancia no es necesaria. Es posible implementar los mejores algoritmos para inferir información de los grafos en un espacio cercano al de su representación comprimida, lo que abre la puerta a manejar eficientemente volúmenes mucho mayores de información. Seguimos trabajando en enfrentar problemas de búsqueda más complejos que los ya abordados, y en poder implementar en el IMFD un servidor que permita desde todo el mundo realizar consultas complejas en una copia completa de Wikidata, pues las soluciones actuales ya no están dando abasto.

La ciencia de la computación abarca un amplio espectro, que va desde investigación muy teórica, cercana a las matemáticas, a otra muy práctica, cercana a la ingeniería. Siempre me ha atraído el área de algoritmos y estructuras de datos, que permite transitar entre ambos extremos: diseñar soluciones a problemas desafiantes que tienen valor teórico y cuyo desempeño se puede demostrar formalmente, pero que también tienen valor práctico, pueden implementarse y convertirse en sistemas que tienen un valor para la sociedad.