DOC PREVIEW
SBU CSE 590 - Multi-dimensional data and spatial range query in sensor networks

This preview shows page 1-2-3-19-20-38-39-40 out of 40 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1MultiMulti--dimensional Data and dimensional Data and Spatial Range Spatial Range Query in Sensor NetworksQuery in Sensor NetworksJie GaoComputer Science DepartmentStony Brook University2PapersPapers• [Li03a] X. Li, Y. J. Kim, R. Govindan, W. Hong, Multi-dimensional 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.3Orthogonal range searchOrthogonal range search• Find all the sensors inside a rectangular box.• Find all the sensors with temperature readings above 70F.4MultiMulti--dimensional datadimensional 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.5Sensor network as a databaseSensor network as a database• Need an indexing scheme.• …. In addition, a storage scheme.• First we look at range query in a centralized setting.61D range search1D 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.3 10 19 23 303 1937 49 5930 4910 372371D range search1D 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].3 10 19 23 303 1937 49 5930 4910 372381D range search1D 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.3 10 19 23 303 1937 49 5930 4910 37239KdKd--treetree• 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).xxyyx10KdKd--treetree• 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.xxyyx11KdKd--treetree• Storage: O(n)• Height of the tree: O(logn)• Query cost? O(n1/2+k), where k is the output size.12r(v)KdKd--treetree• 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).13KdKd--treetree• 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).14KdKd--tree in Rtree in Rdd• 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.15Range treeRange 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 x-corodinatesRange tree on y-corodinates16Range treeRange tree• Query:– First search the 1D range tree on the x-coordinates– For each node on the traversal path, search on the y-coordinates.• Query cost: O(log2n+k)Range tree on x-corodinatesRange tree on y-corodinates17QuadQuad--treetree• 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).18Indexing in a sensor network?Indexing in a sensor network?• Where is the index stored?• How to traverse the tree?• 1stapproach: map a quad-tree to the sensor field.• 2ndapproach: distributed storage and indexing.19DIMENSIONS: summariesDIMENSIONS: summaries• Use a quad-tree partitioning.20DIMENSIONS: queryDIMENSIONS: query• Top-down query processing21Issues with Issues with DIMENSIONsDIMENSIONs• Uneven load: nodes holding coarse data are visited more often.• Root becomes traffic bottleneck.22Distributed index for multiDistributed index for multi--dimensional datadimensional data• Construct the distributed indices. • Locality preserving geographic hash: events with close attributes values are likely to be stored close.• Kd-tree partitioning.23ZonesZones• 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.24ZoneZone--treetree• 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 inthe right sibling tree.25DataData--centric hashingcentric 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.For example: [0.3, 0.8] is stored at 5-bit zone code 01110.The event is hashed to the node that owns the zone.A1<0.5A1<0.5, A2<0.5A1<0.25 or 0.5 ≤ A1<0.75, A2<0.526DataData--centric routingcentric 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.27Routing queriesRouting 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.28Event routing helps resolving undecided zonesEvent routing helps resolving undecided zones• How does each node knows its own zone code?•


View Full Document

SBU CSE 590 - Multi-dimensional data and spatial range query in sensor networks

Download Multi-dimensional data and spatial range query in sensor networks
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Multi-dimensional data and spatial range query in sensor networks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Multi-dimensional data and spatial range query in sensor networks 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?