Abstract:
The results of search queries are augmented with behaviorally related items. Items that are behaviorally related to a particular search query may be identified by analyzing the item selection actions of users who submit the particular search query. For example, if a relatively large number of users who submit a particular search query eventually select a particular item (e.g., during subsequent searching or browsing), that item may subsequently be included in the search results for the search query, even though the item may not match the search query.

Description:
TECHNICAL FIELD 
   The present invention is directed to the field of query processing. 
   BACKGROUND 
   Many World Wide Web sites permit users to perform searches to identify a small number of interesting items among a much larger domain of items. As an example, several web index sites permit users to search for particular web sites among most of the known web sites. Similarly, many online merchants, such as booksellers, permit users to search for particular products among all of the products that can be purchased from a merchant. In many cases, users perform searches in order to ultimately find a single item within an entire domain of items. 
   In order to perform a search, a user submits a query containing one or more query terms. The query also explicitly or implicitly identifies a domain of items to search. For example, a user may submit a query to an online bookseller containing terms that the user believes are words in the title of a book. A query server program processes the query to identify within the domain items matching the terms of the query. The items identified by the query server program are collectively known as a query result. In the example, the query result is a list of books whose titles contain some or all of the query terms. The query result is typically displayed to the user as a list of items. This list may be ordered in various ways. For example, the list may be ordered alphabetically or numerically based on a property of each item, such as the title, author, or release date of each book. As another example, the list may be ordered based on the extent to which each identified item matches the terms of the query. 
   It is fairly common for a user to specify a query containing a term that doesn&#39;t match any items. This may happen, for example, where a user mistypes the non-matching term, or when the user types a term that, though it does not match any items, is a synonym of a word that matches one or more items. In such cases, conventional techniques, which present only items that satisfy the query, present no items to the user. When no items are presented to a user in response to issuing a query, the user can become frustrated with the search engine, and may even discontinue its use. 
   Accordingly, an approach to processing search queries that does not rely on the terms of the query matching text associated with items would have significant utility. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  is a high-level block diagram showing typical components of a computer system or other device upon which the facility executes. 
       FIG. 2  is a data flow diagram showing data flow relating to a query submitted by a client. 
       FIG. 3  is a data flow diagram showing data flow relating to the performance of a selection action by a client. 
       FIG. 4  is a data flow diagram showing data flow relating to the population of the term/item scoring table. 
       FIG. 5  is a flow diagram showing steps typically performed by the facility to generate term/item relatedness scores. 
       FIG. 6  is a table diagram showing sample contents of an item selection event table typically used by the facility. 
       FIG. 7  is a table diagram showing sample contents of a search query event table typically used by the facility. 
       FIG. 8  is a table diagram showing sample contents of the item selection event table following population of the preceding query terms column. 
       FIG. 9  is a table diagram showing sample contents of a term/item scoring table typically generated by the facility. 
       FIG. 10  is a flow diagram showing steps typically performed by the facility in order to augment a query result produced by a search engine for a particular query string. 
       FIG. 11  is a flow diagram showing steps typically performed by the facility in order to generate a set of item recommendations for a particular user. 
   

   DETAILED DESCRIPTION 
   A software facility (the “facility”) is described that (1) discerns from user behavior associations between query terms and items relevant to such query terms, and (2) exploits such associations, such as (a) to add to a query result items not included in the query result produced for the query by a search engine but nonetheless likely to be relevant to the query, or (b) to generate a set of item recommendations for a user based upon the contents of the queries recently submitted by the user. 
   For a group of users, the facility monitors queries submitted and item selection actions taken, such as viewing an item&#39;s item detail page (e.g., as in an online catalog), adding an item to a shopping cart, adding an item to a gift registry, ordering an item, sampling an item, or rating or reviewing an item. For each item selection action by a user, the facility (1) identifies queries submitted by that same user in a short period of time before the selection action, and (2) correlates the item that is the subject of the selection action with the query terms in the identified queries. The facility uses the formed correlations to generate, for each of a number of combinations of a query term and an item, a score reflecting the tendency of users submitting queries containing the query term to go on to select the item. The facility can use a variety of approaches described below to perform the monitoring and determine the scores. 
   In order to exploit these term/item scores to add to a query result items not included by the search engine in the query result produced for the query but nonetheless likely to be relevant to the query, when a new query is received, in addition to being provided to the search index to generate a search result listing items that satisfy the query, it is provided to the facility to identify items that, when paired with the query term(s) in the query, have the highest scores. The facility provides the identified items for inclusion in or display with the query result generated by the search engine. 
   In this way, the facility makes query results potentially more valuable in a variety of different situations. Where a user has submitted a query containing a misspelled query term that, if properly spelled, would match a particular item, and the misspelling is somewhat common among users tracked by the facility, the facility can cause the item to be included in the augmented search result. For example, where a user submits the query “Morrissy” in an attempt to locate an album by the musician Morrissey, the facility may add one or more Morrissey albums to the produced query result where other users have previously submitted a query containing “Morrissy,” and gone on to do any of the following: discovered their spelling error, resubmitted the search with the correct spelling, and selected the album; or used a way other than search to locate and select the album, such as using a browse tree, best seller list, recommendation, wish list, reference to an external source such as an online or paper music magazine, etc. Similarly, when a user has submitted a query containing a synonym for a search term that would match an item that is commonly used by other users to search for the item, the facility can cause the item to be included in the augmented search result. For example, where a user submits the query “Samsung mobile” in an attempt to find wireless telephones manufactured by Samsung, none of which has the word “mobile” associated with them, the facility can cause one or more Samsung cellular wireless telephone items to be added to the query result. 
   Where a user has submitted a query containing a query for a first item that is commonly purchased—or otherwise selected—together with a second, “complement” item, the facility can add the complement item to the search result produced for the query. For example, where a user submits a query that identifies a particular printer item that is often purchased together with a particular printer cable item, the facility can add the printer cable item to the produced search result. Additionally, where a number of users use the same query terms to search for a first item, then follow a “related items” link on the first item&#39;s item detail page to a second item, the facility can add the second item to the search result. For example, where users commonly (1) submit the query “Grinch” to locate the DVD  Dr. Seuss—How the Grinch Stole Christmas , then (2) follow a “related items” link on that item&#39;s item detail page to the item detail page for the DVD  Frosty the Snowman , the facility can add the  Frosty the Snowman  DVD item to the search results generated for subsequent “Grinch” queries. 
   The facility can also exploit the term/item scores to generate a set of item recommendations for a user based upon the contents of the queries recently submitted by the user. When an opportunity arises to present item recommendations to a user—such as when the user displays a special recommendations page, or when the user displays a page of another type that has space reserved for user recommendations—the facility retrieves a history of the user&#39;s recent queries, and for each item, combines scores for combinations of that item with each query term appearing in the user&#39;s query history. The facility then selects a set of items to recommend that have the highest combined score. For example, where an opportunity arises to provide recommendation to a user who has recently submitted the queries “detective” and “mystery,” and where users that submit queries containing either of these query terms frequently buy or otherwise select the book  The Adventures of Sherlock Holmes , the facility can provide recommendations to the user that include this book item. Recommendations generated in this way are often “fresher” than conventional recommendations based upon the user&#39;s purchases, which are sometimes criticized as stagnant. In some embodiments, recommendations generated for a user based upon the contents of the queries recently submitted by the user are combined with conventional recommendations for presentation to the user. 
   By compiling and/or exploiting the term/item scores in some or all of the ways described above, the facility can assist users by leveraging the earlier experiences and actions of all other users. In particular, where other users have had to expend a larger amount of effort to select an item not initially included with the query result that they received, a user that receives an augmented search result or recommendation produced by the facility that contains the item can select the item directly from the augmented search result or recommendation and avoid any additional effort. 
     FIG. 1  is a high-level block diagram showing typical components of a computer system or other device upon which the facility executes. As shown in  FIG. 1 , the computer system  100  comprises a central processing unit (CPU)  110 , input/output devices  120 , and a computer memory (memory)  130 . Among the input/output devices is a storage device  121 , such as a hard disk drive; a computer-readable media drive  122 , which can be used to install software products, including the facility, which are provided on a computer-readable medium, such as a CD-ROM; and a network connection  123  for connection the computer system  100  to other computer systems (not shown). The memory  130  contains a web server program  131  for receiving HTTP requests for a merchant or other publisher&#39;s website, including search query requests and selection action requests; a web server log  132  in which the web server logs as events the HTTP requests it receives; the facility  133 ; term/item association tables  134  generated by the facility from the web server log; and term/item rating tables  135  generated by the facility from the term/item association tables, and used by the facility to determine the extent of relatedness of a term to an item, and to support such functionality as augmenting search results and generating recommendations based upon term/item relatedness. While the facility may be implemented on a computer system or other device configured as described above, those skilled in the art will recognize that it may also be implemented on computer systems and devices having different configurations. 
     FIGS. 2-4  are data flow diagram showing typical data flows producing using the facility.  FIG. 2  is a data flow diagram showing data flow relating to a query submitted by a client.  FIG. 2  shows that a client  201  submits a query  211  to a search engine  203 . In response to receiving the query, the search engine sends items  212 ,  214 , and  216 , as described below. The search engine sends a retrieval request  212  to a search index  204 , which returns a search result  213  based upon the contents of the search index. The search engine sends a storage request  214  to a search query event table  205  to store information about the query event. The search engine sends a retrieval request  215  to the term/item scoring table  206 , which returns highest-scoring items for the terms in the query  216 . When the search engine receives items  213  and  216 , it sends an augmented query result  217  via the Internet to the client. 
     FIG. 3  is a data flow diagram showing data flow relating to the performance of a selection action by a client.  FIG. 3  shows a selection action  311  sent from a client  201  to a selection engine  303 . In response to receiving the selection action, the selection engine (a) sends a storage request  312  to the item selection event table  304  to store information about the selection action, and (b) sends a selection action response  313  via the Internet to the client. 
   Those skilled in the art will appreciate that queries submitted as shown in  FIG. 2  and selection actions submitted as shown in  FIG. 3  may be submitted by various programs executing on the client in various ways. For example, either or both may be submitted by a web browser program at the direct instigation of a human user and received by a web server on behalf of the search engine and/or the selection engine. Where queries and/or selection actions are submitted in this way, an IP address of the client or the value of a cookie stored on the client may be used as the user ID used to correlate search query events and item selection events to generate term/item scores. Alternatively, various other kinds of programs executing on the client may submit queries and/or selection actions, which may be received by various kinds of programs on behalf of the search engine and/or selection engine. For example, the query and/or selection action may be submitted and received as web services requests. Where this is true, the facility may use the client&#39;s IP address or a requester ID submitted in the web services request to correlate queries with selection actions. 
     FIG. 4  is a data flow diagram showing data flow relating to the population of the term/item scoring table. Based upon information in both the item selection event table  304  and the search query event table  205 , the storage request  411  is sent to the term/item scoring table in order to populate the term/item scoring table with term/item scores that are based upon the contents of the item selection event table and the search query event table. 
     FIG. 5  is a flow diagram showing steps typically performed by the facility to generate term/item relatedness scores. The facility typically performs these steps periodically as HTTP requests are received by the web server and logged as events in the web server log. 
   In steps  501 - 505 , the facility loops through events in the web server log that have not yet been processed. In step  502 , the facility branches on the event type of the event: if the event is an item selection event, then the facility continues in step  503 ; if the event is a search query event, then the facility continues in step  504 ; if the event is an event of another type, then the facility continues in step  505 . In step  503 , the facility adds a row for the event to an item selection event table. 
     FIG. 6  is a table diagram showing sample contents of an item selection event table typically used by the facility. The item selection event table  304  is made up of rows, such as rows  601 - 604 . Those skilled in the art will appreciate that a typical item selection event table would contain a much larger number of rows than shown in  FIG. 6 , as would other tables shown in additional table diagrams discussed below. Each row in the item selection event table corresponds to a different item selection event encountered in the web log, and is divided into the following columns: a time column  611  containing the time at which the HTTP request corresponding to the event was received by the web server; a user ID column  612  containing an identifier for the user from whom the HTTP request was received; an item ID column  613  containing an item ID identifying the item that was the subject of the selection request; a selection action type column  614  containing an indication of the type of selection action performed; and a preceding query terms column  615 , left empty in step  503  and described further below in conjunction with  FIG. 8 . For example, the contents of row  601  indicate that, at 10:10:11 a.m. on Jul. 3, 2004, an HTTP request was received from user C representing the purchase of an item having item ID 28834902. Those skilled in the art will recognize that the data shown in  FIG. 6  and the data shown in the additional table diagrams discussed hereafter, or similar data, could be stored in a variety of different forms, including being stored in various types of memory devices, in various organizations, in one or more tables or other data structures, using various forms of indexing, compression, encryption, etc. 
   Returning to  FIG. 5 , after step  503 , the facility continues in step  505 . In step  504 , the facility adds a row for the event to a search query event table maintained by the facility. 
     FIG. 7  is a table diagram showing sample contents of a search query event table typically used by the facility. The search query event table  700  is made up of rows, such as rows  701 - 706 . Each row corresponds to a search query event encountered in the web server log, and is divided into the following columns: a time column  711  indicating the time at which the search query request was received; a user ID column  712  containing a user ID identifying the user from whom the search query request was received; and a query terms column  713  including one or more query terms specified in the search query request. For example, contents of row  701  indicate that, at 10:08:34 a.m. on Jul. 1, 2004, a search query request was received a user having user ID A containing the query term “detective.” In some embodiments, the facility treats an entire query string as a term, while other embodiments of the facility treat each individual word of the query string as a term. 
   Returning to  FIG. 5 , after step  504 , the facility continues in step  505 . In step  505 , if additional events remaining in the web server log to be processed, then the facility continues in step  501  to process the next event, else the facility continues in step  506 . 
   In steps  506 - 508 , the facility loops through each row of the search query event table. In step  507 , the facility copies the query terms from the current row of the search query event table to the preceding query terms field of each row of the item selection event table that both (1) contains the same user ID, and (2) has a time that is within a specified period after the time of the row of the search query event table. The size of the specified period of time is configurable, and should be based on what is understood to be the typical amount of time after performing a search that a user may select an item that is related to the search. Typical periods of time may be ten minutes, one hour, five hours, one day, one week, etc. In step  508 , if additional rows of the search query event table remain to be processed, then the facility continues at step  506  to process the next row, else the facility continues in step  509 . 
     FIG. 8  is a table diagram showing sample contents of the item selection event table following population of the preceding query terms column. In populating the preceding query terms column, the facility has used the time period of one day to determine whether a query request is related to an item selection request. In row  801 , it can be seen that “Samsung mobile” has been added to the preceding query terms field from row  702  of the search query event table, which is the only row of the search query event table containing user ID C, whose time is before the time of row  801  but not more than one day before that time. On the same basis, the same query terms are added to row  804 . In row  802 , it can be seen that the query term “mystery” has been added to the preceding query terms field, from row  704  of the search query event table, which has the same user ID, and a time before, but not more than one day before, the time of row  802 . It can be seen that the query term “detective” in row  701  of the search query event table has not been added to the preceding query terms field of row  802  despite matching the user ID of row  802 , because row  701  has a time that is more than one day before the time of row  802 . In row  803 , it can be seen that “geometry” has been added to the preceding query terms field from row  703  of the search query event table whose user ID matches and whose time was before but not more than one day before the time of row  803 . “Morrissy” has also been added to the preceding query terms column of row  803  from row  705  of the search query event table. “Grinch” from row  706  has not been added to the preceding query terms field of row  803  despite matching the user ID of row  803 , as its time is after the time of row  803 . 
   Returning to  FIG. 5 , in step  509 , the facility uses the item selection event table to generate a term/item scoring table containing relatedness scores for combinations of terms and items. After step  509 , these steps conclude. 
     FIG. 9  is a table diagram showing sample contents of a term/item scoring table typically generated by the facility. The term/item scoring table  900  can be an extremely large table, having large number of both rows and columns, only a very small subset of which is shown in table  900 . In some embodiments, the facility uses a variety of large and/or sparse matrix storage and access techniques to represent the table contents. The table is comprised of rows, such as rows  901  and  902 , each representing a different query term. For example, row  901  represents the query term “Morrissey.” The rows of the table are intersected by columns, such as columns  911  and  912 , each representing a different item. For example, column  911  represents an item having item ID 45645646. Each intersection of a row with a column contains a term/item relatedness score for the term represented by the row and the item represented by the column. For example, the score 4126 occurring at the intersection of row  901  in column  911  is the relatedness score for the combination of the term “Morrissey” and the item having item ID 45645646. Based upon the scores shown, it can be seen that the term “Morrissy” is significantly more related to item 45645646 than is the term “Morrissey.” On the other hand, the term “Morrissey” is slightly more related to item 45645647 than is the term “Morrissy.” 
   Embodiments of the facility generate term/item scores in a variety of ways. Most of the approaches to scoring used by the facility involve, at a minimum, counting the number of users that both (1) submitted a query for the query term, and (2) within the prescribed amount of time, performed a selection action with respect to the item. In one approach to scoring, the facility may simply sum the number of users that both submitted a query for the term and selected the item. In some embodiments, the facility weights differently the types of selection actions. For example, the facility may weight a purchase selection action more heavily than a display item detail selection action. Also, the facility may weight more heavily selection actions that require a greater level of effort to perform, as is discussed in greater detail in U.S. patent application Ser. No. 09/847,954, entitled “Identifying the Items Most Relevant to a Current Query Based on Items Selection in Connection with Similar Queries,” filed on May 2, 2001 (now U.S. Pat. No. 7,124,129, issued on Oct. 17, 2006), which is hereby incorporated by reference in its entirety. 
   Additional approaches used by embodiments of the facility include:
 
score 1 (term, item)= C/SQRT ( A·B )  (1)
         where:   A=number of users that submitted a query for the term,   B=number of users that selected the item, and   C=number of users that both submitted string and selected the item.
 
score 2 (term, item)=( A/B )/( C/D )  (2)
   where:   A=number of users that both submitted string and selected the item,   B=number of users that submitted string,   C=number of users that did not submit a query for the term and selected the item, and   D=number of users that did not submit a query for the term,
 
score 3 (term, item)=( A/C )/( E/F )  (3)
   where:   A=number of users that both submitted string and selected the item,   C=number of users that did not submit a query for the term and selected the item,   E=number of users that submitted a query for the term but did not access the category, and   F=number of users that did not submit a query for the term and did not access the category.
 
score 4 (term, item)=( C/B −(alpha)* A/D )  (4)
   where:   A=number of users that selected the item,   B=number of users that submitted a query for the term,   C=number of users that both submitted a query for the term and selected the item, and   D=total number of users who have selected any item and have submitted any search.       

   The above mentioned scores can be combined in a variety of ways to produce a weighted average of multiple scores. For example:
 
score 5 (term, item)=Σ W   i score i (term, item)  (5)
 
where W is a weighting function for each correlation score, score i  is the correlation score itself, and ΣW i =1. For example, the faculty could combine approaches (2) and (4) above as follows:
 
 CS=w *(score 2 )=(1 −w )*(score 4 )  (6)
 
where w is a weighting factor such as 0.20.
 
   In some embodiments, the facility uses a sliding window approach to incorporate the most recent information derived from weblogs in the relatedness scores determined by the facility. Suitable approaches of this type are described in the aforementioned U.S. patent application Ser. No. 09/847,954 (now U.S. Pat. No. 7,124,129), and in U.S. patent application Ser. No. 10/817,554, entitled “Automated Detection of Associations Between Search Criteria and Item Categories Based on Collective Analysis of User Activity Data,” filed on Apr. 2, 2004 (published on Oct. 6, 2005 as 2005/0222987 A1), which is hereby incorporated by reference in its entirety. In some embodiments, the facility uses an approach of maintaining separate sets of relatedness scores for different user populations of various types. A suitable approach of this type is described in the aforementioned U.S. patent application Ser. No. 09/847,954. 
     FIGS. 10 and 11  are flow diagrams showing how the facility can exploit term/item relatedness scores.  FIG. 10  is a flow diagram showing steps typically performed by the facility in order to augment a query result produced by a search engine for a particular query string. In step  1001 , the facility identifies items having the highest term/item scores for the term or terms in a query. In some embodiments, the facility treats an entire query string as a term, while other embodiments of the facility treat each individual word of the query string as a term. In step  1002 , the facility adds the items identified in step  1001  to the query result produced for the query by the search engine. In step  1002 , the facility can either combine the items identified in step  1001  seamlessly into the list of items already in the query result, or may insert a distinct list of the identified items that is visually separated from the list of items produced by the search engine. For some queries, the search engine may produce empty query results, in which case the augmented query result produced in step  1002  contains only items identified based on their term/item scores. In some embodiments, the facility includes certain related information with each item it adds to the query result, such as, for example, a link to the item detail page for the item; an image related to the item; catalog text associated with the item; the item&#39;s price; the item&#39;s level of availability; controls for purchasing the item, adding it to a wish list, or performing other selection actions; etc. After step  1002 , the steps conclude. 
     FIG. 11  is a flow diagram showing steps typically performed by the facility in order to generate a set of item recommendations for a particular user. In step  1101 , the facility reads query terms from the rows of the search query event table that match the user&#39;s user ID. In some embodiments, the facility processes the rows in step  1101  in later-to-earlier time order, and reads terms only from a limited number of rows, and/or only from rows having dates no more than a certain amount of time in the past. 
   In steps  1102 - 1104 , the facility loops through each item. In step  1103 , the facility combines the term/item scores for the combinations of the current item and each of the terms read in step  1101  to obtain a combined score for the item. In step  1104 , if additional items remain to be processed, then the facility continues in step  1102  to process the next item, else the facility continues in step  1105 . In some embodiments (not shown), the facility limits the number of items for which it performs the processing in step  1103 , such as by performing the processing only for items that have at least one term/item score with one of the red terms that exceeds a score threshold. 
   In step  1105 , the facility recommends one or more items having the highest combined scores. After step  1105 , these steps conclude. 
   The facility may perform the steps of  FIG. 11  either synchronously in response to an opportunity to present item recommendations to a particular user, or asynchronously, in a periodic batch for all users. The item recommendations generated by the facility may be presented to a user in various ways, such as by including the item recommendations in a dedicated item recommendations web page; including the item recommendations in a smaller area of a web page primarily devoted to another subject; e-mailing the item recommendations to the user; etc. 
   It will be appreciated by those skilled in the art that the above-described facility may be straightforwardly adapted or extended in various ways. While the foregoing description makes reference to particular embodiments, the scope of the invention is defined solely by the claims that follow and the elements recited therein.