Thy Shalt Come To The TGIW : Thy Shalt Come To The TGIW From: shuchi@cs.cmu.edu
Subject: TGIW
When: Tonight, 6:00pm
Where: WeH 7220
Nikhil will be talking about his work on Online Scheduling at this week's TGIW. This is joint work with Kedar, Jochen and Amitabh. The schedule and abstract are given below. First years are especially encouraged to attend. […]
Back From The Future : Back From The Future Efficient Finger Search Using Eager Walk
List of Colors : List of Colors Color
Color
Color
Color
Color
Color
Color
Color Color
Color
Color
Important Terms/Phrases : Important Terms/Phrases Catenable (Cannibal on Halloween…)
File
“n” (no “m”)
Nine (no “line”)
Node
Theory
Three (“free” lunch?)
Set Intersection : Set Intersection You have two sets A := {x1, x2, …, xa}, B := {y1, y2, …, yb}
You represent them as BSTs TA and TB
Give an algorithm to find A Å B BST:
Balanced Search Tree
Easy Solution : Easy Solution WLOG assume a ¸ b.
For each yj 2 TB, ask if yj 2 TA.
O(b log a) time Is this optimal?
An Insight : An Insight A := {1,2,3, …, 15} B := {1,3,10,11}
Decisions at “top” mostly the same Show More
1979 Brown, Tarjan : Need b searches in TA, so O(b log a).
The b search paths overlap at least log b levels before all disjoint.
Spend O(b) to cache decisions in top O(log b) levels may save W(b log b).
O(b log(a) – b log(b) + b) = O(b log(a/b)) 1979 Brown, Tarjan
Enters Finger Search : Enters Finger Search FSearch(fx, y):
Given a finger fx, return finger fy in O(log d) time, where d is the distance between x and y in the sorted order.
If y 2 T, return fy+ for smallest y+ 2 T fx: finger on key x
Why Bother Finger Searching? : Why Bother Finger Searching? Another simple intersection algorithm:
f = f0 /* finger on conceptual “y0” */ For i = 1 to b /* in-order walk TB */
f = FSearchA(f, yi) if f on yi then print yi
Next i
Running Time Analysis : Running Time Analysis Do b finger searches in TA.
Suppose distances are d1, d2, …, db.
Know åi di · a
Total time = O(log d1 + log d2 + … + log db)
Time maximized when all di’s are equal, so let di = a/b.
Total time = O(b log(a/b))
Iterators : Iterators Initialization
Termination Condition
Increment
De-referencing InOrder(tree) :=
Iterator it;
for(it.init(tree);
it.hasMore();
it++)
{ // print (*it).node
}
Special Case : Special Case In-order Walk
Complete Binary Search Tree : Complete Binary Search Tree
In-order Walk / Enumeration : In-order Walk / Enumeration Also known as symmetric walk
Node Size : Node Size struct Node
{
int key;
Node *left, *right;
}; Node needs at least three machine words
Running Time Analysis : Running Time Analysis InOrder(node) :=
If(node != Nil)
{
InOrder(node.left);
// print node.key
InOrder(node.right);
} How about time between two consecutive outputs?
Running Time Analysis : Running Time Analysis InOrder(node) :=
If(node != Nil)
{
InOrder(node.left);
// print node.key
InOrder(node.right);
} Amortized O(1) per node
Space Requirement : Space Requirement O(log n) activation records on the program stack InOrder(node) :=
If(node != Nil)
{
InOrder(node.left);
// print node.key
InOrder(node.right);
}
So Far So Good? : So Far So Good? #keys #pointers
I wonder... : I wonder... Worst case O(1)?
Why Bother? : Why Bother? Fast sequential access slow slow slow
Let's Trade : Let's Trade Neighbor pointers Node needs 2 extra words
Faster Insertion : Faster Insertion Indexed Sequence
(B+ Trees) Doubled node ) Doubled space
Oh Well... : Oh Well...
Two Terms : Two Terms Right parent is first ancestor to the right
Two Terms : Two Terms 7 5 6 3 1 2 4 8 15 13 14 11 9 10 12 h 12, 10, 9 i is
“Left spine” of 12 “RL spine” of 8
Our Idea : Our Idea Pre-compute right child’s left spine
How? Discover nodes step-by-step
Our "Hand" Iterator : Our "Hand" Iterator Stack of
(Node *node, Stack *spine)
(n,s) Right Parent Stack This Hand is not valid. Just for illustration. (n,s) (n,s)
Stack of Stacks : Stack of Stacks 7 5 6 3 1 2 4 8 15 13 14 11 9 10 12 Right Parent Stack (RPS) (n,s)
Initialization : Initialization Left spine of root
maintained during
key insertions RPS
De-reference : De-reference Peek top of stack RPS
Termination : Termination Is stack empty? RPS
Increment : Increment Three easy steps
1. Pop top cell and keep its spine (SS)
2. Extend spine of new top cell
3. Prepend SS to RPS RPS
1 2 : 1 2 Three easy steps
1. Pop top cell and keep its spine (SS)
2. Extend spine of new top cell
3. Prepend SS to RPS RPS
1 2 : 1 2 Three easy steps
1. Pop top cell and keep its spine (SS)
2. Extend spine of new top cell
3. Prepend SS to RPS RPS
1 2 : 1 2 Three easy steps
1. Pop top cell and keep its spine (SS)
2. Extend spine of new top cell
3. Prepend SS to RPS RPS
Hand on 2 : Hand on 2 RPS
2 3 : 2 3 Three easy steps
1. Pop top cell and keep its spine (SS)
2. Extend spine of new top cell
3. Prepend SS to RPS RPS SS
2 3 : 2 3 Three easy steps
1. Pop top cell and keep its spine (SS)
2. Extend spine of new top cell
3. Prepend SS to RPS SS RPS
2 3 : 2 3 Three easy steps
1. Pop top cell and keep its spine (SS)
2. Extend spine of new top cell
3. Prepend SS to RPS RPS
3 4 : 3 4 Three easy steps
1. Pop top cell and keep its spine (SS)
2. Extend spine of new top cell
3. Prepend SS to RPS RPS
3 4 : 3 4 Three easy steps
1. Pop top cell and keep its spine (SS)
2. Extend spine of new top cell
3. Prepend SS to RPS RPS
3 4 : 3 4 Three easy steps
1. Pop top cell and keep its spine (SS)
2. Extend spine of new top cell
3. Prepend SS to RPS RPS
4 5 : 4 5 Three easy steps
1. Pop top cell and keep its spine (SS)
2. Extend spine of new top cell
3. Prepend SS to RPS SS RPS
4 5 : 4 5 Three easy steps
1. Pop top cell and keep its spine (SS)
2. Extend spine of new top cell
3. Prepend SS to RPS SS RPS
4 5 : 4 5 Three easy steps
1. Pop top cell and keep its spine (SS)
2. Extend spine of new top cell
3. Prepend SS to RPS RPS
Hand on 5 : Hand on 5 RPS
Checkpoint : Checkpoint Do you understand how to this algorithm manipulate the Hand?
Pop Quiz : Pop Quiz This is the Hand on 5, so what is the Hand on 6?
Pop Quiz : Pop Quiz Three easy steps
1. Pop top cell and keep its spine (SS)
2. Extend spine of new top cell
3. Prepend SS to RPS
Answer : Answer 7 5 6 3 1 2 4 8 15 13 14 11 9 10 12 5 6
Correctness : Correctness A node is either on left spine or not.
If on left spine, init finds it.
If not one left spine, another node must be on its left.
Running Time Analysis : Running Time Analysis Increment has three easy steps
1. Pop top cell and O(1) keep its spine (SS)
2. Extend spine of O(1) new top cell
3. Prepend SS to RPS O(1)
Total Time Worst case O(1)
Space Requirement : Space Requirement Starts with log(n) cells
Each increment 1. Pop top cell and -1 keep its spine (SS) 2. Extend spine of +1 new top cell
3. Prepend SS to RPS +0
Total change 0
How are we doing? : How are we doing?
General Case : General Case Finger Search
1980 Brown, Tarjan : 1980 Brown, Tarjan Level-linked 2-3 trees 7 5 6 3 1 2 4 8 15 13 14 11 9 10 12 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 / 5 pointers per node
Since 1980... : Since 1980... 1988 – Tarjan, Van Wyk Heterogeneous Red-Black
1989 – Pugh Skip List
1995 – Seidel, Aragon Treaps
1996 – Kaplan, Tarjan Purely Functional Catenable Sorted List
2001 – Blandford, Blelloch Heterogeneous Treaps
Since 1980... : Since 1980... 1988 – Tarjan, Van Wyk Heterogeneous Red-Black
1989 – Pugh Skip List
1993 – Cole (conjectured Splay trees by Sleator, Tarjan 1985)
1995 – Seidel, Aragon Treaps
1996 – Kaplan, Tarjan Purely Functional Catenable Sorted List
2001 – Blandford, Blelloch Heterogeneous Treaps
1993 – Cole (conjectured Splay trees by Sleator, Tarjan 1985)
Space-Time Price Chart : Space-Time Price Chart
Our Forward Solution : Our Forward Solution Same data structure as in-order walk!
Pictorial Hand : Pictorial Hand
Global Level : Global Level TODO: show how the invariant is. In particular, create a picture saying how long the spines are (for all nodes, it’s all up to the point where the key on top of it on the stack is)
An Example : An Example curr RP peer
Hand Invariants : Hand Invariants Let stack be labeled upwards
1. What nodes should be on RPS?
2.How long are their spines? 8 4 3 6 x3 x2 x1 s3 s2 s1 Skip Invariants
Hand Invariants : Hand Invariants Let stack be h(xn,sn),(xn-1,sn-1),…,(x1,s1)i
1. x1 is on right spine of tree Æ 8 j > 1 : xj-1 is RP of xj
2. 8 j : sj is a prefix of left spine of xj’s right child Æ 8 j : |sj| = h(xj) – 1 – h(xj+1) 8 4 3 6 x3 x2 x1 s3 s2 s1
Hand Invariants : Hand Invariants Let stack be h(xn,sn),(xn-1,sn-1),…,(x1,s1)i
1. x1 is on right spine of tree Æ 8 j > 1 : xj-1 is RP of xj
2. 8 j : sj is a prefix of left spine of xj’s right child Æ 8 j : |sj| = h(xj) – 1 – h(xj+1) 8 4 3 6 x3 x2 x1 s3 s2 s1
Hand Invariants : Hand Invariants Let stack be h(xn,sn),(xn-1,sn-1),…,(x1,s1)i
1. x1 is on right spine of tree Æ 8 j > 1 : xj-1 is RP of xj
2. 8 j : sj is a prefix of left spine of xj’s right child Æ 8 j : |sj| = h(xj) – 1 – h(xj+1) 8 4 3 6 x3 x2 x1 s3 s2 s1
Hand Invariants : Hand Invariants Let stack be h(xn,sn),(xn-1,sn-1),…,(x1,s1)i
1. x1 is on right spine of tree Æ 8 j > 1 : xj-1 is RP of xj
2. 8 j : sj is a prefix of left spine of xj’s right child Æ 8 j : |sj| = h(xj) – 1 – h(xj+1) 8 4 3 6 x3 x2 x1 s3 s2 s1
Hand Invariants : Hand Invariants Let stack be h(xn,sn),(xn-1,sn-1),…,(x1,s1)i
1. x1 is on right spine of tree Æ 8 j > 1 : xj-1 is RP of xj
2. 8 j : sj is a prefix of left spine of xj’s right child Æ 8 j : |sj| = h(xj) – 1 – h(xj+1) 8 4 3 6 x3 x2 x1 s3 s2 s1
Hand Invariants : Hand Invariants Denote height of xj by h(xj).
Define h(xj) = 0 for any j > n. (In reality, that xj does not exist.) h=1 h=2 h=3 h=4 8 4 3 6 x3 x2 x1 s3 s2 s1
Sub-tree Search Lemma : Sub-tree Search Lemma Given fx to minimum key x of a sub-tree, we can obtain fy in O(log d) time if y is in the same sub-tree as x, or if y is the right parent of the sub-tree’s root. Restoring invariants of hand also takes O(log d) time. Prove Lemma
Finding Our Target : Finding Our Target Suppose we have to go up v levels (and then start going down)
) d ¸ (2v-1-1) v = O(log d) v=3
Fixing Hand Invariants : Fixing Hand Invariants Fixing the spine of the highest node we visited can only take v pointer chasing.
v=3
Fixing Hand Invariants : Fixing Hand Invariants Extend and push when going down
Go right : Extend top cell’s spine
Go left : Push node to RPS
(If equal, pretend go left) v=3
Checkpoint : Checkpoint Do you understand what the lemma is?
(Realize that this sub-tree search does not always happen because the target can be somewhere else.) v=3
Where can our destination be? : Where can our destination be? FSearch(fcurr,y) 1. curr < y < RP
2. y = RP
3. RP < y < peer
4. y = peer
5. peer < y Can distinguish cases in O(1) time
Case 1 : Case 1 1. Do an increment (now at curr++)
2. Sub-tree search
Increment is O(1), Search is O(log d)
Invariants restored automagically
Case 2 : Case 2 Proceed as in case 1
(Sub-tree search for y in will walk right spine as RP 2 , invariants restored automagically)
Analysis is the same as case 1 curr RP peer
Case 3 : Case 3 1. Proceed as in case 2 to obtain a hand on RP (search in gives fRP)
2. Do an increment (now on RP++)
3. Sub-tree search
Case 3 Analysis : d is at least size of
O(log d) to arrive at RP
O(1) to arrive at RP++
O(log d) for a sub-tree search Case 3 Analysis
Case 4 : Case 4 Proceed as in case 3 to obtain fpeer
Analysis is the same as case 3
Case 5 : Case 5 1. Find the largest right parent p · y by popping RPS (and discard spines)
2. Get fp by fixing hand invariants
3. FSearch(fp, y) (this time guaranteed to be case 1)
Graphically : Graphically We know it’s case 5
Graphically : Graphically Find largest parent p · y by popping RPS
Graphically : Graphically p p’s RP p’s peer Fix invariants to obtain fp curr RP peer
Graphically : Graphically p p’s RP p’s peer Now it must be case 1 (or y=p) curr RP peer
Case 5 Analysis : Case 5 Analysis Imagine writing down all keys
… curr, ……, p, ……, y … d ·O(log d) ·O(log d) distance time Skip Details
Case 5 Analysis : Case 5 Analysis Consider RPS before FSearch(fcurr, y).
Let the p be xj.
By invariant 2, |sj| = h(xj) – 1 – h(xj+1). This is the amount of work we have already done previously.
To fix invariant 2, we need to extend sj down to leaf so that |sj| = h(xj) – 1.
) Time = h(xj+1) = v in figure x3 x2 x1 s3 s2 s1 x1 x2 x3
Case 5 Analysis : Case 5 Analysis How many keys between xj+1 and xj?
Answer: 2v-1 – 1
) d > 2v-1 – 1
) v = O(log d) x1 x2 x3
Space-Time Price Chart : Space-Time Price Chart
Enemy of Amortization - 1 : Enemy of Amortization - 1 You are rich…
You have a dual-processor machine
Ideally
1
2
Perhaps reality is
1
2
For the record... : For the record... I predict someone will say
“Come on, who uses multiprocessor?”
Enemy of Amortization - 2 : Enemy of Amortization - 2 I am poor…
My data is on secondary storage InOrder(node) :=
If(node != Nil)
{
InOrder(node.left);
// print node.key
InOrder(node.right);
} slow slow slow
Amortization Issues : Amortization Issues Practice
Real-time systems (Boeing 747…)
Interactive systems (Windoze…)
Databases / File Systems
Theory
Multiple futures in persistent data structures (partially solved by lazy evaluation)
Amortization : Amortization many cheap operations + $$$$$$$$$
one expensive operation - $
savings >0
Persistent Data Structure : Persistent Data Structure
Multiple Futures : Multiple Futures many cheap operations + $$$$$$$$$
many expensive operations -$$$$
savings(???) -$$$
Checkpoint : Checkpoint By now, I want you to realize that sometimes amortized time bound is just undesirable
For the other times, amortized analysis opens a wide space for simpler and faster algorithms with equivalent time bounds
Extension : Extension Slight change will work for any height-balanced BST (e.g. Red-Black, B-Tree)
Treaps? AVL? Splay trees?
Can also support forward and backward simultaneously (messy…)
It's Halloween! : It's Halloween! You are cordially invited to the first HALLOWEEN PARTY of the Millennium on Halloween at the Church after Dusk
DRESS CODE AND DINNER MENU Humans will be eaten. DIRECTIONS Follow the smell of blood up Forbes towards Squirrel Hill, turn right onto Wightman, turn second right onto Bartlett. Your liquid or solid of choice will be found at 5516 Bartlett St. Spouses, dates, siblings, housemates, familiars and friends are welcome. John, Mukesh, and Urs I said “Catenable”; not “Cannibal”