Patent ID: 11947568
Assignee: AMAZON TECHNOLOGIES, INC.
Field: Computer technology (Electrical engineering)
Classification: CPC G | IPC G

Claim 14:
15. The one or more non-transitory, computer-readable storage media of claim 14, wherein the fixed-size array is a two-dimensional array, wherein rows of the fixed-size array correspond to different registers split from respective hash values used to locate the data items in the data storage, wherein columns of the fixed-size array correspond to different numbers of leading zeros to different stochastic ranges split from the respective hash values, and wherein, in determining the estimate of a working set for the application within the range of time based on the accessing, the program instructions cause the one or more computing devices to implement:
scanning columns in each of the rows of the fixed-size array, starting from a column representing a most significant bit until a scanned column that stores a timestamp in the range of time is identified;
adding the number of leading zeros corresponding to the identified columns for the rows to an input data set; and
performing a HyperLogLog estimation technique using the input data set to determine the estimated working set for the range of time.