Expiration of elements associated with a probabilistic data structure
AssigneeAmazon Technologies, Inc.
InventorsGregory Alan Rubin, Petr Praus, Benjamin Tillman Farley
Life of this patent
Estimating the term…
Abstract
A computing resource service receives a request. In response to the request, the computing resource service queries a probabilistic data structure for an entry corresponding to the request. The computing resource service obtains, from the probabilistic data structure, a value that corresponds to the entry. Based at least in part on this value, the computing resource service determines whether the entry has expired. If the entry is expired, the request is fulfilled. However, if the entry has not expired, the request is denied.
Claims20
A computer-implemented method, comprising:
- obtaining a request to utilize a set of credentials associated with a user account, the request specifying an identifier that corresponds to the set of credentials;
- querying a probabilistic data structure to obtain, from the probabilistic data structure, a credential iteration value for an entry corresponding to the identifier, the credential iteration value corresponding to a time that the set of credentials was last used;
- generating, based at least in part on the credential iteration value obtained from the probabilistic data structure, a determination as to whether the set of credentials has expired;
- and
- providing a response to the request based at least in part on the determination such that:
- on a condition that the determination specifies that the set of credentials has expired, the response indicates that the set of credentials has expired;
- and
- on a condition that the determination specifies that the set of credentials has not expired, the response indicates that the set of credentials is valid.
A system, comprising:
- one or more processors;
- and
- memory including instructions that, as a result of being executed by the one or more processors, cause the system to:
- query a probabilistic data structure for an entry corresponding to a request, the entry corresponding to a set of credentials for an account;
- obtain, from the probabilistic data structure, a value corresponding to the entry and to an expiration, the value further denoting a credential iteration value;
- determine, based at least in part on the credential iteration value, whether the set of credentials exists in a previous set of credentials used in association with the account;
- determine, based at least in part on the value corresponding to the entry, whether the expiration has occurred;
- and
- determine, based at least in part on whether the expiration has occurred, a manner of processing the request.
A non-transitory computer-readable storage medium storing thereon executable instructions that, as a result of being executed by one or more processors of a computer system, cause the computer system to at least:
- obtain a request to utilize a set of credentials associated with a user account, the request associated with an entry that corresponds to the set of credentials;
- utilize the entry as input into an entry function to obtain an output value that denotes an credential iteration value;
- determine, based at least on the credential iteration value, that the set of credentials is not in a set of previously used credentials;
- determine, based at least in part on the output value, a set of elements of a probabilistic data structure;
- and
- update the set of elements of the probabilistic data structure to specify a value that indicates a condition for expiration of the set of credentials.
Dependencies are inferred from the claim text.