IMFD researcher receives Test-of-Time Award for research that has had a lasting impact for more than 20 years
Gonzalo Navarro was awarded the Imre Simon Test-of-Time Prize for an article that, more than two decades after its publication, continues to influence the development of the field.
IMFD researcher Gonzalo Navarro, a faculty member in the Department of Computer Science (DCC) at the University of Chile, was awarded the Imre Simon Test-of-Time Prize, an honor that recognizes scientific work whose relevance endures and continues to influence the field’s progress over time.
The award was granted for the paper “Position-Restricted Substring Search, ” co-authored with Veli Mäkinen of the University of Helsinki, Finland. The paper addresses a fundamental problem in computer science: how to efficiently index a text and then search for a pattern within a specific region (an interval), determining how many times it appears and at which positions.
The award was presented during the Latin American Theoretical Informatics Symposium (LATIN), held from April 13 to 17 in Florianópolis, Brazil. This award has been given since 2012 to papers presented at LATIN that are considered to be of great relevance and lasting influence. Eligible articles must have been published at least ten years prior to the current edition of the conference. The following criteria, among others, are taken into account: overall impact on the field, including influence on existing lines of research or new ones arising from the work; number of citations; applicability; and impact on other research and in the real world.
A project that opened up new avenues for development
Gonzalo Navarro’s work stands out for three main contributions. First , it poses a problem that is as natural as it is novel—“one that, strangely enough, no one had considered before and on which a great deal of subsequent work has been done to achieve improvements and study variants,” the researcher notes. This type of problem arises, for example, when searching for a motif within a genome in large genomic collections, extracting fragments from documents where a pattern is known to appear, or analyzing information within specific ranges in historical collections.
Second, it offers a simple solution that is difficult to improve upon. “We found that the space we were using could not be optimized without significantly affecting response times, making this one of the few cases where it is clear that more space is needed to solve a problem efficiently,” he explains.
Finally, the article links wavelet trees—a structure for representing sequences, introduced in 2003—with classical structures in computational geometry. “Our work showed that wavelet trees could solve many geometric problems using less space than traditional structures and opened the door to numerous subsequent applications, both within and outside of geometry,” adds the DCC UChile researcher.
The article has been citedmore than 130 times—excluding self-citations— in books, surveys, and master’s and doctoral theses around the world, from 2007 to the present. “That’s a huge impact,” Navarro notes.
Regarding the significance of this recognition, he notes that while Best Paper Awards project the future impact of a piece of work, Test-of-Time awards recognize the actual impact it has had over the years. “Defining a new problem and connecting fields that previously had no dialogue with one another was an important contribution. Furthermore, it is very satisfying to see that a paper presented at a Latin American conference has achieved international impact, and it is a great incentive to keep working.”
—
Source: DCC UChile Communications.