ACM Paris Kanellakis Theory and Practice Award
Italy - 2022
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.