Cache-oblivious dynamic dictionaries with update/query tradeoffs
Several existing cache-oblivious dynamic dictionaries achieve O(logB N) (or slightly better O(logB N over M )) memory transfers per operation, where N is the number of items stored, M is the memory size, and B is the block size, which matches the classic B-tree data structure. One recent struc...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2011
|
| Online Access: | http://hdl.handle.net/1721.1/62807 https://orcid.org/0000-0003-3803-5703 |
| Summary: | Several existing cache-oblivious dynamic dictionaries
achieve O(logB N) (or slightly better O(logB
N over M )) memory
transfers per operation, where N is the number of
items stored, M is the memory size, and B is the
block size, which matches the classic B-tree data structure.
One recent structure achieves the same query
bound and a sometimes-better amortized update bound
of O (...) memory transfers.
This paper presents a new data structure, the xDict,
implementing predecessor queries in O(...)worstcase
memory transfers and insertions and deletions in
O (...) amortized memory transfers, for any constant " with 0 < epsilon < 1. For example, the xDict achieves subconstant amortized update cost when N = ..., whereas the B-tree’s ... is subconstant only when ... is subconstant only when N = .... The xDict attains the optimal tradeoff between insertions and queries, even in the broader external-memory model, for the range where inserts cost between (...) and O(1= lg3 N) memory transfers. |
|---|