Problem definitions Element e has a working- set number of l. iff: le elements different from e have been searched for since we last searched for e le:012345 123456 An Implicit Dictionary with the Working-Set Property: Insert(e) insert element e into the dictionary and set / e=0 Delete(e): delete element e from the dictionary Search(e: determine if e is in the dictionary and set e=0 Predecessor(e): find the address of the predecessor of e Successor(e): find the address of the successor of e earmarks undforskringsfond Casper Kejlberg-Rasmussen maDalgo- 4/16 UNIVERSIT CENTER FOR MASSIVE DATA ALGORITHMICSCasper Kejlberg-Rasmussen 4/16 Problem Definitions ▪ Element e has a working-set number of le iff: le elements different from e have been searched for since we last searched for e ▪ An Implicit Dictionary with the Working-Set Property: ▪ Insert(e): insert element e into the dictionary and set le =0 ▪ Delete(e): delete element e from the dictionary ▪ Search(e): determine if e is in the dictionary and set le =0 ▪ Predecessor(e): find the address of the predecessor of e ▪ Successor(e): find the address of the successor of e 1 2 3 4 5 le : 0 1 2 3 4 4 6 5