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


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


    Other22nd Annual European Symposium on Algorithms, ESA 2014

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


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

    Cite this