Slot-cache for caching aggregates of data with different expiry times

• US 8,185,355 B2
• Filed: 04/03/2007
• Issued: 05/22/2012
• Est. Priority Date: 04/03/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Nath, Suman K., Ahmad, Yanif
• Primary Examiner(s): Suglo, Janet
• Application Number:
  US11/696,027
• Publication Number:
  US 20080247313A1
• Time in Patent Office: 1,876 Days
• Field of Search: 702/188, 702/176, 711/118, 711/117, 711/133
• US Class Current: 702/188
• CPC Class Codes: H04Q 9/00 Arrangements in telecontrol or telemetry systems for selectively calling a substation from a main station, in which substation desired apparatus is selected for applying a control signal thereto or for obtaining measured values therefrom

Abstract

Techniques for collecting and displaying sensor data captured by a spatially and temporally representative sample of sensors requested in a search query are described. The sensors are represented in an index structure (e.g., a data tree) having a plurality of leaf nodes and internal nodes. The leaf nodes are associated with sensors and the internal nodes are allotted with caches having cache slots for storing sensor data with various expiry times. In response to a query, the index structure is leveraged to identify a set of nodes associated with sensors of a user selected spatial region. Sensor data having an expiry time greater than a user specified expiry time is then collected from one or more cache slots of the set of nodes. In this manner, the number of sensors to be probed to collect the sensor data is reduced.

Claims

1. A computer-implemented method comprising:

under control of one or more computing systems comprising one or more processors,

constructing an index of a plurality of nodes associated with sensors, the plurality of nodes being arranged in a hierarchy of layers of a tree structure, the plurality of nodes including leaf nodes and internal nodes, a cache associated with each of the internal nodes having a fixed number of cache slots;

assigning an expiry time period to each of the cache slots of the cache associated with each of the internal nodes such that expiry time periods assigned to corresponding cache slots of the internal nodes in each layer of the tree structure are substantially the same;

storing sensor data in each of the cache slots of the cache included in each of the internal nodes based upon whether an expiry time associated with each set of the sensor data captured by the sensors falls within the expiry time period assigned to each of the cache slots of the cache associated with each of the internal nodes;

receiving a query requesting query sensor data corresponding to a selected spatial region, the query including a specified expiry time for the requested query sensor data;

traversing through the index to identify nodes associated with one or more sensors of the sensors, the one or more sensors being in the selected spatial region; and

obtaining the requested query sensor data by identifying one or more cache slots, each of the one or more cache slots having the assigned expiry time period greater than the specified expiry time.

2. The computer-implemented method as recited in claim 1, wherein the leaf nodes cache the sensor data captured from associated sensors and the internal nodes aggregate the sensor data of the leaf nodes dependent therefrom.

3. The computer-implemented method as recited in claim 1, further comprising updating one or more cache slots of an internal node of the internal nodes with updated sensor data when the corresponding cache slots of internal nodes dependent therefrom receive fresh sensor data, wherein the updated sensor data is obtained by aggregating the sensor data in the corresponding cache slots of the internal nodes dependent therefrom.

4. The computer-implemented method as recited in claim 1, wherein the obtaining comprises identifying one or more leaf nodes including sensor data having expiry time periods at least equal to the specified expiry time period.

5. The computer-implemented method as recited in claim 1, further comprising presenting a representation of the requested sensor data in a user interface in response to the query.

6. The computer-implemented method as recited in claim 1, further comprising calculating a value based at least on:

(i) an average value from sensor data from the set of sensors in the selected spatial region having the expiry time greater than the specified expiry time;

(ii) a maximum value from sensor data from the set of sensors in the selected spatial region having the expiry time greater than the specified expiry time;

(iii) a minimum value from sensor data from the set of sensors in the selected spatial region having the expiry time greater than the specified expiry time;

or

(iv) a sum value from sensor data from the set of sensors in the selected spatial region having the expiry time greater than the specified expiry time.

7. The computer-implemented method as recited in claim 1, wherein the obtaining comprises:

aggregating the sensor data having different expiry times from the identified one or more cache slots.

8. A computing device comprising:

one or more processors; and

memory to store computer-program instructions executable by the one or more processors, the instructions to store;

a database to store an index structure that includes nodes associated with the sensors, the nodes having cache slots for storing sensor data having different expiry times, the sensor data being obtained from the sensors, wherein;

the index structure comprises a tree structure with a plurality of nodes arranged in plural layers, the plurality of nodes including leaf nodes that cache sensor data having different expiry times captured from associated sensors and internal nodes that include cache slots to store aggregated sensor data having different expiry times, each of the cache slots being associated with an expiry time period,

sensor data having an expiry time is inserted into one of the cache slots of an internal node based on whether the expiry time of sensor data falls within the expiry time period associated with the one of the cache slots, and

the aggregated sensor data stored in the cache slots of the internal nodes is obtained by aggregating sensor data having different expiry times that are inserted in the cache slots of the internal nodes, each of the different expiry times falling within the expiry time period of the one of the cache slots; and

a web portal configured to;

collect metadata of sensors and index the metadata into the index structure based on a spatial distribution of the sensors,

receive a query for specified sensor data expiring after a predefined time, and

identify, using the index structure, a set of nodes from which to collect the specified sensor data expiring after the predefined time.

9. The computing device of claim 8, wherein the web portal comprises:

an indexing module to create the index structure as the tree structure with the nodes arranged in plural layers in a hierarchical manner, the nodes having the cache slots for storing sensor data having different expiry times;

a maintenance module to maintain the sensor data stored in the cache slots;

a query processing module to determine, based on the query, the set of internal nodes from which to obtain the specified sensor data; and

a data acquisition module to collect the sensor data from the set of nodes.

10. The computing device of claim 9, wherein the maintenance module is configured to check a size of a cache of a leaf node upon receipt of new sensor data at the cache and eliminate previously stored sensor data that are least frequently accessed.

11. The computing device of claim 9, wherein the index structure further comprises tables associated with the layers in the tree structure, the tables providing associations between nodes in different layers.

12. The computing device of claim 11, wherein the maintenance module is configured to update the tables associated with the layers in the tree structure with updated sensor data when fresh sensor data is received at a leaf node.

13. The computing device of claim 8, further comprising:

a value determined from the specified sensor data expiring after the predefined time based at least on;

(i) an average value of the specified sensor data expiring after the predefined time,

(ii) a maximum value of the specified sensor data expiring after the predefined time;

(iii) a minimum value of the specified sensor data expiring after the predefined time;

or

(iv) a sum of the specified sensor data expiring after the predefined time.

14. A system memory comprising computer executable instructions that, when executed, perform acts comprising:

generating an index structure comprising a plurality of nodes arranged in a hierarchy of layers, the plurality of nodes having leaf nodes and internal nodes, the leaf nodes including caches for storing leaf sensor data obtained from associated sensors and the internal nodes including caches with multiple cache slots having expiry time periods for storing internal sensor data having different expiry times, the storing being based on whether the different expiry times of sensor data fall within each of the expiry time periods that the multiple cache slots have, wherein the expiry time periods of the multiple cache slots of the caches of the internal nodes are synchronized across different layers in the index structure;

receiving a query for sensor data expiring after a specified time;

using the index structure to identify a set of internal nodes from which to collect the sensor data expiring after the specified time; and

acquiring the sensor data expiring after the specified time.

15. The system memory as recited in claim 14, wherein the index structure further comprises tables associated with the layers in the index structure, the tables providing associations between the plurality of nodes in different layers.

16. The system memory as recited in claim 15, further comprising revising the tables by inserting new leaf sensor data and updating corresponding internal sensor data.

17. The system memory as recited in claim 14, wherein the generating further comprises designating similar expiry time periods to corresponding cache slots of the internal nodes.

18. The system memory as recited in claim 17, further comprising obtaining the internal sensor data in a cache slot of an internal node by aggregating either leaf sensor data having expiry times that fall within the expiry time period of the cache slot or internal sensor data present in one or more corresponding cache slots of internal nodes dependent therefrom.