Multi dimensional Data and Spatial Range Query in Sensor Networks Jie Gao Computer Science Department Stony Brook University 1 Papers Li03a X Li Y J Kim R Govindan W Hong Multidimensional Range Queries in Sensor Networks Proc ACM SenSys 2003 Gao04 J Gao L Guibas J Hershberger L Zhang Fractional Cascaded information in a sensor network IPSN 04 2 Orthogonal range search Find all the sensors inside a rectangular box Find all the sensors with temperature readings above 70F 3 Multi dimensional data Monitor environments Multiple sensors multiple attributes Query might be multi dimensional as well List all sensors with temperature value 70 80 and light level 10 20 4 Sensor network as a database Need an indexing scheme In addition a storage scheme First we look at range query in a centralized setting 5 1D range search Find the data inside a query interval x x 1D range tree a balanced partitioning tree on a sorted list Each leaf stores an input value Each internal node stores the splitting value 23 10 37 3 3 19 10 19 30 23 30 49 37 49 59 6 1D range search Find the data inside a query interval x x Start from the root and descend the tree to find the interval where x and x stays Include all the leaves in the sub trees between the two traversing paths from the root Example 9 33 23 10 37 3 3 19 10 19 30 23 30 49 37 49 59 7 1D range search Storage n n 2 n 4 1 2n O n Height of the tree O logn Query time O logn k where k is the output size 23 10 37 3 3 19 10 19 30 23 30 49 37 49 59 8 Kd tree A recursive space partitioning tree Partition along x and y axis in an alternating fashion Each internal node stores the splitting node along x or y x y x y x 9 Kd tree 2D query R x x y y Check with each internal node whether the cutting line intersects R If yes recurse on both If no only recurse on the half plane that intersects R x y x y x 10 Kd tree Storage O n Height of the tree O logn Query cost O n1 2 k where k is the output size 11 Kd tree Query cost O n1 2 k where k is the output size Intuition we visit 2 types of nodes r v is fully contained in R this is counted in k r v is not fully contained in R intersected by boundaries of R Thus we bound the number of nodes intersected by a vertical line denoted by Q n r v 12 Kd tree Thus we bound the number of nodes intersected by a vertical line denoted by Q n Look at the 4 grandchildren the line intersects at most 2 of them Thus Q n 2Q n 4 O 1 O n1 2 The query cost is O k 4Q n O n1 2 k 13 Kd tree in Rd High dimensional kd tree If the dimension is d we can build a kd tree with O n size and query cost O n1 1 d k where k is the output size Query cost is too high We can get it down if we sacrifice on space Range tree O nlogd 1n space and O logdn k query cost 14 Range tree Recall the 1d range tree 2D range tree First build a 1D range tree on x coordinates For each internal node take all the nodes in its subtree build a 1D range tree on y coordinates Total space O nlogn Range tree on y corodinates Range tree on x corodinates 15 Range tree Query First search the 1D range tree on the x coordinates For each node on the traversal path search on the ycoordinates Query cost O log2n k Range tree on y corodinates Range tree on x corodinates 16 Quad tree A recursive space partitioning tree The depth might be as high as n Worst case query cost is not bounded For uniform sensor distribution the depth is O logn 17 Indexing in a sensor network Where is the index stored How to traverse the tree 1st approach map a quad tree to the sensor field 2nd approach distributed storage and indexing 18 DIMENSIONS summaries Use a quad tree partitioning 19 DIMENSIONS query Top down query processing 20 Issues with DIMENSIONs Uneven load nodes holding coarse data are visited more often Root becomes traffic bottleneck 21 Distributed index for multi dimensional data Construct the distributed indices Locality preserving geographic hash events with close attributes values are likely to be stored close Kd tree partitioning 22 Zones The sensor network is partitioned to equal geographical size regions along x and y directions alternatively Each cell is given a zone code left bottom is 0 right top is 1 23 Zone tree Each node x owns a zone the largest one that contains x only If a zone is empty it is owned by the backup node the rightmost zone in the left sibling tree or the leftmost zone in the right sibling tree 24 Data centric hashing Hash a multi dimensional event to a zone A multi dimensional event Ai i 1 m Ai 0 1 Suppose the zone code has k bits k is a multiple of m For i 1 to m if Ai 0 5 the i th bit is assigned 0 otherwise 1 For i m 1 to 2m if Ai m 0 25 or 0 5 Ai m 0 75 the i th bit is assigned 0 otherwise 1 A1 0 5 A2 0 5 For example 0 3 0 8 is stored at 5bit zone code 01110 The event is hashed to the node that owns the zone A1 0 25 or 0 5 A1 0 75 A2 0 5 A1 0 5 25 Data centric routing The encoding node where the event E is generated may not know the bits of the hashed zone Node A encodes the node by using the length of its own code and generates the zone code c E Node A routes by GPSR to the centroid of the zone c E Intermediate nodes may refine code c E If the current node B finds a match of its own code and the event code c E then B stores the event 26 Routing queries Looking for a point event is the same as routing an event A range query is routed to a zone corresponding to the entire range and then progressively split into smaller sub queries 27 Event routing helps resolving undecided zones How does each node knows its own zone code Assume that every node knows the outer boundary A node checks its 1 hop neighbors and decides on the largest zone that only contains itself This may not fully resolve all the boundaries 28 Event routing helps resolving undecided zones A claims the ownership of event E But A is not sure of its upper boundary So A sends …