Home Page Italiana

Giovanni Manzini

Giovanni Manzini
Department of Computer Science
Viale T. Michel, 11
I-15121 Alessandria (Italy)
Tel. +39 0131 360173 --- Fax. +39 0131 360198
E-Mail: manzXYZ@mfn.unipmn.it (---> replace XYZ with "ini").

I am professor of computer science at the University of "Piemonte Orientale" (Eastern Piedmont).
I received my PhD in Applied Mathematics from the Scuola Normale Superiore of Pisa. I have been Visiting Scientist at the Laboratory for Information and Decisions Systems of the Massachusetts Institute of Technology, and Visiting Assistant Professor at the Department of Computer Science of the Johns Hopkins University. I am also a member of the WebAlgo group of the Institute of Informatics and Telematics of the National Research Council.

Research. My current research interest is the design of algorithms and data structures for solving theoretical and applied problems in the fields of Data Compression and Indexing Data Structures for Massive Data Sets.

Software Projects. Together with colleagues and students I have developed a few software projects related to my research. My current major project is the bwtdisk library for the computation of the Burrows-Wheeler transform in external memory. The main feature of this library is that it stores the input output and intermediate files in compressed form, and that it accesses files on disk only by sequential scans thus taking full advantage of modern caching architectures. A related project is a family of lightweight algorithms for the computation of the Suffix Array and the LCP Array. Although these algorithms are no longer the state-of-the-art, they were the first designed to use a small working space without sacrificing speed, an approach later followed by all the most successful suffix array construction algorithms.
Older projects are a Compression Booster based on the Burrows-Wheeler Transform, a Simple and Fast DNA Compression Algorithm, and two algorithms for the bandwidth minimization problem cited by Knuth in the book: Selected Papers on Analysis of Algorithms.

Miscellanea. I have been invited speaker at the conferences IWOCA '09 and MFCS '99, and invited lecturer at the 2008 Lipari School on Algorithms: Science and Engineering. I have served on the program committee of the conferences SPIRE '08, ICTCS '07, SPIRE '07, SPIRE '06, CPM '05, and FUN '04. I was co-organizer of the DIMACS Workshop: The Burrows-Wheeler Transform: Ten Years Later, and guest editor of a Special Issue of Theoretical Computer Science devoted to the Burrows-Wheeler Transform and its Applications.

Recent Papers

• P. Ferragina, T. Gagie, G. Manzini
  Lightweight Data Indexing and Compression in External Memory.
  Proc. 9th Latin American Theoretical Informatics Symposium (LATIN '10)
  Springer Verlag Lecture Notes in Computer Science n. 6034, 698-711.
  Oaxaca, México, 2010.

• P. Ferragina, G. Manzini
  On Compressing the Textual Web.
  Proc. 3rd ACM International Conference on Web Search and Data Mining (WSDM '10)
  New York City, USA, 2010.

• P. Ferragina, F. Luccio, G. Manzini, S. Muthukrishnan.
  Compressing and Indexing Labeled Trees, with Applications.
  Journal of the ACM, Vol 57, (2009), 1-33.
  (DOI link).

• J. Kärkkäinen, G. Manzini, S. Puglisi
  Permuted Longest-Common-Prefix Array.
  Proc. 20th Symposium on Combinatorial Pattern Matching (CPM '09),
  Lille, France, 2009.
  Springer Verlag Lecture Notes in Computer Science n. 5577, 181-192.
  (DOI link).

• P. Ferragina, R. Giancarlo, G. Manzini
  The Myriad Virtues of Wavelet Trees.
  Information and Computation, Vol. 207, (2009), 849-866.
  (DOI link).

• P. Ferragina, G. Manzini, S. Muthukrishnan, (Editors).
  The Burrows-Wheeler Transform and its applications.
  Theoretical Computer Science. Vol. 387, n. 2, (2007).
  (DOI link).

• P. Ferragina, R. Giancarlo, V. Greco, G. Manzini, G. Valiente
  Compression-based Classification of Biological Sequences and Structures via the Universal Similarity Metric: Experimental Assessment.
  BMC Bioinformatics, 8:252, (2007)
  (DOI link).

• T. Gagie, G. Manzini
  Space-conscious compression.
  Proc. 32nd Int. Symposium on Mathematical Foundations of Computer Science (MFCS '07),
  Cesky Krumlov, Czech Republic, 2007.
  Springer Verlag Lecture Notes in Computer Science, n. 4708, 206-217.
  (DOI link).

• T. Gagie, G. Manzini
  Move-to-Front, Distance Coding, and Inversion Frequencies Revisited.
  Proc. 18th Symposium on Combinatorial Pattern Matching (CPM '07),
  London, Ontario, Canada, 2007.
  Springer Verlag Lecture Notes in Computer Science, n. 4580, 71-82.
  (DOI link).

• P. Ferragina, G. Manzini, V. Mäkinen, G. Navarro
  Compressed Representations of Sequences and Full-Text Indexes
  ACM Transactions on Algorithms. Vol. 3 (2007).
  (DOI link).

List of selected publications