More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries (2009)
Grossi, Roberto, Orlandi, Alessio, Raman, Rajeev, Rao, S. Srinivasa
We consider the problem of representing, in a compressed format, a bit-vector $S$ of $m$ bits with $n$ 1s, supporting the following operations, where $b \in \{0, 1 \}$: $rank_b(S,i)$ returns the...
Optimal cache-aware suffix selection (2009)
Franceschini, Gianni, Grossi, Roberto, Muthukrishnan, S.
Given string $S[1..N]$ and integer $k$, the {\em suffix selection} problem is to determine the $k$th lexicographically smallest amongst the suffixes $S[i... N]$, $1 \leq i \leq N$. We study the...
Optimal cache-aware suffix selection (2009)
Franceschini, Gianni, Grossi, Roberto, Muthukrishnan, S.
Given string $S[1..N]$ and integer $k$, the {\em suffix selection} problem is to determine the $k$th lexicographically smallest amongst the suffixes $S[i\ldots N]$, $1 \leq i \leq N$. We study the...
Optimal cache-aware suffix selection (2009)
Franceschini, Gianni, Grossi, Roberto, Muthukrishnan, S.
Given string $S[1..N]$ and integer $k$, the {\em suffix selection} problem is to determine the $k$th lexicographically smallest amongst the suffixes $S[i\ldots N]$, $1 \leq i \leq N$. We study the...
More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries (2009)
Grossi, Roberto, Orlandi, Alessio, Raman, Rajeev, Srinivasa Rao, S.
We consider the problem of representing, in a compressed format, a bit-vector $S$ of $m$ bits with $n$ $1$s, supporting the following operations, where $b \in \{ 0, 1 \}$: $rank_b(S,i)$ returns the...
More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries (2009)
Grossi, Roberto, Orlandi, Alessio, Raman, Rajeev, Srinivasa Rao, S.
We consider the problem of representing, in a compressed format, a bit-vector $S$ of $m$ bits with $n$ $1$s, supporting the following operations, where $b \in \{ 0, 1 \}$: $rank_b(S,i)$ returns the...
Optimal Cache-Aware Suffix Selection (2009)
Franceschini, Gianni, Grossi, Roberto, Muthukrishnan, S.
Given string $S[1..N]$ and integer $k$, the {em suffix selection} problem is to determine the $k$th lexicographically smallest amongst the suffixes $S[ildots N]$, $1 leq i leq N$. We study the suffix...
More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries (2009)
Grossi, Roberto, Orlandi, Alessio, Raman, Rajeev, Rao, S. Srinivasa
We consider the problem of representing, in a compressed format, a bit-vector~$S$ of $m$ bits with $n$ $mathbf{1}$s, supporting the following operations, where $b in { mathbf{0}, mathbf{1} }$:...
A General Technique for Managing Strings in Comparison-Driven Data Structures (2008)
Gianni Franceschini, Roberto Grossi
Abstract. This paper presents a general technique for optimally transforming any dynamic data structure D that operates on atomic and indivisible keys by constant-time comparisons, into a data...
Roberto Grossi, J. Ian Munro, Linda Pagli
Abstract We reopen the issue of finding an implicit data struc-ture for the dictionary problem. In particular, we examine the problem of maintaining n data values in the first n lo-cations of an...
Distilling Router Data Analysis for Faster and Simpler Dynamic IP Lookup Algorithms (2008)
Abstract. We consider the problem of fast IP address lookup in the forwarding engines of Internet routers. We analyze over 2400 public snapshots of routing tables collected over five years,...
A Trie-Based Approach for Compacting Automata (2008)
Maxime Crochemore, Chiara Epifanio, Roberto Grossi
Abstract. We describe a new technique for reducing the number of nodes and symbols in automata based on tries. The technique stems from some results on anti-dictionaries for data compression and does...
Optimal In-Place Sorting of Vectors and Records (2008)
Gianni Franceschini, Roberto Grossi
Abstract. We study the problem of determining the complexity of optimal comparison-based in-place sorting when the key length, k, is not a constant. We present the first algorithm for...
Running Head Deterministic Protocols for Mobile Robots (2008)
Roberto Grossi, Andrea Pietracaprina, Roberto Grossi
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,...
Abstract: The suffix tree is a compacted trie that stores all suffixes of a given text string. This data structure has been intensively employed in pattern matching on strings and trees, with a wide...
The Pre-history and Future of the Block-Sorting Compression Algorithm (2008)
Mike Burrows, David Wheeler, Lee Butterman, Nasir Memon, Paolo Ferragina, Raffaele Giancarlo, ...
2
Roberto Grossi, Ankur Gupta, Jeffrey Scott Vitter
We present a unified algorithmic framework to obtain nearly optimal space bounds for text compression and compressed text indexing, apart from lower-order terms. For a text T of n symbols drawn from...
Entropy-Compressed Indexes for Multidimensional Pattern Matching (2008)
Roberto Grossi, Ankur Gupta, Jeffrey Scott Vitter
In this talk, we will discuss the challenges involved in developing a multidimensional generalizations of compressed text indexing structures. These structures depend on some notion of...
Abstract: The suffix tree is a compacted trie that stores all suffixes of a given text string. This data structure has been intensively employed in pattern matching on strings and trees, with a wide...
Roberto Grossi, Ankur Gupta, Jerey Scott Vitter
We present a novel implementation of compressed sux arrays exhibiting new tradeos between search time and space occupancy for a given text (or sequence) of n symbols over an alphabet , where each...
Nadia Pisanti, Nadia Pisanti, Maxime Crochemore, Maxime Crochemore, Roberto Grossi, Roberto Grossi, ...
We investigate the problem of determining the basis of repeated motifs with don't cares in an input string. We give new upper and lower bounds on the problem, introducing a notion of basis that...
Revised version of \Ecient Cross-Trees for External Memory" (2007)
Roberto Grossi, Roberto Grossi
Due to a printing problem, the revised version of our paper [19] has been replaced by the (shorter) submitted version. In this technical report, we include the revised version that has not been...
SUCCINCT DATA STRUCTURES Date: (2007)
Ankur Gupta, Jeffrey Scott Vitter, Pankaj Agarwal, Roberto Grossi, Xiaobai Sun, Ankur Gupta, ...
Rank-sensitive data structures (2005)
Iwona Bialynicka-birula, Roberto Grossi
Abstract. Output-sensitive data structures result from preprocessing n items and are capable of reporting the items satisfying an on-line query in O(t(n) + ℓ) time, where t(n) is the cost of...
Gianni Franceschini, Roberto Grossi
Questions about order versus disorder in systems and models have been fascinating scientists over the years. In Computer Science, order is intimately related to sorting, commonly meant as the task of...
Gianni Franceschini, Roberto Grossi
An array of n distinct keys can be sorted for logarithmic searching or can be organized as a heap for logarithmic updating, but it is unclear how to attain logarithmic time for both searching and...
Roberto Grossi, Jeffrey Scott Vitter
The proliferation of online text, such as on the World Wide Web and in databases, motivates the need for space-efficient text indexing methods that support fast string searching. We model this...
Fast compression with a static model in high-order entropy (2004)
Luca Foschini, Roberto Grossi, Ankur Gupta, Jeffrey Scott Vitter
We report on a simple encoding format called wzip for decompressing blocksorting transforms, such as the Burrows-Wheeler Transform (BWT). Our compressor uses the simple notions of gamma encoding and...
When indexing equals compression: Experiments with compressing suffix arrays and applications (2004)
Roberto Grossi, Ankur Gupta, Jeffrey Scott Vitter
We report on a new and improved version of high-order entropy-compressed suffix arrays, which has theoretical performance guarantees similar to those in our earlier work [16], yet represents an...
A comparative study of bases for motif inference (2004)
Nadia Pisanti, Maxime Crochemore, Roberto Grossi, Marie-france Sagot
Motif inference is at the heart of several time-demanding computational tasks, such as in molecular biology, data mining and identification of structured motifs in sequences, and in data compression,...
High-order entropy-compressed text indexes (2003)
Roberto Grossi, Ankur Gupta, Jeffrey Scott Vitter
We present a novel implementation of compressed suffix arrays exhibiting new tradeoffs between search time and space occupancy for a given text (or sequence) of n symbols over an alphabet Σ, where...
Bases of motifs for generating repeated patterns with wild cards (2003)
Nadia Pisanti, Maxime Crochemore, Roberto Grossi, Marie-france Sagot
Motif inference represents one of the most important areas of research in computational biology, and one of its oldest ones. Despite this, the problem remains very much open in the sense that no...
Optimal cache-oblivious implicit dictionaries (2003)
Gianni Franceschini, Roberto Grossi
Abstract. We consider the issues of implicitness and cache-obliviousness in the classical dictionary problem for n distinct keys over an unbounded and ordered universe. One finding in this paper is...
Optimal space-time dictionaries over an unbounded universe with flat implicit trees (2003)
Gianni Franceschini, Roberto Grossi
In the classical dictionary problem, a set of n distinct keys over an unbounded and ordered universe is maintained under insertions and deletions of individual keys while supporting search...
Optimal Deterministic Protocols for Mobile Robots on a Grid (2002)
Roberto Grossi, Andrea Pietracaprina, Geppino Pucci
. A Multi Robot Grid System consists of m robots that operate in a set of n m work locations connected by aisles in a p n \Theta p n grid. From time to time the robots need move along the aisles, in...
Optimal Deterministic Protocols for Mobile Robots on a Grid (2002)
Andrea Pietracaprina, Roberto Grossi, Geppino Pucci, Roberto Grossi
This paper studies a system of m robots operating in a set of n work locations connected by aisles in a p n \Theta p n grid, where m n. From time to time the robots need to move along the aisles, in...
Optimal Deterministic Protocols for Mobile Robots on a Grid (2002)
Roberto Grossi, Andrea Pietracaprina, Geppino Pucci, Prof Roberto Grossi
This paper studies a system of m robots operating in a set of n work locations connected by aisles in a p n \Theta p n grid, where m n. From time to time the robots need to move along the aisles, in...
A Basis for Repeated Motifs in Pattern Discovery and Text Mining Nadia Pisanti (2002)
Nadia Pisanti, Maxime Crochemore Roberto, Roberto Grossi, Marie-france Sagot
We present a new notion of basis that is able to generate the repeated motifs (possibly exponential in number) that appear at least twice with don't care symbols in a string of length n over an...
Roberto Grossi, Jeffrey Scott Vitter
The proliferation of online text, such as on the World Wide Web and in databases, motivates the need for space-efficient index methods that support fast search. Consider a text T of n binary symbols...
IP Address Lookup Made Fast and Simple (1999)
Pierluigi Crescenzi, Leandro Dardini, Pierluigi Crescenzi, Ro Dardini, Ro Dardini, Roberto Grossi, ...
The IP address lookup problem is one of the major bottlenecks in high performance routers. Previous solutions to this problem first describe it in the general terms of longest prefix matching and,...
Roberto Grossi, Giuseppe F. Italiano
We describe a general paradigm for maintaining multidimensional keys in linked data structures. In particular, we show how to augment data structures de ned on one-dimensional keys so as to store,...
Efficient Cross-Trees for External Memory (1998)
Roberto Grossi, Roberto Grossi, Giuseppe F. Italiano
. We describe efficient methods for organizing and maintaining large multidimensional data sets in external memory. This is particular important as access to external memory is currently several...
Improved Dynamic Text Indexing (1998)
Paolo Ferragina, Roberto Grossi
In the dynamic text indexing problem, a text string has to be maintained under string insertions and deletions in order to answer on-line queries about arbitrary pattern occurrences. By means of some...
Paolo Ferragina, Roberto Grossi
We introduce a new text-indexing data structure, the String B-Tree, that can be seen as a link between some traditional external-memory and string-matching data structures. In a short phrase, it is a...
On Sorting Strings in External Memory (1997)
Lars Arge, Paolo Ferragina, Roberto Grossi, Jeffrey Scott Vitter
) Lars Arge Paolo Ferragina y Roberto Grossi z Jeffrey Scott Vitter x Abstract. In this paper we address for the first time the I/O complexity of the problem of sorting strings in external memory,...
Efficient Splitting and Merging Algorithms for Order Decomposable Problems (1997)
Roberto Grossi, Giuseppe F. Italiano
Let S be a set whose items are sorted with respect to d ? 1 total orders OE 1 ; : : : ; OE d , and which is subject to dynamic operations, such as insertions of a single item, deletions of a single...
On sorting strings in external memory (extended abstract (1997)
Lars Arge, Paolo Ferragina, Roberto Grossi, Jeffrey Scott Vitter
Abstract. In this paper we address for the first time the I/O complexity of the problem of sorting strings in external memory, which is a fundamental component of many large-scale text applications....
An experimental study of sb-trees (1996)
Paolo Ferragina, Roberto Grossi
In a previous work of ours [13], we proposed a text indexing data structure for external memory, which we called SB-tree, that combines the best B-tree and suffix array qualities to overcome the...