One-pass sampling of hierarchically organized sensors

• US 7,933,919 B2
• Filed: 11/30/2007
• Issued: 04/26/2011
• Est. Priority Date: 11/30/2007
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kumar Nath, Suman
• Primary Examiner(s): Wassum; Luke S.
• Assistant Examiner(s): Rayyan; Susan F
• Application Number:
  US11/948,667
• Publication Number:
  US 20090144011A1
• Time in Patent Office: 1,243 Days
• Field of Search: 707/705, 707/778, 707/769, 711117-118, 711/133, 711/116
• US Class Current: 707/769
• 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 at least one processor coupled to at least one machine-readable storage medium storing instructions executable by the at least one processor to implement:

an interface component configured to provide a query;

a sample component configured to probe a random subset of sensors to compute aggregate query results, wherein the subset is identified in a single pass over a hierarchical structure as a function of the query and a target sample size;

an oversample component configured to increase the target sample size by a margin to increase a likelihood of acquiring data from at least the target sample size; and

a margin component configured to determine a size of the margin by at least one of identifying a default margin or selecting an optimal smallest margin.

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

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

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

5. The system of claim 1, further comprising a context component configured to provision a historical availability of one or more sensors based on a known lack of availability of a portion of the one or more sensors in a particular region.

6. The system of claim 5, wherein the margin component is configured to predict a number of unavailable sensors as a function of at least one of time, date, day of week, or number of attempted accesses to the one or more sensors.

7. The system of claim 5, wherein 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 configured to redistribute a 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 a component configured to retrieve sensor data from a cache memory rather than directly probing sensors for at least one sensor.

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

11. The system of claim 1, wherein the sample component is configured to report the aggregate query results.

12. A method of sensor sampling, comprising:

identifying, in a single pass over a hierarchically organized structure, a random subset of sensors for acquiring data, in accordance with a query and a target sample size;

increasing the target sample size by a margin of sensors for over-sampling, to increase a likelihood of acquiring data from at least the target sample size; and

determining a size of the margin by at least one of identifying a default margin or selecting an optimal smallest margin.

13. The method of claim 12, further comprising:

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

splitting the target sample size among child nodes relevant to the query at each layer based on a weight associated with the child nodes.

14. The method of claim 12, further comprising increasing the target sample size by the margin, based on sensor unavailability.

15. The method of claim 14, further comprising, based on a predicted sensor unavailability, scaling up the target sample size by a non-leaf tree node such that when a random number of descendent sensors of the non-leaf tree node are probed, an expected number of sensors less than the random number will be available to provide data.

16. The method of claim 14, further comprising redistributing sampling among nodes yet to be probed where the target sample size lags behind a target size for at least some nodes to increase a probability that the target sample size is achieved in a 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 computer-readable non-transitory storage medium storing instructions, the instructions if executed by a computing device causing the computing device to perform operations comprising:

acquiring a query;

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

increasing the target sample size by a margin of sensors for over-sampling, to increase a likelihood of acquiring data from at least the target sample size; and

determining a size of the margin by at least one of identifying a default margin or selecting an optimal smallest margin.

19. The computer-readable storage medium of claim 18, the operations further comprising predicting a number of unavailable sensors as a function of at least one of time, date, day of week, or number of attempted accesses to the one or more sensors.

20. The computer-readable storage medium of claim 19, the operations further comprising retrieving at least a portion of sensor data from a cache.