Roberto Grossi

I&C Journal 2020 Journal Article

Large-scale clique cover of real-world networks

• Alessio Conte
• Roberto Grossi
• Andrea Marino

The edge clique cover (ecc ) problem deals with discovering a set of (possibly overlapping) cliques in a given graph that covers each of the graph's edges. This problem finds applications ranging from social networks to compiler optimization and stringology. We consider several variants of the ecc problem, using classical quality measures (like the number of cliques) and new ones. We describe efficient heuristic algorithms, the fastest one taking O ( m d G ) time for a graph with m edges, degeneracy d G (also known as k-core number). For large real-world networks with millions of nodes, like social networks, an algorithm should have (almost) linear running time to be practical: Our algorithm for finding eccs of large networks has linear-time performance in practice because d G is small, as our experiments show, on real-world networks with thousands to several million nodes.

TCS Journal 2020 Journal Article

Longest property-preserved common factor: A new string-processing framework

• Lorraine A.K. Ayad
• Giulia Bernardini
• Roberto Grossi
• Costas S. Iliopoulos
• Nadia Pisanti
• Solon P. Pissis
• Giovanna Rosone

We introduce a new family of string processing problems. Given two or more strings, we are asked to compute a factor common to all strings that preserves a specific property and has maximal length. We consider three fundamental string properties: square-free factors, periodic factors, and palindromic factors under three different settings, one per property. In the first setting, we are given a string x and we are asked to construct a data structure over x answering the following type of online queries: given a string y, find a longest square-free factor common to x and y. In the second setting, we are given k strings and an integer 1 < k ′ ≤ k and we are asked to find a longest periodic factor common to at least k ′ strings. In the third one, we are given two strings and we are asked to find a longest palindromic factor common to the two strings. We present linear-time solutions for all settings. This is a full and extended version of a paper from SPIRE 2018.

MFCS Conference 2019 Conference Paper

Listing Induced Steiner Subgraphs as a Compact Way to Discover Steiner Trees in Graphs

• Alessio Conte
• Roberto Grossi
• Mamadou Moustapha Kanté
• Andrea Marino 0001
• Takeaki Uno
• Kunihiro Wasa

This paper investigates induced Steiner subgraphs as a variant of the classical Steiner trees, so as to compactly represent the (exponentially many) Steiner trees sharing the same underlying induced subgraph. We prove that the enumeration of all (inclusion-minimal) induced Steiner subgraphs is harder than the well-known Hypergraph Transversal enumeration problem if the number of terminals is not fixed. When the number of terminals is fixed, we propose a polynomial delay algorithm for listing all induced Steiner subgraphs of minimum size. We also propose a polynomial delay algorithm for listing the set of minimal induced Steiner subgraphs when the number of terminals is 3.

MFCS Conference 2018 Conference Paper

Listing Subgraphs by Cartesian Decomposition

• Alessio Conte
• Roberto Grossi
• Andrea Marino 0001
• Romeo Rizzi
• Luca Versari

We investigate a decomposition technique for listing problems in graphs and set systems. It is based on the Cartesian product of some iterators, which list the solutions of simpler problems. Our ideas applies to several problems, and we illustrate one of them in depth, namely, listing all minimum spanning trees of a weighted graph G. Here iterators over the spanning trees for unweighted graphs can be obtained by a suitable modification of the listing algorithm by [Shioura et al. , SICOMP 1997], and the decomposition of G is obtained by suitably partitioning its edges according to their weights. By combining these iterators in a Cartesian product scheme that employs Gray coding, we give the first algorithm which lists all minimum spanning trees of G in constant delay, where the delay is the time elapsed between any two consecutive outputs. Our solution requires polynomial preprocessing time and uses polynomial space.

TCS Journal 2018 Journal Article

Motif trie: An efficient text index for pattern discovery with don't cares

• Roberto Grossi
• Giulia Menconi
• Nadia Pisanti
• Roberto Trani
• Søren Vind

We introduce the motif trie data structure, which has applications in pattern matching and discovery in genomic analysis, plagiarism detection, data mining, intrusion detection, spam fighting and time series analysis, to name a few. Here the extraction of recurring patterns in sequential and textual data is one of the main computational bottlenecks. For this, we address the problem of extracting maximal patterns with at most k don't care symbols and at least q occurrences, according to a maximality notion we define. We apply the motif trie to this problem, also showing how to build it efficiently. As a result, we give the first algorithm that attains a stronger notion of output-sensitivity, where the cost for an input sequence of n symbols is proportional to the actual number of occurrences of each pattern, which is at most n (much smaller in practice). This avoids the best-known cost of O ( n c ) per pattern, for constant c > 1, which is otherwise impractical for massive sequences with large n.

TCS Journal 2016 Journal Article

Linear-size suffix tries

• Maxime Crochemore
• Chiara Epifanio
• Roberto Grossi
• Filippo Mignosi

Suffix trees are highly regarded data structures for text indexing and string algorithms [MCreight 76, Weiner 73]. For any given string w of length n = | w |, a suffix tree for w takes O ( n ) nodes and links. It is often presented as a compacted version of a suffix trie for w, where the latter is the trie (or digital search tree) built on the suffixes of w. Here the compaction process replaces each maximal chain of unary nodes with a single arc. For this, the suffix tree requires that the labels of its arcs are substrings encoded as pointers to w (or equivalent information). On the contrary, the arcs of the suffix trie are labeled by single symbols but there can be Θ ( n 2 ) nodes and links for suffix tries in the worst case because of their unary nodes. It is an interesting question if the suffix trie can be stored using O ( n ) nodes. We present the linear-size suffix trie, which guarantees O ( n ) nodes. We use a new technique for reducing the number of unary nodes to O ( n ), that stems from some results on antidictionaries. For instance, by using the linear-size suffix trie, we are able to check whether a pattern p of length m = | p | occurs in w in O ( m log ⁡ | Σ | ) time and we can find the longest common substring of two strings w 1 and w 2 in O ( ( | w 1 | + | w 2 | ) log ⁡ | Σ | ) time for an alphabet Σ.

SODA Conference 2016 Conference Paper

New Bounds for Approximating Extremal Distances in Undirected Graphs

• Massimo Cairo
• Roberto Grossi
• Romeo Rizzi

We provide new bounds for the approximation of extremal distances (the diameter, the radius, and the eccentricities of all nodes) of an undirected graph with n nodes and m edges. First, we show under the Strong Exponential Time Hypothesis (SETH) of Impagliazzo, Paturi and Zane [JCSS01] that it is impossible to get a (3/2 – ∊ )-approximation of the diameter or a (5/3 – ∊ )-approximation of all the eccentricities in O ( m 2– δ ) time for any ∊, δ > 0, even allowing for a constant additive term in the approximation. Second, we present an algorithmic scheme that gives a (2 – 1/2 k )-approximation of the diameter and the radius and a (3 – 4/(2 k + 1))-approximation of all eccentricities in expected time for any k ≥ 0. For k ≥ 2, this gives a family of previously unknown bounds, and approaches near-linear running time as k grows. Third, we observe a connection between the approximation of the diameter and the h -dominating sets, which are subsets of nodes at distance ≤ h from every other node. We give bounds for the size of these sets, related with the diameter.

TCS Journal 2014 Journal Article

Towards optimal packed string matching

• Oren Ben-Kiki
• Philip Bille
• Dany Breslauer
• Leszek Ga̧sieniec
• Roberto Grossi
• Oren Weimann

In the packed string matching problem, it is assumed that each machine word can accommodate up to α characters, thus an n-character string occupies n / α memory words. (a) We extend the Crochemore–Perrin constant-space O ( n ) -time string-matching algorithm to run in optimal O ( n / α ) time and even in real-time, achieving a factor α speedup over traditional algorithms that examine each character individually. Our macro-level algorithm only uses the standard A C 0 instructions of the word-RAM model (i. e. no integer multiplication) plus two specialized micro-level A C 0 word-size packed-string instructions. The main word-size string-matching instruction wssm is available in contemporary commodity processors. The other word-size maximum-suffix instruction wslm is only required during the pattern pre-processing. Benchmarks show that our solution can be efficiently implemented, unlike some prior theoretical packed string matching work. (b) We also consider the complexity of the packed string matching problem in the classical word-RAM model in the absence of the specialized micro-level instructions wssm and wslm. We propose micro-level algorithms for the theoretically efficient emulation using parallel algorithms techniques to emulate wssm and using the Four-Russians technique to emulate wslm. Surprisingly, our bit-parallel emulation of wssm also leads to a new simplified parallel random access machine string-matching algorithm. As a byproduct to facilitate our results we develop a new algorithm for finding the leftmost (most significant) 1 bits in consecutive non-overlapping blocks of uniform size inside a word. This latter problem is not known to be reducible to finding the rightmost 1, which can be easily solved, since we do not know how to reverse the bits of a word in O ( 1 ) time.

TCS Journal 2013 Journal Article

On computing the diameter of real-world undirected graphs

• Pilu Crescenzi
• Roberto Grossi
• Michel Habib
• Leonardo Lanzi
• Andrea Marino

We propose a new algorithm for the classical problem of computing the diameter of undirected unweighted graphs, namely, the maximum distance among all the pairs of nodes, where the distance of a pair of nodes is the number of edges contained in the shortest path connecting these two nodes. Although its worst-case complexity is O ( n m ) time, where n is the number of nodes and m is the number of edges of the graph, we experimentally show that our algorithm works in O ( m ) time in practice, requiring few breadth-first searches to complete its task on almost 200 real-world graphs.

SODA Conference 2013 Conference Paper

Optimal Listing of Cycles and st-Paths in Undirected Graphs

• Etienne Birmelé
• Rui A. Ferreira
• Roberto Grossi
• Andrea Marino 0001
• Nadia Pisanti
• Romeo Rizzi
• Gustavo Sacomoto

The classical problem of efficiently listing all the simple cycles in a graph has been studied since the early 70s. For a graph with n vertices and m edges, containing η cycles, the most efficient solution was presented by Johnson [SIAM J. Computing, 1975] and takes O ((η + 1)( m + n )) time. This solution is not optimal for undirected graphs: nevertheless, no theoretical improvements have been proposed in the past decades. We present the first optimal solution to list all the simple cycles in an undirected graph G. Specifically, let ( G ) denote the set of all these cycles (| ( G )| = η). For a cycle c ∊ ( G ), let | c | denote the number of edges in c. Our algorithm requires time and is asymptotically optimal: Ω( m ) time is necessarily required to read G as input, and time is required to list the output. We also present the first optimal solution to list all the simple paths from s to t (shortly, st -paths) in an undirected graph G. Let st ( G ) denote the set of st -paths in G and, for an st -path π ∊ st ( G ), let |π| be the number of edges in π. Our algorithm lists all the st -paths in G optimally in time.

TCS Journal 2013 Journal Article

Simple real-time constant-space string matching

• Dany Breslauer
• Roberto Grossi
• Filippo Mignosi

String matching is the classical problem of finding all occurrences of a pattern in a text. A real-time string matching algorithm takes worst-case constant-time to check if a pattern occurrence ends at each text location. We derive a real-time variation of the elegant Crochemore–Perrin constant-space string matching algorithm that has a simple and efficient control structure. We use observations about the locations of critical factorizations to deploy two tightly-coupled simplified real-time instances of the Crochemore–Perrin algorithm that search for complementary parts of the pattern whose simultaneous occurrence indicates an occurrence of the complete pattern.

I&C Journal 2012 Journal Article

Consecutive ones property and PQ-trees for multisets: Hardness of counting their orderings

• Giovanni Battaglia
• Roberto Grossi
• Noemi Scutellà

A binary matrix satisfies the consecutive ones property (c1p) if its columns can be permuted such that the 1s in each row of the resulting matrix are consecutive. Equivalently, a family of sets F = { Q 1, …, Q m }, where Q i ⊆ R for some universe R, satisfies the c1p if the symbols in R can be permuted such that the elements of each set Q i ∈ F occur consecutively, as a contiguous segment of the permutation of Rʼs symbols. Motivated by combinatorial problems on sequences with repeated symbols, we consider the c1p version on multisets and prove that counting the orderings (permutations) thus generated is # P -complete. We prove completeness results also for counting the permutations generated by PQ-trees (which are related to the c1p), thus showing that a polynomial-time algorithm is unlikely to exist when dealing with multisets and sequences with repeated symbols. To prove our results, we use a combinatorial approach based on parsimonious reductions from the Hamiltonian path problem, which enables us to prove also the hardness of approximation for these counting problems.

TCS Journal 2011 Journal Article

A quick tour on suffix arrays and compressed suffix arrays

• Roberto Grossi

Suffix arrays are a key data structure for solving a run of problems on texts and sequences, from data compression and information retrieval to biological sequence analysis and pattern discovery. In their simplest version, they can just be seen as a permutation of the elements in { 1, 2, …, n }, encoding the sorted sequence of suffixes from a given text of length n, under the lexicographic order. Yet, they are on a par with ubiquitous and sophisticated suffix trees. Over the years, many interesting combinatorial properties have been devised for this special class of permutations: for instance, they can implicitly encode extra information, and they are a well characterized subset of the n! permutations. This paper gives a short tutorial on suffix arrays and their compressed version to explore and review some of their algorithmic features, discussing the space issues related to their usage in text indexing, combinatorial pattern matching, and data compression.

TCS Journal 2009 Journal Article

Masking patterns in sequences: A new class of motif discovery with don’t cares

• Giovanni Battaglia
• Davide Cangelosi
• Roberto Grossi
• Nadia Pisanti

We introduce a new notion of motifs, called masks, that succinctly represents the repeated patterns for an input sequence T of n symbols drawn from an alphabet Σ. We show how to build the set of all frequent maximal masks of length L in O ( 2 L n ) time and space in the worst case, using the Karp–Miller–Rosenberg approach. We analytically show that our algorithm performs better than the method based on constant-time enumerating and checking all the potential ( | Σ | + 1 ) L candidate patterns in T, after a polynomial-time preprocessing of T. Our algorithm is also cache-friendly, attaining O ( 2 L s o r t ( n ) ) block transfers, where s o r t ( n ) is the cache complexity of sorting n items.

SODA Conference 2006 Conference Paper

Squeezing succinct data structures into entropy bounds

• Kunihiko Sadakane
• Roberto Grossi

FOCS Conference 2004 Conference Paper

No Sorting? Better Searching!

• Gianni Franceschini
• Roberto Grossi

Sorting is commonly meant as the task of arranging keys in increasing or decreasing order (or small variations of this order). Given n keys underlying a total order, the best organization in an array is maintaining them in sorted order. Searching requires /spl Theta/ (log n) comparisons in the worst case, which is optimal. We demonstrate that this basic fact in data structures does not hold for the general case of multidimensional keys, whose comparison cost is proportional to their length. In two papers by Andersson et al. (1994) and Andersson et al. (1995) and the full version in 2001, Andersson et al. study the complexity of searching a sorted array of n keys, each of length k, arranged in lexicographic (or alphabetic) order for an arbitrary, possibly unbounded, ordered alphabet. They give sophisticated arguments for proving a tight bound in the worst case for this basic data organization, up to a constant factor, obtaining /spl Theta/(((k log log n)/(log log (4 + ((k log log n)/log n)))) + k log n) character comparisons (or probes). Note that the bound is /spl Theta/ (log n) when k = 1, which is the case that is well known in algorithmics. We describe a permutation of the n keys that is different from the sorted order, and sorting is just the starting point for describing our preprocessing. When keys are stored according to this "unsorted" order in the array, the complexity of searching drops to /spl Theta/ (k + log n) character comparisons (or probes) in the worst case, which is optimal among all possible permutations of the n keys in the array, up to a constant factor. Again, the bound is /spl Theta/ (log n) when k = 1. Jointly with the aforementioned result of Anders son et al. , our finding provably shows that keeping k-dimensional keys sorted in an array is not the best data organization for searching. This fact was not observable before by just considering k = O(1) as sorting is an optimal organization in this case. More implications of our result are commented in the introduction.

SODA Conference 2004 Conference Paper

When indexing equals compression: experiments with compressing suffix arrays and applications

• Roberto Grossi
• Ankur Gupta 0003
• Jeffrey Scott Vitter

MFCS Conference 2003 Conference Paper

A Basis of Tiling Motifs for Generating Repeated Patterns and Its Complexity for Higher Quorum

• Nadia Pisanti
• Maxime Crochemore
• Roberto Grossi
• Marie-France Sagot

Abstract We investigate the problem of determining the basis of motifs (a form of repeated patterns with don’t cares) in an input string. We give new upper and lower bounds on the problem, introducing a new notion of basis that is provably smaller than (and contained in) previously defined ones. Our basis can be computed in less time and space, and is still able to generate the same set of motifs. We also prove that the number of motifs in all these bases grows exponentially with the quorum, the minimal number of times a motif must appear. We show that a polynomial-time algorithm exists only for fixed quorum.

SODA Conference 2003 Conference Paper

High-order entropy-compressed text indexes

• Roberto Grossi
• Ankur Gupta 0003
• Jeffrey Scott Vitter

SODA Conference 2003 Conference Paper

Implicit dictionaries supporting searches and amortized updates in O(log n log log n) time

• Gianni Franceschini
• Roberto Grossi

TCS Journal 2003 Journal Article

Text sparsification via local maxima

• Pilu Crescenzi
• Alberto Del Lungo
• Roberto Grossi
• Elena Lodi
• Linda Pagli
• Gianluca Rossi

In this paper we investigate some properties and algorithms related to a text sparsification technique based on the identification of local maxima in the given string. As the number of local maxima depends on the order assigned to the alphabet symbols, we first consider the case in which the order can be chosen in an arbitrary way. We show that looking for an order that minimizes the number of local maxima in the given text string is an NP-hard problem. Then, we consider the case in which the order is fixed a priori. Even though the order is not necessarily optimal, we can exploit the property that the average number of local maxima induced by the order in an arbitrary text is approximately one third of the text length. In particular, we describe how to iterate the process of selecting the local maxima by one or more iterations, so as to obtain a sparsified text. We show how to use this technique to filter the access to unstructured texts, which appear to have no natural division in words. Finally, we experimentally show that our approach can be successfully used in order to create a space efficient index for searching sufficiently long patterns in a DNA sequence as quickly as a full index.

FOCS Conference 2002 Conference Paper

Implicit B-Trees: New Results for the Dictionary Problem

• Gianni Franceschini
• Roberto Grossi
• J. Ian Munro
• Linda Pagli

We reopen the issue of finding an implicit data structure for the dictionary problem. In particular, we examine the problem of maintaining n data values in the first n locations of an array in such a way that we can efficiently perform the operations insert, delete and search. No information other than n and the data is to be retained; and the only operations which we may perform on the data values (other than reads and writes) are comparisons. Our structure supports these operations in O(log/sup 2/ n/log log n) time, marking the first improvement on the problem since the mid 1980's. En route we develop a number of space efficient techniques for handling segments of a large array in a memory hierarchy. We achieve a cost of O(log/sub B/ n) block transfers like in regular B-trees, under the realistic assumption that a block stores B = /spl Omega/(log n) keys, so that reporting r consecutive keys in sorted order has a cost of O(log/sub B/n+r/B) block transfers. Being implicit, our B-tree occupies exactly [n/B] blocks after each update.

I&C Journal 2002 Journal Article

Optimal Deterministic Protocols for Mobile Robots on a Grid

• Roberto Grossi
• Andrea Pietracaprina
• Geppino Pucci

This paper studies a system of m robots operating in a set of n work locations connected by aisles in a n × n grid, where m≤n. From time to time the robots need to move along the aisles, in order to visit disjoint sets of locations. The movement of the robots must comply with the following constraints: (1) no two robots can collide at a grid node or traverse a grid edge at the same time; (2) a robot's sensory capability is limited to detecting the presence of another robot at a neighboring node. We present a deterministic protocol that, for any small constant ϵ>0, allows m≤(1-ϵ)n robots to visit their target locations in O( dn ) time, where each robot visits no more than d≤n targets and no target is visited by more than one robot. We also prove a lower bound showing that our protocol is optimal. Prior to this paper, no optimal protocols were known for d>1. For d=1, optimal protocols were known only for m≤ n, while for general m≤n only a suboptimal randomized protocol was known.

STOC Conference 2000 Conference Paper

Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)

• Roberto Grossi
• Jeffrey Scott Vitter

I&C Journal 1999 Journal Article

Efficient Splitting and Merging Algorithms for Order Decomposable Problems

• Roberto Grossi
• Giuseppe F. Italiano

Let S be a set whose items are sorted with respect to d>1 total orders ≺1, …, ≺ d, and which is subject to dynamic operations, such as insertions of a single item, deletions of a single item, split and concatenate operations performed according to any chosen order ≺ i (1⩽i⩽d). This generalizes to dimension d>1 the notion of concatenable data structures, such as the 2-3-trees, which support splits and concatenates under a single total order. The main contribution of this paper is a general and novel technique for solving order decomposable problems on S which yields new and efficient concatenable data structures for dimension d>1. By using our technique we maintain S with the time bounds: O(log n) for the insertion or the deletion of a single item, where n is the number of items currently in S; n 1−1/d for splits and concatenates along any order, and for rectangular range queries. The space required is O(n). We provide several applications of our technique. Namely, we present new multidimensional data structures implementing two-dimensional priority queues, two-dimensional search trees, and concatenable interval trees; these data structures allow us to improve many previously known results on decomposable problems under split and concatenate operations, such as membership query, minimum-weight item, range query, convex hulls, and Voronoi diagrams.

STOC Conference 1997 Conference Paper

On Sorting Strings in External Memory (Extended Abstract)

• Lars Arge
• Paolo Ferragina
• Roberto Grossi
• Jeffrey Scott Vitter

SODA Conference 1996 Conference Paper

Fast String Searching in Secondary Storage: Theoretical Developments And Experimental Results

• Paolo Ferragina
• Roberto Grossi

I&C Journal 1996 Journal Article

On the Construction of Classes of Suffix Trees for Square Matrices: Algorithms and Applications

• Raffaele Giancarlo
• Roberto Grossi

We provide a uniform framework for the study of index data structures for a two-dimensional matrixTEXT[1: n, 1: n] whose entries are drawn from an ordered alphabetΣ. An index forTEXTcan be informally seen as the two-dimensional analog of the suffix tree for a string. It allows on-line searches and statistics to be performed onTEXTby representing compactly theΘ(n 3) square submatrices ofTEXTin optimalO(n 2) space. We identify 4 n−1families of indices forTEXT, each containing ∏ n i=1 (2i−1)! isomorphic data structures. We also develop techniques leading to a single algorithm that efficiently builds any index in any family inO(n 2 log n) time andO(n 2) space. Such an algorithm improves in various respects the algorithms for the construction of the PAT tree and the Lsuffix tree. The framework and the algorithm easily generalize tod>2 dimensions. Moreover, as part of our algorithm, we provide new algorithmic tools that yield a space-efficient implementation of the “naming scheme” of R. Karpet al. (in“Proceedings, Fourth Symposium on Theory of Computing, ” pp. 125–136) for strings and matrices.

STOC Conference 1995 Conference Paper

A fully-dynamic data structure for external substring search (Extended Abstract)

• Paolo Ferragina
• Roberto Grossi

SODA Conference 1995 Conference Paper

Fast Incremental Text Editing

• Paolo Ferragina
• Roberto Grossi

FOCS Conference 1995 Conference Paper

Optimal On-Line Search and Sublinear Time Update in String Matching

• Paolo Ferragina
• Roberto Grossi

We study in a dynamic setting the problem of online searching for the occurrences of an arbitrary pattern string P[1, p] in an indexed text string T[1, n]. That is, we assume that the text T may be updated by inserting or deleting an arbitrary string Y[1, y]. Our main contribution is presenting the first dynamic algorithm that achieves optimal time, i. e. /spl Theta/(p+occ), to find the occ occurrences of P, and sublinear time per update, i. e. O(/spl radic/(n+y)), in the worst case. The required space is optimal /spl Theta/(n).

TCS Journal 1993 Journal Article

On finding common subtrees

• Roberto Grossi

Let T and R be two arbitrary ordered trees, |T| ⩾ |R|, whose nodes are labelled over an alphabet A. We devise a simple solution for detecting all the common subtrees in O(|T|) time and space if the size of A is finite, and O(|T| log min (|A|, |T|)) time otherwise. We solve the problem of finding in T and R all occurrences (if any) of any given tree B in either O(|T|⧸|B|) or O(|B|+|T|⧸|B|) time. This requires to set up a simple data structure in O(|T|) time that allows to find all maximal subtrees of B in O (|B|) time and to solve other related problems.