Author name cluster

Luís M.S. Russo

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

1 author row

I&C Journal 2022 Journal Article

A practical succinct dynamic graph representation

Miguel E. Coimbra
Joana Hrotkó
Alexandre P. Francisco
Luís M.S. Russo
Guillermo de Bernardo
Susana Ladra
Gonzalo Navarro

We address the problem of representing dynamic graphs using k 2 -trees. The k 2 -tree data structure is one of the succinct data structures proposed for representing static graphs, and binary relations in general. It relies on compact representations of bit vectors. Hence, by relying on compact representations of dynamic bit vectors, we can also represent dynamic graphs. However, this approach suffers of a well known bottleneck in compressed dynamic indexing. In this paper we present a k 2 -tree based implementation which follows instead the ideas by Munro et al. (PODS 2015) to circumvent this bottleneck. We present two dynamic graph k 2 -tree implementations, one as a standalone implementation and another as a C++ library. The library includes efficient edge and neighbourhood iterators, as well as some illustrative algorithms. Our experimental results show that these implementations are competitive in practice.

Details DOI

I&C Journal 2022 Journal Article

Order-preserving pattern matching indeterminate strings

Luís M.S. Russo
Diogo Costa
Rui Henriques
Hideo Bannai
Alexandre P. Francisco

Given a pattern p of size m and a text t, the problem of order-preserving pattern matching (OPPM) is to find all substrings of t that satisfy one of the orderings defined by p. This problem has applications on time series analysis. However given its strict nature this model is unable to deal with indetermination, thus limiting its application to noisy time series. In this paper we introduce indeterminate characters to alleviate this limitation. We then propose two polynomial time algorithms. If the indetermination is limited to p confirming one occurrence can be computed in O ( r m lg ⁡ r ) time, where r is a bound on the number of uncertain characters per position. If the indetermination alternates, but does not occur at the same position in t and p, we present an algorithm that requires O ( r m ( m + log ⁡ r ) ) time. We also show that the general problem is NP-hard and provide a polynomial size boolean formula.

Details DOI

TCS Journal 2022 Journal Article

Range minimum queries in minimal space

Luís M.S. Russo

We consider the problem of computing a sequence of range minimum queries. We assume a sequence of commands that contains values and queries. Our goal is to quickly determine the minimum value that exists between the current position and a previous position i. Range minimum queries are used as a sub-routine of several algorithms, namely related to string processing. We propose a data structure that can process these command sequences. We obtain efficient results for several variations of the problem, in particular we obtain O ( 1 ) time per command for the offline version and O ( α ( n ) ) amortized time for the online version, where α ( n ) is the inverse Ackermann function and n the number of values in the sequence. This data structure also has very small space requirements, namely O ( ℓ ) where ℓ is the maximum number of active i positions. We implemented our data structure and show that it is competitive against existing alternatives. We obtain comparable processing time, in the nanosecond range, and much smaller space requirements.

Details DOI

TCS Journal 2020 Journal Article

Cartesian and Lyndon trees

Maxime Crochemore
Luís M.S. Russo

The article describes the structural and algorithmic relations between Cartesian trees and Lyndon trees. This leads to a uniform presentation of the Lyndon table of a word corresponding to the Next Nearest Smaller table of a sequence of numbers. It shows how to efficiently compute runs, that is, maximal periodicities occurring in a word.

Details DOI

TCS Journal 2019 Journal Article

A study on splay trees

Luís M.S. Russo

We study the dynamic optimality conjecture, which predicts that splay trees are a form of universally efficient binary search tree, for any access sequence. We reduce this claim to a regular access bound, which seems plausible and might be easier to prove. This approach may be useful to establish dynamic optimality.

Details DOI

TCS Journal 2013 Journal Article

Space-efficient data-analysis queries on grids

Gonzalo Navarro
Yakov Nekrich
Luís M.S. Russo

We consider various data-analysis queries on two-dimensional points. We give new space/time tradeoffs over previous work on geometric queries such as dominance and rectangle visibility, and on semigroup and group queries such as sum, average, variance, minimum and maximum. We also introduce new solutions to queries less frequently considered in the literature such as two-dimensional quantiles, majorities, successor/predecessor, mode, and various top- k queries, considering static and dynamic scenarios.

Details DOI

TCS Journal 2012 Journal Article

Monge properties of sequence alignment

Luís M.S. Russo

Alignment is an important sequence comparison measure. Algorithms that compute alignments have a wide range of applications, namely in bioinformatic tools. Alignments can be computed as maximum scoring paths in Alignment DAGs. In this paper we study the properties of matrices that contain alignment scores between a string and all the sub-strings of another string. We focus on the fact that these matrices have the Monge property and are sparse in some sense. Related studies were recently presented for HSM and DIST matrices, leading to O ( n log n ) procedure for multiplying those matrices, where O ( n ) bounds the sizes of the strings. Our results strictly generalize previous solutions. We measure the sparseness of the matrices with variable δ and present an algorithm for matrix multiplication in O ( ( n + δ ) log 3 ( n + δ ) ) time, which we improve to O ( ( n + δ ) log 2 ( n + δ ) ), within the same space. We discuss applications of this algorithm, namely fully incremental alignment and alignment update. We study, experimentally, the performance of the methods we propose.

Details DOI