Real-time estimation of working sets
AssigneeAmazon Technologies, Inc.
InventorsJorge Peixoto Vasquez, Matthew Graham Baldwin, Donavan Miller
Life of this patent
Estimating the term…
Abstract
Methods, systems, and computer-readable media for real-time estimation of working sets are disclosed. A plurality of counters are initialized. The counters represent cardinality estimates of data elements accessed for respective time intervals. A request for data is received during the respective time intervals. One or more data elements are determined that are accessed in responding to the request. The counters are updated using the one or more data elements, such that one of the counters is increased by a quantity of the data elements that are accessed for the first time during the respective time interval. The working set estimates for the respective time intervals are determined using the counters.
Claims20
A system, comprising:
- one or more computing devices configured to implement a working set estimator, wherein the working set estimator is configured to:
- initialize a plurality of counters associated with a server, wherein the counters represent cardinality estimates of data elements accessed for respective time intervals;
- determine one or more data elements accessed during the respective time intervals;
- update the plurality of counters using the one or more data elements, wherein one of the counters is increased by a quantity of the one or more data elements that are accessed for the first time during the respective time interval;
- determine working set estimates for the respective time intervals using the counters, wherein the counters are reset after expiration.
A method performed by one or more computing devices, comprising:
- maintaining a plurality of counters, wherein the counters represent cardinality estimates of data elements accessed for respective time intervals;
- determining one or more data elements accessed during the respective time intervals;
- updating the plurality of counters using the one or more data elements;
- and
- determining working set estimates for the respective time intervals using the counters.
A non-transitory computer-readable storage medium storing program instructions computer-executable to perform:
- initializing a plurality of counters, wherein the counters represent cardinality estimates of data elements accessed for respective time intervals;
- determining one or more data elements accessed during the respective time intervals in responding to a request or in processing a work item;
- updating the plurality of counters using the one or more data elements;
- and
- determining working set estimates for the respective time intervals using the counters.
Dependencies are inferred from the claim text.