advertisement

2001 10 31 Finger Search

43 %
57 %
advertisement
Information about 2001 10 31 Finger Search
Entertainment

Published on November 2, 2007

Author: Rafael

Source: authorstream.com

advertisement

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”

Add a comment

Related presentations

Related pages

2001-10-31 Finger Search - Ace Recommendation Platform - 1

1Thy Shalt Come To The TGIWFro m : s h uc h i@ c s .c m u.e d uS ub je c t: TGIWWh e n: T o nig h t, 6 :0 0 p mWh e re : We H 7 2 2 0Nikh il will b e ta ...
Read more

Improved Bounds for Finger Search on a RAM - Springer

We present a new finger search tree with O(1) ... STOC 2001, pp. 335–342. ... Over 10 million scientific documents at your fingertips.
Read more

List of Tweenies episodes - Wikipedia, the free encyclopedia

List of Tweenies episodes ... 31 January 2001 () Max searches for scrap metal for Milo. 228 ... 10 December 2001 ...
Read more

Fingerprint - Wikipedia, the free encyclopedia

... but these are not factors that should have affected fingerprint search ... its use in forensic science in his book Finger ... 2001. Fingerprints: The ...
Read more

Rubber Finger | Sick | 2001 - YouTube

Rubber Finger performing Sick in Los Banos, 2001. Skip navigation ... Rubber Finger | Sick | 2001 ... 10. Trenzor Music Channel 309 views.
Read more

Alle Spiele des Jahres | Spiel des Jahres e.V.

Search this site . Preisträger. ... 2001 : 10 : 2-5 : 30 : Torres: 2000 : 12 ... 95 31 384. Mo - Do: 08:00 - 15:30 Uhr
Read more

Friends and Family (2001) - IMDb

Friends and Family Not ... Search for "Friends and Family" on Amazon.com. Connect with IMDb. ... Friends and Family (2001) 6.4 /10.
Read more

Google UK

UK version of the global search engine. Search the world's information, including webpages, images, videos and more.
Read more

Mark Knopfler gives a guitar lesson 2001 - YouTube

The great Mark Knopfler tells us how he plays the guitar Enjoy!!! ... Mark Knopfler gives a guitar lesson 2001 YouTube; ... 10:31. Andrewshadowy ...
Read more