DSpace Angular :: Browsing by Author "Riveros Jaeger, Cristian"

Browsing by Author "Riveros Jaeger, Cristian"

Now showing 1 - 19 of 19

A family of centrality measures based on subgraph
(2019) Salas Cornejo, Jorge; Riveros Jaeger, Cristian; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Esta tesis introduce las bases teóricas de un nuevo enfoque para las medidas de centralidad sobre bases de datos de grafos. El principio fundamental de este enfoque es simple: mientras más subgrafos relevantes envuelvan a un vértice, más central será dentro de la red. La idea de ”subgrafos relevantes” se formaliza eligiendo una familia de subgrafos que, dado un grafo G y un vértice v en G, esta asigna un conjunto de subgrafos conexos de G que contienen a v. Cualquiera de estas familias define una medida de centralidad al contar la cantidad de subgrafos asignados a cada vértice, i.e, un vértice será más importante para la red si pertenece a más subgrafos dentro de la familia. Se muestran ejemplo de este enfoque, en particular, se propone all-subgraphs centrality, una medida de centralidad que toma en cuenta todos los posibles subgrafos. Se analizan las propiedades fundamentales sobre familias de subgrafos que garantizan propiedades deseables sobre la medida de centralidad. Interesantemente, all-subgraphs centrality satisface todas estas propiedades, mostrando su robustes como noción de centralidad. Finalmente, se prueba la complejidad computacional del conteo de ciertas familias de subgrafos y se muestra un algoritmo de tiempo polinomial para computar all-subgraphs centrality cuando el grafo posee tree width acotado.
A framework for annotating CSV-like data
(2016) Arenas Saavedra, Marcelo Alejandro; Maturana, F.; Riveros Jaeger, Cristian; Vrgoc, Domagoj
A framework for complex event processing
(2017) Grez Arrau, Alejandro; Riveros Jaeger, Cristian; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Complex Event Processing (CEP) ha surgido como el campo unificador para las tecnologías que requieren procesar y correlacionar en tiempo real datos heterogéneos y distribuidos. CEP tiene aplicaciones en diversas áreas, lo que ha resultado en que haya un gran número de propuestas para procesar eventos complejos. Sin embargo, los sistemas CEP existentes están basados en soluciones ad-hoc que no se sustentan en bases teóricas sólidas, lo que los hace difíciles de entender, extender y generalizar. Además, son presentados generalmente de manera informal como interfaces de programación, y el utilizar cada uno de ellos requiere aprender un conjunto completamente nuevo de conocimientos. En esta tesis buscamos definir un marco riguroso para CEP. Comenzamos proponiendo un lenguaje formal para especificar eventos complejos, llamado CEPL, que contiene los operadores más comunes utilizados en la literatura y el cual tiene semántica simple y denotacional. Además, formalizamos las llamadas estrategias de selección, que son la piedra angular de CEP y en los sistemas existentes son presentadas sólo como extensiones en su diseño. Con la semántica ya definida, estudiamos cómo evaluar eficientemente CEPL. Obtenemos resultados de optimización basados en la re escritura de fórmulas, proponiendo una forma normal para manejar filtros unarios. Además, damos un modelo computacional formal para CEP basado en transductores y autómatas simbólicos, llamado matchautomata, el cual captura el fragmento regular de fórmulas con predicados unarios. Utilizando técnicas de reescritura y transformando a autómata, mostramos que el fragmento regular de CEPL puede ser evaluado eficientemente (tiempo constante por evento) cuando se utiliza la estrategia de selección next. Con estos resultados, proponemos un marco para evaluar eficientemente CEPL, estableciendo bases sólidas para futuros sistemas CEP.
Bounded Repairability for Regular Tree Languages
(2016) Bourhis, Pierre; Puppis, Gabriele; Riveros Jaeger, Cristian; Staworko, Slawek
Complex event recognition meets hierarchical conjunctive queries
(2024) Pinto Araya, Dante; Riveros Jaeger, Cristian; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Las consultas conjuntivas jerárquicas (HCQ) son un subconjunto de las consultas conjuntivas (CQ) con propiedades algorítmicas robustas. Berkholz, Keppeler y Schweikardt, entre otros, han demostrado que HCQ es la subclase de CQ mas grande que admite la evaluación dinámica de consultas con constant update time y constant dealy enumeration. Por otra parte, nos encontramos con el concepto de Complex Event Recognition (CER), una tecnología prominente para la evaluación de patrones sobre streams de datos. Dado que un stream de datos puede interpretarse como una secuencia, potencialmente infinita, de inserciones para la evaluación dinámica de consultas, es natural preguntarse si es posible aprovechar las propiedades de las HCQ para encontrar una clase robusta de consultas que puedan evaluarse de forma eficiente en el setting de CER. En esta tesis buscamos combinar las HCQ con patrones de secuencia para encontrar una clase de consultas de CER que tengan lo mejor de ambos mundos. Con este objetivo, proponemos un modelo de autómata, llamado Parallelized Complex Event Automata (PCEA), para evaluar consultas de CER con correlación (i.e., joins) sobre streams de datos. Este modelo nos permite expresar patrones de secuencia y comparar valores entre tuplas, pero además incorpora una definición alternativa de no determinismo que llamamos paralelización. Mostramos que para toda HCQ, utilizando bag semantics, es posible construir un PCEA equivalente. Adicionalmente, mostramos que HCQ es la clase de consultas conjuntivas acíclicas más grande que este modelo puede definir. Por lo anterior, PCEA es un modelo que captura precisamente las HCQ y las extiende con patrones de secuencia. Finalmente, mostramos que PCEA hereda las propiedades algorítmicas de las HCQ, presentando un algoritmo de evaluación para PCEA bajo sliding windows con logarithmic update time y output-linear delay.
Copyless cost-register automata : Structure, expressiveness, and closure properties
(2019) Mazowiecki, Filip; Riveros Jaeger, Cristian
Descriptive complexity for counting complexity classes
(2017) Muñoz Cruces, Martín Alonso,; Arenas Saavedra, Marcelo Alejandro; Riveros Jaeger, Cristian; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
La complejidad descriptiva ha sido muy exitosa en caracterizar clases de complejidad de decisión en términos de propiedades definibles en algunas lógicas. Sin embargo, la complejidad descriptiva para clases de complejidad de conteo, como FP y #P, no ha sido estudiada sistemáticamente, y no está tan desarrollada como su análogo de decisión. En este artículo, proponemos un marco teórico basado en lógicas con peso para tratar este problema. Específicamente, al enfocarnos en los números naturales obtenemos una lógica llamada Lógica de Segundo Orden Cuantitativa (QSO), y mostramos cómo algunos de sus fragmentos pueden ser usados para capturar clases de complejidad de conteo fundamentales como FP, #P y FPSPACE, entre otras. También usamos QSO para definir una jerarquía dentro de #P, identificando clases de complejidad de conteo con buenas propiedades de clausura y aproximación, y que admiten problemas completos naturales. Finalmente, añadimos recursión a QSO, y mostramos cómo esta extensión captura naturalmente clases de complejidad de conteo inferiores como #L.
Descriptive Complexity for counting complexity classes
(IEEE, 2017) Arenas Saavedra, Marcelo Alejandro; Muñoz Cruces, Martin Alonso; Riveros Jaeger, Cristian
Descriptive Complexity has been very successful in characterizing complexity classes of decision problems in terms of the properties definable in some logics. However, descriptive complexity for counting complexity classes, such as FP and #P, has not been systematically studied, and it is not as developed as its decision counterpart. In this paper, we propose a framework based on Weighted Logics to address this issue. Specifically, by focusing on the natural numbers we obtain a logic called Quantitative Second Order Logics (QSO), and show how some of its fragments can be used to capture fundamental counting complexity classes such as FP, #P and FPSPACE, among others. We also use QSO to define a hierarchy inside #P, identifying counting complexity classes with good closure and approximation properties, and which admit natural complete problems. Finally, we add recursion to QSO, and show how this extension naturally captures lower counting complexity classes such as #L.
Efficient enumeration algorithms for regular document spanners
(2020) Florenzano Hernández, Fernando Alberto; Riveros Jaeger, Cristian; Ugarte, M.; Vansummeren, S.; Vrgoc, Domagoj
Efficient evaluation of correlation and ranked enumeration for complex event recognition
(2023) Grez Arrau, Alejandro; Riveros Jaeger, Cristian; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Con el paso del tiempo, son cada vez más necesarias herramientas que permitan resolver consultas a datos en tiempo real, lo que se vuelve más complejo a medida que la cantidad de datos que se procesan se vuelve cada vez mayor. El área de Complex Event Recognition (CER) engloba herramientas que buscan solventar esta necesidad, al proveer sistemas particulares especializadas en la evaluación de consultas sobre flujos de datos, enfocándose principalmente endarrespuestasentiemporealaconsultas conunaltoniveldeexpresividad. Eneste trabajobuscamosaportaraesta ´areaal abstraernosde lossistemasdesarrolladosyestudiar lasnecesidadesm´ as recurrentesde losusuariosdeestasherramientasdesdeunpuntodevistate´ orico.Primero,proponemosunmarcote´ oricopara CER,quedefineunlenguajeb´asicodeconsultasconunasem´anticaclaradesusoperadoresycapazdeexpresarel llamadofragmentoregulardeloslenguajesCER, junto conalgoritmosdeevaluaci´ onqueentregans´ olidasgarant´ ıasdeeficienciaalusuario: procesamientodecadaeventoentiempoconstanteyenumeraci´ ondecadaresultado entiempolinealeneltama˜ nodeeste. Luego,nosenfocamosenextenderdichomarcote´ oricodedosmaneras.Primero, extendemosellenguajeconeloperadorpartition-by,quepermiteexpresarunaversi´ on restringidadecorrelaci´ onconigualdadeinigualdad,yproponemosunnuevonuevo algoritmoquepermiteevaluarconsultasconesteoperador,manteniendolasmismas garant´ ıasdeeficiencia. Finalmente,proponemost´ecnicasdeevaluaci´ ondeconsultas sobrel´ ogicamon´ adicadesegundoordenquepermitenentregar losresultadosenordendeacuerdoaunafunci´ ondecostosdefinidaporelusuario,quetomatiempode procesamientolinealsobreellargodelinputytieneunfactorlogar´ ıtmicodellargodel inputenel tiempodeenumeraci´ ondecadaresultado. Luego,utilizamosestat´ecnica paraextenderelmarcoCERpropuestoconeloperadordeventanasdetiempowithin.
Expressive power of linear algebra query languages
(2020) Muñoz Serrano, Thomas; Riveros Jaeger, Cristian; Vrgoc, Domagoj; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Los algoritmos del álgebra lineal a menudo requieren algún tipo de iteración o recursión, como lo ilustran los algoritmos estándar para la eliminación gaussiana, la inversión de matrices y la clausura transitiva. Una característica clave compartida por estos algoritmos es que permiten que se repitan varios pasos, pero limitados por la dimensión de la matriz. En esta tesis, ampliamos el lenguaje de consulta para matrices MATLANG con este tipo de recursión, y evidenciamos que esto es suficiente para expresar algoritmos clásicos del álgebra lineal. Estudiamos el poder expresivo de este lenguaje y demostramos que corresponde naturalmente a las familias de circuitos aritméticos, que a menudo se dice que capturan el álgebra lineal. Además, analizamos varios sub-fragmentos de nuestro lenguaje, y se demuestra que su poder expresivo está estrechamente relacionado con formalismos lógicos en las relaciones anotadas en semi-anillos.
Expressiveness and complexity analysis of information extraction languages
(2017) Maturana Sanguineti, Francisco José; Riveros Jaeger, Cristian; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Los lenguajes de Extracción de Información (EI) en base a reglas han recibido atención de parte de la comunidad de bases de datos últimamente, con varios lenguajes nuevos apareciendo en los últimos años. A pesar de que los sistemas de EI suelen procesar datos semi-estructurados, todos los lenguajes que se han propuesto hasta ahora están diseñados para producir relaciones y, por lo tanto, son incapaces de trabajar con información incompleta. Además, existe poco conocimiento acerca de cómo estas propuestas se comparan en términos de poder expresivo y complejidad. Para remediar esto, esta tesis estudia la expresividad y complejidad de distintos lenguajes de EI a través de un marco teórico unificador con soporte para información incompleta.Con este fin, se propone un lenguaje que generaliza otras propuestas anteriores y que utiliza funciones parciales (también llamadas mappings) en lugar de relaciones. Luego utilizamos este lenguaje general para comparar distintos métodos de EI definidos en el pasado y estudiar sus propiedades computacionales, tales como: enumeración de consultas, satisfacibilidad y equivalencia. Como se muestra, ninguno de los métodos propuestos domina a los otros, sin embargo, combinando ciertas características de distintos enfoques se puede obtener un lenguaje para EI que es expresivo, puede implementarse eficientemente y puede ser utilizado en la práctica.
Extending SPARQL engines with multiway joins
(2019) Rojas Victoriano, Carlos; Riveros Jaeger, Cristian; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
En los últimos años han surgido nuevos algoritmos de join, los cuales no evalúan la operación como un operador binario como ha sido usual, sino que como un gran operador de join que reúne una cantidad arbitraria de relaciones a la vez. Estos algoritmos ofrecen garantías teóricas de eficiencia y se ha demostrado que para el peor caso, su complejidad asintótica es óptima. Más aún, se ha mostrado empíricamente que mejoran significativamente los tiempos de ejecución de consultas para bases de datos relacionales y de grafos. A pesar de estos prometedores resultados teóricos y prácticos, la comunidad de la Web Semántica aún no ha adoptado tales técnicas. De hecho, ninguna base de datos RDF nativa soporta actualmente tales algoritmos de join. El objetivo de este trabajo es mostrar cómo modificar un motor RDF existente para incorporar uno de estos algoritmos y estudiar su rendimiento en consultas intensivas en joins. Específicamente, en este trabajo se propone un nuevo procedimiento para evaluar consultas SPARQL basadas en un algoritmo de multiway join óptimo para el peor caso llamado Leapfrog Triejoin. Para esto modificamos el motor RDF Apache Jena para que resuelva las consultas usando este nuevo método. Luego presentamos resultados de dos benchmarks SPARQL conocidos: Berlín y WatDiv. Además proponemos un nuevo benchmark basado en Wikidata que busca proporcionar información sobre el rendimiento del join sobre un conjunto de patrones de consulta intensivo en joins y diverso. Nuestros resultados muestran que Apache Jena con este nuevo algoritmo ejecuta consultas intensivas en join más rápido que la versión base y otros dos motores SPARQL (Virtuoso y Blazegraph), llegando en algunos casos a ser órdenes de magnitud más rápido.
On the expressiveness and structural properties of centrality measures
(2024) Salas Cornejo, Jorge; Pieris, Andreas; Riveros Jaeger, Cristian; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Centrality measures are used as analytical tools to understand graph-based data in various contexts. They are particularly useful for detecting important agents in disease spreading, influential individuals in social networks, or political decisionmakers. This is primarily due to the diversity of measures and their potential for exploitation in theoretical analyses. However, there exists a gap in the understanding of centrality from a foundational perspective. In this thesis, we provide an in-depth study of centrality measures from two different angles. Firstly, we examine how centralities behave over trees. Due to the simple structure of trees, it is easier to analyze each centrality measure in a restricted setting. We introduce the rooting tree property and propose a framework of potential functions to characterize rooting measures. In the last two Chapters, we present a novel study of the family of subgraph-based centralities (SBMs), which serve as a general framework for developing new measures. To define an SBM, we select a set of important subgraphs relevant to a specific application. The most important vertices are then determined based on the number of important subgraphs surrounding them. Initially, we investigate the absolute and ranking expressiveness of SBMs, answering the question of when an arbitrary centrality measure can be defined as an SBM. This, in turn, allows us to compare commonly used centralities within the scope of SBMs. Finally, we conduct an experimental study of important subgraph-based measures, as well as commonly used measures, using statistical scores such as Pearson correlation, ranking distances, and similarities to identify evidence of closely related measures.
Probabilistic automata of bounded ambiguity
(2020) Fijalkow, N.; Riveros Jaeger, Cristian; Worrell, J.
Rematch: A novel regex engine for finding all matches
(2024) Van Sint Jan Campos, Nicolás Andre; Riveros Jaeger, Cristian; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
En esta tesis presentamos el sistema REmatch para la extraccion de información. REmatch esta basado en un algoritmo de enumeración recientemente propuesto para evaluar expresiones regulares con variables de captura que soportan la semantica de encontrar todos los resultados. Se expone lo necesario para hacer que un algoritmo teóricamente óptimo funcione en la práctica. Como mostraremos, una implementación ingenua del algoritmo original tendría dificultades para lidiar con cargas de trabajo realistas. Dado lo anterior, desarrollamos un nuevo algoritmo y una serie de optimizaciones que hacen que REmatch sea tan o mas rápido que muchos motores RegEx populares, al mismo tiempo que puede devolver todos los resultados, una tarea con la que la mayoría de los otros motores suele tener problemas.
The per-character cost of repairing word languages
(2014) Benedikt, M.; Puppis, G.; Riveros Jaeger, Cristian
Towards the computation of motif-based centrality measures over real-world networks
(2023) Bugedo Bugedo, Sebastián; Riveros Jaeger, Cristian; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Las medidas de centralidad han probado ser una herramienta valiosa para analizar datos en forma de grafos. Algunas aplicaciones sobre bases de datos de grafos, tales como grafos de conocimiento o motores de búsqueda en la web semántica, han sido propuestas últimamente. En esta área, las medidas de centralidad basadas en motivos han surgido como un acercamiento prometedor para entender medidas de centralidad en bases de datos de grafos y para definir una familia de nuevas medidas con propiedades teóricas deseables. No obstante, estas son difíciles de computar en general (i.e. #P-hard). En consecuencia, hasta ahora no existen estudios experimentales de dichas medidas en redes reales. En esta tesis nos embarcamos en el computo de medidas de centralidad basadas en motivos y en comprender cómo se comportan sobre redes reales. Para lograr este objetivo, comenzamos estudiando si es posible aproximar estas medidas. Así, presentamos nuevos resultados teóricos que confirman su dificultad de cómputo y aproximación. Debido a esto, perseguimos un camino diferente usando técnicas algorítmicas avanzadas y paralelización para superar las restricciones teóricas en un contexto práctico. Específicamente, presentamos un algoritmo empírico de parámetros fijos que tiene tiempo lineal sobre el tamaño del grafo, pero exponencial en su treewidth. Más aún, mostramos cómo paralelizar el algoritmo en una arquitectura de múltiples núcleos. De esta forma, presentamos una primera implementación de nuestro algoritmo, capaz de calcular centralidad basada en subgrafos en instancias de miles de nodos. Finalmente, comparamos los resultados con medidas de centralidad usadas en la literatura. Con todo, este trabajo constituye el primer estudio práctico de medidas basadas en motivos, sentando las bases para estudios futuros y aplicaciones sobre datos en grafos.
Which XML Schemas are Streaming Bounded Repairable?
(2015) Bourhis Gabri, Pierre; Puppis, Ele; Riveros Jaeger, Cristian

Browsing by Author "Riveros Jaeger, Cristian"

Results Per Page

Sort Options