MONTE CARLO METHODS
MONTE CARLO METHODS CIS 5930
Popular in Course
Popular in Comm Sciences and Disorders
This 12 page Class Notes was uploaded by Mrs. Rahul Wuckert on Thursday September 17, 2015. The Class Notes belongs to CIS 5930 at Florida State University taught by Feifei Li in Fall. Since its upload, it has received 45 views. For similar materials see /class/205696/cis-5930-florida-state-university in Comm Sciences and Disorders at Florida State University.
Reviews for MONTE CARLO METHODS
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/17/15
Range Searching using Kd Tree Hemant M Kakde 25 08 2005 1 Introduction to Range Searching At rst sight it seems that database has little to do with geometry The queries about data in database can be interpreted geometricallyln this case the records in the database are transformed into points in multidimensional space and the queries about records are transformed into the queries over this set of points Every point in the space will have some information of person associated with it Consider the example of the database of personal administration where the general infor mation of each employee is stored Consider an example of query where we want to report all employees born between 1950 and 1955 who earns between Rs3000 and Rs4000 per month The query will report all the points that whose frost co ordinate lies between 1950 and 1955 and second co ordinate lies between 3000 and 4000 In general if we are interested in answering queries on d elds of the records in our database we transforms the records to points in d dimensional space Such a query is called rectangular range query or an orthogonal range query ln Range Search problems the collection of points in space and the query is some standard geometric shape translatable in space Range search consist either of retrieving report problems or ofcounting count problems all points contained within the query domain Saary 39 o O O O 4000 0 o O o O o o O o O 3000 o O O o O O E Date of Birth 1950 1955 Fig Interpreting a database Query Geometrically Figure 1 2 1 Dimensional Range Searching Let us consider the set of points Pp1p2 up We have to search the range X7X7 and we have to report which points lies in that range To solve the problem of range searching we use the data structure known as balanced binary search tree T The leaves of the T store the points of P and the internal nodes of T will store the splitting values to guide the search Let M denote the value stored at each split node v The left subtree of the node v contains all points smaller than or equal to M7 and the right subtree contains all the points strictly greater than M Let we search with X and X7 in T u and u be the two leaves where the searches end7 respectively Then the points in the interval XZX7 are stored in the leaves in between u and M including u and u To nd the leaves between u and V we select the tree rooted at nodes v in between the two search paths whose parent are on the search path To nd these nodes we rst nd the node 05pm where the paths to X and X7 splits Figure 2 21 Algorithm To nd the split node let us consider lCV arid rCV denote the left and right child7 respectively7 of the node V Fly The Selected Sumnes Figure 3 Procedure name FlNDSPLlTNODE Input A Tree T and two values X and X7 With XSX7 Output The node V Where the paths to X and X7 split7 or the leaf Where both path ends 1 vHrootT 2 While V is not a leaf and X7Sv or Xgtv 3 do if X7 S M 4 then vH lcv 5 else vH rcv 6 return V Starting from vspm we then follow the search path of X At each node where the path goes left7 we report all the leaves in the right subtree7 because this subtree is in between the the two search paths Similarly7 we follow the path of X7 and we report the leaves in the left subtree of the node where the path goes right Finally we check the points stored at the leaves whether they lies in the range X 7 X7 l or not Now we see the query algorithm which uses the subroutine REPORTSUBTREE7 which traverses the subtree rooted at the node and reports all the stored at its leavesThis subroutine takes takes the amount of time linear in the number of reported points7 this is because the number of internal nodes of any binary tree is less than its internal node 22 Algorithm Procedure name 1DRANGEQUERYT7XX7 Input A binary search tree T and a range XX Output All points stored in T that lie in the range 1 vspl tltFlNDSPLlTNODET7X7X7 2 if vspm is a leaf 3 then check if the point stored at vspm must be reported else Follow the path to X and report the points in subtree right of the path Vlt lc vspm do ifX7 S M 4 5 6 While v is not a leaf 7 8 then REPORTSUBTREErcv 9 vH lcv 10 else vH rcv 11 check if the point stored at the leaf V must be reported 12 Similarly7 follow the path to X77 reports the points subtree left of the path7 and check if the point stored at the leaf where the path ends must be reported 221 Complexity analysis The data structure binary search tree uses 0n storage and it can be built in On log n time In worst case all the points could be in query range7 so the query time will be n The query time of n cannot be avoided when we have to report all the points Therefore we shall give more re ned analysis of query time The re ned analysis takes not only n7 the number of points in the set P7 into account but also k7 the number of reported points As we know that the REPORTSUBTREE is linear in the number of reported points7 then the total time spent in all such calls is 0k The remaining nodes that are visited are the nodes of the search path of X and X7 Because T is balanced7 these paths have a length Olog n The time we spent at each node is 017 so the total time spent in these nodes is Olog n7 which gives a query time of Ologn k 222 Theorem Theorem 1 Let P be the set of n points in one Z dirnensional space The set P can be stored in balanced binary search tree which uses 0n storage and has 0n logn construction time such that the points in the query range can be reported in time 0k logn where k is the number of reported points 3 Kd Trees Consider the 2 dimensional rectangular range searching problem Let P be the set of n points in the plane The basic assumption is no two point have same x coordinate7 and no two points have same y coordinate De nition 1 A 2 dirnensi0nal rectangular range query on P asks for the points from P lying inside the query rectangle A point p pzpy lies inside this rectangle if and only if meh c and pyelw Let7s consider the following recursive de nition of the binary search tree the set of 1 dimensional points is split into two subsets of roughly equal size7 one subset contains the point smaller than or equal to splitting value7 the other contains the points larger than splitting value The splitting value is stored at the root and the two subsets are stored recursively in two subtrees Flg A Kd Tm 1 Th wly m pllne ls dead 0 Cmrespnnlng Elnuy m Figure 4 Each point has its X coordinate and y coordinate Therefore we rst split on X coordinate and then on y coordinate7 then again on x coordinate7 and so on At the root we split the set P with vertical line 1 into two subsets of roughly equal size This is done by nding the median X coordinate of the points and drawing the vertical line through it The splitting line is stored at the root Heft7 the subset of points to left is stored in the left subtree7 and PM the subset of points to right is stored in the right subtree At the left child of the root we split the Pleft into two subsets with a horizontal line This is done by nding the median y coordinate if the points in Pleft The points below or on it are stored in the left subtree7 and the points above are stored in right subtree The left child itself store the splitting line Similarly PM is split with a horizontal line7 which are stored in the left and right subtree of the right child At the grandchildren of the root7 we split again with a vertical line In general7 we split with a vertical line at nodes whose depth is even7 and we split with horizontal line whose depth is odd 31 Algorithm Let us consider the procedure for constructing the kd tree It has two parameters7 a set if points and an integer The rst parameter is set for which we want to build kd tree7 initially this the set P The second parameter is the depth of the root of the subtree that the recursive call constructs Initially the depth parameter is zero The procedure returns the root of the kd tree Procedure name BUlLDKDTREEP7depth Input A set of points P and the current depth depth Output The root of the kd tree storing P 1 if P contains only one point 2 then return a leaf storing this point 3 else if depth is even 4 then Split P into two subsets with a vertical line 1 through the median X coordinate of the points in PLet P1 be the set of points to the left of l or on 17 and let P2 be the set of points to the right of l 5 else Split P into two subsets with a horizontal line 1 through the median y coordinate of the points in PLet P1 be the set of points to the below of l or on 17 and let P2 be the set of points above 1 6 weftHBUILDKDTREEP17 depth 1 7 1 thHBUILDKDTREEP27 depth 1 8Create a node v storing 17 make cleft the left child of v7 and make might the right child of v 9 return V 311 Construction time of 2dimensional kdtree The most expensive step is to nd the median The median can be nd in linear time but linear time median nding algorithms are rather complicated So rst presort the set of points on X coordinate and then on y coordinate The parameter set P is now passed to the procedure in the form of two sorted list Given the two sorted list it is easy to nd the median in linear time Hence the building time satis es the recurrence TnO1 if n1 On2T fnZTif ngt1 which solves to O n log 11 Because the kd tree is the binary tree and every leaf and internal node uses 01 storage therefore the total storage is 0n Lemma 1 A kd tree for a set of n points uses 0n storage and and can be constructed in On logn The splitting line stored at the root partition the plane in two half planes The left child of the root corresponds to the left half plane and right child corresponds to right half plane The left child of the left child of the root corresponds to the region bounded to the right by the splitting line stored at the root and bounded from above by the line stored at the left child of the root In general the region corresponding to the node v is the rectangle which can be unbounded on one or more sides It is bounded by splitting lines stored at the ancestors of v We denote the region corresponding to the node v by regionv The region of the root of the kd tree is whole planeObserve that a point is stored in subtree rooted at node v if and only if it lies in regionv We have to search the subtree rooted at v only if the query rectangle intersects the regionv Observation 1 We traverse the kd tree but visit only nodes whose region is intersected by query rectangle When a region is fully contained in the query rectangle then report all the points stored at its subtreeWhen traverse reaches a leaf7 we check Whether the point is contained in the query region and7 if so7 report it let us consider the diagram given below FUAQMIWnnkdlrll Figure 5 The grey nodes are visited When When we query With grey rectangle The node marked With star corresponds to a region that is completely contained in the query rectangle7 Which is shown by darker rectangle in g Hence7 the dark grey subtree rooted at this node is traversed and all points stored in it are reported The other leaves that are visited corresponds to region that are only partially inside the query rectangle Hence7 the points stored in them must be tested for inclusion in the query range this results in point P5 and P11 being reported7 and points P37 P12 and P13 not being reported 32 Algorithm Let us consider the procedure for searching the kd tree It has two parameters7 the root of the kd tree and the query range R Procedure name SEARCHKDTREEWR Input The root of a subtree of a kd tree7 and a range R Output All points at leaves below V that lies in range 1 ifv is a leaf 2 then Report the stored at V if it lies in R 3 else if regionlvc is fully contained in R 4 then REPORTSUBTREElcV else if regionlcv intersects R then SEARCHKDTREE1CVR 39 regionrvc is fully contained in R then REPORTSUBTREErcV else if regionlcv intersects R 10 then SEARCHKDTREE1CVR H H The region corresponding to the left child of a node V at even depth can be computed from regionv as follows regionlcv regionv lvleft where lv is the splitting line stored at v7 and vleft is the half plane to the left of and including lv Lemma 2 A query with an axis parallel rectangle in a kd tree storing rt points can be performed in Ohk time where k is the number of reported points First of all note that the time to traverse a subtree and report the points stored in its leaves is linear in number of reported points Therefore the total time is 0k It remains to bound the number of nodes Visited by the query algorithm that are not in one of the traversed subtreesFor each such node v7 the regionv is intersected by7 but not fully contained in the rangeTo analyze the number of such nodes7 we shall bound the number of regions intersected by any vertical line This will give us an upper bound on the number of regions intersected by the left and right edge of query rectangle Similarly7 we can nd the number regions intersected by the top and bottom lines of query rectangle 321 Complexity analysis Let lbe the vertical line and T be a kd tree Let lrootT be the splitting line stored at the root of the kd tree The line 1 intersects either the region to the left of lrootT or the region to the right of lrootT but not bothThis observation seems to imply that Qn the number of intersected regions in the kd tree storing a set of n points satis es the recurrence QnlQn2 But this is not true because the splitting lines are horizontal at the children of the root This means that if the line 1 intersects the regionlcrootT then it will always intersect the regions corresponding to both children of lcrootT Hence the recurrence we get is incorrect To write the correct recurrence for Qn we go down two steps in tree Each of the four nodes at depth two in the tree corresponds to a region containing n4 points Two of the four nodes correspond to intersected regions so we have to count the number of intersected regions in these subtrees recursively More over 1 intersects the regions of the root and of the root and of one of its children Hence Qn satis es the recurrence QnOlif n1 22Qn4if ngt1 This recurrence solves to Qn0h In other words any vertical line intersects regions in kd treeSirnilarly horizontal line intersects regions The total number of regions intersected by the boundary of a rectangular range query is bounded by ONT Theorem 2 A kd tree for a set P of n points can be build in On logn time A rectan gular range query on the kd tree takes Oh k time where k is the number of reported points Kd trees can be also be used for higher dimensional spaces The construction algorithm is very similar to the planar case At the root we split the set of points into two subsets of roughly the same size by a hyperplane perpendicular to the Xl axis In other words at the root the point set is partitioned based on the rst coordinate of the points At the children of the root the partition is based on second coordinate at nodes at depth two on the third coordinate and so on until depth of d l we partition on last coordinate Ai depth d we start all over again partitioning on rst coordinate The recursion stops only 11 When one point is left7 Which is then stored at the leaf Because a d dirnensional kd tree for a set of n points is a binary tree With n leaves7 it uses 0n storage The construction time is 0n logn Nodes in a d dirnensional kd tree corresponds to regions7 as in the plane The query algorithm Visits those nodes Whose regions are properly intersected by the query range7 and traverses subtree that are rooted at nodes Whose region is fully contained in the query range It can be shown that the query time is bounded by 0n1 1dk References 1 T H Corrnen7 C E Leiserson7 R L Rivest and C Stein7 Introduction to Algorithms7 Prentice Hall lndia7 New Delhi 2 Franco P Preparata and Micheal lan Sharnos7 Computational Geometry An Intro duction7 Springer Verlag7USA
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'