Cache-Oblivious Implicit Predecessor Dictionaries with the Working-Set Property Casper Kejlberg-Rasmussen Joint work with Gerth Stolting Brodal maDalgo===。 CENTER FOR MASSIVE DATA ALGORITHMICS Danmarks Grundforskningsfond Danish National AARHUS Research Foundation UNIVERSITY
Casper Kejlberg-Rasmussen 1/16 Cache-Oblivious Implicit Predecessor Dictionaries with the Working-Set Property Casper Kejlberg-Rasmussen Joint work with Gerth Stølting Brodal
Outline Problem definitions Previous results An Implicit Moveable Dictionary An Implicit Dictionary with the Working-Set Property earmarks undforskringsfond Casper Kejlberg-Rasmussen maDalgo- 2/16 UNIVERSIT CENTER FOR MASSIVE DATA ALGORITHMICS
Casper Kejlberg-Rasmussen 2/16 Outline ▪ Problem Definitions ▪ Previous Results ▪ An Implicit Moveable Dictionary ▪ An Implicit Dictionary with the Working-Set Property
Problem definitions Implicit model. All operations from the ram It is not allowed to create words only to move them All n words have to be in continuous positions Often it is assumed that all elements are distinct Fundamental trick; encode a bit in a pair of elements X 0, if X=min(x y) 1, if X=max(x,y) earmarks undforskringsfond Casper Kejlberg-Rasmussen maDalgo- 3/16 UNIVERSIT CENTER FOR MASSIVE DATA ALGORITHMICS
Casper Kejlberg-Rasmussen 3/16 Problem Definitions ▪ Implicit model: ▪ All operations from the RAM ▪ It is not allowed to create words, only to move them ▪ All n words have to be in continuous positions ▪ Often it is assumed that all elements are distinct ▪ Fundamental trick: encode a bit in a pair of elements ... 1 n x y b b= 0, if x=min(x,y) 1, if x=max(x,y)
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 ALGORITHMICS
Casper 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
Outline Problem definitions Previous results An Implicit Moveable Dictionary An Implicit Dictionary with the Working-Set Property earmarks undforskringsfond Casper Kejlberg-Rasmussen maDalgo- 5/16 UNIVERSIT CENTER FOR MASSIVE DATA ALGORITHMICS
Casper Kejlberg-Rasmussen 5/16 Outline ▪ Problem Definitions ▪ Previous Results ▪ An Implicit Moveable Dictionary ▪ An Implicit Dictionary with the Working-Set Property