2012/09/24 by Belazzougui, Djamal, Boldi, Paolo, Vigna, Sebastiano · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1209.5441
A predecessor (successor) search finds the largest element x- smaller than the input string x (the smallest element x+ larger than or equal to x, respectively) out of a given set S; in this paper, we consider the static case (i.e., S is fixed and does not change over time) and assume that the n elements of S are available for inspection. We present a number of algorithms that, with a small additional index (usually of O(n log w) bits, where w is the string length), can answer predecessor/successor queries quickly and with time bounds that depend on different kinds of distance, improving significantly several results that appeared in the recent literature. Intuitively, our first result has a running time that depends on the distance between x and x^±: it is especially efficient when the input x is either very close to or very far from x- or x+; our second result depends on some global notion of distance in the set S, and is fast when the elements of S are more or less equally spaced in the universe; finally, for our third result we rely on a finger (i.e., an element of S) to improve upon the first one; its running time depends on the distance between the input and the finger.