Improved data structures for the orthogonal range successor problem

AbstractLet P be a set of n points that lie on an n×n grid. The well-known orthogonal range reporting problem is to preprocess P so that for any query rectangle R, we can report all points in P∩R efficiently. In many applications driven by the information retrieval or the bioinformatics communities, we do not need all the points in P∩R, but need only just the point that has the smallest y-coordinate; this motivates the study of a variation called the orthogonal range successor problem. If space is the major concern, the best-known result is by Mäkinen and Navarro, which requires an optimal index space of n+o(n) words and supports each query in O(logn) time. In contrast, if query time is the major concern, the best-known result is by Crochemore et al., which supports each query in O(1) time with O(n1+ε) index space. In this paper, we first propose another optimal-space index with a faster O(logn/loglogn) query time. The improvement stems from the design of an index with O(1) query time when the points are restricted to lie on a narrow grid, and the subsequent application of the wavelet tree technique to support the desired query. Based on the proposed index, we directly obtain improved results for the successive indexing problem and the position-restricted pattern matching problem in the literature. We next propose an O(n1+ε)-word index that supports each query in O(1) time. When compared with the result by Crochemore et al., our scheme is conceptually simpler and easier for construction. In addition, our scheme can be easily extended to work for high-dimensional cases