The batched predecessor problem in external memory

Michael A. Bender, Martín Farach-Colton, Mayank Goswami, Dzejla Medjedovic, Pablo Montes, Meng-Tsung Tsai

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

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 languageEnglish
Title of host publicationAlgorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings
PublisherSpringer Verlag
Pages112-124
Number of pages13
ISBN (Print)9783662447765
DOIs
StatePublished - 1 Jan 2014
Event22nd Annual European Symposium on Algorithms, ESA 2014 - Wroclaw, Poland
Duration: 8 Sep 201410 Sep 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8737 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference22nd Annual European Symposium on Algorithms, ESA 2014
CountryPoland
CityWroclaw
Period8/09/1410/09/14

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

  • Cite this

    Bender, M. A., Farach-Colton, M., Goswami, M., Medjedovic, D., Montes, P., & Tsai, M-T. (2014). The batched predecessor problem in external memory. In 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