Trie-compressed intersectable sets

Abstract

En esta tesis, se presentan algoritmos y estructuras de datos eficientes en espacio y tiempo para el problema offline set intersection. Mostramos que un conjunto de enteros ordenados s c [0..u) de n elementos se puede representar usando espacio comprimido, mientras se soportan intersecciones de k conjuntos en tiempo adaptativo O(k&log(u/&)), siendo & la medida de alternancia introducida por Barbay y Kenyon. De esta manera, se mostrará que el desempeño adaptativo de algoritmos como el de Demaine, López-Ortiz y Munro [SODA, 2000], y el de Barbay y Kenyon [TALG, 2008] se puede lograr usando espacio comprimido, introduciendo nuevos conocimientos sobre este problema algorítmico fundamental. Los resultados experimentales sugieren que nuestros enfoques son competitivos en la práctica, superando las alternativas más eficientes (Partioned Elias-Fano, Roaring Bitmaps, y Recursive Universe Partitioning (RUP)) en varios escenarios, ofreciendo en general trade-offs espacio-tiempo relevantes.