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
N1 - Funding Information: This research was supported in part by NSF grants CCF 1114809, CCF 1114930, CCF 1217708, IIS 1247726, IIS 1247750, and IIS 1251137.
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
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 -