An Implicit Moveable Dictionary C L and r will shrink and grow over time L/R might get too small L/R might get too large compared to c We introduce the notion of jobs Grow-left/right -Counters when l/r gets too small Shrink-left/right- Counters when l/r gets too large Jobs run o(1) steps every operation: searches, updates earmarks undforskringsfond Casper Kejlberg-Rasmussen maDalgo- 10/16 UNIVERSIT CENTER FOR MASSIVE DATA ALGORITHMICSCasper Kejlberg-Rasmussen 10/16 An Implicit Moveable Dictionary ▪ L and R will shrink and grow over time ▪ L/R might get too small ▪ L/R might get too large compared to C ▪ We introduce the notion of jobs ▪ Grow-left/right – Counters when L/R gets too small ▪ Shrink-left/right – Counters when L/R gets too large ▪ Jobs run O(1) steps every operation: searches, updates L C R