DSpace Angular :: Browsing by Author "Reutter de la Maza, Juan"

Browsing by Author "Reutter de la Maza, Juan"

Now showing 1 - 20 of 23

Bitcoin price prediction through stimulus analysis : on the footprints of twitter's crypto-influencers
(2021) Cheuque Cerda, Germán Alfredo; Reutter de la Maza, Juan; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
El lanzamiento del protocolo de Bitcoin y su subyacente cripto moneda, han comenzado a dar forma a la manera en que vemos las monedas digitales, abriendo una gran lista de nuevos e interesantes desafíos. Entre ellos, nos centramos en el objetivo de investigar cómo se ve afectado el precio de las monedas digitales. Lo cual por cierto, es una pregunta natural, especialmente cuando consideramos la montaña rusa de precios que presenciamos para Bitcoin entre 2017 y 2018. En esta investigación trabajaremos bajo la hipótesis de que el precio se ve afectado por la huella digital de personas influyentes. Nos referiremos a ellos como criptoinfluencers. En esta investigación proporcionamos modelos basados en aprendizaje automático (redes neuronales y árboles aleatorios de decisión) para predecir el precio del bitcoin. Comparamos lo que sucede cuando estos modelos se alimentan solo con el historial de precios reciente versus lo que sucede cuando se alimenta adicionalmente con información textual codificada obtenida desde estos usuarios influyentes a partir de sus opiniones. De acuerdo a nuestros resultados, mostramos que los humanos tienen un desempeño promedio al interpretar opiniones referentes a Bitcoin de un 75%. Por esta razón y para aumentar nuestras posibilidades, hemos explorado siete modelos entrenados para codificar este tipo de información, incluyendo dos de los modelos más recientes en técnicas de transferencia inductiva del aprendizajes: ULMFit y BERT. Mostramos evidencia preliminar de que los datos de Twitter deberían ayudar a predecir el precio de bitcoin al ser capaz de respaldar el proceso de decisión en la tarea de predecir el precio de Bitcoin un día en el futuro. Logramos hacer que nuestros modelos pasaran de proyectar el precio actual hacia el futuro como la única y mejor predicción, a hacer unas más realistas, cosa que solo podemos atribuir a la introducción de un estímulo externo al precio y al proceso de selección de variables. Para desafiar nuestros modelos, exploramos la tarea de simulación de precios. Nuestros resultados no fueron concluyentes en este aspecto, ya que tenemos modelos que muestran diferentes niveles de rendimiento en diferentes lapsos de tiempo hacia el futuro. Sin embargo, estos resultados en general no muestran consciencia a cambios de precio más allá de una semana de iniciada la simulación. Nuestro mejor modelo genera predicciones siendo respaldado por la opinión de estos usuarios influyentes, pero es una predicción con un error aceptable hasta una ventana futura máxima de solo un día. La evidencia reciente muestra que el comportamiento de alta variabilidad de Bitcoin está sucediendo nuevamente. Para febrero de 2021, Bitcoin alcanzó un nuevo máximo histórico de casi 57000 USD, lo que es evidencia de cuán volátil es el comportamiento de este cripto-activo.
Complexity of answering counting aggregate queries over DL-Lite
(2015) Kostylev, Egor V.; Reutter de la Maza, Juan
Containment of queries for graphs with data
(2018) Kostylev, Egor V.; Reutter de la Maza, Juan; Vrgoc, Domagoj
Data Exchange Beyond Complete Data
(2013) Arenas Saavedra, Marcelo Alejandro; Pérez, Jorge; Reutter de la Maza, Juan
Efficient processing of recursive and federated queries in SPARQL
(2021) Soto Suárez, Adrián Andrés; Reutter de la Maza, Juan; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Han pasado décadas desde los primeros pasos de la Web Semántica, y si bien, los avances han sido considerables, aún hay espacio para mejorar. En esta tesis discutimos una forma de extender SPARQL con funcionalidades recursivas, con el fin de extender el poder expresivo del lenguaje, pero también abarcar casos de uso que aún no están cubiertos. Además proponemos nuevos algoritmos que nos permiten evaluar las funcionalidades recursivas y las consultas generales de SPARQL de forma más eficiente, tanto en entornos locales como distribuidos en la web. Este trabajo se abre con la presentación de SPARQL Recursivo, una extensión al lenguaje basado en uno perador de punto fijo. Luego definimos un fragmento de este lenguaje, que es menos expresivo pero puede ser evaluado de forma más eficiente. Después mostramos cómo la idea de lenguajes recursivos puede ser utilizada para computar procedimientos de analítica de grafos con SPARQL, estudiando qué otros operadores necesita el lenguaje para llevar acabo esta tarea. Así, proponemos el lenguaje SPARQAL, para hacer analítica de grafos dentro de bases de datos RDF. Sin embargo, el desarrollo de estas extensiones produce una sobrecarga del motor de consultas, por la cantidad de Basic Graph Patterns que hay que resolver. Por esta razón es que buscamos técnicas para proponer nuevos algoritmos de evaluación para este fragmento de SPARQL. Nuestras técnicas están basadas en los algoritmos de join Worst-case optimal, una nueva familia de algoritmos con buenas propiedades teóricas. De esta forma diseñamos e implementamos un algoritmo basado en el LeapfrogTriejoin que, según lo que muestran nuestros experimentos, resuelve los patrones de grafos de forma mucho más eficiente. Luego de esto, buscamos entender cómo estas técnicas de join pueden ser extendidas para entornos Web distribuidos y cómo nos pueden ayudar a integrar datos que actualmente no son accesibles para la Web Semántica.
Excalibur key-generation protocols for dag hierarchic decryption
(2019) Monsalve Santander, Geraldine; Reutter de la Maza, Juan; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Aplicaciones criptográficas de llave pública usualmente requieren estructurar privilegios de desencriptación acorde a alguna jerarquía. Para evitar filtraciones y transferencias de las llaves secretas, usualmente esto se resuelve mediante procesos de re-rencriptación o recurriendo a entidades confiables. En un enfoque inicial Goubin y Vial-Prado aprovechan el esquema de encriptación multillave FHE-NTRU para proponer los protocolos Excalibur. Estos protocolos definen privilegios de desencriptación al momento de la creación de llaves, evitando filtraciones de cada uno de los secretos involucrados, incluso por parte de quien posee la llave poderosa, i.e. los privilegios de desencriptación. Los algoritmos se definen para escenarios con dos participantes, y se extienden para cadenas de participantes con privilegios de desencriptación heredables. En esta tesis proponemos nuevos protocolos para la generación de llaves Excalibur, en un escenario de jerarquía DAG, extendiendo así el trabajo previo de Goubin y Vial-Prado. Además, se presentan demostraciones formales de seguridad en presencia de adversarios semi-honestos, donde el caso base de nuestras demostraciones de seguridad pueden considerarse como una prueba basada en simulación más formal del trabajo anteriormente mencionado. Finalmente, nuestros protocolos son compatibles con las propiedades homomórficas del esquema FHE-NTRU.
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.
Formal specification, expressiveness and complexity analysis for JSON schema
(2016) Suárez Barría, Fernando; Reutter de la Maza, Juan; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
JSON es hoy en día el formato más popular para el traspaso de datos en la web. Sin embargo, todavía carece de un esquema estandarizado que permita a desarrolladores especificar la estructura estos documentos. JSON Schema es una propuesta para definir metadata a través de esquemas para documentos JSON. Sin embargo, todavía está en una etapa de madurez muy temprana, y no existe una especificación formal que capture al lenguaje en su totalidad. En esta tesis se lleva a cabo el primer análisis formal de documentos JSON Schema. En primer lugar, se propone una definición formal tanto de la sintaxis como de la semántica para la validación de estos documentos. Luego, en base a esta definición, se procede a capturar el poder expresivo del lenguaje. Por un lado, se demuestra que JSON Schema puede simular autómatas de árbol, con el sólo uso de un subconjunto muy restringido de la especificación. Por otro lado, se muestra que JSON Schema puede ser capturado por lógica monádica de segundo orden sobre árboles.Finalmente, se analiza la complejidad computacional de los principales problemas de decisión presentes en el contexto esquemas para lenguajes formales, el problema de validación y el problema de satisfacibilidad para documentos JSON Schema. Estos problemas resultan de gran importancia en el desarrollo de algoritmos eficientes para el traspaso de datos en la web. Por un lado, se muestra que el problema de validación puede ser resuelto de manera eficiente para esquemas fijos. Sin embargo, en términos de complejidad combinada el problema resulta ser inherentemente secuencial. Por otro lado, se propone un algoritmo exponencial para resolver el problema de satisfacibilidad. Además, se demuestra que este problema no puede ser computado con una mejor cota que la obtenida.
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
Identifiability of JSON schema from positive examples.
(2018) Castro Retamal, Jaime Esteban; Reutter de la Maza, Juan; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
JSON (JavaScript Object Notation) es probablemente el formato de datos más usado para hacer requests u obtener responses desde APIs. A pesar de la existencia de JSON Schema, un estándar para definir la estructura de documentos tipo JSON, la gran mayoría de la documentación de APIs se basa solamente en ejemplos donde no están claros los casos bordes que pueden existir. En esta situación, los desarrolladores deben dilucidar por ellos mismos si es posible recibir valores nulos o si existen datos opcionales. Al mismo tiempo, los programadores no pueden aprovechar los beneficios de tener un esquema de datos explícito, como por ejemplo, la posibilidad de efectuar una validación de datos, la creación de ejemplos automática para realizar testing, autocompletado en IDEs, entre otros. El problema se hace más evidente si se toma en cuenta la fragilidad de las implementaciones cuando se hacen cambios pequeños en el formato de las requests o responses. En primer lugar, se analizan los límites teóricos de la inferencia de JSON Schema a partir de ejemplos. Para ello se selecciona un marco teórico sobre el cual se crean las definiciones y se presentan los resultados. Luego, en base a este marco teórico, se analiza la factibilidad de aprender distintas clases de JSON Schema y se identifican aquellas que tienen buenos resultados. Después, se examina uno de los pocos repositorios con esquemas JSON para entender cómo se usa la especificación en la práctica. Con esos antecedentes se propone un conjunto de características que se pueden inferir a partir de ejemplos bajo el marco teórico seleccionado. Además, se entrega un algoritmo para realizar la tarea de aprendizaje de esquemas. Finalmente, se muestran resultados de aplicar el algoritmo sobre tres conjuntos de ejemplos provenientes de Open Weather Map, Git Hub, y Twitter.
JSON : Data model and query languages
(2020) Bourhis, P.; Reutter de la Maza, Juan; Vrgoc, Domagoj
Querying APIs with SPARQL: language and worst-case optimal algorithms
(2018) Mosser, Matthieu; Pieressa, Fernando; Reutter de la Maza, Juan; Soto Suárez, Adrián Andrés; Vrgoč, Domagoj; Gangemi, Aldo; Navigli, Roberto; Vidal, Maria-Esther; Hitzler, Pascal; Troncy, Raphaël; Hollink, Laura; Tordai, Anna; Alam, Mehwish
Regular Queries on Graph Databases
(2017) Reutter de la Maza, Juan; Romero, Miguel; Vardi, Moshe Y.
Semantics and complexity of bitcoin script
(2021) Reisenegger Butrón, Thomas; Reutter de la Maza, Juan; Arenas Saavedra, Marcelo Alejandro; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Con la creciente popularidad de Bitcoin ha surgido la necesidad de entender las funcionalidades, la seguridad y el rendimiento de los distintos mecanismos que componen su protocolo. El lenguaje de programación asociado a Bitcoin, Script, es uno de los principales componentes de las transacciones de Bitcoin. Este fue diseñado deliberadamente para no ser Turing completo, de forma que no fuera posible crear ejecuciones sin fin. Sin embargo, no existen muchos estudios dedicados a analizar las propiedades y limitaciones del lenguaje. Es más, no existe un marco de referencia formal que permita analizar estas características. En este trabajo buscamos proveer este marco de referencia, que permita estudiar Script y analizar ciertos problemas relacionados al lenguaje. Concretamente, definiremos formalmente la semántica de Script y estudiaremos el problema de determinar si un programa definido por un usuario está bien formado, es decir, si puede ser desbloqueado o presenta errores que impiden que esto ocurra. Específicamente, demostraremos que este problema es NP-duro, proveyendo una reducción desde programación lineal entera, y que, para el conjunto más relevante de operadores, si establecemos ciertas suposiciones razonables sobre el uso del lenguaje, el problema se encuentra en NP.
Semantics and validation of recursive SHACL
(Springer Verlag, 2018) Corman, Julien; Reutter de la Maza, Juan; Savković, Ognjen
With the popularity of RDF as an independent data model came the need for specifying constraints on RDF graphs, and for mechanisms to detect violations of such constraints. One of the most promising schema languages for RDF is SHACL, a recent W3C recommendation. Unfortunately, the specification of SHACL leaves open the problem of validation against recursive constraints. This omission is important because SHACL by design favors constraints that reference other ones, which in practice may easily yield reference cycles. In this paper, we propose a concise formal semantics for the so-called “core constraint components” of SHACL. This semantics handles arbitrary recursion, while being compliant with the current standard. Graph validation is based on the existence of an assignment of SHACL “shapes” to nodes in the graph under validation, stating which shapes are verified or violated, while verifying the targets of the validation process. We show in particular that the design of SHACL forces us to consider cases in which these assignments are partial, or, in other words, where the truth value of a constraint at some nodes of a graph may be left unknown. Dealing with recursion also comes at a price, as validating an RDF graph against SHACL constraints is NP-hard in the size of the graph, and this lower bound still holds for constraints with stratified negation. Therefore we also propose a tractable approximation to the validation problem.
Speeding up Monero’s balance computation
(2021) Herrera Sufán, Raimundo; Reutter de la Maza, Juan; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Las criptomonedas se han establecido como activos digitales relevantes que apuntan a convertirse en el medio de intercambio principal en las proximas décadas. Con la rápida adopción y gran número de usuarios, la usabilidad y privacidad se han convertido en aspectos críticos para su éxito. Monero es una moneda digital que ofrece propiedades requeridas por cualquier activo que pretende ser considerado un reemplazo viable del dinero, especialmente respecto a la privacidad y seguridad. Sin embargo, para ofrecer esas características, Monero compromete la usabilidad de ciertas operaciones de uso diario, como el cálculo del balance de un usuario. Esta operación en particular es lenta debido a que para realizarla es necesario escanear la totalidad del blockchain de Monero. En este trabajo, presentamos diversas formas en las que disminuir el tiempo que toma el cálculo del balance, comprometiendo mínimamente elementos privados no críticos. Específicamente, introducimos un procedimiento para generar múltiples transacciones de consolidación que permiten a los usuarios evitar escaneos completos del blockchain cada vez que necesiten obtener su balance, reduciendo significativamente los tiempos de la operación gastando mínimas cantidades de dinero. Además proporcionamos esquemas que usan técnicas de indexación para obtener el historial de transacciones de un usuario en menos tiempo y que por lo tanto posibilitan realizar el cálculo de balance más rápido, solamente revelando la cantidad de dichas transacciones a observadores externos. Finalmente mostramos cómo aprovechar las propuestas a traves de la descripción de servicios y billeteras manejadas por terceros que ayudan al usuario a ahorrarse parte del calculo del balance de forma segura. A lo largo de todo nuestro trabajo, discutimos las concesiones incurridas al modificar el estado actual del protocolo de Monero e incorporar nuestras mejoras, dado que apuntamos a mantener la mayor parte de las garantías de privacidad mientras ofrecemos mejoras en usabilidad.
Static analysis of navigational XPath over graph databases
(2016) Kostylev, Egor V.; Reutter de la Maza, Juan; Vrgoc, Domagoj
The expressiveness of SHACL and a tractable language fragment proposal.
(2020) Florenzano Hernández, Fernando Alberto; Reutter de la Maza, Juan; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
SHACL (Shapes Constraint Language) es una especificación para describir y validar grafos RDF que recientemente se convirtió en recomendación de la W3C. La dificultad principal que presenta su uso es la ausencia de una definición oficial para el manejo de restricciones recursivas. Además, el hecho de que grafos RDF por lo general son accesibles mediante alojamiento remoto a través de solo consultas SPARQL hace que la validación dependa de dichos sistemas. En esta tesis, extendemos trabajo previo con el objetivo de mejorar el entendimiento de lo conocido del problema de validación. Primero, investigamos la posibilidad de validar un grafo contra esquemas no recursivos utilizando solo procesamiento en memoria, y mediante el procesamiento de una única consulta general. Para el caso recursivo, cuyo problema es NP-duro, revisamos la jerarquía de fragmentos de SHACL conocidos y sus respectivas dificultades. Finalmente, proponemos un nuevo fragmento de restricciones y mostramos un algoritmo que resuelve eficientemente el problema de validación. Este último se puede utilizar cuando es necesario manejar restricciones recursivas, pero manteniendo cotas de ejecución eficientes sin tener que recurrir a maquinaria externa.
The Ring: Worst-case Optimal Joins in Graph Databases using (Almost) No Extra Space
(2024) Arroyuelo Billiardi, Diego Gastón; Gómez-Brandón, Adrián; Hogan, Aidan; Navarro, Gonzalo; Reutter de la Maza, Juan; Rojas-Ledesma, Javiel; Soto, Adrián
We present an indexing scheme for triple-based graphs that supports join queries in worst-case optimal (wco) time within compact space. This scheme, called a ring, regards each triple as a cyclic string of length 3. Each rotation of the triples is lexicographically sorted and the values of the last attribute are stored as a column, so we obtain the order of the next column by stably re-sorting the triples by its attribute. We show that, by representing the columns with a compact data structure called a wavelet tree, this ordering enables forward and backward navigation between columns without needing pointers. These wavelet trees further support wco join algorithms and cardinality estimations for query planning. While traditional data structures such as B-Trees, tries, and so on, require 6 index orders to support all possible wco joins over triples, we can use one ring to index them all. This ring replaces the graph and uses only sublinear extra space, thus supporting wco joins in almost no space beyond storing the graph itself. Experiments querying a large graph (Wikidata) in memory show that the ring offers nearly the best overall query times while using only a small fraction of the space required by several state-of-the-art approaches. We then turn our attention to some theoretical results for indexing tables of arity d higher than 3 in such a way that supports wco joins. While a single ring of length d no longer suffices to cover all d! orders, we need much fewer rings to index them all: O(2d) rings with a small constant. For example, we need 5 rings instead of 120 orders for d=5. We show that our rings become a particular case of what we dub order graphs, whose nodes are attribute orders and where stably sorting by some attribute leads us from an order to another, thereby inducing an edge labeled by the attribute. The index is then the set of columns associated with the edges, and a set of rings is just one possible graph shape. We show that other shapes, like for example a single ring instead of several ones of length d, can lead us to even smaller indexes, and that other more general shapes are also possible. For example, we handle d=5 attributes within space equivalent to 4 rings.
Trial: A Navigational Algebra for RDF Triplestores
(2018) Libkin, Leonid; Reutter de la Maza, Juan; Soto Suárez, Adrián Andrés; Vrgoc, Domagoj

Browsing by Author "Reutter de la Maza, Juan"

Results Per Page

Sort Options