Browsing by Author "Carmona Tabja, Gabriel Alfredo"
Now showing 1 - 2 of 2
- Results Per Page
- Sort Options
Thesis Brodnik's data structure in practice, revisited(Universidad Técnica Federico Santa María, 2025-06-04) Lagos Cortés, Carlos Cristóbal; Marti Lara, José Luis; Departamento de Informática; Asín Achá, Roberto Javier; Carmona Tabja, Gabriel AlfredoIn 1999, Brodnik et al. proposed an alternative data structure to dynamic arrays for efficient data stream processing. Despite its theoretical promise, this structure has received limited implementation and evaluation on modern computer architectures. This work presents a novel C++-compatible implementation of Brodnik's structure, specifically designed as a container for use with the stack adapter. We evaluate the performance of this implementation across different application scenarios, including sorting and examining its effectiveness as the underlying container for priority_queue, and stack adapters. When employed as the underlying container for stack operations, our implementation demonstrates significant time performance advantages over the standard vector implementation while achieving substantial space savings. Compared to the default stack container, deque, Brodnik's structure matches the temporal performance while delivering improved space efficiency. These results establish the practical viability of Brodnik's theoretical framework in contemporary computing environments and highlight new opportunities for efficient data stream processing in performance-critical applications.Thesis Implementación de un algoritmo aproximado para la estructura partitioned elias-fano e-optimal(2022-08) Carmona Tabja, Gabriel Alfredo; Martí Lara, José Luis; Departamento de Informática; Arroyuelo Billiardi, DiegoLas representaciones que permiten comprimir información son útiles en el día de hoy, esto debido a la masividad de la información, por lo que se busca poder comprimir correctamente la información original de tal forma de mantenerla correctamente, pero ocupando menos espacio. Entre las representaciones existen, Partitioned Elias-Fano corresponde a una estructura que permite comprimir la información correctamente, esta estructura tiene dos implementaciones: uniform que consiste en dividir la información en bloques con una cantidad uniforme de 1’s y -optimal que consiste en dividir la información en bloques de bits con una cantidad variable de 1’s utilizando un algoritmo aproximado. En ambas implementaciones, cada bloque será dividida por separado. Pero, además de comprimir el poder realizar operaciones sobre este conjunto comprimido es importante para no tener que descomprimir la información cada vez que se quiera realizar una consulta. Por esto, se implementaron las operaciones rank y select en la representación Partitioned Elias-Fano y los resultados de las pruebas de estas operaciones indican que si bien esta representación comprime correctamente, los tiempos de estas operaciones son notablemente mayores a otras representaciones.
Política de Privacidad 
