TY - GEN

T1 - The batched predecessor problem in external memory

AU - Bender, Michael A.

AU - Farach-Colton, Martín

AU - Goswami, Mayank

AU - Medjedovic, Dzejla

AU - Montes, Pablo

AU - Tsai, Meng Tsung

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84958528757&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958528757&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-44777-2_10

DO - 10.1007/978-3-662-44777-2_10

M3 - Conference contribution

AN - SCOPUS:84958528757

SN - 9783662447765

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

SP - 112

EP - 124

BT - Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings

PB - Springer Verlag

T2 - 22nd Annual European Symposium on Algorithms, ESA 2014

Y2 - 8 September 2014 through 10 September 2014

ER -