ONE-PASS SAMPLING OF HIERARCHICALLY ORGANIZED SENSORS

• US 20090144011A1
• Filed: 11/30/2007
• Published: 06/04/2009
• Est. Priority Date: 11/30/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kumar Nath, Suman
• Granted Patent: US 7,933,919 B2
• Time in Patent Office: Days
• US Class Current: 702/116
• CPC Class Codes: G01C 25/00 Manufacturing, calibrating, cleaning, or repairing instruments or devices referred to in the other groups of this subclass testing, calibrating or compensating compasses G01C17/38

Abstract

One-pass sampling is employed within a hierarchically organized structure to efficiently and expeditiously respond to sensor inquires. Identification of relevant sensors and sampling of those sensors is combined and performed in a single pass. Oversampling can also be employed to ensure a target sample size is met where some sensors fail or are otherwise unavailable. Further yet, sensor data can be cached and utilized to hasten processing as well as compensate for occasional sensor unavailability.

Claims

1. A query processing system, comprising:

an interface component that acquires a query; and

a sample component that probes a random subset of sensors to compute aggregate query results, the subset is identified in a single pass over a hierarchical structure as a function of the query and a target sample size.

2. The system of claim 1, further comprising a partition component that recursively partitions the target sample size amongst nodes at each hierarchical level.

3. The system of claim 2, further comprising a component that identifies weight associated with each node to enable partitioning based thereon.

4. The system of claim 3, the weight relates to number of sensors associated with each node.

5. The system of claim 1, further comprising an oversample component that increases the target sample size by a margin to ensure the initial size is met in light of occasionally unavailable sensors.

6. The system of claim 5, the margin is determined as a function of historical availability of individual sensors.

7. The system of claim 5, the target sample size is increased exactly once in any path from a root to a leaf node associated with individual sensors.

8. The system of claim 5, further comprising a component that redistributes sampling load to alternate nodes where sample size is less than the target sample size for at least one node.

9. The system of claim 1, further comprising component that retrieves sensor data from cache memory rather than directly probing sensors for at least one sensor.

10. The system of claim 1, the hierarchical structure is one of an r-tree, a b-tree, or a colr-tree

11. The system of claim 1, the sample component reports the aggregate query results.

12. A method of sensor sampling, comprising:

descending layer by layer in a hierarchically organized structure identifying sensors beginning at a root in accordance with a query;

splitting a target sample size amongst child nodes relevant to the query at each layer; and

fetching data from a designated number of sensors identified at a node entirely within an area defined by the query.

13. The method of claim 12, determining a weight associated with the child nodes and splitting the target sample based thereon.

14. The method of claim 12, further comprising increasing the target sample size by a margin to ensure identification of the target sample size in light of sensor unavailability.

15. The method of claim 14, determining the margin as a function of historical availability of sensors.

16. The method of claim 14, further comprising redistributing sampling among nodes yet to be probed where the sample size lags behind target size for at least some nodes to increase the probability that the target sample size is achieved in the presence of sensor deployment irregularity.

17. The method of 14, further comprising checking a cache for sensor data that satisfies a query prior to fetching data from sensors.

18. A data acquisition system, comprising:

means for acquiring a query; and

means for one pass sampling of hierarchically organized structure to identify a subset of sensors to probe to compute and return aggregate results to the query as a function of a target sample size.

19. The system of claim 18, further comprising a means for over sampling to ensure the target sample size in the presence of unavailable sensors.

20. The system of claim 19, further comprising a means for retrieving at least a portion of sensor data from a cache.