Patent Publication Number: US-2006010229-A1

Title: User intention modeling for web navigation

Description:
RELATED APPLICATIONS  
      This patent application is a continuation of U.S. patent application Ser. No. 10/142,625, filed on May 9, 2002, titled “User Intention Modeling for Web Navigation”, commonly owned hereby, and incorporated by reference. 
    
    
     TECHNICAL FIELD  
      The following description relates to navigating and accessing information on the World Wide Web (Web).  
     BACKGROUND  
      The Internet has been growing at an incredible speed. Although not all Internet servers are part of the World Wide Web (WWW), in 1999 it was reported that there were at least 9 million Web servers and 1.5 billion Web pages on the Internet. Some individuals estimated that the number of Web pages on the Internet would reach 7.7 billion by the end of the year 2001. Users surf the WWW by navigating along hyperlinks in electronic documents (e.g., a Web page) that connect various pieces of content. Unfortunately, user navigation of the rapidly growing database of information on the Internet to achieve a particular information goal can be substantially problematic.  
      For instance, searching for specific information in such a huge “database” as the WWW is typically a time consuming hit or miss procedure, even with the help of one or more search engines. Additionally, even though high-speed broadband networks have been deployed in many places, the time delay of information transportation on the Internet is still a serious problem. If we could predict a Web surfer&#39;s information goals (e.g., what is being sought), we might be able to improve the user&#39;s Web navigation experience by recommending related Web pages and reducing the amount of time that the user perceives as having been required to receive desired content (e.g., this is typically achieved by pre-fetching and caching Web pages that are predicted to be visited by the user).  
      A number of traditional user intention prediction techniques attempt to achieve such goals. Unfortunately, these conventional navigation intention prediction techniques do not typically adequately address the Web navigation problem. This is because such techniques typically only predict a single “next step” from the user&#39;s current Web location. Yet, Web surfers generally have more substantial information requirements including information goals that simply cannot be met by predicting only a single “next step” of navigation.  
      The following disclosed subject matter addresses these and other problems of Web navigation.  
     SUMMARY  
      This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the detailed description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter.  
      In view of the above, user intention modeling for Web navigation is described. In one aspect, a statistical multi-step n-gram probability model is used to predict a user&#39;s optimal information goal. The optimal information goal is based on a sequence of previously visited network content pieces and a globally optimized navigation path through the sequence.  
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
      The same numbers are used throughout the drawings to reference like features and components.  
       FIG. 1  is a block diagram to compare aspects of a novel exemplary globally optimized navigation prediction to a conventional locally maximized navigation prediction.  
       FIG. 2  illustrates an exemplary system to utilize multi-step n-gram user navigation prediction model to predict a user&#39;s optimal information goal, wherein the goal is based on a globally optimized navigation path through a sequence of previously visited network content pieces.  
       FIG. 3  shows an exemplary computing device that utilizes a multi-step dynamic n-gram prediction model to predict a user&#39;s optimal information goal, wherein the goal is based on a globally optimized navigation path through a sequence of previously visited network content pieces.  
       FIG. 4  shows an exemplary procedure  400  to utilize a multi-step dynamic n-gram prediction model to predict a user&#39;s optimal information goal, wherein the goal is based on a globally optimized navigation path through a sequence of previously visited network content pieces.  
       FIG. 5  shows an example of a suitable computing environment on which an exemplary system and procedure to utilize multi-step n-gram user navigation prediction model to predict a user&#39;s optimal information goal based on probabilities and a “Web surfing history” may be implemented.  
    
    
     DETAILED DESCRIPTION  
      The following description sets forth exemplary subject matter to provide user intention modeling for Web navigation. The subject matter is described with specificity to meet statutory requirements. However, the description itself is not intended to limit the scope of this patent. Rather, the inventors have contemplated that the claimed subject matter might also be embodied in other ways, to include different elements or combinations of elements similar to the ones described in this document, in conjunction with other present or future technologies.  
      Overview  
      Systems to help users navigate the WWW or Web are known. For instance, traditional information retrieval methods (such as TF*IDF) have been used to help a user locate information by evaluating the similarity between two documents, and applying a reinforcement learning method to a Website&#39;s structure (e.g., hyperlinks on a page). Other conventional information retrieval methods pre-fetch documents based on the assumption that the previous page sequences that a user had visited represent a Markov chain with an applied time factor. Other systems utilize a Bayesian Network to predict a user&#39;s next query using only query and trim information, assuming that a next query only depended on the previous query and the time interval—independent on other factors. Yet, other conventional systems rely on determining the longest repeating page subsequence (a path) that all users have visited, or single step n-gram language models that consider a sequence of n Web pages as an n-gram, counting the times each n-gram appears to make a prediction based on the maximal count.  
      The principal problem of these conventional techniques is that they typically stop at a partial or local maximal state (i.e., a single “next step” of Web navigation). Yet, users typically have more substantial information requirements or goals, which generally cannot be adequately represented by only a single next action of Web navigation from the user&#39;s current navigation state on the Web. This is because the user&#39;s ultimate information goal may involve many more actions or navigation steps to an ultimate information goal (e.g., a particular Web-based location or electronic document). The following disclosed subject matter addresses this significant problem by utilizing a multi-step n-gram prediction model to predict a globally optimized navigation path (e.g., set of Universal Resource Locations (URLs)) to the user&#39;s information intent.  
      Globally Optimized Navigation Vs. Locally Maximized Navigation  
       FIG. 1  is a block diagram showing a comparison of exemplary globally optimized navigation prediction to conventional locally maximized navigation prediction. To illustrate this comparison, assume that the user is at location A and assume that the user&#39;s ultimate information goal is at location B. Lines  102  through  110  represent the possible navigation paths that the user could take from location A to the ultimate information goal, B.  
      The path  102  from A to C represents a conventional one-step n-gram or “next step” prediction of navigation towards B. If we choose one-step prediction, then C is the best choice. But after one reaches reach point C, one will determine that goal B cannot be reached. So one-step prediction is not the global optimization method, but rather, only a local path.  
      There are other local paths that could also have been selected (e.g., paths  104  to E or  106  to D) based on conventional techniques (e.g., one-step n-gram predictions, or predictions based on Web page content, previous queries, mining longest repeating sequences of Web site visits, classifying a sequence of n Web pages as an n-gram to count the times each n-gram appears to make a user intention prediction based on a maximal count, and so on), but as will be described in greater detail below, merely selecting one of these locally maximized predictions from A to C, D, or even E does not take into consideration any probability that once at a particular location (e.g., C, D, or E), that the user will find it easy, natural, or even possible to continue on that particular predicted path to the ultimate information goal B.  
      In contrast to conventional systems, which do not take into account such probabilities, the disclosed multi-step n-gram prediction model is based on such probabilities. Specifically, a user&#39;s previous navigation history is used to calculate the various probabilities of navigation (e.g., from A) towards the user&#39;s information goal (e.g., B). To illustrate this, consider that next to each path  102  through  110  is a “cost=value” distinction to represent a probability that the user will visit a next location A through E from a different location A through E given the user&#39;s previous navigation history. The higher the cost value, the lower the probability that the user will visit the next site from the different location.  
      For the reasons already discussed, we know that path  102  from A to C is not a good choice to arrive at B, yet now we have additional information that tells us that the cost of visiting C from A has a cost of two (2), which represents a local optima, but not the global optima. This means that if we use one-step prediction, then C is the best answer. However, if we use multi-step prediction, C is not the best answer to reach the goal B for the reasons discussed above. Accordingly, A to C represents a locally optimal path to B, not a globally optimal path to B.  
      This is especially true since there is no direct history of user navigation from C to B. Looking at paths  104  and  108 , or A to D to B, the relative costs three (3) and six (6) respectively add up to a cost of nine (9). Taking paths  106  and  110  into consideration, or A to E to B, the relative costs three-point-five (3.5) and two (2) respectively add up to a cost of five-point-five (5.5), less that 9. Thus multiple step navigation from A to E to B, in this example, represents the globally optimal navigation path from A to B.  
      To appreciate the global aspect of the foregoing example, consider that had only the next step of navigation from A to B (e.g., from A to D or from A to E) been considered, conventional user predictions techniques (at best) would have selected either D or E—with one location not necessarily being preferable over the other. However, according to the probability information provided in this disclosure, it is evident that there should be a preference over which leg of the navigation to B to select. The cost of leg A to D (3) is less that the cost of A to E (3.5). Thus, the globally best navigation solution involves taking leg A to E—a path that had a global multi-step n-gram solution not been considered, would not have been apparent.  
      Accordingly, and in contrast to conventional user navigation prediction techniques, the following disclosed subject matter provides a multi-step dynamic n-gram prediction model to predict an ultimate user information goal based on a globally optimized path through previous sites visited by the user.  
      An Exemplary System  
       FIG. 2  illustrates an exemplary system  200  to utilize multi-step n-gram user navigation model to predict a users an optimal information goal based on probabilities and a Web surfing history. In system  200  one or more (x) clients  202  are coupled to an information content store  204 . The information content store  204  is any combination of local storage (e.g., local volatile or non-volatile memory), networked storage (e.g., a parallel connection, an organizational intranet, the Internet, and so on), or other communication configurations.  
      These communication configurations provide for electronic exchange of information using an appropriate protocol (e.g., TCP/IP, UDP, SOAP, etc.) between the host device  202  and one or more information content sources or servers (not shown) that include multiple (v) pieces of information content  206 . This electronic exchange provides for client  202  communication with information content store  204  to access (e.g., view, search, download, etc.) pieces of information content  206 .  
      The storage of information content pieces  206  within information content store  204  can be arranged in any of a wide variety of manners and according to any of a wide variety of data formats. For example, information content pieces  206  may be stored on multiple servers hosting Web pages accessible via a network using an appropriate protocol such as Hypertext Transfer Protocol (HTTP). Web pages are documents that a user can view or otherwise render and which typically include links to one or more other pages that the user can access. Web pages are typically stored as one or more files at a remote location(s), being accessed by the user via a computer that is operatively coupled to a network  204 . Web pages often include multiple pieces of information content  206  such still images, frames of motion video, audio, multimedia, and so on.  
      A user of a client  202  navigates the information content store  204  for pieces of information content  206 . As a user operates within the computing environment of a client  202 , the client  202  monitors the user&#39;s navigation session activities and detects the user&#39;s current session and historical navigation paths to any number of pieces of information content  206 . The client  202  analyzes this globally optimized information within a statistical multi-step n-gram probability model to predict a user&#39;s optimal information goal. This multi-step n-gram prediction based on probabilities and navigation histories is dynamic, because it is performed in real-time while the user is surfing on the Web. Aspects of the statistical multi-step n-gram probability model are described in greater detail below in reference to program module  310  of  FIG. 3 .  
      A Client Computer  202   
       FIG. 3  shows an exemplary computing device  202  that utilizes a multi-step n-gram user navigation model to predict a user&#39;s optimal information goal based on probabilities and the user&#39;s “Web surfing history. The computer  202  is operational as any one of a number of different computing devices such as a personal computer, an image server computer, a thin client, a thick client, a hand-held or laptop device, a multiprocessor system, a microprocessor-based system, a set top box, programmable consumer electronics, a wireless phone, an application specific integrated circuit (ASIC), a network PC, minicomputer, mainframe computer, and so on.  
      The host computer includes a processor  302  that is coupled to a system memory  304 . The system memory  304  includes any combination of volatile and non-volatile computer-readable media for reading and writing. Volatile computer-readable media includes, for example, random access memory (RAM). Non-volatile computer-readable media includes, for example, read only memory (ROM), magnetic media such as a hard disk, an optical disk drive, a floppy diskette, a flash memory card, a CD-ROM, and so on.  
      The processor  302  is configured to fetch and execute computer program instructions from program modules  306 ; and configured to fetch data  308  while executing the program modules  306 . Program modules typically include routines, programs, objects, components, data structures, etc., for performing particular tasks or implementing particular abstract data types. For instance, program modules  306  include the multi-step n-gram user navigation prediction module  310 , a browser module  312  such as a Web browser provided by Microsoft Corporation of Redmond, Wash., and other application modules  314 . Program data includes a Web log database  316  and other data  318 . We now describe exemplary aspects of these modules  306  and data  308  with respect to the operation of the client  202 .  
      The N-Gram Model  
      The multi-step n-gram navigation prediction module  310  predicts a user&#39;s optimal information goal or content piece  106 , wherein the goal is based on a globally optimized navigation path through a sequence of previously visited network content pieces. In this manner, it can be said that the module  310  predicts at least a subset of all of the possible locations or URLs that lie on that optimized path—the possible locations being determined from a user&#39;s prior WWW navigation history.  
      The substantially optimized navigation path to the user&#39;s information intention is global because it does consider other possible paths to the user&#39;s informational goal—although the module  310  may determine that certain paths are not appropriate for inclusion in the globally optimized path. The actual number of steps or paths from one location to another that comprise the globally optimized path is not only based on analysis of user navigation history to generate path probabilities, but also based on an entropy evaluation, which is discussed in greater detail below.  
      A user&#39;s navigation path is represented as a sequence of visited content pieces  206  or Web pages w 1 , w 2 ,Λ, w i ,Λ, w L , where w i  is the ith visited Web page in the sequence. To estimate the probability of the navigation path, the following Bayesian rule is applied to rewrite the probability estimation as equation 2.  
               Pr   ⁡     (       w   1     ,     w   2     ,   Λ   ,     w   i     ,   Λ   ,     w   L       )       =       Pr   ⁡     (     w   1     )       ⁢       ∏     i   =   2     L     ⁢           ⁢     Pr   (       w   i     ⁢            w   1     ,   Λ   ,     w     i   -   1         )                     (   1   )             
 
      A statistical language model (SLM) is applied to estimate the probability Pr(w i |w 1 ,Λ,w i−1 ) in equation (1).  
      The n-gram Markov model assumes that each word in a sequence is only determined by its previous (n−1) words. We assume that each Web page sequence with length n is called an n-gram Web page sequence. The next hyperlink the user will select is assumed dependant only on the previous (n−1) hyperlink the user has just clicked. Hence, the n-gram probability is re-written in equation (2).  
                   Pr   (         w   i     ⁢            w   1     ,   Λ   ,     w     i   -   1         )       ⁢       ≈     Pr   (       w   i     ⁢            w     i   -   n   +   1       ,   …   ⁢           ,     w     i   -   2       ,     w     i   -   1         )                           ⁢     =       Pr   ⁡     (       w     i   -   n   +   1       ,   …   ⁢           ,     w     i   -   2       ,     w     i   -   1       ,     w   i       )         Pr   ⁡     (       w     i   -   n   +   1       ,   …   ⁢           ,     w     i   -   2       ,     w     i   -   1         )                           ⁢     =         C   ⁡     (       w     i   -   n   +   1       ,   …   ⁢           ,     w     i   -   2       ,     w     i   -   1       ,     w   i       )       /     C   n           C   ⁡     (       w     i   -   n   +   1       ,   …   ⁢           ,     w     i   -   2       ,     w     i   -   1         )       /     C     n   -   1                             ⁢     =         C   ⁡     (       w     i   -   n   +   1       ,   …   ⁢           ,     w     i   -   2       ,     w     i   -   1       ,     w   i       )         C   ⁡     (       w     i   -   n   +   1       ,   …   ⁢           ,     w     i   -   2       ,     w     i   -   1         )         *   C                     (   2   )             
 
 where, C(w i−n+1 , . . . ,w i−2 , w i−1 , w i ) denotes the count of the n-Gram (w i−n+1 , . . . , w i−2 ,w i−1 ,w i ) appearing in the training data. C n  is the total number of the n-grams. C n−1  is the total number of the (n−1)-grams. C equals to C n /C n−1 . C n , C n−1 , and C are constants. From equation (1) and (2) we know that if C(w i−n+1 , . . . , w i−2 , w i−1 ) is known, the probability of Pr(w i |w 1 , w 2 , . . . , w i−1 ) is only influenced by the count C(w i−n+1 ,Λ, w i−1 , w i ). 
 
 The Global Optimization Model 
 
      The objective is to predict a user&#39;s real intention or information goal based on the user&#39;s previous information navigation behavior. However, unlike conventional techniques, which just predict one step ahead towards a user&#39;s predicted objective, the multi-step navigation prediction module  310  predicts one or more steps ahead such that the ultimate Web page after several steps is the user&#39;s real intention.  
      For instance, suppose the user has already visited k−1 Web pages w 1 , w 2 .Λ, w i ,Λ, w k−1 , and the user&#39;s real intention is w L . The aim is to find out the path w k , w k+1 ,Λ, w L  such that the probability of the overall navigation path Pr(w 1 ,w 2 ,Λ, w k−1 ,w k ,Λ w L ) is maximized. This is a global optimization method or technique. The conventional one-step n-gram model assumes that the local optimization at the next step (e.g., see the local maximized path A to C discussed above in reference to  FIG. 1 ) is the user&#39;s real intention. Thus it only chooses a wk to maximize the probability Pr(w 1 , w 2 , . . . , w k−1 , w k ) instead of the global probability—thus, it is likely to reach a local optimal point, especially when the data is not sufficient. This is similar to the “hill-climbing” algorithm and other searching algorithms often utilized in artificial intelligence (AI) algorithms.  
      For example, if a user likes to read news on a news Web-site but his/her favorite part of news is in always at a very deep level (e.g., the fourth level), each time the user must follow three hyperlinks to reach it. The user is not interested in all of the hyperlinks that are included in this path excepting the last one. In this case, the hyperlinks at the beginning of this path may have very small probabilities. Thus, if conventional one-step n-gram prediction is utilized, the first predicted hyperlink might take the user to a wrong way and the user may never arrive at the informational goal.  
      To avoid reaching the local optimal of conventional one step prediction systems, the probability of the entire path is maximized. Specifically, the global optimization is shown in equation (3).  
                 arg   ⁢           ⁢   max       w   k       ⁢       ∏     i   =   k     ∞     ⁢           ⁢     Pr   (       w   i     ⁢            w   1     ⁢           ⁢   …   ⁢           ⁢     w     i   -   2       ⁢     w     i   -   1         )                   (   3   )             
 
      Next, it is shown that the global optimization reflects the probability of the entire path, i.e. Pr(w k+1 w k+2  . . . |w 1  . . . w k−1 w k ). The proof is shown in equation (4).  
                     ∏     i   =     k   +   1       L     ⁢           ⁢     Pr   (         w   i     ⁢            w   1     ⁢   …   ⁢           ⁢     w     i   -   2       ⁢     w     i   -   1         )       =       ∏     i   =     k   +   1       L     ⁢           ⁢       Pr   ⁡     (       w   1     ⁢           ⁢   …   ⁢           ⁢     w     i   -   2       ⁢     w     i   -   1       ⁢     w   i       )         Pr   ⁡     (       w   1     ⁢           ⁢   …   ⁢           ⁢     w     i   -   2       ⁢     w     i   -   1         )                           =         ∏     i   =     k   +   1       L     ⁢           ⁢     Pr   ⁡     (       w   1     ⁢           ⁢   …   ⁢           ⁢     w     i   -   2       ⁢     w     i   -   1       ⁢     w   i       )             ∏     i   =     k   +   1       L     ⁢           ⁢     Pr   ⁡     (       w   1     ⁢           ⁢   …   ⁢           ⁢     w     i   -   2       ⁢     w     i   -   1         )                       =       Pr   ⁡     (       w   1     ⁢           ⁢   …   ⁢           ⁢     w     L   -   1       ⁢     w   L       )         Pr   ⁡     (       w   1     ⁢           ⁢   …   ⁢           ⁢     w     k   -   1       ⁢     w   k       )                     =     Pr   (       w     k   +   1       ⁢           ⁢   …   ⁢           ⁢     w     L   -   1       ⁢     w   L     ⁢            w   1     ⁢           ⁢   …   ⁢           ⁢     w     k   -   1       ⁢     w   k       )                       (   4   )             
 
      Hence, if L goes to infinite, the desired global optimization result is obtained. Furthermore, if the process of user navigation can be assumed to be a second-order Markov process, Pr(w i |w 1  . . . w i−2 w i−1 )=Pr(w i |w i−2 w i−1 ). Thus, equation (3) can be simplified to equation (5):  
                 arg   ⁢           ⁢   max       w   i       ⁢       ∏     i   =     k   +   1       ∞     ⁢           ⁢     Pr   (       w   i     ⁢            w     i   -   2       ⁢     w     i   -   1         )                   (   5   )             
 
      Although equation (5) is a simplified model, its complexity is still very high. A dynamic multi-step prediction method reduces this complexity such that i=k+1 to i=k+t, where t is a parameter representing that how many steps should be predicted forward. The parameter t is determined dynamically by employing the perplexity to measure the efficacy of the t-steps prediction. Such perplexity is used in statistical speech recognition techniques. The perplexity reflects the entropy of the path. The perplexity of t-steps prediction is defined in equation (6)  
               1   t     ⁢       ∑     i   =     k   +   1         i   =     k   +   t         ⁢     log   ⁢           ⁢     (     Pr   ⁡     (       w   i     ⁢            w     i   -   2       ⁢     w     i   -   1         )       )       ⁢                         (   6   )             
 
      Finally the user&#39;s optimal information goal is expressed in the following equation:  
                 arg   ⁢           ⁢   max     t     ⁢     (       1   t     ⁢       ∑     i   =     k   +   1         i   =     k   +   t         ⁢           ⁢     log   ⁢           ⁢       Pr   ⁡     (       w   i     ⁢            w     i   -   2       ⁢     w     i   -   1         )       )       .                     (   7   )             
 
 An Exemplary Procedure 
 
       FIG. 4  shows an exemplary procedure  400  that utilizes a multi-step n-gram user navigation model to predict a user&#39;s optimal information goal based on probabilities and the user&#39;s “Web surfing history. At block  402 , the procedure  400  records a Web log  316  indicating a user&#39;s Web navigation history. Such information can be collected by the browser  312  to automatically monitor the user&#39;s actions, for example, for the following operations. 
          Visits: When a user types in a URL in a browser  312  address box or choose a URL from a list (e.g., the favorite list), the browser will log the user name, start time, URL and elapse time into the log  316 .     Clicks: When a user click a hyperlink in a web-page, the browser  312  will log the user name, start time, from URL, click URL, text or image over the click URL and elapse time into the log  316 .     Querys: When a user submits a query to a search engine or type in a query in a text box, the browser  312  will log the user name, start time, query site, query words, returned results, clicked results, and elapse time into the log  316 .     Save As: When a user clicks a right mouse button and downloads a hyperlink or electronic image, the browser  312  will log the user name, start time and save object into the log  316 .        
      At block  404 , after generating a user log  316  (i.e., at block  402 ), a number of heuristic rules (e.g., based on any combination of URL, a hyperlink, a user name, a start time, text corresponding to a URL, a query, elapsed time, and/or an object name) are utilized to segment the surfing logs  316  into different sessions. Each session is represented by a list of URLs: u 1 ,u 2 ,Λ,u n .  
      At block  406 , the procedure  400  uses the statistical n-gram model to calculate the probability that the user may visit an URL from another URL given list of URLs (i.e., represented in the user log  316 ). Specifically:  
         Pr   ⁡     (       u   1     ,     u   2     ,   Λ   ,     u   n       )       =       Pr   ⁡     (     u   1     )       ⁢     Pr   (       u   2     ⁢          u   1     )     ⁢       ∏     i   =   3     n     ⁢           ⁢     Pr   (       u   i     ⁢            u     i   -   2       ,     u     i   -   1         )     ⁢     
     ⁢     Pr   (         u   i     ⁢            u     i   -   2       ,     u     i   -   1         )       =       C   ⁡     (       u     i   -   2       ⁢     u     i   -   1       ⁢     u   i       )         C   ⁡     (       u     i   -   2       ⁢     u     i   -   1         )                             
 
 Additionally, a smoothing and back-off method is applied to the calculation of Pr(u i |u i−2 , u i−1 ) to deal with the data sparse problem. 
 
      At block  408 , the procedure  400  dynamically predicts a globally optimized navigation path based on the determined probabilities (block  406 ) for the user to reach an ultimate information goal. Specifically, given navigation patterns u 1 ,u 2 ,Λ,u k , the most possible next browsing page u k+1  is determined, wherein u k+1  represents the best path to meet the user&#39;s real intention based on the following:  
           arg   ⁢           ⁢   max     i     ⁢       ∏     i   =     k   +   1       ∞     ⁢           ⁢     Pr   (       u   i     ⁢              u     i   -   2       ⁢     u     i   -   1         )     .               
 
 This search can be performed by a number of techniques such as a Viterbi Beam Search. (Note, the conventional solution is to determine a local optimization according to:  
           arg   ⁢           ⁢   max     i     ⁢           ⁢       pr   ⁡     (       u   i     ⁢            u     k   -   1       ⁢     u   k       )       )       .         
 
 An Exemplary Computing Environment 
 
       FIG. 5  shows an example of a suitable computing environment  500  on which an exemplary system and procedure using a multi-step dynamic n-gram prediction model to predict a user&#39;s optimal information goal, wherein the goal is based on a globally optimized navigation path through a sequence of previously visited network content pieces may be implemented. Exemplary computing environment  500  is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of an exemplary system and procedure to cluster queries. The computing environment  500  should not be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary computing environment  500 .  
      An exemplary system and procedure to use a multi-step dynamic n-gram prediction model to predict a user&#39;s optimal information goal based on a globally optimized navigation path through a sequence of previously visited network content pieces may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc., that perform particular tasks or implement particular abstract data types.  
      An exemplary system and procedure to use a multi-step dynamic n-gram prediction model to predict a user&#39;s optimal information goal based on a globally optimized navigation path through a sequence of previously visited network content pieces may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices.  
      As shown in  FIG. 5 , the computing environment  500  includes a general-purpose computing device in the form of a computer  202  of  FIGS. 2 and 3 . The components of computer  202  may include, for example, one or more processors or processing units  302 , a system memory  304 , and a bus  516  that couples various system components including the system memory  304  to the processor  302 .  
      Bus  516  represents one or more of any of several types of bus structures, including a memory bus or memory controller, a peripheral bus, an accelerated graphics port, and a processor or local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnects (PCI) bus also known as Mezzanine bus.  
      Computer  202  typically includes a variety of computer-readable media. Such media may be any available media that is accessible by the computer  202 , and it includes both volatile and non-volatile media, removable and non-removable media. For example, the system memory  304  includes computer readable media in the form of volatile memory, such as random access memory (RAM)  520 , and/or non-volatile memory, such as read only memory (ROM)  518 . A basic input/output system (BIOS)  522 , containing the basic routines that help to transfer information between elements within computer  202 , such as during start-up, is stored in ROM  518 . RAM  520  typically contains data  308  and/or program modules  306  that are immediately accessible to and/or presently be operated on by processor  302 .  
      Computer  202  may further include other removable/non-removable, volatile/non-volatile computer storage media. By way of example only,  FIG. 5  illustrates a hard disk drive  524  for reading from and writing to a non-removable, non-volatile magnetic media (not shown and typically called a “hard drive”), a magnetic disk drive  526  for reading from and writing to a removable, non-volatile magnetic disk  528  (e.g., a “floppy disk”), and an optical disk drive  530  for reading from or writing to a removable, non-volatile optical disk  532  such as a CD-ROM, DVD-ROM or other optical media. The hard disk drive  524 , magnetic disk drive  526 , and optical disk drive  530  are each connected to bus  516  by one or more interfaces  534 .  
      The drives and their associated computer-readable media provide nonvolatile storage of computer readable instructions, data structures, program modules, and other data for computer  202 . Although the exemplary environment described herein employs a hard disk, a removable magnetic disk  528  and a removable optical disk  532 , it should be appreciated by those skilled in the art that other types of computer readable media which can store data that is accessible by a computer, such as magnetic cassettes, flash memory cards, digital video disks, random access memories (RAMs), read only memories (ROM), and the like, may also be used in the exemplary operating environment.  
      A number of program modules may be stored on the hard disk, magnetic disk  528 , optical disk  532 , ROM  518 , or RAM  520 , including, by way of example, and not limitation, an OS  538 , one or more application programs  306 , other program modules  542 , and program data  308 . Each such OS  538 , one or more application programs  306 , other program modules  542 , and program data  308  (or some combination thereof) may include an embodiment of an exemplary system and procedure to use a multi-step dynamic n-gram prediction model to predict a user&#39;s optimal information goal based on a globally optimized navigation path through a sequence of previously visited network content pieces.  
      A user may enter commands and information into computer  202  through input devices such as keyboard  546  and pointing device  548  (such as a “mouse”). Other input devices (not shown) may include a microphone, joystick, game pad, satellite dish, serial port, scanner, or the like. These and other input devices are connected to the processing unit  302  through a user input interface  550  that is coupled to bus  516 , but may be connected by other interface and bus structures, such as a parallel port, game port, or a universal serial bus (USB).  
      A monitor  552  (e.g., the monitor  330  of  FIG. 3 ) or other type of display device is also connected to bus  516  via an interface, such as a video adapter  554 . In addition to the monitor, personal computers typically include other peripheral output devices (not shown), such as speakers and printers, which may be connected through output peripheral interface  555 .  
      Computer  202  may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer  562 . Logical connections shown in  FIG. 5  are a local area network (LAN)  557  and a general wide area network (WAN)  559 . Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets, and the Internet. Remote computer  562  may include many or all of the elements and features described herein relative to computer  202 .  
      When used in a LAN networking environment, the computer  202  is connected to LAN  557  via network interface or adapter  566 . When used in a WAN networking environment, the computer typically includes a modem  558  or other means for establishing communications over the WAN  559 . The modem  558 , which may be internal or external, may be connected to the system bus  516  via the user input interface  550  or other appropriate mechanism.  
      Depicted in  FIG. 5  is a specific implementation of a WAN via the Internet. Computer  202  typically includes a modem  558  or other means for establishing communications over the Internet  560 . Modem  558 , which may be internal or external, is connected to bus  516  via interface  550 .  
      In a networked environment, program modules depicted relative to the personal computer  202 , or portions thereof, may be stored in a remote memory storage device. By way of example, and not limitation,  FIG. 5  illustrates remote application programs  569  as residing on a memory device of remote computer  562 . The network connections shown and described are exemplary and other means of establishing a communications link between the computers may be used.  
      Computer Readable Media  
      An implementation of exemplary subject matter to system and procedure using a multi-step dynamic n-gram prediction model to predict a user&#39;s optimal information goal based on a globally optimized navigation path through a sequence of previously visited network content pieces may be stored on or transmitted across some form of computer-readable media. Computer-readable media can be any available media that can be accessed by a computer. By way of example, and not limitation, computer readable media may comprise “computer storage media” and “communications media.” 
      “Computer storage media” include volatile and non-volatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules, or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by a computer.  
      “Communication media” typically embodies computer readable instructions, data structures, program modules, or other data in a modulated data signal, such as carrier wave or other transport mechanism. Communication media also includes any information delivery media.  
      The term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared, and other wireless media. Combinations of any of the above are also included within the scope of computer readable media.  
     CONCLUSION  
      The disclosed subject matter provides a novel multi-step n-gram user navigation prediction model to predict a user&#39;s optimal information goal based on a globally optimized navigation path through a sequence of previously visited network content pieces. Although the described subject matter has been described in language specific to structural features and methodological operations, it is understood that the arrangements and procedures as defined the appended claims are not necessarily limited to the specific features or operations described. Rather, the specific features and operations disclosed are preferred forms of implementing the claimed subject matter.