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

4 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 (US)
Title of host publicationAlgorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings
PublisherSpringer Verlag
Pages112-124
Number of pages13
ISBN (Print)9783662447765
DOIs
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

Other

Other22nd Annual European Symposium on Algorithms, ESA 2014
CountryPoland
CityWroclaw
Period9/8/149/10/14

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this