DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Response to Amendment
A request for continued examination under 37 CFR 1.114, including the fee set forth in 37 CFR 1.17(e), was filed in this application after final rejection. Since this application is eligible for continued examination under 37 CFR 1.114, and the fee set forth in 37 CFR 1.17(e) has been timely paid, the finality of the previous Office action has been withdrawn pursuant to 37 CFR 1.114. Applicant's submission filed 1/7/2026 has been entered. The claims 1 and 11 have been amended. The claims 1-20 are pending in the current application.
Response to Arguments
Applicant's arguments filed 1/7/2026 have been fully considered but are moot in view of the new ground(s) of rejection set forth in the Office Action.
Rath at least suggests the claim limitation:
determining, by a processor, a path in the data repository based on the first user request, retrieving a first tile from the data repository based on the path (
Rath teaches at Paragraph 0086 that the ingested data 1391A may be spatially partitioned along non-overlapping spatial boundaries according to the time series or range of the data, one or more tags associated with the data, the region that produced the data, the category to which the data belongs, and/or other suitable metadata. Ingested time-series data 1391A may be mapped to different partitions based on hierarchical clustering in order to achieve better performance of data storage and retrieval.
Rath teaches at Paragraph 0051 that time-series data may be partitioned or tiled along a spatial dimension 301 and also a time dimension 302. And at FIG. 6 and Paragraph 0052 that query 620 may query (a tile) over the most recent values of a particular time series 601, e.g., by interacting with the hot tier to obtain relevant query results. For example, the query 620 may represent a look into the most recent measurements of a specific sensor in near real-time.
Rath teaches at Paragraph 0064 that a query processor may direct a request 810 for data within the specified time range to one or more storage resources (e.g., hot tier storage nodes) of the storage tier 150A and the query processor may produce one or more query results 835 based on the continuous function(s) 825, e.g., by applying one or more operations from the function library 830.
Rath teaches at Paragraph [0051] FIG. 6 illustrates further aspects of the example system environment for a scalable architecture for a distributed time-series database, including examples of queries of time-series data in one or more storage tiers, according to one embodiment. As discussed above, time-series data may be partitioned or tiled along a spatial dimension 301 and also a time dimension 302. Because tiers may differ in their retention policies and latency for storing new data, some data points may be represented in one tier but not another. In one embodiment, the query processors 170 may rely on an (path) index of time-series data that takes into account the spatial dimension and the time dimension along with a tier dimension. This 3D indexing 171 may permit the query processors 170 to direct query predicates to particular storage tiers and particular storage resources (tiles) within those tiers.
Rath teaches at Paragraph 0053 that queries may be coordinated using a scalable query routing layer that receives query requests from clients and directs those queries to individual query processors. In one embodiment, at least some of the query processors may be specific to particular storage tiers. In one embodiment, queries may use a syntax like that of Structured Query Language (SQL). Queries of the hot tier may be answerable by performing a scanning, filtering, and/or aggregation on data that is wholly contained within a tile. Queries of the hot tier may be composable by merging independent results from different tiles. Queries of the hot tier may have reasonably bounded results from tiles. Queries of the hot tier may not have an unbounded error for approximate aggregation algorithms.
Rath teaches at Paragraph 0063 that a query 895 may include several items that the query processors 170 may use to identify the underlying data for the query. A query 895 may indicate one or more time series, e.g., by specifying one or more dimensions. As discussed above, a time series may be uniquely identified by a set of dimensions. To be applicable to a particular time series, a query 895 may indicate all or part of the dimensions associated with that time series. A query 895 may also indicate a time range, e.g., an interval within a starting point in time and an ending point in time. In one embodiment, a current time range may include the current time as the ending time. In one embodiment, the time range for a query may be specified in the query language with a timerange( ) function in the WHERE clause, such as in the following example query.
It is known that the query inherently includes a data path specification for the tile.
Rath teaches at Paragraph [0086] In one embodiment, the ingested data 1391A may be spatially partitioned along non-overlapping spatial boundaries according to the time series or range of the data, one or more tags associated with the data, the region that produced the data, the category to which the data belongs, and/or other suitable metadata. Ingested time-series data 1391A may be mapped to different partitions based on hierarchical clustering in order to achieve better performance of data storage and retrieval. A partition may include one time series or multiple time series. The partition(s) 1330A may be maintained using persistent storage resources and may be termed durable partitions. In one embodiment, the durable partition(s) 1330A may be provided by a local instance of a streaming service 120. The streaming service 120 may use shards or other divisions to implement the non-overlapping partition(s) 1330A. The data 1391A may be routed from the durable partition(s) 1330A to the stream processor(s) 1340A according to routing metadata, e.g., that maps different time series or ranges of the data to different stream processors. In one embodiment, a given stream processor 1340A may be assigned to one and only one partition at a time.).
Stankoulov teaches the claim limitation that Determining, by a processor, a path in the data repository based on the first user request, retrieving a first tile from the data repository based on the path (Stankoulov teaches at FIG. 34 and Paragraph 0309-0311 that that the process may determine whether there are tiles available to load….such tiles may include information for links (paths) that are near the requested links that may be structured such that associated information is included in a set of data).
Pfeifle teaches the claim limitation of determining, by a processor, a path in the data repository based on the first user request, retrieving a first tile from the data repository based on the path (Pfeifle teaches at Paragraph 0073 and Paragraph 0021 and Paragraph 0038/0066 determining/identifying by a processor link data record L2 (a path) in the data repository (navigation database storing tiles) based on the end user request of the navigation system 200, retrieving/loading a first tile T2 from the data repository based on the path).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated the data path for the tiles to have modified routing metadata of Rath to have retrieved tiles/partitions of the time series data. One of the ordinary skill in the art would have been motivated to have included link data records for the loading/retrieving/traversing of the tiles of the time series.
Beedgen teaches at Paragraph 0270 that it is possible to display the results of a counting aggregation query by time and at Paragraph 0273 that users would like to query the metrics time series in aggregation. A user might wish to see, for example, the average of all CPU usage over time in a cluster of machines. When they query the system, users will then specify only a subset of the identifying metadata they are interested in. The system will then match all the time series identified by the subset of identifying metadata provided, and execute the query using a desired aggregation function (average, 99th percentiles, …) over all the data points in all the time series.
Beedgen teaches at Paragraph 0297 that finer partitioning may be provided by adding a time level indexing scheme ta the granularity of weeks or months and at FIG. 20 and Paragraph 0317 receiving a query and the query comprising a set of query metadata and a query time range and the selected metrics time series is returned and the selected metrics time series is visualized in a graphical user interface.
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated the query language identifying metadata of a tile of the selected metrics time series to have modified routing metadata of Rath to have retrieved tiles/partitions of the time series data. One of the ordinary skill in the art would have been motivated to have included link data records for the loading/retrieving/traversing of the tiles of the time series.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-20 are rejected under 35 U.S.C. 103 as being unpatentable over
Rath et al. US-PGPUB No. 2020/0167355 (hereinafter Rath) view of
Saxena et al. US-Patent No. 11,513,854 (hereinafter Saxena);
Goyal et al. US-Patent No. 10,997,137 (hereinafter Goyal).
Guha et al. US Patent No. 10,902,062 (hereinafter Guha);
Kumar et al. US-Patent No. 11,366,801 (hereinafter Kumar);
All of the above five references are assigned to the same assignee Amazon;
Goyal et al. US-Patent No. 11,409,771 (hereinafter Goyal ‘771);
Sorenson et al. US-Patent No. 11,599,516 (hereinafter Sorenson);
Stankoulov US-PGPUB No. 2017/0199047 (hereinafter Stankoulov);
Pfeifle US-PGPUB No. 2014/0136107 (hereinafter Pfeifle);
All of the above two references are also assigned the same assignee Amazon which are drawn in parallel with the Rath reference;
Mills US-PGPUB No. 2016/0203176 (hereinafter Mills);
Beedgen et al. US-PGPUB No. 2019/0258677 (hereinafter Beedgen) and Kawata et al. US-PGPUB No. 2021/0125387 (hereinafter Kawata).
Re Claim 1:
Rath teaches a computer-implemented method of managing multi-resolution time series data, comprising:
generating and storing in a data repository, from time series data, a plurality of tiles for each resolution of a plurality of resolutions (
Rath teaches at FIG. 3 generating a plurality of tiles 310A1-310A3 of first resolution and tiles 310C1-310C2 of a second resolution stored in the storage Tier 150A),
wherein a first plurality of tiles associated with one resolution of the plurality of resolutions covers the same time period as a second plurality of tiles associated with another resolution of the plurality of resolutions (
Rath teaches at FIG. 3 generating a plurality of tiles 310A1-310A3 of first resolution which covers the same time period in temporal dimension as the tiles 310C1-310C2 of a second resolution),
wherein each tile of the plurality of tiles for the plurality of resolutions has a common number of N values (
Rath teaches at Paragraph [0054] that the database 100 may be optimized for queries in a variety of data resolutions and formats. The query processors 170 may understand the location, resolution, and format of series data and thus simplify and expedite the synthesis of multiple time series. For example, time data in the hot tier can be stored in a different resolution, format, and location than time data in a cold tier, and such differences may be transparent to the user application.
Rath teaches at FIG. 6 and Paragraph 0052 that the time series data may be maintained in one or more storage tiers for the most recent seconds 614 or milliseconds and queries 620-660 may represent different use cases and a query 620 may query over the most recent values of a particular time series 601 by interacting with the hot tier to obtain relevant query results.
Rath teaches at FIG. 6 that the temporal dimension 302 includes the time range in seconds 614 of the query 620 or Query 630. Rath teaches at FIG. 9 and Paragraph 0068 that FIG. 9 illustrates further aspects of the example system environment for implementing continuous functions in a time-series database, including an example of discrete-to-continuous conversion, according to one embodiment. A set of discrete data points 815 may represent a sequence of measurements along a measurement dimension 901 and a temporal dimension 302. The discrete data points 815 may represent a segment of a time series. Upon being retrieved from one or more storage tiers for query processing, the discrete data points 815 may be converted to a continuous function 825. The continuous function 825 may represent values for the measurement dimension 901 at all possible points in time 302 within the time range of the segment.
Rath teaches at FIG. 3 and Paragraph 0045 that tiles may be partitioned along non-overlapping temporal boundaries. Rath teaches at Paragraph 0023 that a data point may include a measurement and a timestamp and a given contiguous subset of such data points may represent a segment of the time series and at FIG. 10B each tile has N number of discrete measurements (and thus the tile 310B2 of FIG. 3 has the same temporal dimension as the tile 310B3 of FIG. 3 and therefore the tile 310B2 has the same number of measurements as the tile 310B3 according to the teaching of FIG. 10B). Rath teaches at Paragraph 0062 that he query language may permit one or more of the following functions to be specified in queries: min, max, distinct, first, last, derivative, moving average, percentile, cumulative sum, standard deviation, mean, median, count, sum, difference, top, and/or elapsed and at Paragraph 0064 that in performing the query 895, a query processor may evaluate the time range indicated in the 895 to determine the time bounds. As discussed above, different storage tiers 150A-150N may store data points for the same time series, often at different ranges of time such as the most recent data in a hot tier and older data in a cold tier. The query processor may then determine which storage tier(s) and storage resources within the tier(s) to which query predicates should be sent, and the rest of the query may be executed against time-series segments that only contain data within the specified time range),
wherein the N values represent all measurements associated with a duration of time covered by the tile in the time series data (
Rath teaches at Paragraph 0027 that clients 190 may represent various types of client devices that generate or otherwise provide data in various time series to the database 100. A time series may include a set of values that change over time, such as sensor measurements or system metrics, and that are timestamped or otherwise positioned along a temporal axis.
Rath teaches at Paragraph [0054] that the database 100 may be optimized for queries in a variety of data resolutions and formats. The query processors 170 may understand the location, resolution, and format of series data and thus simplify and expedite the synthesis of multiple time series. For example, time data in the hot tier can be stored in a different resolution, format, and location than time data in a cold tier, and such differences may be transparent to the user application.
Rath teaches at FIG. 6 and Paragraph 0052 that the time series data may be maintained in one or more storage tiers for the most recent seconds 614 or milliseconds and queries 620-660 may represent different use cases and a query 620 may query over the most recent values of a particular time series 601 by interacting with the hot tier to obtain relevant query results.
Rath teaches at FIG. 6 that the temporal dimension 302 includes the time range in seconds 614 of the query 620 or Query 630. Rath teaches at FIG. 9 and Paragraph 0068 that FIG. 9 illustrates further aspects of the example system environment for implementing continuous functions in a time-series database, including an example of discrete-to-continuous conversion, according to one embodiment. A set of discrete data points 815 may represent a sequence of measurements along a measurement dimension 901 and a temporal dimension 302. The discrete data points 815 may represent a segment of a time series. Upon being retrieved from one or more storage tiers for query processing, the discrete data points 815 may be converted to a continuous function 825. The continuous function 825 may represent values for the measurement dimension 901 at all possible points in time 302 within the time range of the segment.
Rath teaches at FIG. 3 and Paragraph 0045 that tiles may be partitioned along non-overlapping temporal boundaries. Rath teaches at Paragraph 0023 that a data point may include a measurement and a timestamp and a given contiguous subset of such data points may represent a segment of the time series and at FIG. 10B each tile has N number of discrete measurements. Rath teaches at Paragraph 0062 that he query language may permit one or more of the following functions to be specified in queries: min, max, distinct, first, last, derivative, moving average, percentile, cumulative sum, standard deviation, mean, median, count, sum, difference, top, and/or elapsed and at Paragraph 0064 that in performing the query 895, a query processor may evaluate the time range indicated in the 895 to determine the time bounds. As discussed above, different storage tiers 150A-150N may store data points for the same time series, often at different ranges of time such as the most recent data in a hot tier and older data in a cold tier. The query processor may then determine which storage tier(s) and storage resources within the tier(s) to which query predicates should be sent, and the rest of the query may be executed against time-series segments that only contain data within the specified time range);
receiving, after generating the pluralities of tiles, a first user request from a requesting computer, the first user request specifying a first timestamp and a first resolution of the plurality of resolutions (
Rath teaches at FIG. 1 that the clients 190 provides a request for the time series data.
Rath teaches at Paragraph 0053 that queries may be coordinated using a scalable query routing layer that receives query requests from clients and directs those queries to individual query processors. In one embodiment, at least some of the query processors may be specific to particular storage tiers. In one embodiment, queries may use a syntax like that of Structured Query Language (SQL). Queries of the hot tier may be answerable by performing a scanning, filtering, and/or aggregation on data that is wholly contained within a tile. Queries of the hot tier may be composable by merging independent results from different tiles. Queries of the hot tier may have reasonably bounded results from tiles. Queries of the hot tier may not have an unbounded error for approximate aggregation algorithms.
Rath teaches at Paragraph 0029 that the ingestion routers 110 may divide the data 191 from the clients 190 into non-overlapping partitions 130. In one embodiment, the ingested data may be spatially partitioned along non-overlapping spatial boundaries according to the time series or range of the data, one or more tags associated with the data, the region that produced the data, the category to which the data belongs, and/or other suitable metadata.
Rath teaches at FIG. 3 and Paragraph 0045 that tiles may be partitioned along non-overlapping temporal boundaries. Rath teaches at Paragraph 0023 that a data point may include a measurement and a timestamp and a given contiguous subset of such data points may represent a segment of the time series and at FIG. 10B each tile has N number of discrete measurements (and thus the tile 310B2 of FIG. 3 has the same temporal dimension as the tile 310B3 of FIG. 3 and therefore the tile 310B2 has the same number of measurements as the tile 310B3 according to the teaching of FIG. 10B).
Rath teaches at Paragraph [0054] that the database 100 may be optimized for queries in a variety of data resolutions and formats. The query processors 170 may understand the location, resolution, and format of series data and thus simplify and expedite the synthesis of multiple time series. For example, time data in the hot tier can be stored in a different resolution, format, and location than time data in a cold tier, and such differences may be transparent to the user application.
Rath teaches at FIG. 6 and Paragraph 0052 that the time series data may be maintained in one or more storage tiers for the most recent seconds 614 or milliseconds and queries 620-660 may represent different use cases and a query 620 may query over the most recent values of a particular time series 601 by interacting with the hot tier to obtain relevant query results.
Rath teaches at FIG. 6 that the temporal dimension 302 includes the time range in seconds 614 of the query 620 or Query 630. Rath teaches at FIG. 9 and Paragraph 0068 that FIG. 9 illustrates further aspects of the example system environment for implementing continuous functions in a time-series database, including an example of discrete-to-continuous conversion, according to one embodiment. A set of discrete data points 815 may represent a sequence of measurements along a measurement dimension 901 and a temporal dimension 302. The discrete data points 815 may represent a segment of a time series. Upon being retrieved from one or more storage tiers for query processing, the discrete data points 815 may be converted to a continuous function 825. The continuous function 825 may represent values for the measurement dimension 901 at all possible points in time 302 within the time range of the segment.
Rath teaches at FIG. 3 and Paragraph 0045 that tiles may be partitioned along non-overlapping temporal boundaries. Rath teaches at Paragraph 0023 that a data point may include a measurement and a timestamp and a given contiguous subset of such data points may represent a segment of the time series and at FIG. 10B each tile has N number of discrete measurements. Rath teaches at Paragraph 0062 that the query language may permit one or more of the following functions to be specified in queries: min, max, distinct, first, last, derivative, moving average, percentile, cumulative sum, standard deviation, mean, median, count, sum, difference, top, and/or elapsed and at Paragraph 0064 that in performing the query 895, a query processor may evaluate the time range indicated in the 895 to determine the time bounds. As discussed above, different storage tiers 150A-150N may store data points for the same time series, often at different ranges of time such as the most recent data in a hot tier and older data in a cold tier. The query processor may then determine which storage tier(s) and storage resources within the tier(s) to which query predicates should be sent, and the rest of the query may be executed against time-series segments that only contain data within the specified time range).
Rath at least suggests the claim limitation:
determining, by a processor, a path in the data repository based on the first user request, retrieving a first tile from the data repository based on the path (
Rath teaches at Paragraph 0086 that the ingested data 1391A may be spatially partitioned along non-overlapping spatial boundaries according to the time series or range of the data, one or more tags associated with the data, the region that produced the data, the category to which the data belongs, and/or other suitable metadata. Ingested time-series data 1391A may be mapped to different partitions based on hierarchical clustering in order to achieve better performance of data storage and retrieval.
Rath teaches at Paragraph 0051 that time-series data may be partitioned or tiled along a spatial dimension 301 and also a time dimension 302. And at FIG. 6 and Paragraph 0052 that query 620 may query (a tile) over the most recent values of a particular time series 601, e.g., by interacting with the hot tier to obtain relevant query results. For example, the query 620 may represent a look into the most recent measurements of a specific sensor in near real-time.
Rath teaches at Paragraph 0064 that a query processor may direct a request 810 for data within the specified time range to one or more storage resources (e.g., hot tier storage nodes) of the storage tier 150A and the query processor may produce one or more query results 835 based on the continuous function(s) 825, e.g., by applying one or more operations from the function library 830.
Rath teaches at Paragraph [0051] FIG. 6 illustrates further aspects of the example system environment for a scalable architecture for a distributed time-series database, including examples of queries of time-series data in one or more storage tiers, according to one embodiment. As discussed above, time-series data may be partitioned or tiled along a spatial dimension 301 and also a time dimension 302. Because tiers may differ in their retention policies and latency for storing new data, some data points may be represented in one tier but not another. In one embodiment, the query processors 170 may rely on an (path) index of time-series data that takes into account the spatial dimension and the time dimension along with a tier dimension. This 3D indexing 171 may permit the query processors 170 to direct query predicates to particular storage tiers and particular storage resources (tiles) within those tiers.
Rath teaches at Paragraph 0053 that queries may be coordinated using a scalable query routing layer that receives query requests from clients and directs those queries to individual query processors. In one embodiment, at least some of the query processors may be specific to particular storage tiers. In one embodiment, queries may use a syntax like that of Structured Query Language (SQL). Queries of the hot tier may be answerable by performing a scanning, filtering, and/or aggregation on data that is wholly contained within a tile. Queries of the hot tier may be composable by merging independent results from different tiles. Queries of the hot tier may have reasonably bounded results from tiles. Queries of the hot tier may not have an unbounded error for approximate aggregation algorithms.
Rath teaches at Paragraph 0063 that a query 895 may include several items that the query processors 170 may use to identify the underlying data for the query. A query 895 may indicate one or more time series, e.g., by specifying one or more dimensions. As discussed above, a time series may be uniquely identified by a set of dimensions. To be applicable to a particular time series, a query 895 may indicate all or part of the dimensions associated with that time series. A query 895 may also indicate a time range, e.g., an interval within a starting point in time and an ending point in time. In one embodiment, a current time range may include the current time as the ending time. In one embodiment, the time range for a query may be specified in the query language with a timerange( ) function in the WHERE clause, such as in the following example query.
It is known that the query inherently includes a data path specification for the tile.
Rath teaches at Paragraph [0086] In one embodiment, the ingested data 1391A may be spatially partitioned along non-overlapping spatial boundaries according to the time series or range of the data, one or more tags associated with the data, the region that produced the data, the category to which the data belongs, and/or other suitable metadata. Ingested time-series data 1391A may be mapped to different partitions based on hierarchical clustering in order to achieve better performance of data storage and retrieval. A partition may include one time series or multiple time series. The partition(s) 1330A may be maintained using persistent storage resources and may be termed durable partitions. In one embodiment, the durable partition(s) 1330A may be provided by a local instance of a streaming service 120. The streaming service 120 may use shards or other divisions to implement the non-overlapping partition(s) 1330A. The data 1391A may be routed from the durable partition(s) 1330A to the stream processor(s) 1340A according to routing metadata, e.g., that maps different time series or ranges of the data to different stream processors. In one embodiment, a given stream processor 1340A may be assigned to one and only one partition at a time.).
Stankoulov teaches the claim limitation that Determining, by a processor, a path in the data repository based on the first user request, retrieving a first tile from the data repository based on the path (Stankoulov teaches at FIG. 34 and Paragraph 0309-0311 that that the process may determine whether there are tiles available to load….such tiles may include information for links (paths) that are near the requested links that may be structured such that associated information is included in a set of data).
Pfeifle teaches the claim limitation of determining, by a processor, a path in the data repository based on the first user request, retrieving a first tile from the data repository based on the path (Pfeifle teaches at Paragraph 0073 and Paragraph 0021 and Paragraph 0038/0066 determining/identifying by a processor link data record L2 (a path) in the data repository (navigation database storing tiles) based on the end user request of the navigation system 200, retrieving/loading a first tile T2 from the data repository based on the path).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated the data path for the tiles to have modified routing metadata of Rath to have retrieved tiles/partitions of the time series data. One of the ordinary skill in the art would have been motivated to have included link data records for the loading/retrieving/traversing of the tiles of the time series.
Beedgen teaches at Paragraph 0270 that it is possible to display the results of a counting aggregation query by time and at Paragraph 0273 that users would like to query the metrics time series in aggregation. A user might wish to see, for example, the average of all CPU usage over time in a cluster of machines. When they query the system, users will then specify only a subset of the identifying metadata they are interested in. The system will then match all the time series identified by the subset of identifying metadata provided, and execute the query using a desired aggregation function (average, 99th percentiles, …) over all the data points in all the time series.
Beedgen teaches at Paragraph 0297 that finer partitioning may be provided by adding a time level indexing scheme ta the granularity of weeks or months and at FIG. 20 and Paragraph 0317 receiving a query and the query comprising a set of query metadata and a query time range and the selected metrics time series is returned and the selected metrics time series is visualized in a graphical user interface.
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated the query language identifying metadata of a tile of the selected metrics time series to have modified routing metadata of Rath to have retrieved tiles/partitions of the time series data. One of the ordinary skill in the art would have been motivated to have included link data records for the loading/retrieving/traversing of the tiles of the time series.
Goyal teaches: determining, by a processor, that no tile is available based on the first timestamp and the first resolution (
Goyal teaches at column 13, lines 20-35 that by using the original tile as a source and performing a query of the original tile for data points within the new tile's range. In one embodiment, for a temporal split initiated before the starting time of the new tile, a backfill may be unnecessary because data within the new tile's time range may not have been received by the database 100. In one embodiment, a backfill may be attempted, but a query of the original tile for data within the new tile's boundaries may return no data.
Saxena teaches at FIG. 4A and column 13, lines 8-20 that the resource usage monitoring 183 may determine that task 175B is consuming an excessive amount of resources 171B relative to one or more resource usage restrictions associated with that task. The database 100 may terminate that task 175B to enforce the resource usage restriction(s). Task termination may involve discontinuing execution of the task 175B whose resource usage exceeds a resource usage restriction. The control plane 180 may notify the corresponding client of the termination due to excessive resource usage. The host at which the task 175B was terminated may be left with more available resources for execution of other tasks.).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated Goyal’s determining that no tile is available for the query timestamp and the first resolution tile into Rath’ tile querying to have determined that the timestamp of the query tile is not within the new tile’s boundaries. One of the ordinary skill in the art would have been motivated to have determined the query result based on the query timestamp and query resolution.
Kumar and Guha teach that a first number of measurements associated with the first duration of time in the time series data being less than a second number of measurements associated with a second duration of time based on a second timestamp and the first resolution (
Kumar teaches at column 18, lines 30-64 that respective split criteria, e.g., the maximum number of keys for which entries can be accommodated at a given node may be defined for respective levels within the tree-based index, e.g., a root node may meet its split criterion when it has reached R entries, a leaf node meet its split criterion which it has reached F entries….timestamps corresponding to the N most recent writes to a given node may be stored in the node and the node may be deemed to have met its split criterion if the number of writes to it within a specified period T exceed a threshold.
Guha teaches at column 5, lines 60-67 and column 6, lines 1-10 that as new data points of the stream arrive, each of the trees of a random cut forest may represent a dynamically updated sample of the stream’s observation records….a node representing the new data point may be added to the tree by adding a new leaf node the added data point.
Guha taches at column 5, lines 15-20 that leaf nodes correspond to individual points representing minimal bounding boxes and at column 11, lines 25-40 that the SMAS may first collect a baseline set of data points from the specified streaming data sources to generate an initial forest of random cut trees, with each tree corresponding to a particular subset of the baseline set and the leaf nodes of the trees may correspond to respective data points and Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated Guha/Kumar’s teaching that each leaf node representing a 2D tile includes the respective N data points (measurements) into Rath’s storage of 2D tiles defined by spatial and temporal boundaries of the data points sampled at the nanosecond resolution timestamps. One of the ordinary skill in the art would have been motivated to have provided a tree structure for storing a set of data points (measurements).
Rath at least suggests transmitting, by the processor, a first response including the first tile to the requesting computer (
Rath teaches at FIG. 8 and Paragraph 0064-0066 transmitting query results to the request client 890 where the query results include the data points associated with the time range for a particular tile.
Rath teaches at FIG. 3 and Paragraph 0045 that tiles may be partitioned along non-overlapping temporal boundaries. Rath teaches at Paragraph 0023 that a data point may include a measurement and a timestamp and a given contiguous subset of such data points may represent a segment of the time series and at FIG. 10B each tile has N number of discrete measurements. Rath teaches at Paragraph 0062 that the query language may permit one or more of the following functions to be specified in queries: min, max, distinct, first, last, derivative, moving average, percentile, cumulative sum, standard deviation, mean, median, count, sum, difference, top, and/or elapsed and at Paragraph 0064 that in performing the query 895, a query processor may evaluate the time range indicated in the 895 to determine the time bounds. As discussed above, different storage tiers 150A-150N may store data points for the same time series, often at different ranges of time such as the most recent data in a hot tier and older data in a cold tier. The query processor may then determine which storage tier(s) and storage resources within the tier(s) to which query predicates should be sent, and the rest of the query may be executed against time-series segments that only contain data within the specified time range).
Mills at least suggests transmitting, by the processor, a first response including the first tile to the requesting computer (Mills teaches at FIG. 2 and Paragraph 0036 that each element stream 202 (each DAY-tile) may also include a sum and an average. It is understood that each element stream 202 (each DAY-tile) is a tile and each element stream 202 includes a common number of N values. As shown in FIG. 2, there is a total of 31 element streams 202 (31 DAY-tiles) and each element stream 202 constitutes a tile. Mills additionally teaches at Paragraph 0070 that the system applies each valid rollup function (min, max, avg, sum, gap counts, etc.) to the base streams’ intervals and at Paragraph 0080 a button allows the user to select from a number of different rollup function results to display (avg, min, max, sum, gaps, …) and at Paragraph 0097 that the rollup stream 1104 (HOUR-tile corresponding the element stream 201 of FIG. 2) may have been defined by the user to retrieve/display stream results as a single aggregation function described herein, such as sum, min, max, avg. etc. and at Paragraph 0099 that each of nine aggregation functions (FIRST, LAST, AVG, MIN, MAX, NONGAPS, SUM, MIN DATE, MAX DATE) is associated with one of the sub-streams 1106-1114 associated with the rollup stream 1104 (an hours-based rollup stream). It is clearly understood that each Hours-Tile 1104 includes a common number of 9 values. Mills at least suggests transmitting by the source devices 112 of FIG. 1 a first response including the first HOUR-tile 1104 and no other tile to the requesting computer 120 of FIG. 1 for generating a visualization of the 9 values of the first HOUR-tile 1104 simultaneously).
Beedgen implicitly teaches transmitting, by the processor, a first response including the first tile to the requesting computer (
Beedgen teaches at Paragraph 0290 for a query over a time range within the last 24 hours, an existing system would scan 90* more data than strictly necessary. Using the techniques described herein, the system would be aware that 89,000 of the time series have no data in the last 24 hours. Thus, the techniques provide performance improvements that allow for pre-filtering down to the 1,000 entries (corresponding to the one 24-hour tile) which may actually contain data.
Beedgen shows at FIG. 17 and Paragraph 0296-0297 displaying a plurality of aggregated values (e.g., average, 99th percentiles) for an aggregated 24-hour window (24-hour buckets/tiles) while the time series is divided into the two-super-tiles (partitions).
Beedgen teaches at Paragraph 0262 bucketing the raw logs into buckets of time intervals such as one-minute buckets or five-minute buckets and at Paragraph 0296 that the 24-hour window used in the examples described herein may be selected and at Paragraph 0297 involving time-series indexing of time series with a 24-hour threshold that buckets time series into two partitions (24-hour buckets).
Beedgen teaches at Paragraph 0270 that it is possible to display the results of a counting aggregation query by time and at Paragraph 0273 that users would like to query the metrics time series in aggregation. A user might wish to see, for example, the average of all CPU usage over time in a cluster of machines. When they query the system, users will then specify only a subset of the identifying metadata they are interested in. The system will then match all the time series identified by the subset of identifying metadata provided, and execute the query using a desired aggregation function (average, 99th percentiles, …) over all the data points in all the time series.
Beedgen teaches at Paragraph 0297 that finer partitioning may be provided by adding a time level indexing scheme ta the granularity of weeks or months and at FIG. 20 and Paragraph 0317 receiving a query and the query comprising a set of query metadata and a query time range and the selected metrics time series is returned and the selected metrics time series is visualized in a graphical user interface).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated Beedgen’s teaching of displaying multiple aggregated values associated with each aggregation unit time interval/zone (24 hours) for a number of aggregated values based on the aggregation function to have modified Rath and Mills’s display of aggregated values to have displayed multiple aggregated values simultaneously at each aggregation unit time interval/zone. One of the ordinary skill in the art would have been motivated to have provided multiple aggregated values for each aggregation unit time interval/zone.
In the same field of endeavor, Kawata implicitly teaches at FIG. 7 and 16-17 and Paragraph 0133 and Paragraph 0147 transmitting, by the processor, a first response including the first tile to the requesting computer (
Kawata teaches at FIG. 8 and Paragraph 0093-0094 that aggregation unit 610 is the 24-hour buckets/tiles when the 24-hour time input frame is selected and the evaluation start date/time input frame 604 is an input field for the administrator to operate the input/output device 30 to specify the date and time to start the evaluation of the cluster. Kawata teaches at FIG. 13 and Paragraph 0132 that each of the histograms 612a/612b/612c/612d corresponding to the 24-hour bucket/time is separately created at a time for each aggregation unit time.
Kawata teaches at Paragraph 0133 that the graph 602 including histograms is displayed and the measured values are aggregated based on the input values of the graph display start date/time input frame 608, the graph display end date/time input frame 609 and the aggregation unit time input frame 610 and at Paragraph 0147 and Paragraph 0151 that the graph of FIG. 14 is displayed as a graph with the aggregation unit time being “12 hours” and at FIG. 7 that Region 1, Region 2, Region 3 and Region 4 correspond to the claimed super-tiles and at FIGS. 16-17 and each bar graph represents a super-tile wherein a plurality of aggregated values of each bar tile/measurement are displayed simultaneously for clusters c1/c2/c3 of each bar chart/tile of each aggregation unit time in FIG. 17 and for measurement item a and measurement item b of each bar tile in FIG. 7).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated Kawata’s teaching of displaying multiple aggregated values with respect to each aggregation unit time interval/zone (e.g., 24-hour) for a number of measurement units/clusters to have modified Rath, Mills and Beedgen’s display of aggregated values to have displayed multiple measurement units at each aggregation unit time interval/zone. One of the ordinary skill in the art would have been motivated to have provided multiple aggregated values for each aggregation unit time interval/zone.
Goyal 771/Sorenson teaches a computer-implemented method of managing multi-resolution time series data, comprising:
generating and storing in a data repository, from time series data, a plurality of tiles for each resolution of a plurality of resolutions (
Sorenson teaches at FIGS. 8A-8D that the root node 811 (the high-level meta tile) or the index nodes (second high-level meta tiles) has a first resolution and the leaf nodes 821-831-841-851-861 has a second resolution and at FIG. 3 generating a plurality of tiles 310A1-310A3 of first resolution and tiles 310C1-310C2 of a second resolution.
Goyal ‘771 teaches at FIG. 13A-13B generating a plurality of tiles 1310A-1310Z of a first resolution and a plurality of tiles 1310B1-1310B2 of a second resolution and at FIG. 3 generating tiles 310A1-310A3 of a first resolution and tiles 310C1-310C2 of a second resolution),
wherein a first plurality of tiles associated with one resolution of the plurality of resolutions covers the same time period as a second plurality of tiles associated with another resolution of the plurality of resolutions (
Sorenson teaches at FIGS. 8A-8D that the root node 811 (the high-level meta tile) or the index nodes (second high-level meta tiles) has a first resolution and the leaf nodes 821-831-841-851-861 has a second resolution and at FIG. 3 generating a plurality of tiles 310A1-310A3 of first resolution which covers the same time period as the tiles 310C1-310C2 of a second resolution.
Goyal ‘771 teaches at FIG. 13A-13B generating a plurality of tiles 1310A-1310Z of a first resolution and a plurality of tiles 1310B1-1310B2 of a second resolution and at FIG. 3 generating tile 310A1-310A3 of a first resolution which covers the same time period as the tiles 310C1-310C2 of a second resolution),
wherein each tile of the plurality of tiles for the plurality of resolutions has a common number of N values (
Sorenson teaches at column 2, lines 45-60 that the time-series database may use a metadata index to identify the locations to which incoming time-series data points within particular time and space range are routed.
Sorenson teaches at column 9, lines 6-20 that the time-series data may be partitioned into a set of tiles 162 along non-overlapping temporal and spatial boundaries and at column 6, lines 5-31 that a data point may be associated with a timestamp, one or more dimensions (in name-value pairs) representing characteristics of the time series, and a measure representing a variable whose value is tracked over time. Timestamps may be provided by clients or automatically added upon ingestion. Measures may be identified by names and may often have numeric values. Measures may be used by the database 100 in generating aggregations such as min, max, average, and count. For example, a time series related to automobiles may be identified by a unique combination of values for dimensions of a vehicle identification number (VIN), country, state, and city, while measures for such a time series may include the battery state and the miles traveled per day. In one embodiment, queries may specify time intervals and/or dimension names and/or dimension values instead of or in addition to individual measures.
This teaching of storing the data points (measurements) with timestamps along with the 2D tiles being defined by spatial and temporal boundaries indicates that each 2D tile has the number of the data points where the number is defined by the temporal range divided by the sampling timestamp interval.
Sorenson teaches at FIG. 3 and column 12, lines 25-30 that tiles may be closed when the amount of data reached a threshold or when a maximum time interval is reached and at FIG. 6A and column 16, lines 20-30 that an index node may be limited to a maximum number of pointers to leaf nodes, beyond which the index may re-distribute the pointers to index nodes at the next lowest level.
Sorenson teaches at FIGS. 8A-8D and column 18, lines 18-65 that an index node has exceeded the maximum number of child references and the maximum number may be four and the root node 810 may point to five leaf nodes. to perform rebalancing of the index 122 when an intermediate index node has exceeded the maximum number of child pointers, the parent meta tile of the meta tile to be split may be identified……child pointers may be redistributed among the sibling index nodes and a new sibling index node may be created…if the parent does not exceed the maximum number of child pointers. If the parent node also exceeds the maximum number of child pointers, then the parent’s parent node may be identified for rebalancing and a single transaction in the data store 130 may be performed to create the new meta tiles and each with a different portion of the child pointers and at column 19, lines 4-20 that the maximum number of child pointers may be four.
Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database and the metadata index may be traversed to determine one or more storage locations of the requested time-series data in one or more data sources. Traversal may include selecting paths, e.g., pointers to leaf nodes whose spatial and temporal boundaries overlap with the spatial and temporal boundaries of the query. As a result of the traversal, one or more of the leaf nodes may be reached or selected and one or more other leaf nodes may not be reached or selected.
Goyal ‘771 teaches at FIG. 13A-13B generating a plurality of tiles 1310A-1310Z of a first resolution and a plurality of tiles 1310B1-1310B2 of a second resolution and at FIG. 3 generating tile 310A1-310A3 of a first resolution and tiles 310C1-310C2 of a second resolution),
wherein the N values represent all measurements associated with a duration of time covered by the tile in the time series data (
Goyal ‘771 teaches at FIG. 3 and column 12, lines 15-45 that in the example of FIG. 3, a set of time series may be routed to storage nodes 140A, 140B, and 140C based on a spatial range (e.g., using schema-based clustering). Particular partitions of time-series data may be mapped to particular storage nodes for writing data from the partitions to the hot tier 150A. For example, one partition may be assigned to storage node 140A that writes to the hot tier, another partition may be assigned to storage node 140B that writes to the hot tier, and yet another partition may be assigned to storage node 140C that writes to the hot tier. For a given time series or partition, tiles representing older windows of time may be termed “closed,” while a tile representing a current window of time may be termed “open.” Tiles may be closed when the amount of data reached a threshold or when a maximum time interval is reached. For current data points (e.g., data not received out of order), the storage node for a partition may write to an open tile. Out-of-order data may be routed to previously closed tiles in some circumstances. Tiles whose temporal boundaries are beyond the retention period (e.g., three hours) for the tier and table may be deemed expired and either deleted or marked for deletion. As shown in the example of FIG. 3, storage node 140A may write to an open tile 310A3 that was preceded in time by a tile 310A2 that was preceded in time by a now-expired tile 310A. Similarly, storage node 140B may write to an open tile 310B4 that was preceded in time by a tile 310B3 that was preceded in time by a tile 310B2 that was preceded in time by a now-expired tile 310B1. Additionally, storage node 140C may write to an open tile 310C2 that was preceded in time by a tile 310C1. As discussed above, the contents of a tile may be replicated (e.g., using three replicas) across different location or zones to achieve greater durability within the hot tier);
receiving, after generating the pluralities of tiles, a first user request from a requesting computer, the first user request specifying a first timestamp and a first resolution of the plurality of resolutions (
Sorenson teaches at column 9, lines 6-20 that the time-series data may be partitioned into a set of tiles 162 along non-overlapping temporal and spatial boundaries and at column 6, lines 5-31 that a data point may be associated with a timestamp, one or more dimensions (in name-value pairs) representing characteristics of the time series, and a measure representing a variable whose value is tracked over time. Timestamps may be provided by clients or automatically added upon ingestion. Measures may be identified by names and may often have numeric values. Measures may be used by the database 100 in generating aggregations such as min, max, average, and count. For example, a time series related to automobiles may be identified by a unique combination of values for dimensions of a vehicle identification number (VIN), country, state, and city, while measures for such a time series may include the battery state and the miles traveled per day. In one embodiment, queries may specify time intervals and/or dimension names and/or dimension values instead of or in addition to individual measures.
This teaching of storing the data points (measurements) with timestamps along with the 2D tiles being defined by spatial and temporal boundaries indicates that each 2D tile has the number of the data points where the number is defined by the temporal range divided by the sampling timestamp interval.
Sorenson teaches at FIG. 3 and column 12, lines 25-30 that tiles may be closed when the amount of data reached a threshold or when a maximum time interval is reached and at FIG. 6A and column 16, lines 20-30 that an index node may be limited to a maximum number of pointers to leaf nodes, beyond which the index may re-distribute the pointers to index nodes at the next lowest level.
Sorenson teaches at FIGS. 8A-8D and column 18, lines 18-65 that an index node has exceeded the maximum number of child references and the maximum number may be four and the root node 810 may point to five leaf nodes. to perform rebalancing of the index 122 when an intermediate index node has exceeded the maximum number of child pointers, the parent meta tile of the meta tile to be split may be identified……child pointers may be redistributed among the sibling index nodes and a new sibling index node may be created…if the parent does not exceed the maximum number of child pointers. If the parent node also exceeds the maximum number of child pointers, then the parent’s parent node may be identified for rebalancing and a single transaction in the data store 130 may be performed to create the new meta tiles and each with a different portion of the child pointers and at column 19, lines 4-20 that the maximum number of child pointers may be four.
Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database and the metadata index may be traversed to determine one or more storage locations of the requested time-series data in one or more data sources. Traversal may include selecting paths, e.g., pointers to leaf nodes whose spatial and temporal boundaries overlap with the spatial and temporal boundaries of the query. As a result of the traversal, one or more of the leaf nodes may be reached or selected and one or more other leaf nodes may not be reached or selected.
Goyal ‘771 teaches that column 7, lines 5-25 that a data point may be associated with a timestamp….timestamps may be provided by clients or automatically added upon ingestion. Measures may be identified by names and may often have numeric values. Measures may be used by the database 100 in generating aggregations such as min, max, average, and count. For example, a time series related to automobiles may be identified by a unique combination of values for dimensions of a vehicle identification number (VIN), country, state, and city, while measures for such a time series may include the battery state and the miles traveled per day. In one embodiment, queries may specify time intervals and/or dimension names and/or dimension values instead of or in addition to individual measures).
Determining, by a processor, a path in the data repository based on the first user request; retrieving a first tile from the data repository based on the path (
Sorenson teaches at column 5, lines 40-60 that in addition to the ingestion routers 110, the database 100 may include hosts such as storage nodes 140 and query processors 170. A fleet of storage nodes 140 may take the partitioned time-series data from the ingestion routers 110, potentially process the data in various ways, and add the data to one or more storage tiers 150A-150N. For example, the storage nodes 140 may write data from one partition to a “hot” storage tier 150A at a lower latency and to a “cold” storage tier 150N at a higher latency. In various embodiments, storage nodes may perform reordering, deduplication, aggregation of different time periods, rollups, and other transformations on time series data. Storage nodes 140 may perform tasks such as creating materialized views or derived tables based on a partition, such as an aggregation or rollup of a time interval. The tasks may include continuous queries that are performed repeatedly over time, e.g., to create aggregations for each hour or day of a time series as that time period is finalized. By co-locating related time-series using the clustering scheme 112, tasks such as aggregations and cross-series rollups may be optimized or otherwise have their performance improved).
Sorenson at least suggests: determining, by a processor, that no tile is available based on the first timestamp and the first resolution (
Sorenson teaches at FIG. 6B and column 16, lines 28-67 that FIG. 6B illustrates an example of a query performed using a metadata index with a root index node (meta tile) and an additional layer of index nodes (meta tiles), according to some embodiments. In some embodiments, to enable efficient lookup for data sources in a query, the metadata index service 120 may prune metadata based on input space and time bounding boxes such that meta tiles do not overlap in terms of bounding boxes. As shown in the example of FIG. 6B, a query 690 may be submitted (e.g., using the query processor(s) 170) that represents a spatial range and/or temporal range. The bounding box of the query 690 with respect to the spatial range 601 and temporal range 609 of the meta tile 610 is illustrated in FIG. 6B. To identify leaf nodes that include storage location information relevant to the query, the index 122 may be traversed from the root node 610 while selecting paths whose spatial and temporal ranges are relevant to those of the query 690. In the example of FIG. 6B, traversal need not proceed to index node 620 or index node 630 because those nodes do not represent spatial and temporal ranges desired by the query 690. However, traversal may proceed to index node 640 because it represents spatial and temporal ranges sought by the query 690. For similar reasons, traversal may then proceed to the leaf node 660 referenced by pointer 641 and to the leaf node 670 referenced by pointer 642, and the storage location information may be retrieved using those leaf nodes to determine where to direct a relevant portion of the query 690 (e.g., to one or more database clusters storing tiles that correspond to leaf nodes 660 and 670). Similarly, traversal may proceed to index node 650 because it represents spatial and temporal ranges sought by the query 690. Traversal may then proceed to the leaf node 680 referenced by pointer 652 but not to the leaf node referenced by pointer 651, and the storage location information may be retrieved using the leaf node 680 to determine where to direct a relevant portion of the query 690 (e.g., to a database cluster storing a tile that corresponds to leaf node 680).
Sorenson teaches at column 19, lines 45-60 that FIG. 9 is a flowchart illustrating a method for using a scalable metadata index for a time-series database, according to some embodiments. As shown in 900, a query may be received by a query processor of a time-series database, e.g., based on user input via a user interface or input via a programmatic interface. The query may include or indicate spatial and temporal boundaries of requested time-series data in a particular customer table. For example, the spatial boundaries may include one or more specific values for keys or a range of values for keys. The temporal boundaries may include a starting time and an ending time.
Sorenson teaches at column 20, lines 30-55 that as shown in 930, one or more elements of time-series data relevant to the query may be obtained or retrieved from the storage location(s) identified using the metadata index. To maintain high availability and high throughput for queries of time-series data, the time-series database may use the metadata index service to identify the locations to which queries for particular time and space ranges are routed);
Goyal teaches: determining, by a processor, that no tile is available based on the first timestamp and the first resolution (
Goyal teaches at column 13, lines 20-35 that by using the original tile as a source and performing a query of the original tile for data points within the new tile's range. In one embodiment, for a temporal split initiated before the starting time of the new tile, a backfill may be unnecessary because data within the new tile's time range may not have been received by the database 100. In one embodiment, a backfill may be attempted, but a query of the original tile for data within the new tile's boundaries may return no data.
Saxena teaches at FIG. 4A and column 13, lines 8-20 that the resource usage monitoring 183 may determine that task 175B is consuming an excessive amount of resources 171B relative to one or more resource usage restrictions associated with that task. The database 100 may terminate that task 175B to enforce the resource usage restriction(s). Task termination may involve discontinuing execution of the task 175B whose resource usage exceeds a resource usage restriction. The control plane 180 may notify the corresponding client of the termination due to excessive resource usage. The host at which the task 175B was terminated may be left with more available resources for execution of other tasks.).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated Goyal’s determining that no tile is available for the query timestamp and the first resolution tile into Goyal 771/Sorenson’ tile querying to have determined that the timestamp of the query tile is not within the new tile’s boundaries. One of the ordinary skill in the art would have been motivated to have determined the query result based on the query timestamp and query resolution.
Kumar and Guha teach that a first number of measurements associated with the first duration of time in the time series data being less than a second number of measurements associated with a second duration of time based on a second timestamp and the first resolution (
Kumar teaches at column 18, lines 30-64 that respective split criteria, e.g., the maximum number of keys for which entries can be accommodated at a given node may be defined for respective levels within the tree-based index, e.g., a root node may meet its split criterion when it has reached R entries, a leaf node meet its split criterion which it has reached F entries….timestamps corresponding to the N most recent writes to a given node may be stored in the node and the node may be deemed to have met its split criterion if the number of writes to it within a specified period T exceed a threshold.
Guha teaches at column 5, lines 60-67 and column 6, lines 1-10 that as new data points of the stream arrive, each of the trees of a random cut forest may represent a dynamically updated sample of the stream’s observation records….a node representing the new data point may be added to the tree by adding a new leaf node the added data point.
Guha taches at column 5, lines 15-20 that leaf nodes correspond to individual points representing minimal bounding boxes and at column 11, lines 25-40 that the SMAS may first collect a baseline set of data points from the specified streaming data sources to generate an initial forest of random cut trees, with each tree corresponding to a particular subset of the baseline set and the leaf nodes of the trees may correspond to respective data points and Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated Guha/Kumar’s teaching that each leaf node representing a 2D tile includes the respective N data points (measurements) into Sorenson/Goyal ‘771’s storage of 2D tiles defined by spatial and temporal boundaries of the data points sampled at the nanosecond resolution timestamps. One of the ordinary skill in the art would have been motivated to have provided a tree structure for storing a set of data points (measurements).
Mills teaches that a first number of measurements associated with the first duration of time in the time series data being less than a second number of measurements associated with a second duration of time based on a second timestamp and the first resolution (
Mills teaches at FIG. 2 and Paragraph 0036 that elements within the range starting at 200A and ending at 200C will be input to element 201A. Data with time stamps 12:00:04 AM and 12:59:57 AM in stream 200 are contained in element 201A.
Mills teaches at FIG. 2 that each YEAR super-tile has a plurality of tiles with one resolution of the plurality of resolutions {MONTHS, DAYS, HOURS, SECONDS} wherein each plurality of tiles 200-201-202-203 is associated with a different resolution in FIG. 2 of Mills and each YEAR super-tile has a plurality of tiles with one resolution of the plurality of resolutions {MONTHS, DAYS, HOURS, SECONDS}),
Mills teaches at FIG. 2 and Paragraph 0036 that each element stream 202 (each DAY-tile) may also include a sum and an average. It is understood that each element stream 202 (each DAY-tile) is a tile and each element stream 202 includes a common number of N values. As shown in FIG. 2, there is a total of 31 element streams 202 (31 DAY-tiles) and each element stream 202 constitutes a tile. Mills additionally teaches at Paragraph 0070 that the system applies each valid rollup function (min, max, avg, sum, gap counts, etc.) to the base streams’ intervals and at Paragraph 0080 a button allows the user to select from a number of different rollup function results to display (avg, min, max, sum, gaps, …) and at Paragraph 0097 that the rollup stream 1104 (HOUR-tile corresponding the element stream 201 of FIG. 2) may have been defined by the user to retrieve/display stream results as a single aggregation function described herein, such as sum, min, max, avg. etc. and at Paragraph 0099 that each of nine aggregation functions (FIRST, LAST, AVG, MIN, MAX, NONGAPS, SUM, MIN DATE, MAX DATE) is associated with one of the sub-streams 1106-1114 associated with the rollup stream 1104 (an hours-based rollup stream). It is clearly understood that each Hours-Tile 1104 includes a common number of 9 values. Mills teaches transmitting by the source devices 112 of FIG. 1 a first response including the first HOUR-tile 1104 and no other tile to the requesting computer 120 of FIG. 1 for generating a visualization of the 9 values of the first HOUR-tile 1104 simultaneously.
Mills teaches at Paragraph 0080 that the section 604 may also include a button which allows the user to select from a number of rollup function results to display, avg, min, max, sum, gaps.
Mills teaches FIG. 2 that the plurality of tiles 200 (tiles of seconds) covers the same time period of the super-tile 204 as the plurality of tiles 201/202/203 over a year period),
Mills teaches at FIGS. 6-7 and Paragraph 0077 that user requested a retrieval and calculation of rollups on a year’s worth of one-second data on a currently active stream, it would take several seconds just to read the one-second data off the disc drive and at Paragraph 0079 that the time extents used in the display areas 612, 614 is determined via time controls 616 and at Paragraph 0080 that the section 604 may also include a button called “Data Points” which allows the user to select from a number of different rollup function results to display and at Paragraph 0081 that the user is viewing one hour values…By selecting an element of the graph, the display changes to show five-minute intervals within the selected hour.
Mills teaches at Paragraph 0035 when measurement data is received via a network transaction with a remote sensor device, the measurement data is added to a storage location 200A for stream 200 based on a timestamp included with the data and the time interval associated with the storage location 200A.
Mills teaches at FIG. 2 identifying a storage location of a first tile 200/201/202/203 in the first supertile 204 and in response retrieving the first tile at the storage location and at Paragraph 0050 so stream 200 may actually record data in one-second intervals, but the data may be uploaded to the service every 10 seconds).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated Mills’s super-tile having higher resolution than a tile and elements within the ranges of tiles will be input to the super-tile such that the super-tile having higher measurements than its tile counterpart to have recognized that Goyal 771/Sorenson’s super-tile having higher resolution are tied to higher measurement data points than its tile counterpart because the measurement data points are gathered at nanosecond resolution. One of the ordinary skill in the art would have been motivated to have compared a greater amount of the data points measured at the timestamps covered by the large time range of the super-tile with less amount of the data points measured at the timestamps covered by the narrow time range of the tile.
Sorenson and Mills at least suggests the claim limitation of determining, by a processor, a path in the data repository based on the first user request; retrieving a first tile from the data repository based on the path (
Sorenson teaches at column 5, lines 40-60 that in addition to the ingestion routers 110, the database 100 may include hosts such as storage nodes 140 and query processors 170. A fleet of storage nodes 140 may take the partitioned time-series data from the ingestion routers 110, potentially process the data in various ways, and add the data to one or more storage tiers 150A-150N. For example, the storage nodes 140 may write data from one partition to a “hot” storage tier 150A at a lower latency and to a “cold” storage tier 150N at a higher latency. In various embodiments, storage nodes may perform reordering, deduplication, aggregation of different time periods, rollups, and other transformations on time series data. Storage nodes 140 may perform tasks such as creating materialized views or derived tables based on a partition, such as an aggregation or rollup of a time interval. The tasks may include continuous queries that are performed repeatedly over time, e.g., to create aggregations for each hour or day of a time series as that time period is finalized. By co-locating related time-series using the clustering scheme 112, tasks such as aggregations and cross-series rollups may be optimized or otherwise have their performance improved).
Mills at least suggests Determining, by a processor, a path in the data repository based on the first user request; retrieving a first tile from the data repository based on the path (Mills teaches at FIG. 2 and Paragraph 0036 that each element stream 202 (each DAY-tile) may also include a sum and an average. It is understood that each element stream 202 (each DAY-tile) is a tile and each element stream 202 includes a common number of N values. As shown in FIG. 2, there is a total of 31 element streams 202 (31 DAY-tiles) and each element stream 202 constitutes a tile. Mills additionally teaches at Paragraph 0070 that the system applies each valid rollup function (min, max, avg, sum, gap counts, etc.) to the base streams’ intervals and at Paragraph 0080 a button allows the user to select from a number of different rollup function results to display (avg, min, max, sum, gaps, …) and at Paragraph 0097 that the rollup stream 1104 (HOUR-tile corresponding the element stream 201 of FIG. 2) may have been defined by the user to retrieve/display stream results as a single aggregation function described herein, such as sum, min, max, avg. etc. and at Paragraph 0099 that each of nine aggregation functions (FIRST, LAST, AVG, MIN, MAX, NONGAPS, SUM, MIN DATE, MAX DATE) is associated with one of the sub-streams 1106-1114 associated with the rollup stream 1104 (an hours-based rollup stream). It is clearly understood that each Hours-Tile 1104 includes a common number of 9 values. Mills at least suggests transmitting by the source devices 112 of FIG. 1 a first response including the first HOUR-tile 1104 and no other tile to the requesting computer 120 of FIG. 1 for generating a visualization of the 9 values of the first HOUR-tile 1104 simultaneously).
Beedgen implicitly teaches Determining, by a processor, a path in the data repository based on the first user request; retrieving a first tile from the data repository based on the path (
Beedgen teaches at Paragraph 0290 for a query over a time range within the last 24 hours, an existing system would scan 90* more data than strictly necessary. Using the techniques described herein, the system would be aware that 89,000 of the time series have no data in the last 24 hours. Thus, the techniques provide performance improvements that allow for pre-filtering down to the 1,000 entries (corresponding to the one 24-hour tile) which may actually contain data.
Beedgen shows at FIG. 17 and Paragraph 0296-0297 displaying a plurality of aggregated values (e.g., average, 99th percentiles) for an aggregated 24-hour window (24-hour buckets/tiles) while the time series is divided into the two-super-tiles (partitions).
Beedgen teaches at Paragraph 0262 bucketing the raw logs into buckets of time intervals such as one-minute buckets or five-minute buckets and at Paragraph 0296 that the 24-hour window used in the examples described herein may be selected and at Paragraph 0297 involving time-series indexing of time series with a 24-hour threshold that buckets time series into two partitions (24-hour buckets).
Beedgen teaches at Paragraph 0270 that it is possible to display the results of a counting aggregation query by time and at Paragraph 0273 that users would like to query the metrics time series in aggregation. A user might wish to see, for example, the average of all CPU usage over time in a cluster of machines. When they query the system, users will then specify only a subset of the identifying metadata they are interested in. The system will then match all the time series identified by the subset of identifying metadata provided, and execute the query using a desired aggregation function (average, 99th percentiles, …) over all the data points in all the time series.
Beedgen teaches at Paragraph 0297 that finer partitioning may be provided by adding a time level indexing scheme ta the granularity of weeks or months and at FIG. 20 and Paragraph 0317 receiving a query and the query comprising a set of query metadata and a query time range and the selected metrics time series is returned and the selected metrics time series is visualized in a graphical user interface).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated Beedgen’s teaching of displaying multiple aggregated values associated with each aggregation unit time interval/zone (24 hours) for a number of aggregated values based on the aggregation function to have modified Goyal 771/Sorenson and Mills’s display of aggregated values to have displayed multiple aggregated values simultaneously at each aggregation unit time interval/zone. One of the ordinary skill in the art would have been motivated to have provided multiple aggregated values for each aggregation unit time interval/zone.
In the same field of endeavor, Kawata implicitly teaches at FIG. 7 and 16-17 and Paragraph 0133 and Paragraph 0147 Determining, by a processor, a path in the data repository based on the first user request; retrieving a first tile from the data repository based on the path (
Kawata teaches at FIG. 8 and Paragraph 0093-0094 that aggregation unit 610 is the 24-hour buckets/tiles when the 24-hour time input frame is selected and the evaluation start date/time input frame 604 is an input field for the administrator to operate the input/output device 30 to specify the date and time to start the evaluation of the cluster. Kawata teaches at FIG. 13 and Paragraph 0132 that each of the histograms 612a/612b/612c/612d corresponding to the 24-hour bucket/time is separately created at a time for each aggregation unit time.
Kawata teaches at Paragraph 0133 that the graph 602 including histograms is displayed and the measured values are aggregated based on the input values of the graph display start date/time input frame 608, the graph display end date/time input frame 609 and the aggregation unit time input frame 610 and at Paragraph 0147 and Paragraph 0151 that the graph of FIG. 14 is displayed as a graph with the aggregation unit time being “12 hours” and at FIG. 7 that Region 1, Region 2, Region 3 and Region 4 correspond to the claimed super-tiles and at FIGS. 16-17 and each bar graph represents a super-tile wherein a plurality of aggregated values of each bar tile/measurement are displayed simultaneously for clusters c1/c2/c3 of each bar chart/tile of each aggregation unit time in FIG. 17 and for measurement item a and measurement item b of each bar tile in FIG. 7).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated Kawata’s teaching of displaying multiple aggregated values with respect to each aggregation unit time interval/zone (e.g., 24-hour) for a number of measurement units/clusters to have modified Goyal 771/Sorenson, Mills and Beedgen’s display of aggregated values to have displayed multiple measurement units at each aggregation unit time interval/zone. One of the ordinary skill in the art would have been motivated to have provided multiple aggregated values for each aggregation unit time interval/zone.
Re Claim 2:
The claim 2 encompasses the same scope of invention as that of the claim 1 except additional claim limitation that the pluralities of tiles forming a tree, with each node corresponding to a tile, each level corresponding to a resolution, and a leaf corresponding to a tile having N measurements in the time series data as the N values.
Sorenson implicitly teaches the claim limitation that the pluralities of tiles forming a tree, with each node corresponding to a tile, each level corresponding to a resolution, and a leaf corresponding to a tile having N measurements in the time series data as the N values (
Sorenson teaches at column 2, lines 66-67 and column 3, lines 1-20 that the metadata index may be implemented using a directed acyclic graph (DAG) or other tree-like data structure. The graph may include various types of nodes such as a root index node representing a high-level meta tile, optionally one or more intermediate index nodes representing portions of the high-level meta tile, and a layer of leaf nodes that include pointers to location data for particular tiles in the underlying data store. Particular nodes may be associated with particular spatial and temporal ranges of time-series data.
Sorenson teaches at FIG. 4 and column 12, lines 47-67 that FIG. 4 illustrates an example of a scalable metadata index for a time-series database including a root node (meta tile) and a leaf node, according to some embodiments. The metadata index 122 may be implemented using a directed acyclic graph (DAG) or other tree-like data structure. In some embodiments, the metadata index 122 may use a two-dimensional B+ tree variant for storing time-series metadata. The graph may include nodes that are associated with particular spatial and temporal ranges of time-series data. The graph may include a root index node representing a high-level meta tile for a particular customer table. For example, the index 122 may include the root node 410 representing such a meta tile. The meta tile may represent the entire spatial range 401 and temporal range 409 of a particular table. The temporal range 409 may begin at a specific date and time and may extend to infinity or to a date and time in the far future. Customer table metadata 132 may include a pointer to the root node 410 for a given table. The graph may optionally include one or more intermediate index nodes that descend from the root node 410 or from other index nodes, each representing particular a portion of the spatial and temporal range of any parent index nodes such as the high-level meta tile 410. Below the index node(s), the graph may include a layer of leaf nodes that include pointers to location data for particular tiles in the underlying data store, where each leaf node represents a spatial and temporal range within the broader spatial and temporal range of a parent index node. For example, the index 122 may include a leaf node 420. The example shown in FIG. 4 may represent the state of an index 122 on creation of the table, where the table includes only one two-dimensional tile representing the entire spatial range 401 and temporal range 409 of the corresponding table.
Sorenson teaches at FIG. 4 and column 13, lines 1-12 that the graph may include a layer of leaf nodes that include pointers to location data for particular tiles in the underlying data store, where each leaf node represents a spatial and temporal range within the broader spatial and temporal range of a parent index node. Sorenson teaches at FIG. 8B that the index node 870 includes a leaf node pointer 811 to a first leaf node 820 representing a first portion of the temporal range 809, a leaf node pointer 812 to a second leaf node 830 representing a second portion of the temporal range 809A where each leaf node represents a spatial and temporal range within the broader spatial and temporal range of a parent index node. Accordingly, the number of data points (measurements) in the root node 810 (a high-level meta tile) is larger than the number of measurements of each leaf node (a lower level meta tile).
Sorenson teaches at column 9, lines 6-20 that the time-series data may be partitioned into a set of tiles 162 along non-overlapping temporal and spatial boundaries and at column 6, lines 5-31 that a data point may be associated with a timestamp, one or more dimensions (in name-value pairs) representing characteristics of the time series, and a measure representing a variable whose value is tracked over time. Timestamps may be provided by clients or automatically added upon ingestion. Measures may be identified by names and may often have numeric values. Measures may be used by the database 100 in generating aggregations such as min, max, average, and count. For example, a time series related to automobiles may be identified by a unique combination of values for dimensions of a vehicle identification number (VIN), country, state, and city, while measures for such a time series may include the battery state and the miles traveled per day. In one embodiment, queries may specify time intervals and/or dimension names and/or dimension values instead of or in addition to individual measures.
This teaching of storing the data points (measurements) with timestamps along with the 2D tiles being defined by spatial and temporal boundaries indicates that each 2D tile has the number of the data points where the number is defined by the temporal range divided by the sampling timestamp interval.
Sorenson teaches at FIG. 3 and column 12, lines 25-30 that tiles may be closed when the amount of data reached a threshold or when a maximum time interval is reached and at FIG. 6A and column 16, lines 20-30 that an index node may be limited to a maximum number of pointers to leaf nodes, beyond which the index may re-distribute the pointers to index nodes at the next lowest level.
Sorenson teaches at FIGS. 8A-8D and column 18, lines 18-65 that an index node has exceeded the maximum number of child references and the maximum number may be four and the root node 810 may point to five leaf nodes. to perform rebalancing of the index 122 when an intermediate index node has exceeded the maximum number of child pointers, the parent meta tile of the meta tile to be split may be identified……child pointers may be redistributed among the sibling index nodes and a new sibling index node may be created…if the parent does not exceed the maximum number of child pointers. If the parent node also exceeds the maximum number of child pointers, then the parent’s parent node may be identified for rebalancing and a single transaction in the data store 130 may be performed to create the new meta tiles and each with a different portion of the child pointers and at column 19, lines 4-20 that the maximum number of child pointers may be four.
Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database and the metadata index may be traversed to determine one or more storage locations of the requested time-series data in one or more data sources. Traversal may include selecting paths, e.g., pointers to leaf nodes whose spatial and temporal boundaries overlap with the spatial and temporal boundaries of the query. As a result of the traversal, one or more of the leaf nodes may be reached or selected and one or more other leaf nodes may not be reached or selected).
Sorenson et al. US-Patent No. 11,599,516 (hereinafter Sorenson) in view of Guha et al. US Patent No. 10,902,062 (hereinafter Guha) teaches the claim limitation that the pluralities of tiles forming a tree, with each node corresponding to a tile, each level corresponding to a resolution, and a leaf corresponding to a tile having N measurements in the time series data as the N values (
Guha taches at column 5, lines 15-20 that leaf nodes correspond to individual points representing minimal bounding boxes and at column 11, lines 25-40 that the SMAS may first collect a baseline set of data points from the specified streaming data sources to generate an initial forest of random cut trees, with each tree corresponding to a particular subset of the baseline set and the leaf nodes of the trees may correspond to respective data points and Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database.
Accordingly, each leaf node corresponding to a 2D tile includes the respective N data points).
Sorenson teaches at column 9, lines 6-20 that the time-series data may be partitioned into a set of tiles 162 along non-overlapping temporal and spatial boundaries.
This teaching of storing the data points (measurements) with nanosecond resolution timestamps along with the 2D tiles being defined by spatial and temporal boundaries indicates that each 2D tile has the number of the data points where the number is defined by the temporal range divided by the nanosecond resolution.
Sorenson teaches at FIG. 3 and column 12, lines 25-30 that tiles may be closed when the amount of data reached a threshold or when a maximum time interval is reached and at FIG. 6A and column 16, lines 20-30 that an index node may be limited to a maximum number of pointers to leaf nodes, beyond which the index may re-distribute the pointers to index nodes at the next lowest level.
Sorenson teaches at FIGS. 8A-8D and column 18, lines 18-65 that an index node has exceeded the maximum number of child references and the maximum number may be four and the root node 810 may point to five leaf nodes. to perform rebalancing of the index 122 when an intermediate index node has exceeded the maximum number of child pointers, the parent meta tile of the meta tile to be split may be identified……child pointers may be redistributed among the sibling index nodes and a new sibling index node may be created…if the parent does not exceed the maximum number of child pointers. If the parent node also exceeds the maximum number of child pointers, then the parent’s parent node may be identified for rebalancing and a single transaction in the data store 130 may be performed to create the new meta tiles and each with a different portion of the child pointers and at column 19, lines 4-20 that the maximum number of child pointers may be four.
Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database and the metadata index may be traversed to determine one or more storage locations of the requested time-series data in one or more data sources. Traversal may include selecting paths, e.g., pointers to leaf nodes whose spatial and temporal boundaries overlap with the spatial and temporal boundaries of the query. As a result of the traversal, one or more of the leaf nodes may be reached or selected and one or more other leaf nodes may not be reached or selected).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated Sorenson and Guha’s teaching that each leaf node representing a 2D tile includes the respective N data points (measurements) into Sorenson and Goyal ‘771’s storage of 2D tiles defined by spatial and temporal boundaries of the data points sampled at the nanosecond resolution timestamps. One of the ordinary skill in the art would have been motivated to have provided a tree structure for storing a set of data points (measurements).
Re Claim 3:
The claim 3 encompasses the same scope of invention as that of the claim 2 except additional claim limitation of receiving new measurements in additional time series data; adding a specific measurement of the new measurements to a specific leaf based on a specific timestamp of the specific measurement.
Sorenson further teaches the claim limitation of receiving new measurements in additional time series data; adding a specific measurement of the new measurements to a specific leaf based on a specific timestamp of the specific measurement (
Sorenson teaches at FIG. 4 and column 13, lines 1-12 that the graph may include a layer of leaf nodes that include pointers to location data for particular tiles in the underlying data store, where each leaf node represents a spatial and temporal range within the broader spatial and temporal range of a parent index node. Sorenson teaches at FIG. 8B that the index node 870 includes a leaf node pointer 811 to a first leaf node 820 representing a first portion of the temporal range 809, a leaf node pointer 812 to a second leaf node 830 representing a second portion of the temporal range 809A where each leaf node represents a spatial and temporal range within the broader spatial and temporal range of a parent index node. Accordingly, the number of data points (measurements) in the root node 810 (a high-level meta tile) is larger than the number of measurements of each leaf node (a lower level meta tile).
Sorenson teaches at column 9, lines 6-20 that the time-series data may be partitioned into a set of tiles 162 along non-overlapping temporal and spatial boundaries and at column 6, lines 5-31 that a data point may be associated with a timestamp, one or more dimensions (in name-value pairs) representing characteristics of the time series, and a measure representing a variable whose value is tracked over time. Timestamps may be provided by clients or automatically added upon ingestion. Measures may be identified by names and may often have numeric values. Measures may be used by the database 100 in generating aggregations such as min, max, average, and count. For example, a time series related to automobiles may be identified by a unique combination of values for dimensions of a vehicle identification number (VIN), country, state, and city, while measures for such a time series may include the battery state and the miles traveled per day. In one embodiment, queries may specify time intervals and/or dimension names and/or dimension values instead of or in addition to individual measures.
This teaching of storing the data points (measurements) with timestamps along with the 2D tiles being defined by spatial and temporal boundaries indicates that each 2D tile has the number of the data points where the number is defined by the temporal range divided by the sampling timestamp interval.
Sorenson teaches at FIG. 3 and column 12, lines 25-30 that tiles may be closed when the amount of data reached a threshold or when a maximum time interval is reached and at FIG. 6A and column 16, lines 20-30 that an index node may be limited to a maximum number of pointers to leaf nodes, beyond which the index may re-distribute the pointers to index nodes at the next lowest level.
Sorenson teaches at FIGS. 8A-8D and column 18, lines 18-65 that an index node has exceeded the maximum number of child references and the maximum number may be four and the root node 810 may point to five leaf nodes. to perform rebalancing of the index 122 when an intermediate index node has exceeded the maximum number of child pointers, the parent meta tile of the meta tile to be split may be identified……child pointers may be redistributed among the sibling index nodes and a new sibling index node may be created…if the parent does not exceed the maximum number of child pointers. If the parent node also exceeds the maximum number of child pointers, then the parent’s parent node may be identified for rebalancing and a single transaction in the data store 130 may be performed to create the new meta tiles and each with a different portion of the child pointers and at column 19, lines 4-20 that the maximum number of child pointers may be four.
Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database and the metadata index may be traversed to determine one or more storage locations of the requested time-series data in one or more data sources. Traversal may include selecting paths, e.g., pointers to leaf nodes whose spatial and temporal boundaries overlap with the spatial and temporal boundaries of the query. As a result of the traversal, one or more of the leaf nodes may be reached or selected and one or more other leaf nodes may not be reached or selected).
Sorenson et al. US-Patent No. 11,599,516 (hereinafter Sorenson) in view of Guha et al. US Patent No. 10,902,062 (hereinafter Guha) and Kumar et al. US-Patent No. 11,366,801 (hereinafter Kumar) teaches the claim limitation of receiving new measurements in additional time series data; adding a specific measurement of the new measurements to a specific leaf based on a specific timestamp of the specific measurement (
Kumar teaches at column 18, lines 30-64 that respective split criteria, e.g., the maximum number of keys for which entries can be accommodated at a given node may be defined for respective levels within the tree-based index, e.g., a leaf node meet its split criterion which it has reached F entries….timestamps corresponding to the N most recent writes to a given node may be stored in the node and the node may be deemed to have met its split criterion if the number of writes to it within a specified period T exceed a threshold.
Guha teaches at column 5, lines 60-67 and column 6, lines 1-10 that as new data points of the stream arrive, each of the trees of a random cut forest may represent a dynamically updated sample of the stream’s observation records….a node representing the new data point may be added to the tree by adding a new leaf node the added data point.
Guha taches at column 5, lines 15-20 that leaf nodes correspond to individual points representing minimal bounding boxes and at column 11, lines 25-40 that the SMAS may first collect a baseline set of data points from the specified streaming data sources to generate an initial forest of random cut trees, with each tree corresponding to a particular subset of the baseline set and the leaf nodes of the trees may correspond to respective data points and Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database.
Accordingly, each leaf node corresponding to a 2D tile includes the respective N data points).
Sorenson teaches at column 9, lines 6-20 that the time-series data may be partitioned into a set of tiles 162 along non-overlapping temporal and spatial boundaries and at column 6, lines 5-31 that a data point may be associated with a timestamp, one or more dimensions (in name-value pairs) representing characteristics of the time series, and a measure representing a variable whose value is tracked over time. Timestamps may be provided by clients or automatically added upon ingestion. Measures may be identified by names and may often have numeric values. Measures may be used by the database 100 in generating aggregations such as min, max, average, and count. For example, a time series related to automobiles may be identified by a unique combination of values for dimensions of a vehicle identification number (VIN), country, state, and city, while measures for such a time series may include the battery state and the miles traveled per day. In one embodiment, queries may specify time intervals and/or dimension names and/or dimension values instead of or in addition to individual measures.
This teaching of storing the data points (measurements) with timestamps along with the 2D tiles being defined by spatial and temporal boundaries indicates that each 2D tile has the number of the data points where the number is defined by the temporal range divided by the sampling timestamp interval.
Sorenson teaches at FIG. 3 and column 12, lines 25-30 that tiles may be closed when the amount of data reached a threshold or when a maximum time interval is reached and at FIG. 6A and column 16, lines 20-30 that an index node may be limited to a maximum number of pointers to leaf nodes, beyond which the index may re-distribute the pointers to index nodes at the next lowest level.
Sorenson teaches at FIGS. 8A-8D and column 18, lines 18-65 that an index node has exceeded the maximum number of child references and the maximum number may be four and the root node 810 may point to five leaf nodes. to perform rebalancing of the index 122 when an intermediate index node has exceeded the maximum number of child pointers, the parent meta tile of the meta tile to be split may be identified……child pointers may be redistributed among the sibling index nodes and a new sibling index node may be created…if the parent does not exceed the maximum number of child pointers. If the parent node also exceeds the maximum number of child pointers, then the parent’s parent node may be identified for rebalancing and a single transaction in the data store 130 may be performed to create the new meta tiles and each with a different portion of the child pointers and at column 19, lines 4-20 that the maximum number of child pointers may be four.
Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database and the metadata index may be traversed to determine one or more storage locations of the requested time-series data in one or more data sources. Traversal may include selecting paths, e.g., pointers to leaf nodes whose spatial and temporal boundaries overlap with the spatial and temporal boundaries of the query. As a result of the traversal, one or more of the leaf nodes may be reached or selected and one or more other leaf nodes may not be reached or selected).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated Sorenson and Guha/Kumar’s teaching that each leaf node representing a 2D tile includes the respective N data points (measurements) into Goyal ‘771’s storage of 2D tiles defined by spatial and temporal boundaries of the data points sampled at the nanosecond resolution timestamps. One of the ordinary skill in the art would have been motivated to have provided a tree structure for storing a set of data points (measurements).
Re Claim 4:
The claim 4 encompasses the same scope of invention as that of the claim 3 except additional claim limitation that determining that a number of measurements in the specific leaf exceeds N; creating a new leaf covering a new duration of time following a specific duration time covered by the specific leaf.
Sorenson further teaches the claim limitation that determining that a number of measurements in the specific leaf exceeds N; creating a new leaf covering a new duration of time following a specific duration time covered by the specific leaf (
Sorenson teaches at FIG. 4 and column 13, lines 1-12 that the graph may include a layer of leaf nodes that include pointers to location data for particular tiles in the underlying data store, where each leaf node represents a spatial and temporal range within the broader spatial and temporal range of a parent index node. Sorenson teaches at FIG. 8B that the index node 870 includes a leaf node pointer 811 to a first leaf node 820 representing a first portion of the temporal range 809, a leaf node pointer 812 to a second leaf node 830 representing a second portion of the temporal range 809A where each leaf node represents a spatial and temporal range within the broader spatial and temporal range of a parent index node. Accordingly, the number of data points (measurements) in the root node 810 (a high-level meta tile) is larger than the number of measurements of each leaf node (a lower level meta tile).
Sorenson teaches at column 9, lines 6-20 that the time-series data may be partitioned into a set of tiles 162 along non-overlapping temporal and spatial boundaries and at column 6, lines 5-31 that a data point may be associated with a timestamp, one or more dimensions (in name-value pairs) representing characteristics of the time series, and a measure representing a variable whose value is tracked over time. Timestamps may be provided by clients or automatically added upon ingestion. Measures may be identified by names and may often have numeric values. Measures may be used by the database 100 in generating aggregations such as min, max, average, and count. For example, a time series related to automobiles may be identified by a unique combination of values for dimensions of a vehicle identification number (VIN), country, state, and city, while measures for such a time series may include the battery state and the miles traveled per day. In one embodiment, queries may specify time intervals and/or dimension names and/or dimension values instead of or in addition to individual measures.
This teaching of storing the data points (measurements) with timestamps along with the 2D tiles being defined by spatial and temporal boundaries indicates that each 2D tile has the number of the data points where the number is defined by the temporal range divided by the sampling timestamp interval.
Sorenson teaches at FIG. 3 and column 12, lines 25-30 that tiles may be closed when the amount of data reached a threshold or when a maximum time interval is reached and at FIG. 6A and column 16, lines 20-30 that an index node may be limited to a maximum number of pointers to leaf nodes, beyond which the index may re-distribute the pointers to index nodes at the next lowest level.
Sorenson teaches at FIGS. 8A-8D and column 18, lines 18-65 that an index node has exceeded the maximum number of child references and the maximum number may be four and the root node 810 may point to five leaf nodes. to perform rebalancing of the index 122 when an intermediate index node has exceeded the maximum number of child pointers, the parent meta tile of the meta tile to be split may be identified……child pointers may be redistributed among the sibling index nodes and a new sibling index node may be created…if the parent does not exceed the maximum number of child pointers. If the parent node also exceeds the maximum number of child pointers, then the parent’s parent node may be identified for rebalancing and a single transaction in the data store 130 may be performed to create the new meta tiles and each with a different portion of the child pointers and at column 19, lines 4-20 that the maximum number of child pointers may be four.
Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database and the metadata index may be traversed to determine one or more storage locations of the requested time-series data in one or more data sources. Traversal may include selecting paths, e.g., pointers to leaf nodes whose spatial and temporal boundaries overlap with the spatial and temporal boundaries of the query. As a result of the traversal, one or more of the leaf nodes may be reached or selected and one or more other leaf nodes may not be reached or selected).
Sorenson et al. US-Patent No. 11,599,516 (hereinafter Sorenson) in view of Guha et al. US Patent No. 10,902,062 (hereinafter Guha) and Kumar et al. US-Patent No. 11,366,801 (hereinafter Kumar) teaches the claim limitation determining that a number of measurements in the specific leaf exceeds N; creating a new leaf covering a new duration of time following a specific duration time covered by the specific leaf (
Kumar teaches at column 18, lines 30-64 that respective split criteria, e.g., the maximum number of keys for which entries can be accommodated at a given node may be defined for respective levels within the tree-based index, e.g., a leaf node meet its split criterion which it has reached F entries….timestamps corresponding to the N most recent writes to a given node may be stored in the node and the node may be deemed to have met its split criterion if the number of writes to it within a specified period T exceed a threshold.
Guha teaches at column 5, lines 60-67 and column 6, lines 1-10 that as new data points of the stream arrive, each of the trees of a random cut forest may represent a dynamically updated sample of the stream’s observation records….a node representing the new data point may be added to the tree by adding a new leaf node the added data point and at column 19, lines 20-25 that the split at the leaf node would make the depth of the new leaf node L+1.
Guha taches at column 5, lines 15-20 that leaf nodes correspond to individual points representing minimal bounding boxes and at column 11, lines 25-40 that the SMAS may first collect a baseline set of data points from the specified streaming data sources to generate an initial forest of random cut trees, with each tree corresponding to a particular subset of the baseline set and the leaf nodes of the trees may correspond to respective data points and Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database.
Accordingly, each leaf node corresponding to a 2D tile includes the respective N data points).
Sorenson teaches at column 9, lines 6-20 that the time-series data may be partitioned into a set of tiles 162 along non-overlapping temporal and spatial boundaries.
This teaching of storing the data points (measurements) with nanosecond resolution timestamps along with the 2D tiles being defined by spatial and temporal boundaries indicates that each 2D tile has the number of the data points where the number is defined by the temporal range divided by the nanosecond resolution.
Sorenson teaches at FIG. 3 and column 12, lines 25-30 that tiles may be closed when the amount of data reached a threshold or when a maximum time interval is reached and at FIG. 6A and column 16, lines 20-30 that an index node may be limited to a maximum number of pointers to leaf nodes, beyond which the index may re-distribute the pointers to index nodes at the next lowest level.
Sorenson teaches at FIGS. 8A-8D and column 18, lines 18-65 that an index node has exceeded the maximum number of child references and the maximum number may be four and the root node 810 may point to five leaf nodes. to perform rebalancing of the index 122 when an intermediate index node has exceeded the maximum number of child pointers, the parent meta tile of the meta tile to be split may be identified……child pointers may be redistributed among the sibling index nodes and a new sibling index node may be created…if the parent does not exceed the maximum number of child pointers. If the parent node also exceeds the maximum number of child pointers, then the parent’s parent node may be identified for rebalancing and a single transaction in the data store 130 may be performed to create the new meta tiles and each with a different portion of the child pointers and at column 19, lines 4-20 that the maximum number of child pointers may be four.
Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database and the metadata index may be traversed to determine one or more storage locations of the requested time-series data in one or more data sources. Traversal may include selecting paths, e.g., pointers to leaf nodes whose spatial and temporal boundaries overlap with the spatial and temporal boundaries of the query. As a result of the traversal, one or more of the leaf nodes may be reached or selected and one or more other leaf nodes may not be reached or selected).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated Sorenson and Guha/Kumar’s teaching that each leaf node representing a 2D tile includes the respective N data points (measurements) into Goyal ‘771’s storage of 2D tiles defined by spatial and temporal boundaries of the data points sampled at the nanosecond resolution timestamps. One of the ordinary skill in the art would have been motivated to have provided a tree structure for storing a set of data points (measurements).
Re Claim 5:
The claim 5 encompasses the same scope of invention as that of the claim 3 except additional claim limitation that determining that a number of measurements in the specific leaf exceeds N; splitting the specific leaf into two leaves covering consecutive durations of time.
Sorenson further teaches the claim limitation of determining that a number of measurements in the specific leaf exceeds N; splitting the specific leaf into two leaves covering consecutive durations of time (
Sorenson teaches at FIG. 4 and column 13, lines 1-12 that the graph may include a layer of leaf nodes that include pointers to location data for particular tiles in the underlying data store, where each leaf node represents a spatial and temporal range within the broader spatial and temporal range of a parent index node. Sorenson teaches at FIG. 8B that the index node 870 includes a leaf node pointer 811 to a first leaf node 820 representing a first portion of the temporal range 809, a leaf node pointer 812 to a second leaf node 830 representing a second portion of the temporal range 809A where each leaf node represents a spatial and temporal range within the broader spatial and temporal range of a parent index node. Accordingly, the number of data points (measurements) in the root node 810 (a high-level meta tile) is larger than the number of measurements of each leaf node (a lower level meta tile).
Sorenson teaches at column 9, lines 6-20 that the time-series data may be partitioned into a set of tiles 162 along non-overlapping temporal and spatial boundaries and at column 6, lines 5-31 that a data point may be associated with a timestamp, one or more dimensions (in name-value pairs) representing characteristics of the time series, and a measure representing a variable whose value is tracked over time. Timestamps may be provided by clients or automatically added upon ingestion. Measures may be identified by names and may often have numeric values. Measures may be used by the database 100 in generating aggregations such as min, max, average, and count. For example, a time series related to automobiles may be identified by a unique combination of values for dimensions of a vehicle identification number (VIN), country, state, and city, while measures for such a time series may include the battery state and the miles traveled per day. In one embodiment, queries may specify time intervals and/or dimension names and/or dimension values instead of or in addition to individual measures.
This teaching of storing the data points (measurements) with timestamps along with the 2D tiles being defined by spatial and temporal boundaries indicates that each 2D tile has the number of the data points where the number is defined by the temporal range divided by the sampling timestamp interval.
Sorenson teaches at FIG. 3 and column 12, lines 25-30 that tiles may be closed when the amount of data reached a threshold or when a maximum time interval is reached and at FIG. 6A and column 16, lines 20-30 that an index node may be limited to a maximum number of pointers to leaf nodes, beyond which the index may re-distribute the pointers to index nodes at the next lowest level.
Sorenson teaches at FIGS. 8A-8D and column 18, lines 18-65 that an index node has exceeded the maximum number of child references and the maximum number may be four and the root node 810 may point to five leaf nodes. to perform rebalancing of the index 122 when an intermediate index node has exceeded the maximum number of child pointers, the parent meta tile of the meta tile to be split may be identified……child pointers may be redistributed among the sibling index nodes and a new sibling index node may be created…if the parent does not exceed the maximum number of child pointers. If the parent node also exceeds the maximum number of child pointers, then the parent’s parent node may be identified for rebalancing and a single transaction in the data store 130 may be performed to create the new meta tiles and each with a different portion of the child pointers and at column 19, lines 4-20 that the maximum number of child pointers may be four.
Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database and the metadata index may be traversed to determine one or more storage locations of the requested time-series data in one or more data sources. Traversal may include selecting paths, e.g., pointers to leaf nodes whose spatial and temporal boundaries overlap with the spatial and temporal boundaries of the query. As a result of the traversal, one or more of the leaf nodes may be reached or selected and one or more other leaf nodes may not be reached or selected).
Sorenson et al. US-Patent No. 11,599,516 (hereinafter Sorenson) in view of Guha et al. US Patent No. 10,902,062 (hereinafter Guha) and Kumar et al. US-Patent No. 11,366,801 (hereinafter Kumar) teaches the claim limitation of determining that a number of measurements in the specific leaf exceeds N; splitting the specific leaf into two leaves covering consecutive durations of time (
Kumar teaches at column 18, lines 30-64 that respective split criteria, e.g., the maximum number of keys for which entries can be accommodated at a given node may be defined for respective levels within the tree-based index, e.g., a root node may meet its split criterion when it has reached R entries, a leaf node meet its split criterion which it has reached F entries….timestamps corresponding to the N most recent writes to a given node may be stored in the node and the node may be deemed to have met its split criterion if the number of writes to it within a specified period T exceed a threshold.
Guha teaches at column 5, lines 60-67 and column 6, lines 1-10 that as new data points of the stream arrive, each of the trees of a random cut forest may represent a dynamically updated sample of the stream’s observation records….a node representing the new data point may be added to the tree by adding a new leaf node the added data point.
Guha taches at column 5, lines 15-20 that leaf nodes correspond to individual points representing minimal bounding boxes and at column 11, lines 25-40 that the SMAS may first collect a baseline set of data points from the specified streaming data sources to generate an initial forest of random cut trees, with each tree corresponding to a particular subset of the baseline set and the leaf nodes of the trees may correspond to respective data points and Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database.
Accordingly, each leaf node corresponding to a 2D tile includes the respective N data points).
Sorenson teaches at column 9, lines 6-20 that the time-series data may be partitioned into a set of tiles 162 along non-overlapping temporal and spatial boundaries.
This teaching of storing the data points (measurements) with nanosecond resolution timestamps along with the 2D tiles being defined by spatial and temporal boundaries indicates that each 2D tile has the number of the data points where the number is defined by the temporal range divided by the nanosecond resolution.
Sorenson teaches at FIG. 3 and column 12, lines 25-30 that tiles may be closed when the amount of data reached a threshold or when a maximum time interval is reached and at FIG. 6A and column 16, lines 20-30 that an index node may be limited to a maximum number of pointers to leaf nodes, beyond which the index may re-distribute the pointers to index nodes at the next lowest level.
Sorenson teaches at FIGS. 8A-8D and column 18, lines 18-65 that an index node has exceeded the maximum number of child references and the maximum number may be four and the root node 810 may point to five leaf nodes. to perform rebalancing of the index 122 when an intermediate index node has exceeded the maximum number of child pointers, the parent meta tile of the meta tile to be split may be identified……child pointers may be redistributed among the sibling index nodes and a new sibling index node may be created…if the parent does not exceed the maximum number of child pointers. If the parent node also exceeds the maximum number of child pointers, then the parent’s parent node may be identified for rebalancing and a single transaction in the data store 130 may be performed to create the new meta tiles and each with a different portion of the child pointers and at column 19, lines 4-20 that the maximum number of child pointers may be four.
Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database and the metadata index may be traversed to determine one or more storage locations of the requested time-series data in one or more data sources. Traversal may include selecting paths, e.g., pointers to leaf nodes whose spatial and temporal boundaries overlap with the spatial and temporal boundaries of the query. As a result of the traversal, one or more of the leaf nodes may be reached or selected and one or more other leaf nodes may not be reached or selected).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated Sorenson and Guha/Kumar’s teaching that each leaf node representing a 2D tile includes the respective N data points (measurements) into Goyal ‘771’s storage of 2D tiles defined by spatial and temporal boundaries of the data points sampled at the nanosecond resolution timestamps. One of the ordinary skill in the art would have been motivated to have provided a tree structure for storing a set of data points (measurements).
Re Claim 6:
The claim 6 encompasses the same scope of invention as that of the claim 2 except additional claim limitation that determining that a number of nodes at a certain level covering consecutive durations of time reaches N; creating a new node at a parent level of the certain level based on the nodes at the certain level.
Sorenson further teaches the claim limitation that determining that a number of nodes at a certain level covering consecutive durations of time reaches N; creating a new node at a parent level of the certain level based on the nodes at the certain level (
Sorenson teaches at FIG. 4 and column 13, lines 1-12 that the graph may include a layer of leaf nodes that include pointers to location data for particular tiles in the underlying data store, where each leaf node represents a spatial and temporal range within the broader spatial and temporal range of a parent index node. Sorenson teaches at FIG. 8B that the index node 870 includes a leaf node pointer 811 to a first leaf node 820 representing a first portion of the temporal range 809, a leaf node pointer 812 to a second leaf node 830 representing a second portion of the temporal range 809A where each leaf node represents a spatial and temporal range within the broader spatial and temporal range of a parent index node. Accordingly, the number of data points (measurements) in the root node 810 (a high-level meta tile) is larger than the number of measurements of each leaf node (a lower level meta tile).
Sorenson teaches at column 9, lines 6-20 that the time-series data may be partitioned into a set of tiles 162 along non-overlapping temporal and spatial boundaries and at column 6, lines 5-31 that a data point may be associated with a timestamp, one or more dimensions (in name-value pairs) representing characteristics of the time series, and a measure representing a variable whose value is tracked over time. Timestamps may be provided by clients or automatically added upon ingestion. Measures may be identified by names and may often have numeric values. Measures may be used by the database 100 in generating aggregations such as min, max, average, and count. For example, a time series related to automobiles may be identified by a unique combination of values for dimensions of a vehicle identification number (VIN), country, state, and city, while measures for such a time series may include the battery state and the miles traveled per day. In one embodiment, queries may specify time intervals and/or dimension names and/or dimension values instead of or in addition to individual measures.
This teaching of storing the data points (measurements) with timestamps along with the 2D tiles being defined by spatial and temporal boundaries indicates that each 2D tile has the number of the data points where the number is defined by the temporal range divided by the sampling timestamp interval.
Sorenson teaches at FIG. 3 and column 12, lines 25-30 that tiles may be closed when the amount of data reached a threshold or when a maximum time interval is reached and at FIG. 6A and column 16, lines 20-30 that an index node may be limited to a maximum number of pointers to leaf nodes, beyond which the index may re-distribute the pointers to index nodes at the next lowest level.
Sorenson teaches at FIGS. 8A-8D and column 18, lines 18-65 that an index node has exceeded the maximum number of child references and the maximum number may be four and the root node 810 may point to five leaf nodes. to perform rebalancing of the index 122 when an intermediate index node has exceeded the maximum number of child pointers, the parent meta tile of the meta tile to be split may be identified……child pointers may be redistributed among the sibling index nodes and a new sibling index node may be created…if the parent does not exceed the maximum number of child pointers. If the parent node also exceeds the maximum number of child pointers, then the parent’s parent node may be identified for rebalancing and a single transaction in the data store 130 may be performed to create the new meta tiles and each with a different portion of the child pointers and at column 19, lines 4-20 that the maximum number of child pointers may be four.
Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database and the metadata index may be traversed to determine one or more storage locations of the requested time-series data in one or more data sources. Traversal may include selecting paths, e.g., pointers to leaf nodes whose spatial and temporal boundaries overlap with the spatial and temporal boundaries of the query. As a result of the traversal, one or more of the leaf nodes may be reached or selected and one or more other leaf nodes may not be reached or selected).
Sorenson et al. US-Patent No. 11,599,516 (hereinafter Sorenson) in view of Guha et al. US Patent No. 10,902,062 (hereinafter Guha) and Kumar et al. US-Patent No. 11,366,801 (hereinafter Kumar) teaches the claim limitation that determining that a number of nodes at a certain level covering consecutive durations of time reaches N; creating a new node at a parent level of the certain level based on the nodes at the certain level (
Kumar teaches at column 18, lines 30-64 that respective split criteria, e.g., the maximum number of keys for which entries can be accommodated at a given node may be defined for respective levels within the tree-based index, e.g., a root node may meet its split criterion when it has reached R entries, a leaf node meet its split criterion which it has reached F entries….timestamps corresponding to the N most recent writes to a given node may be stored in the node and the node may be deemed to have met its split criterion if the number of writes to it within a specified period T exceed a threshold.
Guha teaches at column 5, lines 60-67 and column 6, lines 1-10 that as new data points of the stream arrive, each of the trees of a random cut forest may represent a dynamically updated sample of the stream’s observation records….a node representing the new data point may be added to the tree by adding a new leaf node the added data point.
Guha taches at column 5, lines 15-20 that leaf nodes correspond to individual points representing minimal bounding boxes and at column 11, lines 25-40 that the SMAS may first collect a baseline set of data points from the specified streaming data sources to generate an initial forest of random cut trees, with each tree corresponding to a particular subset of the baseline set and the leaf nodes of the trees may correspond to respective data points and Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database.
Accordingly, each leaf node corresponding to a 2D tile includes the respective N data points).
Sorenson teaches at column 9, lines 6-20 that the time-series data may be partitioned into a set of tiles 162 along non-overlapping temporal and spatial boundaries.
This teaching of storing the data points (measurements) with nanosecond resolution timestamps along with the 2D tiles being defined by spatial and temporal boundaries indicates that each 2D tile has the number of the data points where the number is defined by the temporal range divided by the nanosecond resolution.
Sorenson teaches at FIG. 3 and column 12, lines 25-30 that tiles may be closed when the amount of data reached a threshold or when a maximum time interval is reached and at FIG. 6A and column 16, lines 20-30 that an index node may be limited to a maximum number of pointers to leaf nodes, beyond which the index may re-distribute the pointers to index nodes at the next lowest level.
Sorenson teaches at FIGS. 8A-8D and column 18, lines 18-65 that an index node has exceeded the maximum number of child references and the maximum number may be four and the root node 810 may point to five leaf nodes. to perform rebalancing of the index 122 when an intermediate index node has exceeded the maximum number of child pointers, the parent meta tile of the meta tile to be split may be identified……child pointers may be redistributed among the sibling index nodes and a new sibling index node may be created…if the parent does not exceed the maximum number of child pointers. If the parent node also exceeds the maximum number of child pointers, then the parent’s parent node may be identified for rebalancing and a single transaction in the data store 130 may be performed to create the new meta tiles and each with a different portion of the child pointers and at column 19, lines 4-20 that the maximum number of child pointers may be four.
Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database and the metadata index may be traversed to determine one or more storage locations of the requested time-series data in one or more data sources. Traversal may include selecting paths, e.g., pointers to leaf nodes whose spatial and temporal boundaries overlap with the spatial and temporal boundaries of the query. As a result of the traversal, one or more of the leaf nodes may be reached or selected and one or more other leaf nodes may not be reached or selected).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated Sorenson and Guha/Kumar’s teaching that each leaf node representing a 2D tile includes the respective N data points (measurements) into Goyal ‘771’s storage of 2D tiles defined by spatial and temporal boundaries of the data points sampled at the nanosecond resolution timestamps. One of the ordinary skill in the art would have been motivated to have provided a tree structure for storing a set of data points (measurements).
Re Claim 7:
The claim 7 encompasses the same scope of invention as that of the claim 2 except additional claim limitation that determining that a certain node is added to a certain level; updating a parent node at a parent level of the certain level based on the certain node.
Sorenson et al. US-Patent No. 11,599,516 (hereinafter Sorenson) in view of Guha et al. US Patent No. 10,902,062 (hereinafter Guha) and Kumar et al. US-Patent No. 11,366,801 (hereinafter Kumar) teaches the claim limitation that determining that a certain node is added to a certain level; updating a parent node at a parent level of the certain level based on the certain node (
Kumar teaches at column 18, lines 30-64 that respective split criteria, e.g., the maximum number of keys for which entries can be accommodated at a given node may be defined for respective levels within the tree-based index, e.g., a root node may meet its split criterion when it has reached R entries, a leaf node meet its split criterion which it has reached F entries….timestamps corresponding to the N most recent writes to a given node may be stored in the node and the node may be deemed to have met its split criterion if the number of writes to it within a specified period T exceed a threshold.
Guha teaches at column 5, lines 60-67 and column 6, lines 1-10 that as new data points of the stream arrive, each of the trees of a random cut forest may represent a dynamically updated sample of the stream’s observation records….a node representing the new data point may be added to the tree by adding a new leaf node the added data point.
Guha taches at column 5, lines 15-20 that leaf nodes correspond to individual points representing minimal bounding boxes and at column 11, lines 25-40 that the SMAS may first collect a baseline set of data points from the specified streaming data sources to generate an initial forest of random cut trees, with each tree corresponding to a particular subset of the baseline set and the leaf nodes of the trees may correspond to respective data points and Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database.
Accordingly, each leaf node corresponding to a 2D tile includes the respective N data points).
Sorenson teaches at column 9, lines 6-20 that the time-series data may be partitioned into a set of tiles 162 along non-overlapping temporal and spatial boundaries.
This teaching of storing the data points (measurements) with nanosecond resolution timestamps along with the 2D tiles being defined by spatial and temporal boundaries indicates that each 2D tile has the number of the data points where the number is defined by the temporal range divided by the nanosecond resolution.
Sorenson teaches at FIG. 3 and column 12, lines 25-30 that tiles may be closed when the amount of data reached a threshold or when a maximum time interval is reached and at FIG. 6A and column 16, lines 20-30 that an index node may be limited to a maximum number of pointers to leaf nodes, beyond which the index may re-distribute the pointers to index nodes at the next lowest level.
Sorenson teaches at FIGS. 8A-8D and column 18, lines 18-65 that an index node has exceeded the maximum number of child references and the maximum number may be four and the root node 810 may point to five leaf nodes. to perform rebalancing of the index 122 when an intermediate index node has exceeded the maximum number of child pointers, the parent meta tile of the meta tile to be split may be identified……child pointers may be redistributed among the sibling index nodes and a new sibling index node may be created…if the parent does not exceed the maximum number of child pointers. If the parent node also exceeds the maximum number of child pointers, then the parent’s parent node may be identified for rebalancing and a single transaction in the data store 130 may be performed to create the new meta tiles and each with a different portion of the child pointers and at column 19, lines 4-20 that the maximum number of child pointers may be four.
Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database and the metadata index may be traversed to determine one or more storage locations of the requested time-series data in one or more data sources. Traversal may include selecting paths, e.g., pointers to leaf nodes whose spatial and temporal boundaries overlap with the spatial and temporal boundaries of the query. As a result of the traversal, one or more of the leaf nodes may be reached or selected and one or more other leaf nodes may not be reached or selected).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated Sorenson and Guha/Kumar’s teaching that each leaf node representing a 2D tile includes the respective N data points (measurements) into Goyal ‘771’s storage of 2D tiles defined by spatial and temporal boundaries of the data points sampled at the nanosecond resolution timestamps. One of the ordinary skill in the art would have been motivated to have provided a tree structure for storing a set of data points (measurements).
Re Claim 8:
The claim 8 encompasses the same scope of invention as that of the claim 7 except additional claim limitation that receiving a second user request for the tile to which the parent node corresponds; blocking processing of the second user request until the updating is complete.
Sorenson further teaches the claim limitation that receiving a second user request for the tile to which the parent node corresponds; blocking processing of the second user request until the updating is complete (
Sorenson teaches at FIG. 4 and column 13, lines 1-12 that the graph may include a layer of leaf nodes that include pointers to location data for particular tiles in the underlying data store, where each leaf node represents a spatial and temporal range within the broader spatial and temporal range of a parent index node. Sorenson teaches at FIG. 8B that the index node 870 includes a leaf node pointer 811 to a first leaf node 820 representing a first portion of the temporal range 809, a leaf node pointer 812 to a second leaf node 830 representing a second portion of the temporal range 809A where each leaf node represents a spatial and temporal range within the broader spatial and temporal range of a parent index node. Accordingly, the number of data points (measurements) in the root node 810 (a high-level meta tile) is larger than the number of measurements of each leaf node (a lower level meta tile).
Sorenson teaches at column 9, lines 6-20 that the time-series data may be partitioned into a set of tiles 162 along non-overlapping temporal and spatial boundaries and at column 6, lines 5-31 that a data point may be associated with a timestamp, one or more dimensions (in name-value pairs) representing characteristics of the time series, and a measure representing a variable whose value is tracked over time. Timestamps may be provided by clients or automatically added upon ingestion. Measures may be identified by names and may often have numeric values. Measures may be used by the database 100 in generating aggregations such as min, max, average, and count. For example, a time series related to automobiles may be identified by a unique combination of values for dimensions of a vehicle identification number (VIN), country, state, and city, while measures for such a time series may include the battery state and the miles traveled per day. In one embodiment, queries may specify time intervals and/or dimension names and/or dimension values instead of or in addition to individual measures.
This teaching of storing the data points (measurements) with timestamps along with the 2D tiles being defined by spatial and temporal boundaries indicates that each 2D tile has the number of the data points where the number is defined by the temporal range divided by the sampling timestamp interval.
Sorenson teaches at FIG. 3 and column 12, lines 25-30 that tiles may be closed when the amount of data reached a threshold or when a maximum time interval is reached and at FIG. 6A and column 16, lines 20-30 that an index node may be limited to a maximum number of pointers to leaf nodes, beyond which the index may re-distribute the pointers to index nodes at the next lowest level.
Sorenson teaches at FIGS. 8A-8D and column 18, lines 18-65 that an index node has exceeded the maximum number of child references and the maximum number may be four and the root node 810 may point to five leaf nodes. to perform rebalancing of the index 122 when an intermediate index node has exceeded the maximum number of child pointers, the parent meta tile of the meta tile to be split may be identified……child pointers may be redistributed among the sibling index nodes and a new sibling index node may be created…if the parent does not exceed the maximum number of child pointers. If the parent node also exceeds the maximum number of child pointers, then the parent’s parent node may be identified for rebalancing and a single transaction in the data store 130 may be performed to create the new meta tiles and each with a different portion of the child pointers and at column 19, lines 4-20 that the maximum number of child pointers may be four.
Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database and the metadata index may be traversed to determine one or more storage locations of the requested time-series data in one or more data sources. Traversal may include selecting paths, e.g., pointers to leaf nodes whose spatial and temporal boundaries overlap with the spatial and temporal boundaries of the query. As a result of the traversal, one or more of the leaf nodes may be reached or selected and one or more other leaf nodes may not be reached or selected).
Re Claim 9:
The claim 9 encompasses the same scope of invention as that of the claim 1 except additional claim limitation that the time series data having a plurality of categorical values, the first tile having a count of measurements, a count of unique categorical values of the measurements, or a frequency of a categorical value in the first duration of time.
Kumar and Guha teach the claim limitation that the time series data having a plurality of categorical values, the first tile having a count of measurements, a count of unique categorical values of the measurements, or a frequency of a categorical value in the first duration of time (
Kumar teaches at column 18, lines 30-64 that respective split criteria, e.g., the maximum number of keys for which entries can be accommodated at a given node may be defined for respective levels within the tree-based index, e.g., a root node may meet its split criterion when it has reached R entries, a leaf node meet its split criterion which it has reached F entries….timestamps corresponding to the N most recent writes to a given node may be stored in the node and the node may be deemed to have met its split criterion if the number of writes to it within a specified period T exceed a threshold.
Guha teaches at column 5, lines 60-67 and column 6, lines 1-10 that as new data points of the stream arrive, each of the trees of a random cut forest may represent a dynamically updated sample of the stream’s observation records….a node representing the new data point may be added to the tree by adding a new leaf node the added data point.
Guha taches at column 5, lines 15-20 that leaf nodes correspond to individual points representing minimal bounding boxes and at column 11, lines 25-40 that the SMAS may first collect a baseline set of data points from the specified streaming data sources to generate an initial forest of random cut trees, with each tree corresponding to a particular subset of the baseline set and the leaf nodes of the trees may correspond to respective data points and Sorenson teaches at column 20, lines 5-65 that a leaf node may represent a portion of the spatial and temporal range of its parent node and may correspond to a 2D tile in the time-series database).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated Guha/Kumar’s teaching that each leaf node representing a 2D tile includes the respective N data points (measurements) into Goyal ‘771’s storage of 2D tiles defined by spatial and temporal boundaries of the data points sampled at the nanosecond resolution timestamps. One of the ordinary skill in the art would have been motivated to have provided a tree structure for storing a set of data points (measurements).
Re Claim 10:
The claim 10 encompasses the same scope of invention as that of the claim 1 except additional claim limitation that automatically transmitting a series of responses following the first response respectively corresponding to successively higher resolutions than the first resolution.
Sorenson further teaches the claim limitation that automatically transmitting a series of responses following the first response respectively corresponding to successively higher resolutions than the first resolution (
Sorenson teaches at column 5, lines 40-60 that in addition to the ingestion routers 110, the database 100 may include hosts such as storage nodes 140 and query processors 170. A fleet of storage nodes 140 may take the partitioned time-series data from the ingestion routers 110, potentially process the data in various ways, and add the data to one or more storage tiers 150A-150N. For example, the storage nodes 140 may write data from one partition to a “hot” storage tier 150A at a lower latency and to a “cold” storage tier 150N at a higher latency. In various embodiments, storage nodes may perform reordering, deduplication, aggregation of different time periods, rollups, and other transformations on time series data. Storage nodes 140 may perform tasks such as creating materialized views or derived tables based on a partition, such as an aggregation or rollup of a time interval. The tasks may include continuous queries that are performed repeatedly over time, e.g., to create aggregations for each hour or day of a time series as that time period is finalized. By co-locating related time-series using the clustering scheme 112, tasks such as aggregations and cross-series rollups may be optimized or otherwise have their performance improved).
Beedgen implicitly teaches the claim limitation that automatically transmitting a series of responses following the first response respectively corresponding to successively higher resolutions than the first resolution (
Beedgen teaches at Paragraph 0290 for a query over a time range within the last 24 hours, an existing system would scan 90* more data than strictly necessary. Using the techniques described herein, the system would be aware that 89,000 of the time series have no data in the last 24 hours. Thus, the techniques provide performance improvements that allow for pre-filtering down to the 1,000 entries (corresponding to the one 24-hour tile) which may actually contain data.
Beedgen shows at FIG. 17 and Paragraph 0296-0297 displaying a plurality of aggregated values (e.g., average, 99th percentiles) for an aggregated 24-hour window (24-hour buckets/tiles) while the time series is divided into the two-super-tiles (partitions).
Beedgen teaches at Paragraph 0262 bucketing the raw logs into buckets of time intervals such as one-minute buckets or five-minute buckets and at Paragraph 0296 that the 24-hour window used in the examples described herein may be selected and at Paragraph 0297 involving time-series indexing of time series with a 24-hour threshold that buckets time series into two partitions (24-hour buckets).
Beedgen teaches at Paragraph 0270 that it is possible to display the results of a counting aggregation query by time and at Paragraph 0273 that users would like to query the metrics time series in aggregation. A user might wish to see, for example, the average of all CPU usage over time in a cluster of machines. When they query the system, users will then specify only a subset of the identifying metadata they are interested in. The system will then match all the time series identified by the subset of identifying metadata provided, and execute the query using a desired aggregation function (average, 99th percentiles, …) over all the data points in all the time series.
Beedgen teaches at Paragraph 0297 that finer partitioning may be provided by adding a time level indexing scheme ta the granularity of weeks or months and at FIG. 20 and Paragraph 0317 receiving a query and the query comprising a set of query metadata and a query time range and the selected metrics time series is returned and the selected metrics time series is visualized in a graphical user interface).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated Beedgen’s teaching of displaying multiple aggregated values associated with each aggregation unit time interval/zone (24 hours) for a number of aggregated values based on the aggregation function to have modified Sorenson and Mills’s display of aggregated values to have displayed multiple aggregated values simultaneously at each aggregation unit time interval/zone. One of the ordinary skill in the art would have been motivated to have provided multiple aggregated values for each aggregation unit time interval/zone.
Re Claim 11:
The claim 11 is in parallel with the claim 1 in the form of a computer program product. The claim 11 is subject to the same rationale of rejection as the claim 1.
Additionally, Rath further teaches one or more computer-readable non-transitory storage media storing instructions which, when executed by one or more processors, cause execution of a method of managing multi-resolution time series data (Rath teaches at FIG. 17 and Paragraph 0092-0095 that computing device 3000 may be a uniprocessor system including one processor or a multiprocessor system including several processors 3010A-3010N capable of executing instructions and system memory 3020 may be configured to store program instructions and data accessible by processors 3010A-3010N and the program instructions and data implementing one or more desired functions).
Re Claim 12:
The claim 12 encompasses the same scope of invention as that of the claim 11 except additional claim limitation that the pluralities of tiles forming a tree, with each node corresponding to a tile, each level corresponding to a resolution, and a leaf corresponding to a tile having N measurements in the time series data as the N values.
The claim 12 is in parallel with the claim 2 in the form of a computer program product. The claim 12 is subject to the same rationale of rejection as the claim 2.
Re Claim 13:
The claim 13 encompasses the same scope of invention as that of the claim 11 except additional claim limitation that receiving new measurements in additional time series data; adding a specific measurement of the new measurements to a specific leaf based on a specific timestamp of the specific measurement.
The claim 13 is in parallel with the claim 3 in the form of a computer program product. The claim 13 is subject to the same rationale of rejection as the claim 3.
Re Claim 14:
The claim 14 encompasses the same scope of invention as that of the claim 13 except additional claim limitation that the method further comprising: determining that a number of measurements in the specific leaf exceeds N; creating a new leaf covering a new duration of time following a specific duration time covered by the specific leaf.
The claim 14 is in parallel with the claim 4 in the form of a computer program product. The claim 14 is subject to the same rationale of rejection as the claim 4.
Re Claim 15:
The claim 15 encompasses the same scope of invention as that of the claim 11 except additional claim limitation that the method further comprising: determining that a number of measurements in the specific leaf exceeds N; splitting the specific leaf into two leaves covering consecutive durations of time.
The claim 15 is in parallel with the claim 5 in the form of a computer program product. The claim 15 is subject to the same rationale of rejection as the claim 5.
Re Claim 16:
The claim 16 encompasses the same scope of invention as that of the claim 12 except additional claim limitation that the method further comprising: determining that a number of nodes at a certain level covering consecutive durations of time reaches N; creating a new node at a parent level of the certain level based on the nodes at the certain level.
The claim 16 is in parallel with the claim 6 in the form of a computer program product. The claim 16 is subject to the same rationale of rejection as the claim 6.
Re Claim 17:
The claim 17 encompasses the same scope of invention as that of the claim 12 except additional claim limitation that the method further comprising: determining that a certain node is added to a certain level; updating a parent node at a parent level of the certain level based on the certain node.
The claim 17 is in parallel with the claim 7 in the form of a computer program product. The claim 17 is subject to the same rationale of rejection as the claim 7.
Re Claim 18:
The claim 18 encompasses the same scope of invention as that of the claim 17 except additional claim limitation that the method further comprising: receiving a second user request for the tile to which the parent node corresponds; blocking processing of the second user request until the updating is complete.
The claim 18 is in parallel with the claim 8 in the form of a computer program product. The claim 18 is subject to the same rationale of rejection as the claim 8.
Re Claim 19:
The claim 19 encompasses the same scope of invention as that of the claim 11 except additional claim limitation that the time series data having a plurality of categorical values, the first tile having a count of measurements, a count of unique categorical values of the measurements, or a frequency of a categorical value in the first duration of time.
The claim 19 is in parallel with the claim 9 in the form of a computer program product. The claim 19 is subject to the same rationale of rejection as the claim 9.
Re Claim 20:
The claim 20 encompasses the same scope of invention as that of the claim 11 except additional claim limitation that the method further comprising automatically transmitting a series of responses following the first response respectively corresponding to successively higher resolutions than the first resolution.
The claim 20 is in parallel with the claim 10 in the form of a computer program product. The claim 20 is subject to the same rationale of rejection as the claim 10.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JIN CHENG WANG whose telephone number is (571)272-7665. The examiner can normally be reached Mon-Fri 8:00-5:00.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, King Poon can be reached at 571-270-0728. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/JIN CHENG WANG/Primary Examiner, Art Unit 2617