CROSS-REFERENCES TO RELATED APPLICATIONS

This application claims the benefit of U.S. Provisional Patent Application No. 61/131,498 filed Jun. 10, 2008, entitled â€œSearch result relevancy using real-time implicit relevance feedbackâ€ , which is hereby incorporated by reference in its entirety. Related applications are U.S. patent application Ser. No. 11/510,524 filed Aug. 25, 2006, entitled â€œDynamic Search Engine Results Employing User Behaviorâ€ and U.S. patent application Ser. No. 11/743,076 filed May 1, 2007, entitled â€œReal Time Implicit User Modeling for Personalized Searchâ€ , the disclosures of which are hereby incorporated herein by reference.

BACKGROUND OF THE INVENTION

The present invention relates to search engines which monitor real-time user behavior in order to improve relevance by immediately re-ranking results in response to user actions.

Information Retrieval (IR) systems in general, and search engines in particular, are designed to assist users in locating and identifying documents of interest based on a variety of input regarding the user's information need. This need is most normally received by asking the user to input a query, typically expressed as a set of keywords and sometimes including various Boolean operators. The understanding of the user's intent can then be modified or refined based on other user inputs, both explicit and implicit. The IR system will then comb the universe of available documents for possible matches which, based on any number of different relevancy algorithms, are presented to the user in a descending order of probability of interest. In other words, those documents with the highest probability of being relevant to the user are typically presented first. The objective is to quickly point the user toward documents with the greatest likelihood of satisfying the information need.

Information retrieval on very large data communication networks that contain an enormous amount of information, such as the internet, is particularly difficult given the sizable sets of potentially relevant documents. It is not uncommon for queries on the general internet to return hundreds of thousands, if not millions, of results. Optimally ranking these results based on inherently ambiguous user input, even when taking additional information regarding the user or other searchers into account, is extremely challenging.

IR systems and search engines have thus employed many strategies for combating this issue, most of which seek to achieve a better understanding of the user's information need. Some explicitly request additional information concerning intent, such as directly asking the user to respond to questions regarding both short- and long-terms interests as well as proposing clusters (e.g., a group of key words or categories), drill-downs or reformulations based on the user's query. Others rely on implicit signals derived from user behavior in order to better divine intent.

While the objective of all of these strategies is to produce an optimally ranked set of results based on the user's query and the corpus of user, documents and other information available prior to the user submitting the query, one technique of particular interest involves using real-time user behavior signals to disambiguate intent after the result set has been produced and then exploiting that information to immediately re-rank the results following each user action. (This is described in U.S. patent application Ser. No. 11/510,524 entitled â€œDynamic search engines results employing user behaviorâ€ and Ser. No. 11/743,076 entitled â€œReal time implicit user modeling for personalized search.â€ ) While the other strategies harness various types of information, both implicit and explicit, to produce a static and frequently sub-optimally ranked set of documents, the results with real-time re-ranking are dynamic as each new user input immediately generates an improved ranking and modified result set.

As an example, a user query for â€œdolphinsâ€ is inherently ambiguous as it is unclear whether the individual's intent refers to the mammal or the football team. By observing the past search behavior of the individual, as well as those of other searchers, many IR strategies will attempt to divine which context has the greater likelihood of satisfying this particular user's information need, at the particular point in time, but it's virtually impossible to know with certainty and so the result set will typically contain a mix of both. Once the user actually selects a result from one context or the other, however, the degree to which the user's intent can be inferred is increased dramatically and the result set can be optimized on the fly by immediately re-ranking the documents. For example, should the user select a result related to the Miami Dolphins football team, documents related to football are â€œpromotedâ€ while simultaneously those related to the mammal are â€œsuppressed.â€

While a static result set is easily depicted as a list of documents in something close to descending order of probabilistic relevance, presenting dynamic results poses challenges for the user interface (UI). As the re-ranking of results continuously produces an optimally superior order of documents, it is important for any distraction created by the movement of documents to not impair the advantage of the heightened relevancy.

There is therefore a need to develop a UI capable of delivering the benefits of real-time re-ranking while being as unobtrusive as possible to the user's search experience.

SUMMARY OF THE INVENTION

The present invention provides a system and methods for dynamically altering the UI of an IR system to present the fluid nature of search results as they are re-ranked in real time.

In one embodiment, the adaptive UI is run as a software application between a user and a standard third-party search engine or multiple third-party search engines. This software application can run on the user's computer, a central server, or both. In another embodiment the software for the UI is built into the underlying IR system and may run on the same server as the IR system or a separate server.

In one embodiment, every time a new ranking is produced the search results are immediately redisplayed in their new order. In another embodiment, rather than moving around results that have already been displayed, only the unseen results are re-ranked with the top unseen documents, after the re-ranking, being inserted on the search results page as recommended search results. In another embodiment, such recommendations are nested to several levels with each successive user action bringing forward from subsequent results pages more re-ranked documents. Each set of recommendations may be preceded by some explanatory text or some other design device, or displayed on a different area of the page, to set them apart from the documents that were previously on the results page.

In one embodiment the initial position of each document is indicated by some text or graphical element. For example, a re-ranked result on page 1 that was initially on page 2 might be followed by the text â€œfrom page 2.â€

In one embodiment each result is accompanied by a graphical element or link enabling the immediate re-ranking of documents and display of recommended search results. Clicking a graphical element will behave similarly as if the user had selected the particular document and then returned to the result set. These graphical elements may also accompany each recommended search result and operate in a similar manner. In another embodiment, clicking the graphical element for a document that already has recommendations will cause the recommendations to be removed from the page, along with any associated nested recommendations. Subsequently clicking the same graphical element will alternately display and remove the set of recommendations and any associated nested recommendations.

In one embodiment, clusters or query reformulation suggestions are presented next to each set of recommended documents. Unlike traditional clusters, however, these clusters are refined and selected based on the current real-time user model. Rather than presenting a set of clusters or query reformulation suggestions based on the user's query or the entire document set, the present invention can produce more highly targeted clusters to facilitate the process of moving forward.

In one embodiment, the next page of results, prior to being displayed to the user, is completely re-ranked at the moment the user clicks â€œnextâ€ or â€œmore results.â€ Once these re-ranked results are displayed they become seen and so re-ranking and display of recommendations proceeds as it did on the previous page.

Sponsored links may also be re-ranked or updated based on the real-time model of user intent. In one embodiment, the real-time user model is used to select more appropriate advertisements from the set of advertisements associated with the user's query. In another embodiment, the real-time user model is used to modify the user's query in order to find additional advertisements more precisely related to the user's intent.

In one embodiment, whenever the real-time user model is updated the old advertisements are removed from the page and replaced with new advertisements. In another embodiment, the advertisements operate similar to the organic results with recommended sponsored links being inserted under selected sponsored links. In another embodiment, sponsored links on subsequent pages of results are selected based on the current real-time user model.

The outcome is a dynamic UI that adapts to the real-time user model in order to display the most relevant search results and advertisements in a manner as unobtrusive to the user experience as possible.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a diagram of one embodiment of a system incorporating the present invention.

FIG. 2A is a diagram of one embodiment of the home page.

FIG. 2B is a diagram of one embodiment of the initial search results.

FIG. 2C is a diagram of one embodiment of the re-ranked search results.

FIG. 2D is a diagram of one embodiment of re-ranked search results presented as indented â€œrecommendationsâ€

FIG. 2E is a diagram of one embodiment of re-ranked search results presented as nested â€œrecommendationsâ€

FIG. 3 is a diagram of one embodiment of adaptive UI tools added to the search results page.

DETAILED DESCRIPTION OF THE INVENTION

The preferred embodiment of the present invention operates on the interne, and more specifically the World Wide Web. The invention, however, is not limited to the internet, the World Wide Web or any other particular network architecture, software or hardware which may be described herein. The invention is appropriate for any other network architectures, hardware and software. Furthermore, while the following description relates to an embodiment utilizing the interne and related protocols, other networks and protocols, for example, for use with interactive TVs, cell phones, personal digital assistants and the like, can be used as well.

The functions described herein are performed by programs including executable code or instructions running on one or more general-purpose computers. The functions described herein, however, can also be implemented using special purpose computers, state machines and/or hardwired electronic circuits. The example processes described herein do not necessarily have to be performed in the described sequence and not all states have to be reached or performed.

As used herein, the term â€œwebsiteâ€ refers to a collection of content. Website content is often transmitted to users via one or more servers that implement basic intern& standards. â€œWebsiteâ€ is not intended to imply a single geographic or physical location but also includes multiple geographically distributed servers that are interconnected via one or more communications systems.

As used herein, the term â€œdocumentâ€ is defined broadly and includes any type of content, data or information contained in computer files and websites. Content stored by servers and/or transmitted via the communications networks and systems described herein may be stored as a single document, a collection of documents or even a portion of a document. The term â€œdocumentâ€ is not limited to computer files containing text but also includes files containing graphics, audio, video and other multimedia data. Documents and/or portions of documents may be stored on one or more servers.

As used herein, the term â€œclickâ€ or â€œclick-throughâ€ is defined broadly and refers to clicking on, or hovering over, a hyperlink included within search result listings to view an underlying document or website. The term â€œclicking onâ€ a link or button, or pressing a key to provide a command or make a selection, may also refer to using other input techniques such as voice input, pen input, mousing over or hovering over an input area or the like.

The dynamic UI of the present invention is designed to efficiently communicate the benefits of enhanced relevancy obtained through immediately re-ranking of search results in response to user actions. In order to appreciate the benefits of real-time re-ranking, the display of search results should be updated each time the real-time user model produces a new ranking of search results. In the preferred embodiment, the display of search results is immediately updated every time a re-ranking occurs.

FIG. 1 is a high-level illustration of a preferred embodiment of a system incorporating the present invention. Documents on servers or computers 110-118, on a data communication network 140, such as the interne, are scanned and indexed by search engines on computers and associated databases 120-128. On the interne there are currently billions of documents available, with more being added daily. Google, Yahoo! and Bing are examples of popular intern& search engines, but most any web site that enables users to search for documents on a data communications network and retrieve relevant results can be considered a search engine. Users on computers or terminals 100-108 seeking information can connect with the search engine of their choice, enter keywords related to their searches, and then retrieve lists of matched documents, normally sorted and ranked by an algorithm that places the ones with the highest probability of being relevant to the user's query at the top. The real-time re-ranking engine provides a server 132 and database 130 which plug into the data communications network and then uses the behavior of current users to alter the results provided by one, if not several, of the other search engines. An embodiment of the present invention resides on server 132 with the re-ranking engine.

The description of this system will focus on a website that takes results from other search engines that reside on the internet, however, other embodiments of the system would involve incorporating the re-ranking engine and present invention directly into one of the other search engines 120-128. Rather than collecting the initial search results via a data communications network, the system can gather the results directly from a search engine.

One embodiment of the invention would involve software, which could be made available for download, which resides on users' computers or terminals 100-108. Rather than going to the website of the invention, users will now go directly to a search engine of choice and the process of using user modeling to immediately alter search results will be performed by the software located on the users' computers. The adaptive UI can then be applied on top of the user's search engine within the user's computer.

FIG. 2A is a diagram of a home page of a search engine. While other information and links can be present, the principal purpose of the home page is to enable the user to enter a query consisting of a keyword or set of keywords 202 representing the user's information need before clicking on a button 204 to request that the search engine retrieve the results.

FIG. 2B is a diagram of an example of a search results page depicting what the initial search results for the keyword â€œWashingtonâ€ might look like. Upon receiving a query 212 from a user, expressed as a keyword or set of keywords, the search engine produces a set of results 220-227. Each result is normally comprised of a title, snippet and the Uniform Resource Locater (URL) of the document, the combination of which can be described as the summary. Search engines may also include additional information next to each result, such as images or expanded snippets. Since the number of matched documents rarely fits on a single page, buttons, such as a next results button 216, are typically available to enable users to navigate to subsequent pages of results and then back to previous pages of results. It should also be noted that a search engine may offer supplemental information on the search results page, as is often the case, such as related popular queries, suggested spellings or links to maps and stock quotes.

FIG. 2C is a diagram of an example of how the first modified results might look after the user clicks on the document â€œGeorge Washington Universityâ€ 226 from the initial results as depicted in FIG. 2B and then, after viewing the document, returns to the search results page. The set of matched documents remains the same, yet their order has changed based on the intelligence gathered as a consequence of the user's click on the document â€œGeorge Washington Universityâ€ 226. The re-ranking engine has deduced that the user is most likely interested in universities containing the word â€œWashingtonâ€ as opposed to George Washington the man or Washington the city or state. As a result, the â€œAccess Washington Home Pageâ€ document 220, which was initially at the top of the list, has fallen to the sixth position 245 because the system has deemed, based on the behavior of the user, that the probability of this document being relevant to the user has declined. On the other hand, the â€œUniversity of Washingtonâ€ document 221, which was initially in the second position, has now moved to the top 240 because the system has deemed, again based on the behavior of the user, that the relevance of this document has increased. This process continues, for all practical purposes, for every document returned in the set of search results.

FIG. 2D represents another embodiment of the invention where instead of immediately altering the positions of all of the documents, the documents that have already been seen 260-264 remain â€œstatic,â€ while re-ranked results from subsequent pages are pulled forward 270-272 and indented as â€œrecommendations.â€ In this example, upon the user selecting the document â€œGeorge Washington Universityâ€ 263, the re-ranking engine immediately adjusts the position of all the documents in the result set that have not yet been seen by the user and then the adaptive UI pulls forward three to present to the user as recommendations. Should the user return to the search result page by clicking â€œbackâ€ on the web browser, or select the document without leaving the search result page by doing something such as a Ctrl-click on the result link, the recommended documents will immediately be presented.

In this example, three documents are pulled forward as recommendations, however, any number of documents may be selected, including zero. In another embodiment of the invention, the number of documents pulled forward as recommendations is a function of the quality of results that are already on the page, as determined by the re-ranking engine. For example, if three documents are selected as candidates for recommendations yet the re-ranking engine determines that one of those is inferior to a result that is already displayed on the page, the adaptive UI will only bring forward the other two as recommendations.

Table I is an illustration of how the number of recommended results for a given user action can be made to vary. Assume that the system is configured to bring forward a maximum number of three recommended results after the selection of a document. Documents A through T are ranked from 1 to 20, with the first ten results (documents A through J) being on the first page of search results. At the moment the user selects Document E, which was initially ranked #5, the re-ranking engine calculates the new ranks. Since documents A through J have already been seen by the user, at the moment the user returns to the search results page these documents will remain present in the same order, however, the adaptive UI will bring forward up to three recommended search results from subsequent pages which, in this example, is only the second page. The new ranking indicates that documents M and Q are relevant to the user based on the real-time user model, so they are brought to the first page of results as recommendations. Document T, however, is not since there are still documents on the first page of results (documents H and I) that are more relevant, based on the new ranking, than document T.

TABLE IExample of using recommended result relative quality in thedetermination of the number of recommended search results to displayInitialNewRankRankDocumentNotes113Document ASkipped216Document BSkipped310Document CSkipped47Document DSkipped51Document ESelected document68Document F718Document G84Document H95Document I1020Document J1112Document K1211Document L132Document M1^strecommended result1414Document N1515Document O169Document P173Document Q2^ndrecommended result1819Document R1917Document S206Document TNot brought forward

In some situations a result may be brought forward as a recommended result even if there is a more highly ranked document already on the page. For example, using Table I, should document H have had a new rank of #3 and document Q have had a new rank of #4, the adaptive UI could have still brought forward document Q because, subsequent to the re-ranking, the three most relevant results, not including the selected document, would have been, respectively, documents M, H (already on the first page) and Q. In another embodiment of the invention, the skipped results are not considered when determining how many results to bring forward as, in spite of the fact they might have a high relevance as determined by the real-time user model, they have already been viewed and passed over by the user.

In one embodiment of the invention the top re-ranked documents are pulled forward to the current search results page as recommendations, however, in another embodiment the adaptive UI modifies this slightly by selecting a diverse set of re-ranked documents in order to maximize the likelihood of presenting something relevant to the user. Should the re-ranking engine determine that there are multiple possible sub-contexts for the user's intent, represented as subordinate keywords with significant positive weights or multiple clusters associated with the selected documents, the invention may pull forward the top re-ranked document from each of these sub-contexts (the determination, weighting and use of subordinate keywords is described in detail in the Related Applications described and incorporated by reference above). For example, in FIG. 2D at the moment the user selects the result â€œGeorge Washington Universityâ€ 263, the real-time user model could produce three recommendations 270-272 using the highly-weighted subordinate keywords â€œGeorgeâ€ and â€œUniversityâ€ while attempting to have each recommendation correspond to different sub-context, such as â€œlaw school,â€ â€œmedical centerâ€ and â€œathletics.â€ Even if the top three re-ranked results were all related to the George Washington University Law School, presented results from other sub-contexts enhances the chances that at least one of the recommended search results will correspond to the user's information need.

The benefit of maintaining the results that have already been viewed by the user, in the original order, and then bringing forward re-ranked documents as recommended search results, is that the experience is less jarring to the user. Removing results that have already been seen, even if they haven't been selected, or changing the order of results that have already been displayed on the search results page can be confusing and potentially disconcerting to the user. Before selecting a document, users will often retain a visual image of the search results page, which they expect to remain somewhat consistent upon returning to the search results page. By maintaining the relative positions of the documents that have already been seen while inserting re-ranked documents, users can benefit from the improved relevance without having their search experience excessively disrupted.

Subsequent pages of results are calculated using the real-time user model at the moment the user selects â€œNextâ€ or â€œMore results.â€ All of the documents that have not yet been displayed to the user, either as the original set of results or recommended search results, will be re-ranked before the adaptive UI presents the top re-ranked documents as the next page of results. Once this new page is displayed, however, those documents are considered â€œseenâ€ and the re-ranking process, with new documents brought forward as recommendations following each user action, proceeds as described above. In another embodiment, much as recommendations may be selected to present a diversity of sub-contexts to the user, as described above, re-ranked documents for subsequent pages of results may also be chosen to present a diversity of sub-contexts to the user.

FIG. 2E represents one embodiment of the invention where re-ranked documents, presented as recommended search results, are nested. In this example, after selecting the document â€œGeorge Washington Universityâ€ 281 and being presented with three recommendations 285-287, the user proceeds by selecting the document â€œGeorge Washington Universityâ€”Official Athletic Siteâ€ 287 and is immediately presented with two additional recommendations 290-291. These two new recommendations are based on the real-time user model of inferred intent built from the knowledge that the user has selected â€œGeorge Washington Universityâ€ and â€œGeorge Washington Universityâ€”Official Athletic Siteâ€ as well as skipped over a number of other documents as well as some recommended search results. In this particular example it may be inferred that, while the user's query was for â€œWashington,â€ the intent is more specific to athletic programs at the University of Washington. As a consequence, the two nested recommended search results pertain to such. In one embodiment, the number of recommended result objects in each nest level is enough to provide the user a selection, but not so many as to affect the perception that the user is looking at the same page. In one embodiment, between 3 and 5 objects are provided in each nest level.

Should the user then move forward by selecting the document â€œGeorge Washington University Law Schoolâ€ 285, the real-time user model will be employed to determine a new ranking for all of the documents and the adaptive UI will insert any new recommended results directly under the document the was just selected 285. The real-time user model will take into account all of the user's actions during the current information session and, as such, the recommended results produced will be based on all the previously selected and skipped documents.

In one embodiment of the invention, a decay is used to adjust the weights of positive and negative subordinate keywords as the search is progressing. After each user action, just prior to updating the real-time user model, all of the subordinate keywords may be multiplied by some scaling factor, such as 90%. This will have the benefit of providing slightly more weight to the most recent user actions, which, during relatively long information sessions, will have the benefit of producing new rankings that compensate for any slight changes or drifts in user intent. Long information sessions often involve a learning process on the part of the user which could have an impact on the real-time model of inferred intent.

In one embodiment of the invention, the adaptive UI offers a control, in the form of a link or a button, to enable the user to clear or reset the real-time user model and recommence with the query. This could be particularly useful should the user experience and recognize a significant shift in information need while the search is taking place. Since the real-time user model incorporates all of the user's previous actions in the information session, a significant shift in intent could cause the re-ranking engine to produce results that are potentially no longer relevant. Even if the embodiment includes a â€œdecayâ€ as described above, a control somewhere on the search results page, such as a link called â€œreset recommendationsâ€ or â€œclear user model,â€ could be beneficial to the user in this circumstance.

FIG. 3 depicts how the invention may add an element to each document in order to provide greater control to the user. In one embodiment, small links, icons or other graphical elements, depicted here as a small image of a bull's eye, are associated with each search result. Selecting one of these icons, by virtue of a click for example, will immediately invoke the re-ranking engine in order to produce recommendations as if the user had selected the associated result. While the re-ranking engine will not be able to associate a dwell time with the selection of an icon, because the document is not actually selected to be opened, this action will enable the user to express a certain interest in a particular result in order to be immediately presented with appropriate recommendations based on that interest.

The invention may be configured so that recommendations are displayed when the user selects a result, when the user selects an icon associated with a result, or in just one instance but not the other. The invention may also be configured so that recommendations are never displayed and, as such, re-ranked documents only appear on subsequent pages of results. In another embodiment of the invention, selecting the icon will always produce at least one recommended result, regardless of the quality of that recommendation relative to the other documents that are already on the page. Having the icon â€œforceâ€ at least one recommendation will be a positive indication to the user that the adaptive UI is currently functional.

In one embodiment of the invention, if there are already recommendations associated with a particular result, a click on the icon will remove those recommendations and any nested recommendations. Subsequent clicks on the icon will alternately open and close any recommendations and nested recommendations. This functionality will enable users to easily remove unwanted recommendations from the result page and then bring them back should they so desire.

In one embodiment of the invention, with respect to updating the real-time user to model to calculate new ranks for the documents, the re-ranking engine considers the action of selecting an icon as separate from actually selecting the document to be opened. The amount of weight applied to the modifications that are subsequently made to the real-time user model of inferred intent can thus be adjusted. For example, clicking an icon could be considered a weaker indicator of intent when compared to actually selecting the document to be opened and, as such, modifications to the subordinate keyword weights will be scaled down appropriately. Should the user subsequently proceed to click the result in order to view the document, modifications to the subordinate keywords weights may be scaled back up to full strength.

Selecting the icon to remove recommendations can be considered an indication of negative intent and such an action is similarly incorporated into the real-time user model. In one embodiment, recommendations that are removed from the page by virtue of selecting an icon are treated as if they had been â€œskippedâ€ for purposes of the re-ranking engine. In another embodiment, removing recommendations is a stronger indication of intent than simply skipping a result and, as such, any modifications to the subordinate keyword weights are given additional negative influence.

In one embodiment of the invention, movement indicators are also present next to each recommendation, giving the user an indication of the page or location from where the recommendations were pulled. In the example, the document â€œGeorge Washington University Law Schoolâ€ 306 was pulled forward â€œfrom page 2.â€ This is an indication that the document, now presented as a recommended search result, was initially ranked on page 2 at the time the query was submitted. In another embodiment this movement indicator could be the initial rank of the document, such as â€œ#25â€ . In another embodiment, all of the results on subsequent search results pages also include movement indicators, as they too have had their positions altered from the moment the query was initially submitted.

Clustering and query suggestions are a well-understood practice for search engines and many offer both to their users. There are many ways to produce clusters or query suggestions, but typically they revolve around analyzing the various sub-contexts in the result set to offer possible refinements to the user. For example, looking at the result set for the query â€œWashington,â€ a search engine might propose the following clusters: University of Washington, Washington State, Washington Capitals, Washington Politics, Washington Government, Washington D.C., etc. It's also possible for clusters to be nested within each other. Some search engines also produce query suggestions by looking at refinements produced by previous users who've entered the same query. For example, should the search engine see that many users who query for â€œWashingtonâ€ then proceed to query for â€œUniversity of Washington,â€ the latter could be offered as a query suggestion to users searching for the former. The location on the search results page where the clusters and query suggestions are presented can vary, although they're typically either at the top or bottom, or off to the side in a vertical side bar.

One embodiment of the present invention exploits the real-time user model of inferred intent to produce a list of more highly targeted clusters or query suggestions. For example, at the moment the user selects â€œGeorge Washington Universityâ€ 303 to produce recommendations 306-308, the real-time user model has already inferred that the intent is related to â€œuniversity.â€ As such, the adaptive UI can suggest real-time clusters 315, such as â€œuniversityâ€ and â€œschool,â€ while simultaneously eliminating clusters that are not related to the user's information need, such as â€œmonumentâ€ or â€œpresident.â€ In one embodiment, selecting one of these cluster links will rerun the user's query using the cluster information. For example, clicking â€œuniversityâ€ will run a new query for â€œWashington University.â€ In another embodiment, selecting one of these links will simply take the subset of documents from the original result set that belong to that particular cluster. It is a not a requirement for the real-time clusters to appear above the recommendations. In other embodiments of the invention they may appear anywhere on the search results page. In the case of a query reformulation, where the real-time user model is carried over from a previous query, it would make sense to put the real-time clusters either at the top of bottom of the search results page.

In another embodiment of the invention, clusters are calculated using the set of produced documents at the moment the user submits the query. There exists many techniques for calculating such clusters, but each document should consequently belong to one or more clusters. At the moment the user selects a document, the real-time clusters may be a function of real-time user model as well as the clusters to which the document originally belonged. Additional document selections will further enable the adaptive UI to determine the clusters that are most appropriate to the user by observing the frequency with which selected documents appear in each of the calculated clusters. In another embodiment of the invention, the set of available clusters is recalculated using a subset of the documents in the result set. This subset is selected based on the real-time user model. For example, after each user action the set of available clusters could be recalculated using the top 50 re-ranked documents. This technique will enable the clusters to follow the evolution of the real-time user model.

Real-time clusters can be presented to the user every time there is an update to the real-time user model, which typically occurs when the user selects a document or moves to a subsequent page of results. The real-time clusters take advantage of the cumulative nature of the real-time user model. For example, after selecting â€œGeorge Washington Universityâ€ 303, should the user continue by selecting â€œGeorge Washington Universityâ€”Official Athletic Siteâ€ 308, the adaptive UI can present clusters 316 based on both of these actions, such as â€œuniversity athleticsâ€ and â€œathletics storeâ€ . Real-time cluster and query suggestion links may also be shown immediately upon displaying a subsequent page of results.

The practical advantage of real-time clusters or query suggestions is that they are targeted to the user's real-time intent. Traditionally clusters and query suggestions have been unable to exploit the information present in a real-time user model of inferred intent and, as such, rely on providing a wide range of clusters related to the entire document set, or alternatively the reformulations from users who previously submitted a similar query. This inevitably requires the user to wade through a considerable number of options, which requires time and energy. Conversely, real-time clusters, by virtue of being based off the real-time user model, are more targeted to the user's intent and are typically fewer in number.

The adaptive UI of the present invention can similarly be used to deliver more highly-targeted advertisements. The selection of advertisements can, however, be somewhat different from the re-ranking of organic results. Search engines will typically display advertisements based on a combination of RPC (revenue per click, which is the amount of money the advertiser is willing to pay for a click on a given sponsored link) and CTR (click-through rate, or the rate at which users selected a given sponsored link). The RPC and CTR together are used to maximize the amount of revenue generated for a given user's query by producing a ranked list of available sponsored links.

In one embodiment of the invention, the real-time user model is used to re-rank sponsored links in the same manner that is used to re-rank organic results. The subordinate keywords are matched with the titles, snippets and URLs of the available sponsored links for a given query, and the order of the sponsored links is changed.

To illustrate how this might work, Table II is a representation of sponsored links returned for a user's query for â€œdigital camera.â€ The RPC represents the amount of money that the advertiser is willing to pay for a click while the CTR represents the rate at which users click the advertisement when it is displayed on the search page. The CTR will most certainly be a function of where the advertisement is displayed in relation to the others, but for purposes of this illustration consider the CTR to be normalized.

TABLE IIExample of sponsored advertisements for the user's query â€œdigitalcameraâ€ ranked by the search engine as a function of, amongother things, RPC and CTRRankRPCCTRSponsored Advertisement1$0.502.0%Digital CameraFind Brand Name Digital Cameras at Pricesyou'll Love. Shop Kmart Now!www.Kmart.com2$0.501.9%Best Buyâ€‰Â® Official Site5%-16% Off Select Digital Cameras ThisWeek At Best Buyâ€‰Â®. Shop Now!www.BestBuy.com3$0.551.7%Sonyâ€‰Â® Digital CamerasOfficial Site: Sony Cyber-shotâ€‰Â®Digital Cameras starting at $129.99www.SonyStyle.com/cybershot4$0.551.6%New Digital Camera-TL100Slim Design with Smart Auto.12.2 Megapixels, 2.7â€³ LCD & Morewww.samsung.com/us/tl1005$0.452.0%Digital CameraBrowse New Digital Cameras at Dell.Compare Brands and Megapixels Here!www.Dell.com6$0.402.1%Digital Cameras on SaleFree Shipping & No Tax. AuthorizedDealer. 24/7 Customer Support!RitzCamera.com7$0.351.8%Limited Time Camera DealsSave $100 Instantly on DigitalCameras Only at OfficeMax-Buy Now!www.OfficeMax.com8$0.351.6%Digital Cameras $9.95Sale-Bargain-All BrandsQuantity Discounts-Free Shipwww.EcaMeraFilms.com9$0.301.8%Digital CameraCompare Price and Features.Large Selection In Stock Today.www.Staples.com10$0.251.7%Digital Camera BargainsSave on Every SLR, Standard Point &Shoot and Compact Digital Camera.www.NexTag.com/Digital-Cameras

As can be seen, the advertisements are produced in a certain order which can be a function of many different things, but typically will rely heavily on RPC and CTR. This is because the objective of the search engine is to put the advertisements in an order that will generate the greatest amount of revenue, which is a function of how often an advertisement is clicked multiplied by the amount of revenue generated by each click. That is why advertisements with higher RPCs will sometimes be ranked beneath those with lower RPCs. For example, in Table II the advertisement for â€œSonyÂ® Digital Camerasâ€ is ranked below the advertisement for â€œBest BuyÂ® Official Siteâ€ even though it has a higher RPC. This is because the CTR for the â€œSonyÂ® Digital Camerasâ€ is lower, meaning that in aggregate it'll generate less revenue for that query.

How these advertisements are displayed is then up to the search engine. In many cases they'll be displayed in a column, in descending order, to the right-hand side of the organic results. Typically only a maximum number of advertisements will be displayed, depending, among other things, on the user's query. In some instances the search engine will decide to take a number of the top advertisements and display them either above or below the organic results. Additionally, there are search engines that will mix the advertisements in with the organic results. In most cases, however, the search engine will indicate which results are sponsored by either putting them in a colored box or indication as such with text.

Should a real-time model of the user's intent be available, which is the case when a user has already taken an action during the current information session, then the adaptive UI can exploit this to produce a superior ranking of advertisements. The real-time model of user intent can come from clicks on either organic or sponsored links during the current query or previous queries in the same information session.

Continuing with the current illustration, assume that the real-time user model contains the following subordinate keywords with significant positive weights: sale, save, discount and bargain. Assume as well that the real-time user model also contains the following subordinate keywords with significant negative weights: sony and new. As described above, these subordinate keywords may have been produced by virtue of the user selecting documents or advertisements related to â€œdigital camera salesâ€ while skipping results related to â€œnew digital cameras by Sony.â€

Table III represents how the order of the ads might be changed based on the real-time user model. The ranks of advertisements related to the positive subordinate keywords are improved while the ranks of those ads related to the negative subordinate keywords are reduced. The objective here is still to maximize revenue for the search engine, however, while RPC and CTR information can be taken into account, advertisements that might otherwise have be ranked low are brought forward because they are more closely aligned with the user's real-time information need as indicated by the real-time user model of inferred intent.

TABLE IIIExample of sponsored advertisements for the user's query â€œdigitalcameraâ€ re-ranked by the real-time user model - for ease ofunderstanding, positive subordinate keywords are represented inbold while negative subordinate keywords are in italicNewRankOld RankRPCCTRSponsored Advertisement16$0.402.1%Digital Cameras on SaleFree Shipping & No Tax. AuthorizedDealer. 24/7 Customer Support!RitzCamera.com28$0.351.6%Digital Cameras $9.95Sale-Bargain - All BrandsQuantity Discounts- Free Shipwww.EcaMeraFilms.com37$0.351.8%Limited Time Camera DealsSave $100 Instantly on DigitalCameras Only at OfficeMax-Buy Now!www.OfficeMax.com41$0.502.0%Digital CameraFind Brand Name Digital Cameras atPrices you'll Love. Shop Kmart Now!www.Kmart.com510$0.251.7%Digital Camera BargainsSave on Every SLR, Standard Point &Shoot and Compact Digital Camera.www.NexTag.com/Digital-Cameras62$0.501.9%Best Buyâ€‰Â® Official Site5%-16% Off Select Digital CamerasThis Week At Best Buyâ€‰Â®. Shop Now!www.BestBuy.com75$0.452.0%Digital CameraBrowse New Digital Cameras at Dell.Compare Brands and Megapixels Here!www.Dell.com83$0.551.7%Sonyâ€‰Â® Digital CamerasOfficial Site: Sony Cyber-shotâ€‰Â®Digital Cameras starting at $129.99www.SonyStyle.com/cybershot94$0.551.6%New Digital Camera-TL100Slim Design with Smart Auto.12.2 Megapixels, 2.7â€³ LCD & Morewww.samsung.com/us/tl100109$0.301.8%Digital CameraCompare Price and Features.Large Selection In Stock Today.www.Staples.com

In another embodiment of the invention, highly weighted subordinate keywords or real-time clusters from the real-time user model are used to enhance the user's query in order to identify additional potentially relevant sponsored links. This is particularly useful when the set of sponsored advertisements for a given query is small, or when the user's real-time intent, as described by the real-time user model, varies considerably from the original query.

To illustrate this point, consider a real-time user model where the term â€œbargainâ€ has a significantly high positive weight, or where â€œbargainâ€ represents a real-time cluster of significant weight. Table IV is then an example of sponsored advertisements associated with the user query â€œdigital camera bargain.â€ These sponsored advertisements are ranked by the search engine in a manner similar to the sponsored advertisements in Table II.

TABLE IVExample of sponsored advertisements for the user's query â€œdigitalcamera bargainâ€ ranked by the search engine as a function of,among other things, RPC and CTRRankRPCCTRSponsored Advertisement1$0.752.2%Digital Camera BargainWe Have 800+ Digital Cameras. DigitalCamera Bargain on Sale!www.NexTag.com/Digital-Cameras2$0.501.8%Affordable CamerasFind A Wide Selection Of AffordableCameras At Best Buyâ€‰Â®. Shop Now!www.bestbuy.com3$0.451.7%Digital Cameras CheapBrowse for Point & Shoot DigitalCameras from our Secured Merchants.Become. com4$0.301.6%Save on Digital CamerasLow Low Prices on Brand NamesSame Day Shipping, Buy Now!www.TigerDirect.com5$0.252.0%Digital Camera StoreCanon, Nikon, Sony, Olympus & More!Authorized Dealer-Paypal Acceptedwww.JR.com/Digital_Cameras

The adaptive UI of the present invention may subsequently enhance the list of sponsored advertisements from Table II by methodically inserting those from Table IV. The challenge is that while there is a ranking of advertisements for the user's query â€œdigital cameraâ€ and another ranking of advertisements for the user's query â€œdigital camera bargain,â€ there is no combined ranking of the two sets of advertisements.

In one embodiment of the invention, the two lists are combined as a function of RPC and CTR and then re-ranked using the real-time user model. For the example, first the advertisements of Table IV are added to the advertisements of Table II similar to if all of the advertisements had been related to the initial user query. Then the real-time user model is used to re-rank the advertisements in the same manner as Table III. Table V is a representation of the re-ranked ads from Tables II and IV. In can be noted that in this particular example that the top advertisement, â€œDigital Camera Bargain,â€ wasn't even present in the set of advertisements for the user's original query.

TABLE VExample of sponsored advertisements for the user's query â€œdigitalcameraâ€ re-ranked and then enhanced by sponsored advertisementsfrom a user's query for â€œdigital camera bargainâ€ NewRankOld RankRPCCTRSponsored Advertisement1Table$0.752.2%Digital Camera BargainIV-1We Have 800+ Digital Cameras. DigitalCamera Bargain on Sale!www.NexTag.com/Digital-Cameras2Table II-6$0.402.1%Digital Cameras on SaleFree Shipping & No Tax. AuthorizedDealer. 24/7 Customer Support!RitzCamera.com3Table$0.501.8%Affordable CamerasIV-2Find A Wide Selection Of AffordableCameras At Best Buyâ€‰Â®. Shop Now!www.bestbuy.com4Table$0.301.6%Save on Digital CamerasIV-4Low Low Prices on Brand NamesSame Day Shipping, Buy Now!www.TigerDirect.com5Table II-8$0.351.6%Digital Cameras $9.95Sale-Bargain-All BrandsQuantity Discounts-Free Shipwww.EcaMeraFilms.com6Table 11-7$0.351.8%Limited Time Camera DealsSave $100 Instantly on DigitalCameras Only at OfficeMax-Buy Now!www.OfficeMax.com7Table$0.451.7%Digital Cameras CheapIV-3Browse for Point & Shoot DigitalCameras from our Secured Merchants.Become.com8Table II-1$0.502.0%Digital CameraFind Brand Name Digital Cameras atPrices you'll Love. Shop Kmart Now!www.Kmart.com9Table$0.251.7%Digital Camera BargainsII-10Save on Every SLR, Standard Point &Shoot and Compact Digital Camera.www.NexTag.com/Digital-Cameras10Table II-2$0.501.9%Best Buyâ€‰Â® Official Site5%-16% Off Select Digital CamerasThis Week At Best Buyâ€‰Â®. Shop Now!www.BestBuy.com

In the most commonly used search engines, the sponsored links are separate from the organic results. They are typically displayed in a column to the right of the organic results. However, the most attractive ads can be placed either above or below the organic results. In one embodiment of the invention, as soon as a new ranking of advertisements is available, the old set is removed and simply replaced with the new set. While simple to implement from a UI perspective, the disadvantage of this method is that the old advertisement are no longer available to the user, which could cause frustration.

In another embodiment, the adaptive UI makes the advertisements operate in a similar fashion to the organic results. When either an organic or sponsored result is selected, recommended sponsored links are immediately presented on the search results page, however, the old advertisement are not removed. The recommended sponsored links may be presented either above or below the original sponsored links, or inserted into the list of sponsored links in a fashion similar to the insertion of recommended organic results into the list of organic search documents.

When a subsequent page of results is produced, however, there is an opportunity to display an entirely new set of advertisements based on the real-time user model. In one embodiment of the invention, at the moment the user selects â€œnextâ€ or â€œmore results,â€ the real-time user model is updated, the sponsored links are immediately re-ranked and selected as described above, and then the top recommended sponsored links are displayed on the new page of results in a fashion similar to the display of the original sponsored links on the first page of search results.

In another embodiment of the invention, during a query reformulation that is part of the same information session, the adaptive UI uses the real-time user model to produce a re-ranked set of sponsored links at the moment the new query is submitted. For example, should the user's first query be â€œdigital cameraâ€ and the reformulation be â€œdigital camera slr,â€ then once it is determined that both of these queries belong to the same information session, the real-time user model is carried over to the new query and can used to select new advertisements. Should â€œcanonâ€ have been a highly weighted subordinate keyword, re-ranked advertisements for â€œcanon digital slr camerasâ€ might be selected to appear on the search results page.

In search engines where the sponsored results are mixed in with the organic results, the adaptive UI may simply re-rank the combined result set, as described above, as if all the results were organic. In this scenario, in order to maximize the revenue generated from the query, preference may be given to the sponsored results during the re-ranking process.

The outcome is an adaptive UI for a search engine that harnesses the power of a real-time user model to continuously change, update and reorganize search results and sponsored links based upon the â€œat the momentâ€ intent of the user as deduced from the ongoing behavior of the user during the search process.

The user's browser may be installed on other devices than a computer, such as a personal digital assistant (PDA), a mobile phone, TV, or any other device. The display can be modified to fit a smaller form factor.

As will be understood by those of skill in the art, the present invention could be embodied in other specific forms without departing from the essential characteristics thereof The present invention can use a separate third party search engine, or could be integrated with a search engine. The search engine could be a general search engine that searches the internet, a specialized search engine that searches a particular web site, a database search engine, a meta-search engine that combines the results of multiple other search engines, or any other type of search engine. Accordingly the foregoing description is intended to be illustrative, but not limiting, of the scope of the invention which is set forth in the following claims.