Johannes Fischer erhält den 2022 Imre Simon Test-of-Time Award für seinen Artikel "Optimal Succinctness for Range Minimum Queries" (Latin 2010)
Aus der Laudatio:
Range Minimum Query (RMQ) is used on arrays to find the position of an element with the minimum value between two specified indices. This simple problem — in its formulation — has many different applications including the fundamental problem of finding the least common ancestor (LCA) of two nodes in a tree or the longest common prefix problem (LCP), as well as other exact and approximate string matching problems. In order to make RMQs very efficient, there has been a long quest for preprocessing algorithms and data structures with which RMQs could later be answered very efficiently, ideally in constant time. The first non-trivial solution to the problem, presented by Berkman and Vishkin (SIAM J. Computing, 1993), required linear time for pre- processing and linearithmic space (O(n log(n)) bits, for an array of n items). Many authors have thus been looking for succinct data structures; in this case, data structures using a linear number of bits, without sacrificing the preprocessing or the query times. The LATIN paper of 2010 presented the first scheme achieving O(1) time for queries, O(n) preprocessing time, using only 2n + o(n) bits in the final succinct data structure to answer queries — thus meeting the information-theoretic bound -, and only n + o(n) additional bits during construction time. To achieve the space and time efficiency above, the paper introduced 2d-min-heaps, which are equivalent to the also well-known LRM-trees (left-to-right minima trees) of Navarro and Sadakane (ACM Trans. Algorithms, 2014). The 2d-min-heaps were originally intended to efficiently support RMQs, but they have proved also very useful for several other applications, e.g., the succinct representation of ordinal trees. Fischer’s contributions in the LATIN 2010 paper made their way into the journal article Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays, published in SIAM Journal on Computing 40(2):465–492, together with Volker Heun, in 2011. That paper became very influential in the area of compressed and succinct data structures, and it is a milestone in the quest for the best solutions in time and space to RMQs, with numerous quotations and references too. The relevance of the problem addressed, the originality of the technique used to solve it, the clarity of presentation, and the continued and widespread recognition of this contribution throughout the years since its publication heavily weighed in the committee’s choice.