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.

BibTeX

@InProceedings{CacheFractional_WADS2015,
  AUTHOR        = {Erik D. Demaine and Vineet Gopal and William Hasenplaugh},
  TITLE         = {Cache-Oblivious Iterated Predecessor Queries via Range Coalescing},
  BOOKTITLE     = {Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS 2015)},
  bookurl       = {http://wads2015.cs.uvic.ca/},
  ADDRESS       = {Victoria, British Columbia, Canada},
  MONTH         = {August 5--7},
  YEAR          = 2015,
  PAGES         = {249--262},

  withstudent   = 1,
  doi           = {https://dx.doi.org/10.1007/978-3-319-21840-3_21},
  dblp          = {https://dblp.org/rec/conf/wads/DemaineGH15},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1007/978-3-319-21840-3_21">SpringerLink</A>.},
}

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₁, L₂, …, L_k 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(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²).

Comments:

This paper is also available from SpringerLink.

Availability:

The paper is available in PDF (686k).

See information on file formats.

[Google Scholar search]