### Abstract

We give lower and upper bounds for the batched predecessor problem in external memory. We study tradeoffs between the I/O budget to preprocess a dictionary S versus the I/O requirement to find the predecessor in S of each element in a query set Q. For Q polynomially smaller than S, we give lower bounds in three external-memory models: the I/O comparison model, the I/O pointer-machine model, and the indexability model. In the comparison I/O model, we show that the batched predecessor problem needs Ω(log _{B} n) I/Os per query element (n=|S|) when the preprocessing is bounded by a polynomial. With exponential preprocessing, the problem can be solved faster, in Θ((log _{2} n)/B) per element. We give the tradeoff that quantifies the minimum preprocessing required for a given searching cost. In the pointer-machine model, we show that with O(n ^{4/3-ε} ) preprocessing for any constant ε>0, the optimal algorithm cannot perform asymptotically faster than a B-tree. In the indexability model, we exhibit the tradeoff between the redundancy r and access overhead α of the optimal indexing scheme, showing that to report all query answers in α(x/B) I/Os, log r=Ω((B/α ^{2})log (n/B)). Our lower bounds have matching or nearly matching upper bounds.

Original language | English |
---|---|

Title of host publication | Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings |

Publisher | Springer Verlag |

Pages | 112-124 |

Number of pages | 13 |

ISBN (Print) | 9783662447765 |

DOIs | |

State | Published - 1 Jan 2014 |

Event | 22nd Annual European Symposium on Algorithms, ESA 2014 - Wroclaw, Poland Duration: 8 Sep 2014 → 10 Sep 2014 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 8737 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 22nd Annual European Symposium on Algorithms, ESA 2014 |
---|---|

Country | Poland |

City | Wroclaw |

Period | 8/09/14 → 10/09/14 |

## Fingerprint Dive into the research topics of 'The batched predecessor problem in external memory'. Together they form a unique fingerprint.

## Cite this

*Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings*(pp. 112-124). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8737 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-662-44777-2_10