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.