Predicting user navigation events in a browser using directed graphs

• US 8,600,921 B2
• Filed: 09/15/2011
• Issued: 12/03/2013
• 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:
  US13/233,300
• Publication Number:
  US 20130073509A1
• Time in Patent Office: 810 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, the method comprising:

storing a set of navigation data, the navigation data comprising at least one directed graph, where at least one vertex of the directed graph comprises at least one navigation event and an edge of the directed graph is weighted by a count value representing a number of times a navigation has occurred from a source vertex to a destination vertex coupled thereto by the edge;

identifying a current navigation history, the current navigation history comprising one or more previous navigation events accessed in a browser;

mapping the current navigation history, using a processor, to the at least one directed graph within the set of navigation data;

determining a confidence value for a given navigation event using the at least one directed graph; and

identifying the given navigation event as a likely navigation event based on the confidence value, such that the likely navigation event is configured to be utilized by the browser to assist with navigation operations.

2. The method of claim 1, wherein the at least one directed graph is keyed to at least one previous navigation event in the current 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 n previous navigation events in the current navigation history; and

determining which of the at least one directed graphs is keyed to the n previous navigation events.

5. The method of claim 1, wherein the confidence value is weighted by at least a depth of the at least one 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 stored in the 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, further comprising prerendering the likely navigation event.

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

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

storing a set of navigation data, the navigation data comprising at least one directed graph, where at least one vertex of the directed graph comprises at least one navigation event and an edge of the directed graph is weighted by a count value representing a number of times a navigation has occurred from a source vertex to a destination vertex coupled thereto by the edge;

identifying a current navigation history, the current navigation history comprising one or more previous navigation events accessed in a browser;

mapping the current navigation history to the at least one directed graph within the set of navigation data;

determining a confidence value for a given navigation event using the at least one directed graph; and

identifying the given navigation event as a likely navigation event based on the confidence value, such that the likely navigation event is configured to be utilized by the browser to assist with navigation operations.

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

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

12. The non-transitory computer readable medium of claim 9, further comprising:

identifying n previous navigation events in the current navigation history; and

determining which of the at least one directed graphs is keyed to the n previous navigation events.

13. The non-transitory computer readable medium of claim 9, wherein the confidence value is weighted by a depth of the at least one directed graph.

14. The non-transitory computer readable medium of claim 9, further comprising prerendering the likely navigation event.

15. A processing system for predicting a user navigation event, the processing system comprising:

at least one processor; and

a memory, coupled to the processor, for storing a set of navigation data, the navigation data comprising at least one directed graph, where at least one vertex of the directed graph comprises at least one navigation event and an edge of the directed graph is weighted by a count value representing a number of times a navigation has occurred from a source vertex to a destination vertex coupled by the edge;

wherein the processor is configured to;

identify a current navigation history, the current navigation history comprising one or more previous navigation events accessed in a browser;

map the current navigation history to the at least one directed graph within the set of navigation data;

determine a confidence value for a given navigation event using the at least one directed graph; and

identify the given navigation event as a likely navigation event based on the confidence value, such that the likely navigation event is configured to be utilized by the browser to assist with navigation operations.

16. The processing system of claim 15, wherein the browser is configured to prerender the likely navigation event.

17. The processing system of claim 15, wherein the at least one directed graph is keyed to at least one previous navigation event in the current navigation history.

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

19. The processing system of claim 15, wherein the processor is further configured to:

identify n previous navigation events in the current navigation history; and

determine which of the at least one directed graphs is keyed to the n previous navigation events.

20. The processing system of claim 15, wherein the confidence value is weighted by a depth of the at least one directed graph.

21. The processing system of claim 15, wherein the browser is a web browser.