Deterministic superimposed coding with applications to pattern matching

A superimposed code is a set of binary vectors having the property that no vector is contained in a boolean sum (i.e. bitwise OR) of a small number of others. Such codes are used in information retrieval for constructing so-called signature files; they also have applications in other areas. In this paper we introduce a new notion of data-dependent superimposed codes and give a deterministic algorithm for constructing short such codes. We then show that these codes can be used to achieve an almost optimal de-randomization of several pattern matching algorithms, including the almost-linear algorithm for tree pattern matching developed recently. Thus, we give the first almost-linear time deterministic algorithms for these problems