2001 10 31 Finger Search

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”