PRACTICAL ALPHABET-PARTITIONED RANK/SELECT DATA STRUCTURES WITH SUPPORT FOR DISTRIBUTED COMPUTATION
Abstract
En esta memoria se presentará una estructura de datos sucinta para representaciónde largas cadenas de texto con aplicaciones prácticas en indexamiento ybúsqueda de texto entre otras.Se mostrará como se comporta experimentalmente en cuanto a espacio utilizadoy tiempo de respuesta en relación a otras estructuras usadas con los mismosfines. Cabe destacar que la estructura presenta características que la hacen viableen ambientes distribuidos, al prescindir de una estructura central sacrificando soloun poco de espacio.Además se muestra una aplicación concreta, calculando la intersección de listasinvertidas. In this project it will be introduced a wavelet tree/bit vector based succint datastructure that uses an alphabet partitioning strategy, to represent long string sequenceswith practical aplications in text indexing and search among others.Its performance, space and time wise, will be shown and compared against otherdata structures used with similar purposes. It is worth noting that this data structurealso shows characteristics that make it viable on distributed enviroments bybeing able to prescind from a central data structure at the expense of only a littlespace.Furthermore, it will be shown how it performs in a concrete application, intersectinginverted lists.