Author name cluster

Fabrizio Luccio

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.

6 papers

2 author rows

TCS Journal 2016 Journal Article

More agents may decrease global work: A case in butterfly decontamination

Fabrizio Luccio
Linda Pagli

This paper is a contribution to network decontamination with a view inherited from parallel processing. At the beginning some or all the vertices may be contaminated. The network is visited by a group of decontaminating agents. When a decontaminated vertex is left by the agents, it can be re-contaminated only if the number of infected neighbors exceeds a certain immunity threshold m. The main goal of the studies in this line is to minimize the number A of agents needed to do the job and, for a minimum team, to minimize the number M of agent moves. Instead of M we consider the number T of steps (i. e. parallel moves) as a measure of time, and evaluate the quality of a protocol on the basis of its work W = A T. Taking butterfly networks as an example, we compare different protocols and show that, for some values of m, a larger team of agents may require smaller work.

Details DOI

TCS Journal 2007 Journal Article

Refined upper bounds for right-arm rotation distances

Sean Cleary
Fabrizio Luccio
Linda Pagli

Rotation distances measure the difference in shape in rooted binary trees. We construct sharp bounds on maximal right-arm rotation distance and restricted right-arm rotation distance for trees of size n. These bounds sharpen the results of Cleary and Taback and incorporate the lengths of the right side of the trees to improve the bounds.

Details DOI

FOCS Conference 2005 Conference Paper

Structuring labeled trees for optimal succinctness, and beyond

Paolo Ferragina
Fabrizio Luccio
Giovanni Manzini
S. Muthukrishnan 0001

Consider an ordered, static tree /spl Tscr/ on t nodes where each node has a label from alphabet set /spl Sigma/. Tree /spl Tscr/ may be of arbitrary degree and of arbitrary shape. Say, we wish to support basic navigational operations such as find the parent of node u, the ith child of u, and any child of it with label /spl alpha/. In a seminal work over fifteen years ago, Jacobson (1989) observed that pointer-based tree representations are wasteful in space and introduced the notion of succinct data structures. He studied the special case of unlabeled trees and presented a succinct data structure of 2t + o(t) bits supporting navigational operations in O(1) time. The space used is asymptotically optimal with the information-theoretic lower bound averaged over all trees. This led to a slew of results on succinct data structures for arrays, trees, strings and multisets. Still, for the fundamental problem of structuring labeled trees succinctly, few results, if any, exist even though labeled trees arise frequently in practice, e. g. in the data as in markup text (XML) or in augmented data structures. We present a novel approach to the problem of succinct manipulation of labeled trees by designing what we call the xbw transform of the tree, in the spirit of the well-known Burrows-Wheeler transform for strings. The xbw transform uses path-sorting and grouping to linearize the labeled tree /spl Tscr/ into two coordinated arrays, one capturing the structure and the other the labels. Using the properties of the xbw transform, we (i) derive the first-known (near-)optimal results for succinct representation of labeled trees with O(1) time for navigation operations, (ii) optimally support the powerful subpath search operation for the first time, and (iii) introduce a notion of tree entropy and present linear time algorithms for compressing a given labeled tree up to its entropy beyond the information-theoretic lower bound averaged over all tree inputs. Our xbw transform is simple and likely to spur new results in the theory of tree compression and indexing, and may have some practical impact in XML data processing.

Details

FOCS Conference 2002 Conference Paper

Static Optimality Theorem for External Memory String Access

Valentina Ciriani
Paolo Ferragina
Fabrizio Luccio
S. Muthukrishnan 0001

Data warehouses are increasingly storing and managing large scale string data, and dealing with large volume of transactions that update and search string data. Motivated by this context, we initiate the study of self-adjusting data structures for string dictionary operations, that is, data structures that are designed to be efficient on an entire sequence rather than individual string operations. Furthermore, we study this problem in the external memory model where string data is too massive to be stored in internal memory and has to reside in disks; each access to a disk page fetches B items, and the cost of the operations is the number of pages accessed (I/Os).

Details

I&C Journal 1998 Journal Article

Dynamic Dictionary Matching in External Memory

Paolo Ferragina
Fabrizio Luccio

In thedynamic dictionary matchingproblem, a dictionaryDcontains a set of patterns that can change over time under insertion and deletion of individual patterns. Given an arbitrary textT, we must efficiently list all the dictionary patterns that occur at each text position. We investigate the I/O complexity of this problem for a large dictionary that must be stored in external storage devices. By following a completely new approach, we devise an efficient solution which is based upon the SB-tree data structure (P. Ferragina and R. Grossi, 1995, in“Proc. ACM Symposium on Theory of Computing, ” pp. 693–702), and a novel notion of certificate for the dictionary matching problem. Our data structure can be adapted to efficiently work in main memory and to solve other problems, thus providing a new insight into the nature of the dictionary matching problem.

Details DOI

TCS Journal 1990 Journal Article

String matching with weighted errors

Alan A. Bertossi
Fabrizio Luccio
Elena Lodi
Linda Pagli

In the approximate string matching problem, differences are allowed between the pattern string P and each of its occurrences in the text string T, and one is interested in finding all the occurrences of P in T with at most k differences. We consider here weighted differences (errors) between P and T and develop fast sequential and parallel algorithms. In particular, we allow the following types of errors: mismatch whose weight depends on the mismatching characters, extra character with constant weight, missing character with constant weight, and transposition of two consecutive characters with constant weight. A set of theoretical results allows to extend known algorithms to solve this problem with O(kn) sequential time and O(k + log m) parallel time on a 4PRAM model with max{n + k + 1, m p2} processors, where k is the maximum sum of the error weights, n is the length of T, and m is the length of P.

Details DOI