Slot-Cache for Caching Aggregates of Data with Different Expiry Times

• US 20080247313A1
• Filed: 04/03/2007
• Published: 10/09/2008
• 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
• Granted Patent: US 8,185,355 B2
• Time in Patent Office: Days
• US Class Current: 370/231
• 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 method comprising:

constructing an index of a plurality of nodes associated with sensors, the plurality of nodes including leaf nodes and internal nodes, wherein the internal nodes include caches having multiple cache slots for storing sensor data having different expiry times;

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

traversing through the index to identify nodes associated with a set of sensors in the selected spatial region; and

obtaining the sensor data having an expiry time greater than the specified expiry time.

2. A method as recited in claim 1, wherein the constructing comprises creating a tree structure with the plurality of nodes associated with sensors arranged in a hierarchy of layers, wherein the leaf nodes cache sensor data captured from associated sensors and the internal nodes aggregate the sensor data of the leaf nodes dependent therefrom.

3. A method as recited in claim 2, wherein the constructing further comprises:

assigning expiry time periods to individual cache slots of the caches of the internal nodes; and

storing the sensor data having different expiry times in the cache slots based on a comparison between the expiry times and the expiry time periods of the cache slots.

4. A method as recited in claim 3, wherein corresponding cache slots of the internal nodes in each layer of the tree structure are assigned a similar expiry time period.

5. A method as recited in claim 1, further comprising updating one or more cache slots of an internal node with updated sensor data when 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.

6. A method as recited in claim 1, wherein the obtaining comprises:

identifying one or more cache slots having an expiry time period either inclusive of the specified expiry time or greater than the specified expiry time; and

aggregating sensor data from the identified one or more cache slots.

7. A method as recited in claim 1, wherein the obtaining comprises identifying one or more leaf nodes including sensor data having an expiry time at least equal to the specified expiry time.

8. A method as recited in claim 1, further comprising presenting a representation of the sensor data in a user interface in response to the query.

9. A computer architecture of one or more computing devices, where the one or more computing devices has memory and one or more processors operatively coupled to the memory, the computer architecture comprising:

a web portal hosted on at least one computing device, the web portal collecting metadata of sensors and indexing the metadata into an index structure based on a spatial distribution of the sensors, wherein the index structure 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;

a database to store the index structure; and

the web portal being configured to receive a query for specified sensor data expiring after a predefined time and to identify, using the index structure, a set of nodes from which to collect the specified sensor data expiring after the predefined time.

10. A computer architecture as recited in claim 9, wherein the index structure comprises a tree structure with a plurality of nodes arranged in plural layers, the 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, wherein each cache slot is associated with an expiry time period.

11. A computer architecture as recited in claim 10, wherein the aggregated sensor data in a cache slot of an internal node is obtained from an aggregation of sensor data having an expiry time that falls within the expiry time period of the cache slot.

12. A computer architecture as recited in claim 9, wherein the web portal comprises:

an indexing module to create the index structure as a 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.

13. A computer architecture as recited in claim 12, 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.

14. A computer architecture as recited in claim 12, wherein the index structure further comprises tables associated with the layers in the tree structure, the tables providing associations between nodes in different layers.

15. A computer architecture as recited in claim 14, 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.

16. One or more computer-readable media 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 slots for storing internal sensor data having different expiry times;

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.

17. One or more computer-readable media of claim 16, wherein the index structure further comprises tables associated with the layers in the tree structure, the tables providing associations between the nodes in different layers.

18. One or more computer-readable media of claim 17, further comprising computer executable instructions that, when executed, perform an additional act comprising revising the tables by inserting new leaf sensor data and updating corresponding internal sensor data.

19. One or more computer-readable media of claim 16, wherein the generating further comprises designating similar expiry time periods to corresponding cache slots of the internal nodes.

20. One or more computer-readable media of claim 19, further comprising computer executable instructions that, when executed, perform an additional act 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.