Paper by Erik D. Demaine
- 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
L1, L2, …, Lk and a query value q, the iterated predecessor
problem is to find the largest element in each list which is less than q.
Our solution to this problem, called “range coalescing”, requires
O(logB+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 = Ω(B2).
- Availability:
- The paper is available in PDF (686k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
BibTeX file.
Last updated March 12, 2024 by
Erik Demaine.