Predicting user navigation events

• US 8,732,569 B2
• Filed: 05/04/2011
• Issued: 05/20/2014
• Est. Priority Date: 05/04/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Burkard, Timo, Jain, Arvind
• Primary Examiner(s): Hong, Stephen
• Assistant Examiner(s): Vaughn, Gregory J
• Application Number:
  US13/100,615
• Publication Number:
  US 20120284597A1
• Time in Patent Office: 1,112 Days
• Field of Search: 715/200, 715/205, 715/206, 715/208
• US Class Current: 715/206
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: G06F 40/134 Hyperlinking
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]

Abstract

A method and system for predicting a next navigation event are described. Aspects of the disclosure minimize the delay between a navigation event and a network response by predicting the next navigation event. The system and method may then prerender content associated with the next navigation event. For example, the method and system may predict a likely next uniform resource locator during web browsing to preemptively request content from the network before the user selects the corresponding link on a web page. The methods describe a variety of manners of predicting the next navigation event, including examining individual and aggregate historical data, text entry prediction, and cursor input monitoring.

Claims

1. A computer-implemented method for predicting a navigation event, the method comprising:

tracking a navigation history;

calculating one or more confidence values for one or more of a plurality of navigation events using the navigation history, wherein calculating the one or more confidence values comprises;

monitoring for the selection of a first uniform resource locator;

incrementing, in response to the selection, a frequency value associated with the first uniform resource locator or a frequency value associated with a pair of uniform resource locators, the pair comprising the first uniform resource locator and a source uniform resource locator;

decaying a different frequency value for non-selected uniform resource locators after a predetermined time interval;

storing the frequency value in a memory; and

determining a confidence value for the uniform resource locator or pair of uniform resource locators from at least one frequency value stored in the memory;

determining, using a processor, one or more likely navigation events using the confidence values; and

identifying at least one of the one or more likely navigation events as a predicted navigation event.

2. The method of claim 1, further comprising

retrieving content associated with the predicted navigation event.

3. The method of claim 1, wherein the decaying of the frequency value for the non-selected uniform resource locators is performed in response to the selection of the first uniform resource locator.

4. The method of claim 1, wherein the navigation history is associated with at least one of a particular client or a particular user.

5. The method of claim 1, wherein the navigation history is associated with a plurality of users.

6. The method of claim 5, further comprising:

computing a first hash value for a navigation event associated with a first uniform resource locator or a transitional pair of uniform resource locators, wherein the transitional pair comprises a source uniform resource locator and a destination uniform resource locator;

computing a confidence value for the navigation event; and

transmitting the hash value and the confidence value, such that a receiver of the first hash value and the confidence value computes a second hash value of a second uniform resource locator to identify the first uniform resource locator to which the confidence value applies.

7. The method of claim 5, wherein determining the most likely navigation event comprises:

for at least one uniform resource locator (URL), computing a most visited subsequent URL based on the navigation history of the plurality of users.

8. The method of claim 7, further comprising determining if the number of visits to the subsequent uniform resource locator is greater than a threshold number of visits.

9. The method of claim 7, further comprising determining if a number of users submitting data for the subsequent uniform resource locator is greater than a threshold number of users.

10. The method of claim 7, further comprising:

identifying a window of recent visits to be analyzed to determine the most visited subsequent URL; and

analyzing visits within the identified window.

11. The method of claim 10, wherein the window is specified by a time period or a number of visits.

12. The method of claim 1, wherein the navigation history comprises at least one of a uniform resource locator or a transitional pair of uniform resource locators, wherein the transitional pair of uniform resource locators comprises a source uniform resource locator and a destination uniform resource locator.

13. A computer-implemented method of predicting a next navigation event, the method comprising:

receiving a set of data for a uniform resource locator, the set of data comprising hash values associated with one or more links associated with the uniform resource locator and a set of confidence values associated with the one or more links, wherein calculating the set confidence values comprises;

monitoring for the selection of a first uniform resource locator;

incrementing, in response to the selection, a frequency value associated with the first uniform resource locator or a frequency value associated with a pair of uniform resource locators, the pair comprising the first uniform resource locator and a source uniform resource locator;

decaying a different frequency value for non-selected uniform resource locators after a predetermined time interval;

storing the frequency value in a memory; and

determining a confidence value for the uniform resource locator or pair of uniform resource locators from at least one frequency value stored in the memory;

computing, using a processor, a hash value for one or more links present on a page associated with the uniform resource locator;

comparing the computed hash values with the received hash values to map each computed hash value to a received hash value; and

identifying the confidence value associated with each visible link based upon the received confidence value associated with the received hash value to which the computed hash value for the link maps.

14. The method of claim 13, further comprising predicting one or more next navigation events, where the one or more predicted next navigation events relate to a link with the highest identified confidence value.

15. A processing system for predicting a next navigation event comprising:

at least one processor;

a navigation prediction module associated with the at least one processor; and

memory for storing navigation data, the memory coupled to the at least one processor;

wherein the navigation prediction module is configured to calculate one or more confidence values for one or more of a plurality of navigation events using the navigation data, to determine one or more likely navigation events using the confidence values, and to identify at least one of the one or more likely navigation events as a predicted navigation event,

wherein to calculate the one or more confidence values the navigation prediction module is further configured to monitor for the selection of a first uniform resource locator, increment, in response to the selection, a frequency value associated with the first uniform resource locator or a frequency value associated with a pair of uniform resource locators, the pair comprising the first uniform resource locator and a source uniform resource locator, decay a different frequency value for non-selected uniform resource locators after a predetermined time interval, store the frequency value in a memory, and determine a confidence value for the uniform resource locator or pair of uniform resource locators from at least one frequency value stored in the memory.

16. The system of claim 15, wherein the navigation data comprises at least one of a browsing history, a text entry, or a cursor input.