Abstract
In this paper we present an implicit dynamic dictionary with the working-set property, supporting insert(e) and delete(e) in O(log n) time, predecessor(e) in O(log l_{p(e)}) time, successor(e) in O(log l_{s(e)}) time and search(e) in O(log min(l_{p(e)},l_{e}, l_{s(e)})) time, where n is the number of elements stored in the dictionary, l_{e} is the number of distinct elements searched for since element e was last searched for and p(e) and s(e) are the predecessor and successor of e, respectively. The time-bounds are all worst-case. The dictionary stores the elements in an array of size n using *no* additional space. In the cache-oblivious model the log is base B and the cache-obliviousness is due to our black box use of an existing cache-oblivious implicit dictionary. This is the first implicit dictionary supporting predecessor and successor searches in the working-set bound. Previous implicit structures required O(log n) time.
| Original language | English |
|---|---|
| Book series | Leibniz International Proceedings in Informatics |
| Volume | 25 |
| Pages (from-to) | 11-12 |
| Number of pages | 2 |
| ISSN | 1868-8969 |
| DOIs | |
| Publication status | Published - 2014 |
| Event | Symposium on Theoretical Aspects of Computer Science - Lyon, France Duration: 5 Mar 2014 → 8 Mar 2014 Conference number: 31 |
Conference
| Conference | Symposium on Theoretical Aspects of Computer Science |
|---|---|
| Number | 31 |
| Country/Territory | France |
| City | Lyon |
| Period | 05/03/2014 → 08/03/2014 |
Keywords
- working-set property
- dictionary
- implicit
- cache-oblivious
- worst-case
- external memory
- I/O efficient