# US 2012/0254080 A1 · Markov Modeling of Service Usage Patterns

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0254080 A1
- Document ID: US20120254080A1
- Status: Published application
- Kind: A1
- Application number: 13/413,884
- Filed: 2012-03-07
- Published: 2012-10-04
- Earliest claimed: 2011-03-28
- Assignees: Google Inc.
- Inventors: Karan Bhatnagar; Rohan Khot
- Web page: https://patentgrep.com/patent/US20120254080A1

## CPC

- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## 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.

## Claims

### Claim 1

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 to produce key value pairs, wherein the key value pairs include at least a preceding action indicator, 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, 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, wherein the pre-fetching or caching is adapted to improve the experience of a user by reducing the latency between a user request for content and making the content available to the user.

### Claim 2

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 to produce key value pairs, wherein the key value pairs include at least a preceding action indicator, 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 transition from the precedent action to the subsequent action.

### Claim 3 (depends on 2)

The method of claim 2, wherein each record has a timestamp.

### Claim 4 (depends on 2)

The method of claim 2, wherein each record comprises at least one request.

### Claim 5 (depends on 2)

The method of claim 2, wherein an action comprises at least one request.

### Claim 6 (depends on 4)

The method of claim 4, wherein the detecting in at least one record an action comprises detecting a pattern in at least one request.

### Claim 7 (depends on 2)

The computer-implemented method of claim 2, wherein content includes a file.

### Claim 8 (depends on 2)

The computer-implemented method of claim 2, wherein content includes at least part of a web page.

### Claim 9 (depends on 2)

The computer-implemented method of claim 2, wherein the precedent action is a request for a first page.

### Claim 10 (depends on 2)

The computer-implemented method of claim 2, wherein the subsequent action is a request for a second page.

### Claim 11 (depends on 2)

The computer-implemented method of claim 2, wherein the pre-fetching or caching content based on the calculated transition from the precedent action to the subsequent action is adapted to improve the experience of a user by reducing the latency between a user request for content and making the content available to the user.

### Claim 12 (depends on 4)

The computer-implemented method of claim 4, wherein the detecting in at least one record an action comprises detecting a pattern in at least one request using an N-gram model or a FP growth model.

### Claim 13 (depends on 2)

The computer-implemented method of claim 2, wherein the pre-fetching or caching content based on the calculated transition from the precedent action to the subsequent action is adapted to improve the experience of a user by reducing the latency between a user request for content and making the content available to the user.

### Claim 14

(canceled)

### Claim 15 (depends on 31)

The system of claim 31, wherein each record has a timestamp.

### Claim 16 (depends on 31)

The system of claim 31, wherein each record comprises at least one request.

### Claim 17 (depends on 31)

The system of claim 31, further comprising a client identifying module that identifies the extracted records by client.

### Claim 18 (depends on 16)

The system of claim 16, wherein the action detector comprises a pattern detector that detects a pattern in at least one request and wherein the detected pattern corresponds to an action.

### Claim 19 (depends on 18)

The system of claim 18, wherein the pattern detector detects a pattern of requests using an N-gram model or a FP growth model to detect the pattern.

### Claim 20 (depends on 31)

The system of claim 31, wherein the content pre-fetching or caching module fetches or caches content that includes a web page.

### Claim 21 (depends on 31)

The system of claim 31, wherein the precedent action includes a page request for a first page and the subsequent action includes a page request for a second page.

### Claim 22 (depends on 31)

The system of claim 31, wherein the content pre-fetching or caching module is adapted to improve the experience of a user by reducing the latency between a user request for content and making the content available to the user.

### Claim 23

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 to produce key value pairs, wherein the key value pairs include at least a preceding action indicator, 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 transition from the precedent action to the subsequent action.

### Claim 24 (depends on 23)

The non-transitory computer readable medium of claim 23, wherein each record comprises at least one request.

### Claim 25 (depends on 23)

The non-transitory computer readable medium of claim 23, wherein an action comprises at least one request.

### Claim 26 (depends on 24)

The non-transitory computer readable medium of claim 24, further comprising storing a plurality of instructions that cause a computer to further perform a method comprising detecting a set of requests a pattern of requests by using an N-gram model or a FP growth model.

### Claim 27 (depends on 26)

The non-transitory computer readable medium of claim 26, wherein the set of requests that form a pattern correspond to an action.

### Claim 28 (depends on 23)

The non-transitory computer readable medium of claim 23, wherein content includes at least part of a web page.

### Claim 29 (depends on 23)

The non-transitory computer readable medium of claim 23, wherein the precedent action is a request for a first page and the subsequent action is a request for a second page.

### Claim 30 (depends on 23)

The non-transitory computer readable medium of claim 23, wherein the pre-fetching or caching content based on the calculated transition from the precedent action to the subsequent action is adapted to improve the experience of a user by reducing the latency between a user request for content and making the content available to the user.

### Claim 31

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 to produce key value pairs, wherein the key value pairs include at least a preceding action indicator, 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 transition from the precedent action to the subsequent action.
