Arrow Research search

Author name cluster

Raffaele Giancarlo

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.

17 papers
2 author rows

Possible papers

17

I&C Journal 2023 Journal Article

A new class of string transformations for compressed text indexing

  • Raffaele Giancarlo
  • Giovanni Manzini
  • Antonio Restivo
  • Giovanna Rosone
  • Marinella Sciortino

Introduced about thirty years ago in the field of data compression, the Burrows-Wheeler Transform (BWT) is a string transformation that, besides being a booster of the performance of memoryless compressors, plays a fundamental role in the design of efficient self-indexing compressed data structures. Finding other string transformations with the same remarkable properties of BWT has been a challenge for many researchers for a long time. In this paper, we introduce a whole class of new string transformations, called local orderings-based transformations, which have all the “myriad virtues” of BWT. As a further result, we show that such new string transformations can be used for the construction of the recently introduced r-index, which makes them suitable also for highly repetitive collections. In this context, we consider the problem of finding, for a given string, the BWT variant that minimizes the number of runs in the transformed string.

Details DOI

TCS Journal 2020 Journal Article

The Alternating BWT: An algorithmic perspective

  • Raffaele Giancarlo
  • Giovanni Manzini
  • Antonio Restivo
  • Giovanna Rosone
  • Marinella Sciortino

The Burrows-Wheeler Transform (BWT) is a word transformation introduced in 1994 for Data Compression. It has become a fundamental tool for designing self-indexing data structures, with important applications in several areas in science and engineering. The Alternating Burrows-Wheeler Transform (ABWT) is another transformation recently introduced in Gessel et al. (2012) [21] and studied in the field of Combinatorics on Words. It is analogous to the BWT, except that it uses an alternating lexicographical order instead of the usual one. Building on results in Giancarlo et al. (2018) [23], where we have shown that BWT and ABWT are part of a larger class of reversible transformations, here we provide a combinatorial and algorithmic study of the novel transform ABWT. We establish a deep analogy between BWT and ABWT by proving they are the only ones in the above mentioned class to be rank-invertible, a novel notion guaranteeing efficient invertibility. In addition, we show that the backward-search procedure can be efficiently generalized to the ABWT; this result implies that also the ABWT can be used as a basis for efficient compressed full text indices. Finally, we prove that the ABWT can be efficiently computed by using a combination of the Difference Cover suffix sorting algorithm (Kärkkäinen et al. , 2006 [28]) with a linear time algorithm for finding the minimal cyclic rotation of a word with respect to the alternating lexicographical order.

Details DOI

TCS Journal 2019 Journal Article

DNA combinatorial messages and Epigenomics: The case of chromatin organization and nucleosome occupancy in eukaryotic genomes

  • Raffaele Giancarlo
  • Simona E. Rombo
  • Filippo Utro

Epigenomics is the study of modifications on the genetic material of a cell that do not depend on changes in the DNA sequence, since those latter involve specific proteins around which DNA wraps. The end result is that Epigenomic changes have a fundamental role in the proper working of each cell in Eukaryotic organisms. A particularly important part of Epigenomics concentrates on the study of chromatin, that is, a fiber composed of a DNA-protein complex and very characterizing of Eukaryotes. Understanding how chromatin is assembled and how it changes is fundamental for Biology. In more than thirty years of research in this area, Mathematics and Theoretical Computer Science have gained a prominent role, in terms of modeling and mining, regarding in particular the so-called 10 nm fiber. Starting from some very basic notions of Biology, we briefly illustrate the recent advances obtained via laboratory experiments on the organization and dynamics of chromatin. Then, we mainly concentrate our attention on the contributions given by Combinatorial and Informational Methodologies, that are at the hearth of Theoretical Computer Science, to the understanding of mechanisms determining the 10 nm fiber. We conclude highlighting several directions of investigation that are perceived as important and where Theoretical Computer Science can provide high impact results.

Details DOI

I&C Journal 2009 Journal Article

The myriad virtues of Wavelet Trees

  • Paolo Ferragina
  • Raffaele Giancarlo
  • Giovanni Manzini

Wavelet Trees have been introduced by Grossi et al. in SODA 2003 and have been rapidly recognized as a very flexible tool for the design of compressed full-text indexes and data compression algorithms. Although several papers have investigated the properties and usefulness of this data structure in the full-text indexing scenario, its impact on data compression has not been fully explored. In this paper we provide a throughout theoretical analysis of a wide class of compression algorithms based on Wavelet Trees. Also, we propose a novel framework, called Pruned Wavelet Trees, that aims for the best combination of Wavelet Trees of properly-designed shapes and compressors either binary (like, Run-Length encoders) or non-binary (like, Huffman and Arithmetic encoders).

Details DOI

TCS Journal 2003 Journal Article

On finding common neighborhoods in massive graphs

  • Adam L. Buchsbaum
  • Raffaele Giancarlo
  • Jeffery R. Westbrook

We consider the problem of finding pairs of vertices that share large common neighborhoods in massive graphs. We prove lower bounds on the resources needed to solve this problem on resource-bounded models of computation. In streaming models, in which algorithms can access the input only a constant number of times and only sequentially, we show that, even with randomization, any algorithm that determines if there exists any pair of vertices with a large common neighborhood must essentially store and process the input graph off line. In sampling models, in which algorithms can only query an oracle for the common neighborhoods of specified vertex pairs, we show that any algorithm must sample almost every pair of vertices for their respective common neighborhoods.

Details DOI

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.

Details DOI

FOCS Conference 1990 Conference Paper

On the Exact Complexity of String Matching (Extended Abstract)

  • Livio Colussi
  • Zvi Galil
  • Raffaele Giancarlo

The maximal number of character comparisons made by a linear-time string matching algorithm, given a text string of length n and a pattern string of length m over a general alphabet, is investigated. The number is denoted by c(n, m) or approximated by (1+C)n, where C is a universal constant. The subscript 'online' is added when attention is restricted to online algorithms, and the superscript '1' is added when algorithms that find only one occurrence of the pattern in the text are considered. It is well known that n >

Details

TCS Journal 1989 Journal Article

Speeding up dynamic programming with applications to molecular biology

  • Zvi Galil
  • Raffaele Giancarlo

Consider the problem of computing E[j]= min 0⩽k⩽j−1 {D[k]+w(k, j)}, j=1, …, n, where w is a given weight function, D[0] is given and for every k=1, …, n, D[k] is easily computable from E[k]. This problem appears as a subproblem in dynamic programming solutions to various problems. Obviously, it can be solved in time O(n 2), and for a general weight function no better algorithm is possible. We consider two dual cases that arise in applications: In the concave case, the weight function satisfies the quadrangle inequality: w(k, j)+w(l, j′)⩽w(l, j)+w(k, j′) for all k⩽l⩽j⩽j′. In the convex case, the weight function satisfies the inverse quadrangle inequality. In both cases we show how to use the assumed property of w to derive an O(n log n) algorithm. Even better, linear-time algorithms are obtained if w satisfies the following additional closest zero property: for every two integers l and k, l<k, and real number a, the smallest zero of f(x)=w(l, x)−w(k, x)−a which is larger than k can be found in constant time. The two algorithms speed up several dynamic programming routines that solve as a subproblem the problem above. The speed-up is from O(n 3) to O(n 2log n) or O(n 2). Applications include algorithms for comparing DNA sequences and algorithms used in speech recognition and geology. One typical problem is the following: given the cost of substituting any pair of symbols and a convex cost function g for gaps (where g(r) is the cost of a gap of size r), compute the modified edit distance between the two given sequences.

Details DOI

FOCS Conference 1988 Conference Paper

Speeding up Dynamic Programming

  • David Eppstein
  • Zvi Galil
  • Raffaele Giancarlo

A number of important computational problems in molecular biology, geology, speech recognition, and other areas can be expressed as recurrences which have typically been solved with dynamic programming. By using more sophisticated data structures, and by taking advantage of further structure from the applications, the authors speed up the computation of several of these recurrences by one or two orders of magnitude. The algorithms used are simple and practical. >

Details

TCS Journal 1987 Journal Article

Optimal parallel parsing of bracket languages

  • Wojciech Rytter
  • Raffaele Giancarlo

We prove that the parsing problem for bracket context-free languages can be solved in log n time using n/log n processors on a parallel random access machine without write conflicts (P-RAM). On the way we develop a new general technique for tree compression based on the bracket structure of the tree.

Details DOI

TCS Journal 1987 Journal Article

Parallel string matching with k mismatches

  • Zvi Galil
  • Raffaele Giancarlo

Two improved algorithms for string matching with k mismatches are presented. One algorithm is based on fast integer multiplication algorithms whereas the other follows more closely classic string-matching techniques.

Details DOI
v2026.09.13