Predicting user navigation events in a browser using directed graphs

• US 8,862,529 B1
• Filed: 10/09/2013
• Issued: 10/14/2014
• Est. Priority Date: 09/15/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Burkard, Timo, Hamon, Dominic, Jain, Arvind
• Primary Examiner(s): CHEN, ALAN S
• Application Number:
  US14/049,395
• Time in Patent Office: 370 Days
• Field of Search: None
• US Class Current: 706/45
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: G06F 3/0481 based on specific properties of the displayed interaction object or a metaphor-based environment, e.g. interaction with desktop elements like windows or icons, or assisted by a cursor's changing behaviour or appearance
• CPC Class Codes: G06F 3/04847 Interaction techniques to control parameter settings, e.g. interaction with sliders or dials
• CPC Class Codes: G06F 9/453 Help systems
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/048 Fuzzy inferencing

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 user navigation event, comprising:

generating, using a processor, a mapping between a directed graph and a navigation history, the navigation history comprising one or more previous navigation events associated with a browser, an edge of the directed graph being weighted by a count value representing a number of times a navigation event has occurred from a source vertex to a destination vertex coupled to the edge;

identifying a confidence value for one or more given navigation events using the directed graph, the confidence value representing a probability of a likely navigation event; and

prerendering at least one of the one or more given navigation events as the likely navigation event based on the confidence value, wherein the confidence value of the likely navigation event exceeds a threshold value.

2. The method of claim 1, wherein the directed graph is keyed to at least one of the one or more previous navigation event in the navigation history.

3. The method of claim 2, wherein the at least one previous navigation event is identified in an order each of the at least one previous navigation events were visited.

4. The method of claim 1, further comprising:

identifying selected ones of the one or more previous navigation events in the navigation history; and

determining which of the selected ones of the one or more previous navigation events is keyed the directed graph.

5. The method of claim 1, wherein the confidence value is weighted by a depth of the directed graph.

6. The method of claim 5, wherein a weight of the directed graph is determined by a formula graph_depth^N*samples_in_graph, wherein graph_depth is the depth, samples_in_graph is a number of navigation events associated with the directed graph, and N is a numerical value used to adjust the significance of the graph_depth term in the weight calculation.

7. The method of claim 1, wherein the browser is a web browser.

8. A non-transitory computer-readable storage medium comprising instructions that, when executed by a processor, cause the processor to perform a method, the method comprising:

generating a mapping between a directed graph and a navigation history, the navigation history comprising one or more previous navigation events associated with a browser, an edge of the directed graph being weighted by a count value representing a number of times a navigation event has occurred from a source vertex to a destination vertex coupled to the edge;

identifying a confidence value for one or more given navigation events using the directed graph, the confidence value representing a probability of a likely navigation event; and

prerendering at least one of the one or more given navigation events as the likely navigation event based on the confidence value, wherein the confidence value of the likely navigation event exceeds a threshold value.

9. The non-transitory computer-readable storage medium of claim 8, wherein the directed graph is keyed to at least one of the one or more previous navigation event in the navigation history.

10. The non-transitory computer-readable storage medium of claim 9, wherein the at least one previous navigation event is identified in an order each of the at least one previous navigation events were visited.

11. The non-transitory computer-readable storage medium of claim 8, wherein the method further comprising:

identifying selected ones of the one or more previous navigation events in the navigation history; and

determining which of the selected ones of the one or more previous navigation events is keyed the directed graph.

12. The non-transitory computer-readable storage medium of claim 8, wherein the confidence value is weighted by a depth of the directed graph.

13. The non-transitory computer-readable storage medium of claim 12, wherein a weight of the directed graph is determined by a formula graph_depth^N*samples_in_graph, wherein graph_depth is the depth, samples_in_graph is a number of navigation events associated with the directed graph, and N is a numerical value used to adjust the significance of the graph_depth term in the weight calculation.

14. A system for predicting a user navigation event, comprising:

a memory; and

one or more processors coupled to the memory, the one or more processors being configured to;

generate a mapping between a directed graph and a navigation history, the navigation history comprising one or more previous navigation events associated with a browser, an edge of the directed graph being weighted by a count value representing a number of times a navigation event has occurred from a source vertex to a destination vertex coupled to the edge;

identify a confidence value for one or more given navigation events using the directed graph, the confidence value representing a probability of a likely navigation event; and

prerender at least one of the one or more given navigation events as the likely navigation event based on the confidence value, wherein the confidence value of the likely navigation event exceeds a threshold value.

15. The system of claim 14, wherein the directed graph is keyed to at least one of the one or more previous navigation event in the navigation history.

16. The system of claim 15, wherein the at least one previous navigation event is identified in an order each of the at least one previous navigation events were visited.

17. The system of claim 14, wherein the one or more processors are further configured to:

identify selected ones of the one or more previous navigation events in the navigation history; and

determine which of the selected ones of the one or more previous navigation events is keyed the directed graph.

18. The system of claim 14, wherein the confidence value is weighted by a depth of the directed graph.

19. The system of claim 18, wherein a weight of the directed graph is determined by a formula graph_depth^N*samples_in_graph, wherein graph_depth is the depth, samples_in_graph is a number of navigation events associated with the directed graph, and N is a numerical value used to adjust the significance of the graph_depth term in the weight calculation.

20. The system of claim 14, wherein the browser is a web browser.