Packed Memory Structure
o
Operations:
n
Traverse(k)
--
O(k/B)
n
Insert
--
O(log
2
n/B)
n
Delete
-- O(log
2
n/B)
o
Goal:
n
Design a lock-free version of the cache-
oblivious algorithm
n
