Gerth Stolting Brodal
ABSTRACT
We study trade-offs between the update time and the query time for comparison based external memory dictionaries. The main contributions of this paper are two lower bound trade offs between the I/O complexity of member queries and insertions: If N < M insertions perform at most δ · N/B I/Os, then (1) there exists a query requiring N/(M. ·~O(δ)) I/Os, and (2) there exists a query requiring Ω(logδlog2N ~ I/Os when δ is O(B/log3 N) and N is at least M2. For both lower bound we describe data structures which give matching upper bounds for a wide range of parameters, thereby showing the lower bounds to be tight within these ranges.
Index Terms
- Lower bounds for external memory dictionaries
Recommendations
Tight lower bounds for query processing on streaming and external memory data
It is generally assumed that databases have to reside in external, inexpensive storage because of their sheer size. Current technology for external storage systems presents us with a reality that, performance-wise, a small number of sequential scans of ...
Lower bounds for multivariate approximation by affine-invariant dictionaries
The problem of approximating locally smooth multivariate functions by linear combinations of elements from an affine-invariant redundant dictionary is considered. Augmenting previous upper bound results for approximation, we establish lower bounds on ...
Correlation lower bounds from correlation upper bounds
Study limitations of correlation as asked by Green-Roy-Straubing.First lower bound on correlation for composite moduli.New two-step (lift and reduce) technique for proving correlation lower bounds.New circuit lower bound for circuits: MAJ ANY o ( n ) ...
Comments