Abstract 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 for strings – 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 log log n) on a word RAM, and a static predecessor structure for variable-length binary strings with a query performance of O ( |s| B + log |s | + log log n) I/Os, for query argument s, in the cache-oblivious model.