Cache-Oblivious Iterated Predecessor Queries via Range Coalescing
In this paper we develop an optimal cache-oblivious data structure that solves the iterated predecessor problem. Given k static sorted lists L[subscript 1],L[subscript 2],…,L[subscript k] of average length n and a query value q, the iterated predecessor problem is to find the largest element in eac...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer Berlin / Heidelberg
2017
|
| Online Access: | http://hdl.handle.net/1721.1/110844 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0001-6915-0216 |