**Reference**:- Erik D. Demaine, Vineet Gopal, and William Hasenplaugh, “Cache-Oblivious Iterated Predecessor Queries via Range Coalescing”, in
*Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS 2015)*, Victoria, British Columbia, Canada, August 5–7, 2015, pages 249–262. **Abstract**:-
In this paper we develop an optimal cache-oblivious data structure that solves
the iterated predecessor problem. Given
*k*static sorted length-*n*lists*L*_{1},*L*_{2}, …,*L*_{k}and a query value*q*, theproblem is to find the largest element in each list which is less than*iterated predecessor**q*. Our solution to this problem, called “range coalescing”, requires*O*(log_{B+1}*n*+*k*/*B*) memory transfers for a query on a cache of block size*B*, which is information-theoretically optimal. The range-coalescing data structure consumes*O*(*k**n*) space, and preprocessing requires only*O*(*k**n*/*B*) memory transfers with high probability, given a tall cache of size*M*= Ω(*B*^{2}). **Availability**:- The paper is available in PDF (686k).
- See information on file formats.
- [Google Scholar search]

See also other papers by Erik Demaine.

Last updated September 2, 2021 by Erik Demaine.