Back to results
US 12,585,712 B2Granted
Adversarial bandits policy for crawling highly dynamic content
AssigneeGoogle Inc.
InventorsMichael Bendersky, Przemysław Gajda, Sergey Novikov, Marc Alexander Najork, Shuguang Han
Life of this patent
Estimating the term…
Abstract
Techniques of generating recrawl policies for commercial offer pages include generating a multiple strategy approach using a number of different strategies. In some implementations, each strategy is an arm of a K-armed adversarial bandits algorithm with reinforcement learning. Moreover, in some implementations, the multiple strategy approach also uses a machine learning algorithm to estimate parameters such as a click rate, impression rate, and likelihood of price change, i.e., change rate, which was assumed known in the conventional approaches.
Claims20
A method, comprising:
- receiving, from a repository, a plurality of entities, each of the plurality of entities having a respective value of a quantity that is accurate at a previous time step;
- for each of the plurality of entities, generating associated values of a plurality of parameters at a current time step, the plurality of parameters including at least one of an access rate of that entity from the repository or a likelihood of a change in the respective value of the quantity of that entity;
- selecting a refresh strategy of a plurality of refresh strategies for updating the respective values of the quantity for the plurality of entities according to a refresh policy, the refresh policy including a weight distribution representing a respective likelihood that each of the plurality of refresh strategies is selected, the plurality of refresh strategies including at least two of a uniform strategy, a change-weighted strategy, an access-weighted strategy, or a resource-optimized strategy;
- generating a respective refresh rate for each of the plurality of entities according to the selected refresh strategy, the respective refresh rate for each entity of the plurality of entities being based on the associated values of the plurality of parameters at a sequence of times comprising the previous time step and the current time step;
- and
- performing a refresh operation on the repository based on the respective refresh rates for the plurality of entities, the refresh operation being configured to obtain the respective values of the quantity at the current time step.
3 more elements
A computer program product comprising a nontransitory storage medium, the computer program product including code that, when executed by processing circuitry of a user device configured to perform a method of generating a refresh policy, the method comprising:
- receiving, from a repository, a plurality of entities, each of the plurality of entities having a respective value of a quantity that is accurate at a previous time step;
- for each of the plurality of entities, generating associated values of a plurality of parameters at a current time step, the plurality of parameters including at least one of an access rate of that entity from the repository or a likelihood of a change in the respective value of the quantity of that entity;
- selecting a refresh strategy of a plurality of refresh strategies for updating the respective values of the quantity for the plurality of entities according to a refresh policy, the refresh policy including a weight distribution representing a respective likelihood that each of the plurality of refresh strategies is selected, the plurality of refresh strategies including at least two of a uniform strategy, a change-weighted strategy, an access-weighted strategy, and a resource-optimized strategy;
- generating a respective refresh rate for each of the plurality of entities according to the selected refresh strategy, the respective refresh rate for an entity of the plurality of entities being based on the associated values of the plurality of parameters at a sequence of times comprising the previous time step and the current time step;
- and
- performing a refresh operation on the repository based on the respective refresh rates for the plurality of entities, the refresh operation being configured to obtain the respective value of the quantity at the current time step.
3 more elements
An electronic apparatus configured to generate a refresh policy, the electronic apparatus comprising:
- memory;
- and
- controlling circuitry coupled to the memory, the controlling circuitry being configured to:
- receive, from a repository, a plurality of entities, each of the plurality of entities having a respective value of a quantity that is accurate at a previous time step;
- for each of the plurality of entities, generate associated values of a plurality of parameters at a current time step, the plurality of parameters including at least one of an access rate of that entity from the repository or a likelihood of a change in the respective value of the quantity of that entity;
- select a refresh strategy of a plurality of refresh strategies for updating the respective values of the quantity for the plurality of entities according to a refresh policy, the refresh policy including a weight distribution representing a respective likelihood that each of the plurality of refresh strategies is selected, the plurality of refresh strategies including at least two of a uniform strategy, a change-weighted strategy, an access-weighted strategy, and a resource-optimized strategy;
- generate a respective refresh rate for each of the plurality of entities according to the selected refresh strategy, the respective refresh rate for each entity of the plurality of entities being based on the associated values of the plurality of parameters at a sequence of times comprising the previous time step and the current time step;
- and
- perform a refresh operation on the repository based on the respective refresh rates for the plurality of entities, the refresh operation being configured to obtain the respective value of the quantity at the current time step.
6 more elements
Dependencies are inferred from the claim text.