An algorithm for finding predecessors in integer sets

This paper presents a data structure that supports the operations of inserting and deleting elements drawn from a universe U={0⋯u-1} into a set S, and for finding the predecessors of elements of U in S. We consider both random inputs and worst-case inputs. In the case of random inputs, we show that each operation can be performed in constant time, with high probability, provided that the total number of operations is at most polynomial in u. In Yao’s cell probe model, the algorithm uses O(n) space, where n is the maximum size that S achieves during the sequence of operations. The algorithm can be implemented with the same performance in the RAM model with word size O(log u) at the cost of performing uϵ preprocessing operations, and using u? additional space, for any fixed ϵ > 0. The algorithm can be modified so that even in the worst case no operation takes more than O(log log u) time, at the cost of using O(u) additional space.

Duke Scholars

Author Bruce Maggs Computer Science