Making Deterministic Signatures Quickly

We present a new technique of universe reduction. Primary applications are the dictionary problem and the predecessor problem. We give several new results on static dictionaries in different computational models: the Word RAM, the Practical RAM, and the cache-oblivious model. All algorithms and data structures are deterministic and use linear space. Representative results are: a dictionary with a lookup time of O(log log n) and construction time of O(n) on sorted input on a Word RAM, and a static predecessor structure for variable and unbounded length binary strings that in the cache-oblivious model has a query performance of O ( |s| + log |s|) I/Os, for B query argument s