Inventors of BW-transform and the FM-index Receive Kanellakis Award

The ACM Paris Kanellakis Theory and Practice Award has been presented to Michael Burrows, Google, Paolo Ferragina, University of Pisa and Giovanni Manzini, University of Pisa. The trio was honoured 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, Burrows and his late co-author David Wheeler published their paper describing revolutionary data compression algorithm based on a reversible transformation of the input—the “Burrows-Wheeler Transform” (BWT). A few years later, Ferragina and 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. The introduction of the BW Transform and the development of the FM-index have had a profound impact on the theory of algorithms and data structures with fundamental advancements.