Loading...
Please wait, while we are loading the content...
Similar Documents
Lower Bounds for External Memory Dictionaries (2003)
| Content Provider | CiteSeerX |
|---|---|
| Author | Brodal, Gerth Stølting Fagerberg, Rolf |
| Description | In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA |
| 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 delta N/B I/Os, then (1) there exists a query requiring N/(M ) O(#) ) I/Os, and (2) there exists a query requiring N M ) I/Os when # is O(B/ N) and N is at least M . For both lower bounds 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. |
| File Format | |
| Publisher Date | 2003-01-01 |
| Access Restriction | Open |
| Subject Keyword | Query Time Update Time Member Query External Memory Dictionary Data Structure Wide Range Upper Bound |
| Content Type | Text |
| Resource Type | Proceeding Conference Proceedings Article |
