We consider the problem of performing predecessor searches in a bounded universe while achieving query times that depend on the distribution of queries. We obtain several data structures with various properties: in particular, we give data structures that achieve expected query times logarithmic in the entropy of the distribution of queries but with space bounded in terms of universe size, as well as data structures that use only linear space but with query times that are higher (but still sublinear) functions of the entropy. For these structures, the distribution is assumed to be known. We also consider individual query times on universe elements with general weights, as well as the case when the distribution is not known in advance.
Other problems in bounded universes can also be solved in similar ways. A that supports insertion and deletion in time @math , where @math is the difference between the successor and predecessor (in terms of priority) of the query, is known @cite_7 , as well as a data structure for the , wherein the older of two query elements must be determined, that supports query time @math , where @math is the temporal distance between the given elements @cite_14 .
@cite_14 @cite_7
2136838521 1977421134
In this paper we refer to the Temporal Precedence Problem on Pure Pointer Machines. This problem asks for the design of a data structure, maintaining a set of stored elements and supporting the following two operations: insert and precedes. The operation insert(a) introduces a new element a in the structure, while the operation precedes(a, b) returns true iff element a was inserted before element b temporally. In (11) a solution was provided to the problem with worst-case time complexity O(log log n) per operation and O(n log log n) space, where n is the number of elements inserted. It was also demonstrated that the precedes operation has a lower bound of �( log log n) for the Pure Pointer Machine model of computation. In this paper we present two simple solutions with linear space and worst-case constant insertion time. In addition, we describe two algorithms that can handle the precedes(a, b) operation in O(log log d) time, where d is the temporal distance between the elements a and b. Many computer algorithms have embedded in them a subalgorithm called a priority queue which produces on demand an element of extreme priority among elements in the queue. Queues on unrestricted priority domains have a running time of Θ(nlogn) for sequences ofn queue operations. We describe a simple priority queue over the priority domain 1,⋯,N in which initialization, insertion, and deletion takeO(loglogD) time, whereD is the difference between the next lowest and next highest priority elements in the queue. In the case of initialization,D=Θ(N). Finding a least element, greatest element, and the neighbor in priority order of some specified element take constant time. We also consider dynamic space allocation for the data structures used. Space can be allocated in blocks of size Θ(N 1 p ), for small integerp.