Back to results
US 8,620,839 B2Granted
Markov modeling of service usage patterns
AssigneeGoogle Inc.
InventorsKaran Bhatnagar, Rohan Khot
Life of this patent
Estimating the term…
Abstract
A system for analyzing service usage utilizing Markov models. Records of client requests to the service are extracted from at least one log. The records are grouped by client and sorted by timestamp. A pattern of requests that form an action is detected. Each action has a time. A probability is calculated of a transition from a precedent action to a subsequent action, where the precedent action has a time prior to the subsequent action. A delay time is also calculated between a precedent action and a subsequent action. A probability is calculated for a delay time, such as the likelihood that a delay from a precedent action to a subsequent action will fall within a given time interval.
Claims28
A computer-implemented method, comprising:
- extracting a plurality of records from at least one log, each record having a timestamp and at least one request;
- detecting an action comprising a pattern of requests, where the action has a time and the action relates to a request for content by a client, wherein the detecting an action is performed on each of the extracted records;
- generating a chain of action and timestamp pairs based on the detected action;
- analyzing the generated chain of action and timestamp pairs;
- based on the results of the analysis, producing key value pairs, wherein the key value pairs include at least a preceding action indicator as a first value of a key value pair, and as a second value of a key value pair being a combination of a succeeding action indicator and a delay time, wherein the delay time is equal to a delay of the succeeding action following the preceding action;
- calculating, by a processor, the probability of a transition from a precedent action represented by the first value of the key value pair to a subsequent action represented by the second value of the key value pair based on the produced key value pairs for the plurality of records, where the precedent action has a time prior to the time of the subsequent action and where the precedent action includes a request for a first content and the subsequent request includes a request for a second content;
- and
- pre-fetching or caching content based on the calculated probability of the transition from the precedent action to the subsequent action and a probability of delay from the precedent action to the subsequent action.
5 more elements
A computer-implemented method, comprising:
- extracting a plurality of records from at least one log;
- detecting in at least one record an action having a time;
- generating a chain of action and timestamp pairs based on the detected action;
- analyzing the generated chain of action and timestamp pairs;
- producing key value pairs, wherein the key value pairs include at least a preceding action indicator as a first value of a key value pair, and as a second value of a key value pair being a combination of a succeeding action indicator and a delay time, the delay time being equal to a delay of the succeeding action following the preceding action;
- calculating, by a processor, the probability of a transition from a precedent action to a subsequent action based on the produced key value pairs and a probability of delay from the precedent action to the subsequent action;
- and
- pre-fetching or caching content based on the calculated probability of the transition from the precedent action to the subsequent action and a probability of delay from the precedent action to the subsequent action.
5 more elements
A system, comprising:
- a microprocessor configured to:
- extract a plurality of records from at least one log;
- detect in at least one record an action having a time;
- generate a chain of action and timestamp pairs based on the detected action;
- analyze the generated chain of action and timestamp pairs;
- producing key value pairs, wherein the key value pairs include at least a preceding action indicator as a first value of a key value pair, and as a second value of a key value pair being a combination of a succeeding action indicator and a delay time, the delay time being equal to a delay of the succeeding action following the preceding action;
- calculate, by a processor, the probability of a transition from a precedent action to a subsequent action based on the produced key value pairs;
- and
- pre-fetch or cache content based on the calculated probability of the transition from the precedent action to the subsequent action and a probability of delay from the precedent action to the subsequent action.
6 more elements
A non-transitory computer readable medium storing a plurality of instructions that cause a computer to perform a method comprising:
- extracting a plurality of records from at least one log;
- detecting in at least one record an action having a time;
- generating a chain of action and timestamp pairs based on the detected action;
- analyzing the generated chain of action and timestamp pairs;
- producing value pairs, wherein the key value pairs include at least a preceding action indicator as a first value of a key value pair, and as a second value of a key value pair being a combination of a succeeding action indicator and a delay time, the delay time being equal to a delay of the succeeding action following the preceding action;
- calculating, by a processor, the probability of a transition from a precedent action to a subsequent action based on the produced key value pairs;
- and
- pre-fetching or caching content based on the calculated probability of the transition from the precedent action to the subsequent action and a probability of delay from the precedent action to the subsequent action.
5 more elements
Dependencies are inferred from the claim text.