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
Previous results WS Ref Insert/ Search(e) Predecessor/Additional prop. Delete(e) Successor(e) words M1986 O(log2 n O(log2 n) None FGMP 2002 O(log 2 n/loglog n)O(log2 n/ loglog n None FG2006 O(log n)amor. O(log n) O(log n) one FG2003 O(log n) O(log n O(log n) None I2001+o(0gn) O(log le O(log le* o(n) BHM 2009 o(log n) O(log /e) exp O(log n O(loglog n) BHM 2009 O(log n) O(log /) exp O(log le*)exp. O(vn) BKT O(log n) O(log le) O(log n) None 2010 BK2011 o(log n) O(log min(p(ey ler Iste)) o(log le+) None e"is the predecessor/successor of e earmarks undforskringsfond Casper Kejlberg-Rasmussen maDalgo- 6/16 UNIVERSIT CENTER FOR MASSIVE DATA ALGORITHMICS
Casper Kejlberg-Rasmussen 6/16 Previous Results Ref. WS prop. Insert/ Delete(e) Search(e) Predecessor/ Successor(e) Additional words M1986 - O(log2 n) O(log2 n) - None FGMP 2002 - O(log2 n/loglog n) O(log2 n/ loglog n) - None FG2006 - O(log n) amor. O(log n) O(log n) None FG2003 - O(log n) O(log n) O(log n) None I2001 + O(log n) O(log le) O(log le*) O(n) BHM 2009 + O(log n) O(log le) exp. O(log n) O(loglog n) BHM 2009 + O(log n) O(log le) exp. O(log le*) exp. O(√n) BKT 2010 + O(log n) O(log le) O(log n) None BK2011 + O(log n) O(log min(lp(e), le, ls(e))) O(log le*) None e * is the predecessor/successor of e
Outline Problem definitions Previous results An Implicit Moveable Dictionary An Implicit Dictionary with the Working-Set Property earmarks undforskringsfond Casper Kejlberg-Rasmussen maDalgo- 7/16 UNIVERSIT CENTER FOR MASSIVE DATA ALGORITHMICS
Casper Kejlberg-Rasmussen 7/16 Outline ▪ Problem Definitions ▪ Previous Results ▪ An Implicit Moveable Dictionary ▪ An Implicit Dictionary with the Working-Set Property
An Implicit Moveable Dictionary A implicit moveable dictionary laid out in memory addresses [iij] Interface Insert-left/right(e): insert element e into the dictionary which grows to the left/right Delete-left/right(e): delete element e from the dictionary which shrinks from the left/right Search e): finds the address of e if e is in the dictionary Predecessor(e): finds the address of the predecessor of e Successor(e): finds the address of the successor of e earmarks undforskringsfond Casper Kejlberg-Rasmussen maDalgo- 8/16 UNIVERSIT CENTER FOR MASSIVE DATA ALGORITHMICS
Casper Kejlberg-Rasmussen 8/16 ▪ A implicit moveable dictionary laid out in memory addresses [i;j] ▪ Interface: ▪ Insert-left/right(e): insert element e into the dictionary which grows to the left/right ▪ Delete-left/right(e): delete element e from the dictionary which shrinks from the left/right ▪ Search(e): finds the address of e if e is in the dictionary ▪ Predecessor(e): finds the address of the predecessor of e ▪ Successor(e): finds the address of the successor of e An Implicit Moveable Dictionary i-1 i j
An Implicit Moveable Dictionary C Uses o(1) Fg dictionaries as black boxes Reca∥ the fg interface Insert-right(e): insert element e into the dictionary which grows to the right Delete-right(e): delete element e from the dictionary which shrinks from the right Search e: finds the address of e if e is in the dictionary Predecessor(e): finds the address of the predecessor of e Successor(e): finds the address of the successor of e earmarks undforskringsfond Casper Kejlberg-Rasmussen maDalgo- 9/16 UNIVERSIT CENTER FOR MASSIVE DATA ALGORITHMICS
Casper Kejlberg-Rasmussen 9/16 An Implicit Moveable Dictionary ▪ Uses O(1) FG dictionaries as black boxes ▪ Recall the FG interface: ▪ Insert-right(e): insert element e into the dictionary which grows to the right ▪ Delete-right(e): delete element e from the dictionary which shrinks from the right ▪ Search(e): finds the address of e if e is in the dictionary ▪ Predecessor(e): finds the address of the predecessor of e ▪ Successor(e): finds the address of the successor of e L C R
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 ALGORITHMICS
Casper 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
