TY - GEN
T1 - Cache-oblivious dynamic dictionaries with update/query tradeoffs
AU - Brodal, Gerth Stølting
AU - Demaine, Erik D.
AU - Fineman, Jeremy T.
AU - Iacono, John
AU - Langerman, Stefan
AU - Munro, J. Ian
PY - 2010
Y1 - 2010
N2 - Several existing cache-oblivious dynamic dictionaries achieve O(log B N) (or slightly better O(logB N/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 (1/Bθ(1/log log B)2) logB N + 1/B log2 N) memory transfers. This paper presents a new data structure, the xDict, implementing predecessor queries in O(1/ε logB N/M) worst-case memory transfers and insertions and deletions in O (1/εB 1-ε logB N/M) amortized memory transfers, for any constant ε with 0 < ε < 1. For example, the xDict achieves subconstant amortized update cost when N = M B°(B1-ε), whereas the B-tree's Θ(logB N/M) is subconstant only when N = o(MB), and the previously obtained Θ (1/BΘ(1/(log log B)2) logB N + 1/B log2 N) is subconstant only when N = o(2√B). The xDict attains the optimal tradeoff between insertions and queries, even in the broader external-memory model, for the range where inserts cost between Ω(1/B lg1+ε N) and O(1/lg3 N) memory transfers.
AB - Several existing cache-oblivious dynamic dictionaries achieve O(log B N) (or slightly better O(logB N/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 (1/Bθ(1/log log B)2) logB N + 1/B log2 N) memory transfers. This paper presents a new data structure, the xDict, implementing predecessor queries in O(1/ε logB N/M) worst-case memory transfers and insertions and deletions in O (1/εB 1-ε logB N/M) amortized memory transfers, for any constant ε with 0 < ε < 1. For example, the xDict achieves subconstant amortized update cost when N = M B°(B1-ε), whereas the B-tree's Θ(logB N/M) is subconstant only when N = o(MB), and the previously obtained Θ (1/BΘ(1/(log log B)2) logB N + 1/B log2 N) is subconstant only when N = o(2√B). The xDict attains the optimal tradeoff between insertions and queries, even in the broader external-memory model, for the range where inserts cost between Ω(1/B lg1+ε N) and O(1/lg3 N) memory transfers.
UR - http://www.scopus.com/inward/record.url?scp=77951676777&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77951676777&partnerID=8YFLogxK
U2 - 10.1137/1.9781611973075.117
DO - 10.1137/1.9781611973075.117
M3 - Conference contribution
AN - SCOPUS:77951676777
SN - 9780898717013
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 1448
EP - 1456
BT - Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms
PB - Association for Computing Machinery (ACM)
T2 - 21st Annual ACM-SIAM Symposium on Discrete Algorithms
Y2 - 17 January 2010 through 19 January 2010
ER -