Browsing by Author "Arenas Saavedra, Marcelo Alejandro"

Now showing 1 - 20 of 33
  • Thumbnail Image
    Item
    A framework for annotating CSV-like data
    (2016) Arenas Saavedra, Marcelo Alejandro; Maturana, F.; Riveros Jaeger, Cristian; Vrgoc, Domagoj
  • Thumbnail Image
    Item
    A principled approach to bridging the gap between RDF data and their schemas.
    (2013) Díaz Cáceres, Gonzalo Ignacio; Arenas Saavedra, Marcelo Alejandro; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    Aunque grafos RDF tienen información de su esquema asociados a ellos, en la práctica es muy común encontrar situaciones en que los datos no se conforman totalmente a su esquema. Un ejemplo conspicuo es el de DBpedia, que son datos RDF extraídos desde Wikipedia, una fuente de información públicamente editable. En tales situaciones, se torna interesante estudiar las propiedades estructurales de los datos en sí, dado que el esquema de una descripción incompleta de la organización de una base de datos. En este trabajo nos hemos acercado al estudio de la estructura de un grafo RDF desde primeros principios: proponemos un marco teórico para especificar funciones de estructura, que miden el grado de conformancia entre un grafo RDF y un esquema. En particular, primero se define un lenguaje formal para la especificación de funciones de estructura mediante expresiones que denominamos reglas. Este lenguaje permite a un usuario o a un administrador de una base de datos especificar una regla a la cual un grafo RDF puede conformarse de forma total o parcial.
  • Thumbnail Image
    Item
    Análisis experimental de algoritmos de aproximación aleatorizados para conteo en autómatas
    (2023) Rodríguez Reveco, Ricardo Raúl; Arenas Saavedra, Marcelo Alejandro; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    Esta tesis analiza el rendimiento de algoritmos para el problema #NFA, que consiste en contar la cantidad de palabras aceptadas, de un largo dado, en autómatas finitas no deterministas (NFAs). Este trabajo contiene la primera implementación y análisis empírico del algoritmo de aproximación aleatorizado propuesto por Arenas et al. (2021). Este estudio utiliza una metodología experimental para evaluar el algoritmo en tres familias diferentes de NFAs, incluyendo el modelo de Tabakov-Vardi de NFAs aleatorios.Los resultados muestran que el algoritmo de Arenas et al. no logra superar en eficiencia a los algoritmos tradicionales de determinización, incluso con relajaciones en sus parámetros. Esto sugiere que, aunque el algoritmo presenta una complejidad polinomial teórica, en la realidad no resulta efectivo para situaciones realistas, caracterizándolo como un posible algoritmo galáctico (Lipton & Regan, 2013). Asimismo, la tesis recomienda direcciones de investigación futuras. Esto incluye el desarrollo de métodos alternativos para generar NFAs aleatorios y la mejora de la eficacia en las subrutinas de muestreo de los algoritmos de aproximación aleatorizados. De esta forma, el estudio abre nuevos caminos tanto en el desarrollo de algoritmos para el problema #NFA como en las metodologías de evaluación de estos.
  • Thumbnail Image
    Item
    BERT for scientific articles recommendations using open source information
    (2023) Barías Compagnoni, Bernardo; Arenas Saavedra, Marcelo Alejandro; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    En los últimos años, los modelos de lenguaje han experimentado grandes avances en el Procesamiento del Lenguaje Natural (NLP). En concreto, el pre-entrenamiento y el desarrollo de modelos como BERT (Bidirectional Encoder Representations from Transformers) y sus derivados se han convertido en el estado del arte para muchas tareas de comprensión del lenguaje. Un campo de investigación interesante que utiliza modelos lingüísticos de PNL es el que estudia la similitud entre textos (Shahmirzadi et al., 2019; Wang & Dong, 2020). Estos textos pueden ser desde grandes documentos o párrafos, hasta oraciones o frases cortas. Gran parte de la dificultad de este problema radica en que los textos, en general, no están bien estructurados. Se han utilizado distintas técnicas para tratar de entender el contexto de los textos y comprender así la semántica de los documentos. Naturalmente, si los textos son mas largos, esto se convierte en una tarea más difícil. Dentro del estudio de la similitud entre textos, recientemente se ha intentado estudiar la relación entre pares de artículos científicos (Knoth et al., 2010, 2017; Tarnavsky et al., 2021). Al comparar artículos científicos, aprovechamos que el documento está dividido en distintas partes, como el título, el resumen, las conclusiones y otras áreas. Aunque siguen siendo datos no estructurados, dan cierta estructura al texto de entrada. Esta propiedad también nos permite trabajar con fragmentos de texto mas pequeños y, por tanto, comprender mejor el contexto. En este trabajo utilizamos BERT para proponer un pipeline que, dada una publicación, entregue publicaciones relacionadas: artículos científicos que puedan ser de interés para el lector. Para ello, abordamos dos problemas de NLP aplicados a artículos científicos: la clasificación de textos y la similitud entre pares de textos. Las etiquetas para los conjuntos de datos de estos problemas proceden de información jerárquica estructurada provista por los autores. Además, utilizamos la versión base de BERT para comprender el significado semántico de las publicaciones utilizando únicamente la información del resumen y el título, mediante la construcción de modelos para cada tarea. Estos modelos fueron evaluados en términos de precisión, recall y puntuación F1.
  • Thumbnail Image
    Item
    Building a query language for the web of data : efficiency in an open world
    (2015) Ugarte C., Martín I.; Arenas Saavedra, Marcelo Alejandro; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    Al consultar bases de datos incompletas es importante tener la posibilidad de extender los resultados cuando hay información adicional disponible. Esta funcionalidad ha sido ampliamente adoptada para consultar la Web Semántica, dado que la información en la Web es inherentemente incompleta. Desafortunadamente, la implementación de esta funcionalidad en SPARQL, el lenguaje recomendado por el World Wide Web Consotrium (W3C) para consultar datos en la Semantic Web, trae consigo algunos efectos negativos. Dos de los más importantes son un incremento en la complejidad de evaluar consultas, y un conflicto entre SPARQL y el supuesto de mundo abierto. Diferentes caminos han sido tomados para arreglar estos problemas, de los cuales el más adoptado ha sido restringir SPARQL a patrones bien-diseñados. Sin embargo, aun sigue abierto el problema de determinar si éste es el enfoque correcto en términos de complejidad de evaluación y poder expresivo. El punto de partida de esta tesis el estudio de las propiedades fundamentales que debiese satisfacer un lenguaje de consultas para la Web Semántica, en particular considerando que la información es incompleta.Para esto, investigamos las técnicas que han sido desarrolladas en la lógica de primer orden para caracterizar sintácticamente propiedades semánticas. Luego presentamos un marco teórico que nos permite aplicar estas técnicas al caso de SPARQL, definiendo lenguajes que resultan naturales para capturar las propiedades deseadas. También estudiamos las propiedades computacionales de estos lenguajes para entender su aplicabilidad en implementaciones del mundo real. Lo primero que hacemos es mostrar que los enfoques adoptados anteriormente no son suficientes para conciliar la semántica de SPARQL con el hecho de que la información en la Web es incompleta. Luego definimos un nuevo operador para obtener información opcional, el cual nace naturalmente de las técnicas que estudiamos en lógica de primer orden. Este operador nos permite definir fragmentos de SPARQL con buenas propiedades en términos de poder expresivo y complejidad de evaluación. Luego, nos enfocamos en consultas SPARQL de tipo CONSTRUCT, que son aquellas que generan como resultado el mismo tipo de estructuras que reciben como entrada (grafos RDF). Bajo este fragmento somos capaces de definir un lenguaje de consultas que es simple y a la vez captura las nociones semánticas de interés. Por último, mostramos que este lenguaje presenta, sorprendentemente, una menor complejidad de evaluación que los fragmentos que han sido presentados anteriormente.
  • Thumbnail Image
    Item
    Data Exchange Beyond Complete Data
    (2013) Arenas Saavedra, Marcelo Alejandro; Pérez, Jorge; Reutter de la Maza, Juan
  • Thumbnail Image
    Item
    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.
  • No Thumbnail Available
    Item
    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.
  • Thumbnail Image
    Item
    Designing a Query Language for RDF : marrying Open and Closed Worlds
    (2017) Arenas Saavedra, Marcelo Alejandro; Ugarte, M.
  • Thumbnail Image
    Item
    Discovering XSD Keys from XML Data
    (2014) Arenas Saavedra, Marcelo Alejandro; Daenen, J.; Neven, F.; Ugarte C., Martín I.; Van Den, Bussche J.; Vansummeren, S.
  • Thumbnail Image
    Item
    Efficient logspace classes for enumeration, counting and uniform generation
    (2019) Croquevielle Rendic, Luis Alberto; Arenas Saavedra, Marcelo Alejandro; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    In this work, we study two simple yet general complexity classes, based on logspace Turing machines, which provide a unifying framework for efficient query evaluation in areas like information extraction and graph databases, among others. We investigate the complexity of three fundamental algorithmic problems for these classes: enumeration, counting and uniform generation of solutions, and show that they have several desirable properties in this respect. Both complexity classes are defined in terms of non-deterministic logspace transducers (NL-transducers). For the first class, we consider the case of unambiguous NL-transducers, and we prove constant delay enumeration, and both counting and uniform generation of solutions in polynomial time. For the second class, we consider unrestricted NL-transducers, and we obtain polynomial delay enumeration, approximate counting in polynomial time, and polynomial-time randomized algorithms for uniform generation. More specifically, we show that each problem in this second class admits a fully polynomial-time randomized approximation scheme (FPRAS) and a polynomial-time Las Vegas algorithm for uniform generation. Interestingly, the key idea to prove these results is to show that the fundamental problem #NFA admits an FPRAS, where #NFA is the problem of counting the number of strings of length n accepted by a non-deterministic finite automaton (NFA). While this problem is known to be #P-complete and, more precisely, SPANL-complete, it was open whether this problem admits an FPRAS. In this work, we solve this open problem, and obtain as a welcome corollary that every function in SPANL admits an FPRAS.
  • Thumbnail Image
    Item
    Everything you always wanted to know about blank nodes
    (2014) Hogan, A.; Arenas Saavedra, Marcelo Alejandro; Mallea, A; Polleres, A.
  • Thumbnail Image
    Item
    Expressive languages for querying the semantic web
    (2018) Arenas Saavedra, Marcelo Alejandro; Gottlob, Georg; Pieris, Andreas
  • Thumbnail Image
    Item
    Extending query languages for data exchange
    (2009) Reutter de la Maza, Juan; Arenas Saavedra, Marcelo Alejandro; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    El problema del Data Exchange consiste en tomar datos estructurados bajo un esquema fuente y crear una instancia de un esquema destino que refleje lo más adecuadamente posible los datos fuente. La clase de unión de consultas conjuntivas (UCQ) se comporta particularmente bien en el entorno de Data Exchange; sus respuestas certeras se pueden computar en tiempo polinomial (complejidad de datos). Pero esta no es la única clase con esa propiedad: las respuestas certeras para cualquier programa en DATALOG también pueden seer computadas en tiempo polinomial. El problema es que tanto UCQ como DATALOG no permiten la negación de átomos, pues el añadir negación no restringida vuelve intratable el problema.
  • Thumbnail Image
    Item
    Faceted search over RDF-based knowledge graphs
    (2016) Arenas Saavedra, Marcelo Alejandro; Grau, B.; Kharlamov, E.; Marciuska, S.; Zheleznyakov, D.
  • Thumbnail Image
    Item
    Federating queries in SPARQL 1.1 : Syntax, semantics and evaluation
    (2013) Buil Aranda, Carlos; Arenas Saavedra, Marcelo Alejandro; Corcho, Oscar; Polleres, Axel
  • Thumbnail Image
    Item
    First-Order and Temporal Logics for Nested Words
    (IEEE, 2007) Alur, R.; Arenas Saavedra, Marcelo Alejandro; Barcelo, P.; Etessami, K.; Immerman, N.; Libkin, L.
    Nested words are a structured model of execution paths in procedural programs, reflecting their call and return nesting structure. Finite nested words also capture the structure of parse trees and other tree-structured data, such as XML. We provide new temporal logics for finite and infinite nested words, which are natural extensions of LTL, and prove that these logics are first-order expressively- complete. One of them is based on adding a "within" modality, evaluating a formula on a subword, to a logic CaRet previously studied in the context of verifying properties of recursive state machines. The other logic is based on the notion of a summary path that combines the linear and nesting structures. For that logic, both model-checking and satisfiability are shown to be EXPTIME-complete. Finally, we prove that first-order logic over nested words has the three-variable property, and we present a temporal logic for nested words which is complete for the two- variable fragment of first-order.
  • No Thumbnail Available
    Item
    Foreword: Special Issue on Database Theory
    (2017) Arenas Saavedra, Marcelo Alejandro
  • Thumbnail Image
    Item
    Foundations of Modern Query Languages for Graph Databases
    (2017) Angles, R.; Arenas Saavedra, Marcelo Alejandro; Barceló Baeza, Pablo; Hogan, A.; Reutter de la Maza, Juan; Vrgoc, Domagoj
  • No Thumbnail Available
    Item
    Graph path navigation
    (2019) Arenas Saavedra, Marcelo Alejandro; Barceló, Pablo; Libkin, Leonid; Sakr, Sherif; Zomaya, Albert Y.