Loading...
Please wait, while we are loading the content...
Similar Documents
Optimal resilient dynamic dictionaries (2007)
| Content Provider | CiteSeerX |
|---|---|
| Author | Moruz, Gabriel Jørgensen, Allan Grønlund Brodal, Gerth Stølting Mølhave, Thomas Fagerberg, Rolf |
| Description | In Proc. 14th Annual European Symposium on Algorithms |
| Abstract | Abstract. In the resilient memory model any memory cell can get cor-rupted at any time, and corrupted cells cannot be distinguished from uncorrupted cells. An upper bound, δ, on the number of corruptions and O(1) reliable memory cells are provided. In this model, a data structure is denoted resilient if it gives the correct output on the set of uncor-rupted elements. We propose two optimal resilient static dictionaries, a randomized one and a deterministic one. The randomized dictionary supports searches in O(log n + δ) expected time using O(log δ) random bits in the worst case, under the assumption that corruptions are not performed by an adaptive adversary. The deterministic static dictionary supports searches in O(log n + δ) time in the worst case. We also in-troduce a deterministic dynamic resilient dictionary supporting searches in O(log n + δ) time in the worst case, which is optimal, and updates in O(log n+ δ) amortized time. Our dynamic dictionary supports range queries in O(log n + δ + k) worst case time, where k is the size of the output. 1 |
| File Format | |
| Publisher Date | 2007-01-01 |
| Access Restriction | Open |
| Subject Keyword | Optimal Resilient Dynamic Dictionary Reliable Memory Cell Optimal Resilient Static Dictionary Uncorrupted Cell Resilient Memory Model Memory Cell Data Structure Random Bit Upper Bound Adaptive Adversary Correct Output Deterministic One Dynamic Dictionary Support Range Query Case Time Randomized Dictionary Support Search Uncor-rupted Element Deterministic Static Dictionary Support Search |
| Content Type | Text |
| Resource Type | Conference Proceedings Article |
