16 citations · 48 across the 14 of their papers we have counts for
22 papers
Query Answering under Volume-Based Diversity Functions
Marcelo Arenas, Timo Camillo Merkl, Reinhard Pichler +1
When query evaluation produces too many tuples, a new approach in query answering is to retrieve a diverse subset of them. The standard approach for measuring the diversity of a se…
Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue
Marcelo Arenas, Timo Camillo Merkl, Reinhard Pichler +1
The set of answers to a query may be very large, potentially overwhelming users when presented with the entire set. In such cases, presenting only a small subset of the answers to…
Constant-delay enumeration for SLP-compressed documents
Martín Muñoz, Cristian Riveros
We study the problem of enumerating results from a query over a compressed document. The model we use for compression are straight-line programs (SLPs), which are defined by a cont…
Probabilistic Automata of Bounded Ambiguity
Nathanaël Fijalkow, Cristian Riveros, James Worrell
Probabilistic automata are an extension of nondeterministic finite automata in which transitions are annotated with probabilities. Despite its simplicity, this model is very expres…
Efficient Enumeration Algorithms for Annotated Grammars
Antoine Amarilli, Louis Jachiet, Martín Muñoz +1
We introduce annotated grammars, an extension of context-free grammars which allows annotations on terminals. Our model extends the standard notion of regular spanners, and is more…
How do centrality measures choose the root of trees?
Cristian Riveros, Jorge Salas, Oskar Skibski
Centrality measures are widely used to assign importance to graph-structured data. Recently, understanding the principles of such measures has attracted a lot of attention. Given t…
MillenniumDB: A Persistent, Open-Source, Graph Database
Domagoj Vrgoc, Carlos Rojas, Renzo Angles +7
In this systems paper, we present MillenniumDB: a novel graph database engine that is modular, persistent, and open source. MillenniumDB is based on a graph data model, which we ca…
CORE: a Complex Event Recognition Engine
Marco Bucchi, Alejandro Grez, Andrés Quintana +2
Complex Event Recognition (CER) systems are a prominent technology for finding user-defined query patterns over large data streams in real time. CER query evaluation is known to be…
Expressive power of linear algebra query languages
Floris Geerts, Thomas Muñoz, Cristian Riveros +1
Linear algebra algorithms often require some sort of iteration or recursion as is illustrated by standard algorithms for Gaussian elimination, matrix inversion, and transitive clos…
Ranked enumeration of MSO logic on words
Pierre Bourhis, Alejandro Grez, Louis Jachiet +1
In the last years, enumeration algorithms with bounded delay have attracted a lot of attention for several data management tasks. Given a query and the data, the task is to preproc…
Streaming enumeration on nested documents
Martín Muñoz, Cristian Riveros
Some of the most relevant document schemas used online, such as XML and JSON, have a nested format. In the last decade, the task of extracting data from nested documents over strea…
When is Approximate Counting for Conjunctive Queries Tractable?
Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram +1
Conjunctive queries are one of the most common class of queries used in database systems, and the best studied in the literature. A seminal result of Grohe, Schwentick, and Segoufi…
The monitoring problem for timed automata
Alejandro Grez, Filip Mazowiecki, Michał Pilipczuk +2
We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so under a…
Pumping lemmas for weighted automata
Agnishom Chattopadhyay, Filip Mazowiecki, Anca Muscholl +1
We present pumping lemmas for five classes of functions definable by fragments of weighted automata over the min-plus semiring, the max-plus semiring and the semiring of natural nu…
$\text{#NFA}$ admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes
Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram +1
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…
Descriptive Complexity for Counting Complexity Classes
Marcelo Arenas, Martin Muñoz, Cristian Riveros
Descriptive Complexity has been very successful in characterizing complexity classes of decision problems in terms of the properties definable in some logics. However, descriptive…
Constant delay algorithms for regular document spanners
Fernando Florenzano, Cristian Riveros, Martin Ugarte +2
Regular expressions and automata models with capture variables are core tools in rule-based information extraction. These formalisms, also called regular document spanners, use reg…
A Second-Order Approach to Complex Event Recognition
Alejandro Grez, Cristian Riveros, Martin Ugarte +1
Complex Event Recognition (CER for short) refers to the activity of detecting patterns in streams of continuously arriving data. This field has been traditionally approached from a…
Foundations of Complex Event Processing
Marco Bucchi, Alejandro Grez, Cristian Riveros +1
Complex Event Processing (CEP) has emerged as the unifying field for technologies that require processing and correlating distributed data sources in real-time. CEP finds applicati…
Document Spanners for Extracting Incomplete Information: Expressiveness and Complexity
Francisco Maturana, Cristian Riveros, Domagoj Vrgoč
Rule-based information extraction has lately received a fair amount of attention from the database community, with several languages appearing in the last few years. Although infor…
Copyless Cost-Register Automata: Structure, Expressiveness, and Closure Properties
Filip Mazowiecki, Cristian Riveros
Cost register automata (CRA) and its subclass, copyless CRA, were recently proposed by Alur et al. as a new model for computing functions over strings. We study some structural pro…
Composition and Inversion of Schema Mappings
Marcelo Arenas, Jorge Perez, Juan Reutter +1
In the recent years, a lot of attention has been paid to the development of solid foundations for the composition and inversion of schema mappings. In this paper, we review the pro…