Compact Approximation of Lattice Functions with Applications to Large-Alphabet Text Search

Paolo Boldi, Sebastiano Vigna

We propose a very simple randomised data structure that stores an approximation from above of a lattice-valued function. Computing the function value requires a constant number of…