Thesis:
Trie-compressed intersectable sets

Simple item page

datacite.subject.fos	Natural sciences::Computer and information sciences
datacite.subject.fos	Engineering and technology
dc.contributor.correferente	Asin Acha, Roberto
dc.contributor.correferente	Fariña, Antonio (Universidad de Coruña)
dc.contributor.department	Departamento de Informática
dc.contributor.guia	Arroyuelo Billiardi, Diego Gastón
dc.coverage.spatial	Campus Casa Central Valparaíso
dc.creator	Castillo González, Juan Pablo
dc.date.accessioned	2025-09-09T14:20:33Z
dc.date.available	2025-09-09T14:20:33Z
dc.date.issued	2023-08
dc.description.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.	es
dc.description.abstract	In this thesis, we introduce space- and time-efficient algorithms and data structures for the offline set intersection problem. We show that a sorted integer set S C [0..u) of n elements can be represented using compressed space while supporting k-way intersections in adaptive O(kd log(u/8)) time, & being the alternation measure introduced by Barbay and Kenyon. In this way, we show that the adaptive performance of algorithms such as the one by Demaine, López-Ortiz and Munro [SODA, 2000], and the one by Barbay and Kenyon [TALG, 2008] can be achieved using compressed space, introducing new insights into this fundamental algorithmic problem. Our experimental results suggest that our approaches are competitive in practice, outperforming the most efficient alternatives (Partitioned Elias-Fano indexes, Roaring Bitmaps, and Recursive Universe Partitioning (RUP)) in several scenarios, offering in general relevant space-time trade-offs.	en_US
dc.description.degree	Magíster en Ciencias de la Ingeniería Informática
dc.driver	info:eu-repo/semantics/masterThesis
dc.format.extent	74 páginas
dc.identifier.uri	https://cris.usm.cl/handle/123456789/4060
dc.identifier.uri	https://doi.org/10.71959/kf0r-ws81
dc.language.iso	en
dc.rights	Attribution-NonCommercial-NoDerivatives 4.0 International	en
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subject	conjuntos de enteros
dc.subject	interseccion
dc.subject	Compresion
dc.subject.ods	9 Industria, innovación e infraestructura
dc.subject.ods	4 Educación de calidad
dc.subject.ods	12 Producción y consumo responsables
dc.title	Trie-compressed intersectable sets
dspace.entity.type	Tesis

Files

Original bundle

Now showing 1 - 1 of 1

Name:: MC_JC_2023.pdf
Size:: 3.27 MB
Format:: Adobe Portable Document Format

Collections

Tesis de Postgrado