Michael Burrows

ACM Paris Kanellakis Theory and Practice Award

USA - 2022

citation

For inventing the BW-transform and the FM-index which greatly advanced the field of Compressed Data Structures with fundamental impact on Data Compression and Computational Biology

ACM has named Michael Burrows of Google, Paolo Ferragina and Giovanni Manzini of the University of Pisa recipients of the ACM Paris Kanellakis Theory and Practice award for their invention of the  BW-transform and the FM-index which had a major influence on the field of Compressed Data Structures and fundamental impact on Computational Biology.

 In 1994, Michael Burrows and his late coauthor David Wheeler published their paper describing revolutionary data compression algorithm based on a reversible transformation of the input. This transformation, which became known as the ?Burrows-Wheeler Transform? (BWT), was used as the core of the compressor bzip2. bzip2 achieved compression performance superior to the standard of the time: the compressor gzip and others based on Lempel-Ziv parsing. A few years later, Paolo Ferragina and Giovanni Manzini (IEEE FOCS 2000, JACM 2005) showed that by orchestrating the BWT with a new set of mathematical techniques and algorithmic tools it became possible to build a ?compressed index' , that is, a data structure, later called the FM-index, supporting powerful substring searches within a space asymptotically the same as the one used by the best compressors (which do not support queries). Before the FM-index, it seemed unavoidable to incur a significant space penalty for achieving efficient queries. With the FM-index Ferragina and Manzini were able to disprove this common belief. In addition to being a theoretical breakthrough, the simplicity and effectiveness of the FM-index has made it a premier indexing choice for software tools working on large collections of unstructured data, with the most impressive applications in Computational Biology.

 The mathematical and algorithmic tools introduced by Burrows, Wheeler, Ferragina and Manzini have crucially influenced many subsequent results.  This body of research has created the field of Compressed Data Structures, which remains extremely active today. Over the years the BWT and the FM-index have found several applications in many other areas, including Databases and Information Retrieval at large, as shown by numerous papers and patent applications.

 In conclusion, the introduction of the BW Transform by Burrows and Wheeler, and then of the FM-index by Ferragina and Manzini, have had a profound impact on the theory of algorithms and data structures with fundamental advancements to Data Compression and Computational Biology.

Press Release

2022 ACM Paris Kanellakis Theory and Practice Award

Michael Burrows, Google; Paolo Ferragina, University of Pisa; and Giovanni Manzini, University of Pisa, receive the ACM Paris Kanellakis Theory and Practice Award for inventing the BW-transform and the FM-index that opened and influenced the field of Compressed Data Structures with fundamental impact on Data Compression and Computational Biology.

In 1994, Michael Burrows and his late coauthor David Wheeler published their paper describing revolutionary data compression algorithm based on a reversible transformation of the input. This transformation, which became known as the “Burrows-Wheeler Transform” (BWT), was used as the core of the compressor bzip2. bzip2 achieved compression performance superior to the standard of the time.

A few years later, Paolo Ferragina and Giovanni Manzini showed that, by orchestrating the BWT with a new set of mathematical techniques and algorithmic tools, it became possible to build a “compressed index,” later called the FM-index. Before the FM-index, it seemed unavoidable to incur a significant space penalty for achieving efficient queries. With the FM-index, Ferragina and Manzini were able to disprove this common belief. In addition to being a theoretical breakthrough, the simplicity and effectiveness of the FM-index has made it a premier indexing choice for software tools working on large collections of unstructured data, with the most impressive applications in the field of DNA alignment and Computational Biology in general.

The introduction of the BW Transform by Burrows and Wheeler, and then the development of the FM-index by Ferragina and Manzini, have had a profound impact on the theory of algorithms and data structures with fundamental advancements—first and foremost to Data Compression and Computational Biology, but also to a number of applications in many other areas, including Databases and Information Retrieval at large.