Slot-cache for caching aggregates of data with different expiry times
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
18 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
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. - View Dependent Claims (9, 10, 11, 12, 13)
-
-
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. - View Dependent Claims (15, 16, 17, 18)
-
Specification