Titulación DCC

Los adaptive dynamic bitvectors son una nueva representación de vectores de bits que, además de las consultas usuales, permite insertar y borrar bits. Esto es esencial para tener estructuras compactas dinámicas de todo tipo.

Lo especial de esta implementación es que se adapta naturalmente a la frecuencia de los updates, siendo casi tan rápida como la versión estática cuando los updates se esparsifican. Parte de esta solución consiste en convertir subárboles a hojas estáticas cuando han recibido muchas queries, y romperl estas hojas cuando llegan nuevos updates. 

En este momento tenemos una implementación de prueba de concepto, pero pensamos que es mejorable. La memoria consiste en implementar una versión más eficiente para romper las hojas estáticas, que evite eliminar la hoja y copiar todas las nuevas hojas. En vez, se plantea compartir esta hoja desaparecida entre los nuevos hijos, lo que requiere una administración más compleja de las hojas estáticas pero puede permitir mucha mayor resiliencia frente a los updates.