People of ACM - Paolo Ferragina

July 2, 2026

Paolo Ferragina is a Professor of Computer Science at the Sant'Anna School of Advanced Studies in Pisa, Italy. His research has been primarily focused on the design and analysis of algorithms and data structures for data-intensive platforms. He works to apply algorithmic insights to compressed storage, mining, and the search for information in large amounts of data, mainly in the form of texts, graphs and time series. His research has been supported and stimulated in the past by many industrial collaborations, such as Bloomberg (London), Cerved Group (Italy), European Broadcasting Union (Geneve), Google (Zurich), SadasDB (Italy), Software Heritage Archive (France), Spazio Dati (Italy), ST Microelectronics (Italy), Tiscali (Istella's search engine, Italy), Yahoo! Research (Barcelona), etc.

He has authored more than 200 publications in peer-reviewed international journals and conferences. His books include Pearls of Algorithm Engineering (Cambridge University Press, 2023), and four other volumes in Italian and English on cryptography and computational thinking published by Springer, Il Mulino, Boringhieri, and Pisa University Press.

Among his many honors, Ferragina shared the 2022 ACM Paris Kanellakis Theory and Practice Award with Michael Burrows and Giovanni Manzini for contributions to the field of compressed data structures. He was recently named an ACM Fellow for contributions to data structures and algorithms for efficient search and data compression.

You recently gave a Ted Talk where you reviewed the developmental stages of search engines since the early 1990’s. For ACM’s younger members, will you explain how the first search engines (such as AltaVista) worked?

It has been a little more than 35 years since the “internauts” first had the opportunity to search for documents of interest to them on the newly created Web (1991) by specifying a sequence of keywords. The context was very different from the present one: there were just a few internauts and the Web consisted of only a few million well-maintained and reliable documents (pages) belonging to governmental or university sites. The search engines of the era, whose names such as Wanderer and Aliweb are now forgotten, were based on extremely elementary algorithms for searching for the user-specified keywords through meta-information that the authors of the pages had explicitly associated to them. The sudden growth of the Web made this approach ineffective, and new search engines were born with perhaps more familiar names including Altavista, Lycos, Excite, and Yahoo!. These engines boosted the potential of the users’ searches through the textual content of the pages and, given the growth of the Web, introduced for the first time a set of criteria for sorting (ranking) the many possible results of a search. So, the concept of results relevance emerged.

The first significant approach in computing page relevance was aimed at deriving a score for a single word in a page (P) as the product of two factors: the frequency of that word in P and its rarity within the indexed page collection. The net result was that stop words such as articles or prepositions got a very low relevance score in every page of the collection and thus they were automatically marked as “not interesting” for any query. More surprisingly, other words that might appear “interesting” were scored low (or even zero) by that formula if most or all documents in the collection contained those words, just because they would be not discriminative for a search query.

Moving from scoring individual words to pages was then easy, a page was modelled as a sequence of real numbers, one per distinct word occurring in the indexed page collection. Each number was computed through the formula above, that takes the name TF-IDF (Term Frequency–Inverse Document Frequency). This implies that the vector (now known as embedding) is sparse because only a few distinct words occur in P, and thus the others take a score of 0. A query may be seen as a very short document consisting of a few words. Thus, its vector is very sparse also.

Now, given this vectorized representation of pages and queries, such generation of search engines measured the relevance of a page (P) to a query (Q) by just computing the cosine similarity between their vectors: a measure that returns a value in [0;1] and tends to be 1 as the vector of P and the one of Q are very close to each other in terms of the angle they form in a multi-dimensional space. Although talking about angles, this measure can be computed easily by multiplying and summing the components of P’s and Q’s vectors, thus making this formula efficiently computable by modern computers. However, it goes without saying that Altavista and its competitors could not compare Q’s vector against all page vectors, being them millions in number, so they needed to design new algorithmic techniques to solve efficiently this challenging geometric problem (approximate nearest neighbor). Something that they did with some success, as all Web users got relevant results to most of their queries in a few milliseconds.

Their results were excellent as long as the documents available on the Web were of high quality. However, as both use of the Web in the business sphere and knowledge of how search engines evaluated the page relevance spread, many users—especially companies—began to build pages in such a way as to influence search results (a practice now known as spamming). The technique used was to include numerous words in the Web page that had little or nothing to do with its content but were related to other frequent queries by users, written in the same color as the page’s background so that the reader could not see them—but the search engine did!

How did graph algorithms, which analyze relationships and networks within big data, move search engines to a new level of sophistication?

As soon as it was established that the content of Web pages alone was insufficient to determine their relevance to users’ queries, studies started to consider the Web as a network of pages defined by pointers between them (called hyperlinks). It soon became clear that the properties of this network should also be used to improve the mechanism for evaluating the relevance of the pages. The 1997–1998 biennium marked the beginning of the second generation of search engines and coincided with Google’s birth, with its famous PageRank algorithm crucially based on the interconnections between Web pages.

In the first version of Google, the relevance of a page depended on its content, as in Altavista, but also on what other pages contained about that page. These wordings referring to other pages, called “anchor-texts”, are those associated with hyperlinks and are usually colored in blue or underlined in Web pages; and on the calculation of the “rank” of each page P, called PageRank, which did not depend on the query but captured the relevance (aka, centrality) of the page within the Web network as a function of the number and of the relevance of the pages pointing to it. This is a recursive definition, well-based mathematically and far more complex than the simple count of the hyperlinks pointing to that page. Since its debut, PageRank has proven to be one of the most important and persistent measures used to determine the relevance of a “node” in a network of objects—be they a user, a restaurant, a tweet, or just a Web page. The concept has evolved over the years, but its original definition and properties are still valid and led to the definition of many other important algorithms for the so-called Network Science. Nonetheless, this original algorithm was subject to spamming too, with a technique called “Google bombing.”

Why are algorithms that compress data important? Along with your colleague Giovanni Manzini, you developed the FM (Ferragina Manzini) Index. The FM index enabled powerful substring searches for more efficient queries. How was the FM Index a theoretical breakthrough?

Memory is one of the most contended hardware resources in large-scale applications such as generative AI, recommendation systems, and data-intensive software platforms. Memory, in fact, often becomes the performance bottleneck in the I/O critical path that connects computing with storage. Due to limited memory capacity, more applications have to explore and exploit the memory beyond traditional local main memory, including solid-state or mechanical disks, memory on remote servers, or tapes. These non-local far memories can virtually expand the internal memory size but they are much slower than the latter, so systems leverage local memory as a cache by transparently swapping memory pages between local and far memory, which unfortunately causes read or write amplification.

In order to deliver high performance and achieve cost-efficiency, we need to carefully consider memory overhead that comes from the differential requirements of high-level applications and low-level devices. In those contexts, computational-friendly data compression is critical , if not mandatory. With this linguistic expression, we mean compression formats that combine effective compression ratios with efficient random access to the compressed data that, therefore, do not need the full decompression.

Our FM Index was the first theoretical result to show that it is possible to compress data up to their kth order entropy (a metric that quantifies the uncertainty in a data stream) and be still able to support sophisticated search operations over them decompressing only a small (controlled) compressed part. Nowadays the FM Index supports string searches in several columnar and graph DBs, data-intensive platforms, and various genomic tools, such as BWA (Burrows Wheeler Aligner) and BowTie.

Theoretically speaking, the FM Index paved the way to a new algorithmic field now known as compressed data structures. Compressed data structures have yielded contributions to all data types: arrays, hash tables, vectors, trees and graphs. Since these data structures can execute and complete their operations within the internal memory, its advantage is virtually boosted to larger data sizes, data movements gets reduced not only through the memory and (far) storage hierarchy, but also between DRAM and caches, often inducing better performance by the algorithms that use that storage approach.

In one of your most cited recent papers you (along with five co-authors) present a machine learning approach to evaluate the performance of soccer players. Why does the soccer scenario present an interesting challenge?

In my scientific life I liked to explore the application of Algorithmics to many applicative fields, ranging from DNA to Web, from business to health, and ultimately to soccer. Soccer represents one of the most economically, socially and culturally relevant sport sectors worldwide, involving millions of athletes across professional, semi-professional, youth and amateur contexts. And soccer is the Italian sport, so that any algorithmic invention there would make my group much more famous than winning a Turing Award! Being serious, the rapid growth of wearable technologies, both devices and robotics, is allowing us to grasp more and more multimodal data on which multimedia AI and cross-modal information retrieval could provide more effective integration and semantic exploration of heterogeneous data streams, including videos, images, text annotations, and temporal sensor data.

This also allows us to derive meaning and knowledge for various applications such as injury prediction, workload monitoring, performance evaluation, tactical analysis, and rehabilitation support. However, despite the growing scientific and industrial interest in AI applications in soccer, existing research and implementations remain highly fragmented, confined to commercial platforms, and thus insufficiently accessible, especially to non-top teams. This will be one of the main challenges of our group in the coming years.

In the paper you mention from 2019, we were one of the first research groups to study how the availability of massive data capturing all the events generated during a match (tackles, passes, shots, etc.) could be exploited to design and implement PlayeRank, a data-driven framework that offers a principled multi-dimensional and role-aware evaluation of the performance of soccer players. We showed that the ratings produced by PlayeRank significantly improved the algorithms known at that time, and more interestingly, we discovered interesting patterns about what distinguishes the top players from the others. Seven years have passed since that result and many more Deep Learning algorithms and (multimodal) Generative AI tools have progressively emerged as enabling technologies capable of reshaping how physiological, biomechanical, technical and tactical information is processed, interpreted, and translated into effective operational decisions and interventions.

I think that this is a very challenging multi- and inter-disciplinary scenario that needs the contribution of “hybrid” teams involving not only computer scientists but also physicians, sport scientists, trainers, and managers, just to mention a few. I believe that my university has all these expertise to contribute to achieve successfully this goal.

Recently your research focus has shifted to the interplay between machine learning and data compression. What are a few important trends in this area?

We are investigating this interplay from several scientific angles. We started in 2018 with the design of the so-called “learned data structures”—a field that now abounds with algorithmic proposals both in terms of theoretical results and practical solutions. The distinguishing trait of learned data structures is the ability to reveal and exploit patterns and trends in the input data for achieving more efficiency in time and space, compared to previously known (traditional) data structures. The key design idea consists of augmenting—and sometimes even replacing—classic data-structural building blocks, such as tree nodes or hash tables, with machine learning (ML) models which are better suitable to “notice interesting patterns when they have convenient access to masses of data.” This feature, combined with proper data structural design elements and algorithms has led to outstanding improvements in space occupancy and time efficiency over a plethora of searching and mining problems.

The key algorithmic design challenge in all of those results is to choose the “right model”, namely one that trades properly between its capacity to exploit patterns in the input data, and its space-time efficiency. Most of the time, adopting the most sophisticated model is not advantageous, and simple data structures (such as binary search trees) are much faster and almost as compact as their learned counterparts.

Now we are investigating extensions of those ideas to the context of VectorDBs and GraphDBs, and we are studying the interplay of traditional and learned techniques in lossless compressing and indexing various types of data, with a particular attention to massive source-code collections, thanks to our collaboration with the Software Heritage Archive  and a project sponsored by the Alfred P. Sloan Foundation . The ambitious goal of this project is to enhance the Software Heritage (SWH) archive, the world's largest collection of software source code, by developing advanced compression and search capabilities through more efficient lossless compression methods (possibly based on the predicting powers of LLMs). Our plan is to also develop novel code-to-code search functionality which should make its computational infrastructure more sustainable and scalable. These enhancements could empower diverse applications from the explanation of AI generation of source code, to verifying provenance of code (possibly AI-generated), or supporting new cybersecurity applications.