HK1179707B

HK1179707B - Proposing alternative queries prior to completion of search query

Info

Publication number: HK1179707B
Application number: HK13106679.0A
Authority: HK
Inventors: 理查德．卡斯佩尔斯基; 阿尔卡德．博尔科夫斯基; 拉尔夫．拉巴特
Original assignee: Jollify Management Limited
Priority date: 2005-08-24
Filing date: 2013-06-05
Publication date: 2017-09-08

Description

Proposing alternative queries prior to completion of a search query

This application is a divisional application entitled "alternative queries made before completion of a search query" with application number 200680030930.5, application date 2006, 8/15.

Technical Field

The present invention relates to search engines, and more particularly to providing alternative search queries for predicted search queries.

Background

A search engine is a computer program that helps a user locate information. Using a search engine, a user may enter one or more search query terms and obtain a list of resources that contain or are related to topics that match the search query terms. While search engines are applicable in a variety of environments, search engines are particularly effective for locating resources accessible through the internet. For example, resources that may be located by a search engine include files whose content is composed of a page description language such as hypertext markup language (HTML). Such files are commonly referred to as pages. A user may use a search engine to generate a list of Uniform Resource Locators (URLs) and/or HTML links for documents or pages that may be of interest.

Search engines typically have an interface that allows a user to specify search criteria and an interface that displays search results. Typically, a search engine will rank the search results before presenting the search results interface to the user. This ranking is typically in the form of a "rank", where the documents with the highest rank are those deemed most likely to satisfy the topic of interest reflected by the user-specified search criteria. One (or more) search results pages based on the rank are sent to the user. However, the user still has to spend considerable time and effort processing the search results to determine whether the search query produces sufficient search results. If the user is not satisfied with the results, the user forms a new search query and repeats the process.

Thus, the search process is typically a repetitive task, i.e., the user forms a search query, determines whether a large search result is sufficient, and then, if necessary, reformulates the search query. Thus, the user's experience with a search engine is often frustrating and time consuming.

The approaches described in this section are approaches that could be pursued, rather than the required approaches that have been previously conceived or pursued. Accordingly, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.

Disclosure of Invention

According to one aspect of the present invention, there is provided a computer-implemented method of providing speculative search results, comprising: receiving a search query from a client node, wherein the search query has not been submitted; determining speculative search results for the not yet submitted search query prior to receiving an indication from the client node that the not yet submitted search query is fully formed; and providing the speculative search results to the client node, wherein the speculative search results identify at least one entry that satisfies the search query that has not yet been submitted.

Drawings

The present invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which:

1A, 1B, 1C, and 1D illustrate graphical user interfaces for providing speculative search results according to embodiments of the present invention;

FIG. 2 is a flow diagram illustrating a technique for providing speculative search results for a search query according to an embodiment of the invention;

FIG. 3 is a flow diagram illustrating a technique for determining relevant speculative search results, according to an embodiment of the invention;

FIGS. 4 and 5 illustrate various types of speculative search results provided by embodiments of the present invention;

FIG. 6 illustrates a user interface displaying a predicted query and search results for a most likely predicted query based on input entered in a query field, according to one embodiment of the invention;

FIG. 7 is a flow diagram illustrating how to determine which potential queries will be predictive queries sent to a user by considering temporal relevance, according to one embodiment of the invention;

FIG. 8A is a block diagram illustrating communication between a web browser of a client and a front-end server according to one embodiment of the invention;

FIG. 8B is a block diagram illustrating communication between a web browser of a client and a front-end server according to another embodiment of the present invention;

FIG. 8C is a block diagram illustrating communication between a web browser of a client and a front-end server according to another embodiment of the present invention;

FIG. 9 illustrates an exemplary user interface for displaying alternative terms of a predicted search query according to an embodiment of the present invention;

FIG. 10 is a flowchart illustrating the process steps of determining alternative terms for a predicted search query according to an embodiment of the present invention;

11A, 11B, and 11C are diagrams illustrating user interfaces displaying a predicted search query and an alternative search query, according to embodiments of the invention; and

FIG. 12 is a block diagram that illustrates a computer system upon which the present invention may be implemented.

Detailed Description

In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It may be evident, however, that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention.

Overview of speculative search results

Generally, when forming a search of the world Wide Web or the like, a user will form a search query and then enter a carriage return or click on a "search button" to initiate a search request based on the search query. The act of initiating a search request is also used to indicate that the search query is "submitted". The search query is "not submitted" before the act of initiating a search. Embodiments of the present invention perform a search based on an uncommitted search query and provide speculative search results before a user explicitly initiates a search request.

Techniques are described herein for providing speculative search results for a search query before the search query ends. According to one embodiment, in response to receiving an uncommitted search query from a client node, speculative search results are provided for the client node for the uncommitted search query prior to receiving an indication from the client node that the search query is fully formed. The speculative search results may be displayed on the same web page on the client node as the uncommitted search query, while the search query is still entered by the user. As the user continues to form search queries, new speculative search results may be provided to the user.

The search request and search results may belong to the world Wide Web; however, the techniques described herein are not so limited. More generally, the search request and results may pertain to any searchable data in any format. For example, the data may be a user address book, a stored link, a personal storage image (e.g., a jpeg file, gif file, etc.), video, audio (. mp3 file, wmv file, etc.), associated cards (e.g., v-card), calendar objects, word processing documents, graphics files, or computer code (object files and source code).

Speculative search initiation criteria

To limit the frequency with which new speculative search results are provided during an input search query, it may be determined whether an uncommitted search query meets criteria for initiating a search. This criterion is referred to herein as "speculative search initiation criteria". The speculative search initiation criteria may be designed to qualify speculative search results as highly relevant results. For example, the criteria may be that the user has entered a complete word in an uncommitted search query.

Speculative search initiation criteria may be used to ensure that a user is not burdened with frequently changing search results when forming a search query. Furthermore, the requirement that speculative search initiation criteria be met helps to ensure that the search engine is not burdened with search requests. Additionally, not performing a search until speculative search start criteria are met may increase the likelihood that speculative search results have sufficient relevance to ensure that they are returned to the user. For example, speculative search results that form words based on certain portions may have low relevance. However, there are situations where speculative search results based on partially formed words may be highly relevant. Various techniques are provided to determine which partial search queries (whether partial words or not) are likely to produce relevant speculative search results.

One technique for determining whether an uncommitted search query meets the criteria for initiating a search, and thus is properly formulated, is to calculate the time since the user last entered a character in the search request. If the timer has expired, a search is initiated. The period of the timer may be dynamically adjusted to suit the user. For example, if the user types quickly, a search may be initiated infrequently. Alternatively, if the user types slowly, the search may be initiated frequently.

Another technique for determining whether an uncommitted search query meets speculative search initiation criteria is to determine whether a given character is included in the search query. For example, if a user enters an interval symbol, it is likely that the user has completed a word in which a search query may be well formed to initiate a search. As used herein, a "word" can be either a word in a natural language (e.g., english) or a special symbol, such as an abbreviation, acronym, product code, URL, or the like.

Another technique for determining whether an uncommitted search query is well formed to initiate a search is to determine whether the search query matches or nearly matches a phrase in a dictionary that includes predefined phrases. The predefined phrases may be phrases of possible word combinations in the search request. In one embodiment, the dictionary is based on popular queries. In one embodiment, a dictionary is used to limit the number of search requests as a condition for performing a search, wherein a search query is performed by determining whether an uncommitted search query matches or approximately matches a term or phrase in the dictionary.

Determining whether a search is well formed with respect to an uncommitted search query to initiate a search is not limited to the techniques described herein. Further, any combination of the foregoing techniques may be used for the determination. The determination may also be made at the client node, although this is not a requirement. In one embodiment, the client node has an AJAX (asynchronous JavaScript + XML) engine to facilitate determining whether to communicate an uncommitted search query to a search engine. The client node may make the determination by other techniques. In another embodiment, whether to initiate a search is determined at a node other than the client (e.g., a search engine).

Correlation threshold

After the speculative search initiation criteria have been met, predefined search rules are applied to provide the user with one or some highly relevant speculative search results, which may be displayed on the same web page as the uncommitted search query. For example, the predefined rules may include performing a first search that may produce highly relevant speculative search results. If the first search does not produce speculative search results that meet a particular relevance threshold, the search results are not presented to the user. A second search is performed instead. The second search is performed based on a current state of the uncommitted search query, where the state may be different from a state of the uncommitted search query based on which the first search was performed. If the results of the second search do not meet the relevancy threshold, the results of the second search are not presented to the user. Repeated search processing based on the uncommitted search query may continue until the search query is submitted. Until the search query is submitted, only the speculative search results will be presented to the user when those results meet the relevance threshold.

Different searches may use different search techniques and/or may search different databases. This use of a rank search and relevance threshold provides the user with highly relevant results and avoids overloading the user with results, since results are not returned to the user if the inferred search result relevance or other criteria is deemed too low.

Example of speculative search during query formation

FIGS. 1A, 1B, 1C, and 1D illustrate a graphical user interface 100 for providing speculative search results, according to an embodiment of the invention. The sequence of FIGS. 1A-1D illustrates that as the user continues to further enter search queries, the speculative search results are updated with relevant search results. Techniques for determining when to initiate a new speculative search are described herein.

In FIG. 1A, a user has entered a search query 101A "sun" in a search box 102. The user has not entered an indication that the search query is complete. Thus, the text "sun" constitutes an uncommitted search query. For example, the user has not clicked the "Search the web" button 104 or entered enter to automatically trigger a Search. However, the uncommitted search query 101a is communicated to a search engine, which provides speculative search results 106a based on the uncommitted search query 101 a. In this case, the speculative search result 106a has a hypertext link that provides a Uniform Resource Locator (URL).

The speculative search result 106a is a search result that is determined to have sufficient relevance to benefit from being provided to the user. For example, it is undesirable for the user to be confused with results having a low degree of correlation. Embodiments of the present invention provide a variety of techniques for determining which speculative search results have sufficient relevance to benefit return to a user. Prior to completing search query 101a, the user may click on hypertext link 106a in speculative search result 106a, if desired.

The speculative search results 106a may be updated as the user further enters the search query. FIG. 1B shows the graphical user interface 100 where the user is entering an uncommitted search query 101B, "sunnn". Speculative search results 106b have been provided for the uncommitted search query 101b "sunnn". Accordingly, the speculative search results 106b have been updated based on the updated search query 101 b. In this case, the speculative search results 106b comprise an organized collection of information about the "sunnn" inventory of the uncommitted search query 101 b.

It is not necessary to update the speculative search results each time a user enters a new character in the search query 101. Referring now to FIG. 1C, the uncommitted search query 101C is now "Sunnyvale". Based on the text "Sunnyvale," a new speculative search result 106c is provided for Sunnyvale, Calif. Note that for search queries such as "sunnyv," there is no need to update the speculative search results. Thus, while speculative search results may be provided for the term "sunnyv," embodiments of the present invention determine that such speculative search results should not be provided to a user. Techniques for making such determinations are described herein.

Referring now to FIG. 1D, the search query 101D is now "Sunnyvale weather," where a new speculative search result 106D is provided for Sunnyvale weather, Calif. In this case, the speculative search result 106d includes a link 112 to a weather website and a summary 114 that provides a weather profile of Sunnyvale, Calif.

Providing speculative search results

FIG. 2 is a flow diagram illustrating a process 200 for providing speculative search results to a search query, according to an embodiment of the invention. In block 202, an uncommitted search query is received. For example, an application executing on a client node receives an uncommitted search query entered by a user. The uncommitted search query may be transmitted to a search engine; although communicating the uncommitted search query to the search engine may occur later in process 200.

As used throughout this specification, an uncommitted search query refers to a search query that has not received an indication of completion of a search request, the search query entered through a user interface for entering the search query. For example, when forming a search of the world Wide Web or the like, a user typically enters an enter or clicks "search button" to initiate a search request, thereby indicating that the search query is complete.

In block 204, a determination is made that the uncommitted search query meets the speculative search initiation criteria. In block 206, a search is initiated when the speculative search initiation criteria are met. If a sufficiently good uncommitted search query has not been formed to satisfy the speculative search initiation criteria, process 200 returns to block 202 to receive additional input for the uncommitted search query.

In block 206, a search is performed on the uncommitted search query. The search may be performed in any convenient technique and may include several stages. An embodiment for performing a search is depicted in FIG. 3; however, the present invention is not limited to this technique. Any database may be searched. For example, a database having an index based on a substantial portion of the world Wide Web need not be searched. In one embodiment, at least a portion of the search is conducted against a database of information regarding which user is performing the search query. For example, a user's address book, calendar, etc. may be searched.

In block 208, the speculative search results are provided to the user. Exemplary speculative search results 106 are shown in FIGS. 1A-1D, 4, and 5. The speculative search results may be displayed on the same web page as the user entered the search query. The speculative search results may take many different forms, including, but not limited to, links to web pages, web pages themselves, graphics (e.g., interactive maps), and textual descriptions. Thus, a user may view the speculative search results and determine the relevance of the speculative search results before indicating completion of the search query. Typically, a limited set of results is displayed to the user so as not to overload the user's information. The search engine may transmit the entire web page to the client node, or just update information for the client node to integrate it into the web page currently stored at the client node. In one embodiment, the client node has an AJAX engine to facilitate data transfer between the client and the search engine, as well as to facilitate rendering of updated web pages.

If the user selects a speculative search result in block 210, then content regarding the speculative search result is provided in block 212. For example, if the user selects one of the links in the speculative search results 106 shown in FIGS. 1A-1D, the user may be provided with a web page for the selected link.

If the user makes an indication that the search query is complete, the user is provided with search results that can be returned to the conventional search. Accordingly, if an indication that the search query is complete is received in block 214, the completed search results are provided to the user in block 216. For example, if the user clicks a search button (fig. 1A, 104) or enters an enter, the client node transmits the completed search query to the search engine along with an indication or suggestion that the search query is complete. In response to a completed search query, the search engine provides completed search results, which may include, for example, a list of URLs having a brief description of the content associated with the URL. The completed search results may be provided on a separate web page from the search query web page.

If the user does not indicate that the search query is complete, process 200 returns to block 202 where additional input for the uncommitted search query is received. Process 200 continues and may end when the user selects one of the speculative search results for other information or indicates that the search query is complete.

Performing speculative searches

After a determination has been made to initiate a speculative search, and before the user has explicitly initiated a search request, predefined search rules are applied to provide the user with one or some highly relevant search results, which may be displayed on the same web page as the search query that is still being formed. FIG. 3 is a flow diagram illustrating a process 300 for determining to provide relevant speculative search results to a user, according to an embodiment of the invention. The process 300 provides the user with potentially relevant results and reduces the amount of wasted data by filtering out search results that are deemed less relevant. In block 302, an uncommitted search query is accessed. For example, a search engine accesses an uncommitted search query.

In block 304, a determination is made whether the search query triggered a predefined search result that may include an organized set of information about the search query. For example, based on analysis of many searches, a set of predefined search results is formed that include various links to the search query. As an example, speculative search results for the inventory shown in FIG. 1B are examples of search queries that produce predefined search results. Another example of predefined search results is shown in FIG. 5, where search results converted from U.S. dollars to yen are provided in response to the search query "convert 1 dongle to yen".

If the search query matches (or approximately matches) the predefined search results in block 304, the predefined search results are provided in block 306. For example, the web server transmits predefined search results to the client node, where execution of an application on the client node may display the results on the same web page as the search query being formed.

In block 308, the uncommitted search query is analyzed to determine whether it may be a search query to obtain a navigation link, such as a URL. For example, if a user is unsure of a URL, many users employ search queries to obtain the URL. By analyzing the uncommitted search query, a determination is made whether the search query is an attempt to locate a URL. In some cases, a user may type in a search query that is expected to be logically related to a URL; however, the actual URL is different than expected. Built-in intelligence can correct this situation so that the user is provided with the URL of a highly relevant website.

If it is determined in block 308 that the search query is available for navigation links, in block 310, the navigation links are provided to the user. For example, the search engine transmits the network link to the client node, where an application executing on the client node displays the navigation link on the same web page as the search query.

If the unsubmitted search query does not trigger a predefined search result or navigation link, then in block 312, a determination is made whether to provide a fallback (fallback) search result to the user. The relevance of potential backup results may be assessed before providing them to the user so that the user does not flood results with low relevance. In one embodiment of the invention, the lexicon is used to filter the search query prior to performing the backup search. Thus, if the search query does not match (or does not closely match) a term or phrase in the dictionary, process 300 proceeds to block 314 where a backup search is not performed. In one embodiment, the phrases in the lexicon are learned from a statistical analysis of the search.

If the test of block 312 determines that a backup search should be performed, then in block 316, one or more backup search results are selected to be provided to the user. The backup search results may include a web page title, a summary of one or more pages, and a Uniform Resource Locator (URL) for a page. The backup results may provide a single result (or a limited number of results) of a web search or a local web search. In addition, the search range may be adjusted to affect the desired relevance of the search results. Backup search results are described in more detail below.

Backup search results

A backup search may be defined as a group of common search results rather than providing rare search results with low relevance. For example, the results of the top 50,000 searches are tracked, wherein providing only backup search results for an uncommitted search query triggers one of the popular search results. Any convenient number of popular search results may be used. Thus, embodiments of the present invention avoid providing irrelevant search results to a user simply because a search based on an uncommitted search query triggers an ambiguous web page. The backup search results may be based on any set of user searches ranging from everyone using the search engine to only the user forming the current search query.

To simplify the user experience, a limited number of backup results are shown on the search query page. For example, in one embodiment, only a single result is provided to the user. Typically, the results of the searcher are in line with the degree of relevance. In one embodiment, the search result with the highest relevance is provided. Optionally, some results may be provided based on the analysis of the correlation. In one embodiment, a search result is only provided if its relevance exceeds a threshold. Multiple results may be provided if the distribution of the correlation between the first few results is very tight. The threshold may be dynamic. Regarding its relevance, a summary of the results may be shown to help guide the user.

The degree of correlation may be determined by various techniques. For example, the relevance score of a page may be based on how many words from a search query are contained in the page, and/or the frequency with which those words appear in the page. The page relevance score will also take into account certain "page quality metrics", such as reference indices, page resource copyrights, etc. Page relevance may also be defined to correspond to the user who submitted the query. For example, relevance can be based on the language used to submit the query (e.g., English or French). For another example, the relevance may be based on an attribute of the user (e.g., a geographic area, gender, or social group of the user). Thus, the page relevance score for a query submitted by a uk user may be determined differently than the page relevance score for the same query submitted by a us user.

Suggestions for improving search queries

To improve the quality of the search query, embodiments of the present invention suggest alternative spellings for the search query that are formed before the user indicates that the search query is complete. For example, a user may enter a preliminary search query that is determined to have a potential misspelling. According to embodiments of the present invention, the user is prompted with alternative spelling suggestions. Further, spelling suggestions are provided before the user indicates that the search query is complete. The user may click on a provided link associated with the spelling suggestion to automatically correct the spelling in the search box. Further, in response to the user clicking on a link related to the suggested spelling, a navigational link may be provided as a speculative search result.

In another embodiment, the user is prompted to attempt another search query based on an analysis of the uncommitted search query. While the user is still entering the search query, suggested alternative search queries are provided in response to the uncommitted search query.

In one embodiment, a history of user search requests is tracked and used to determine relevant search results. For example, if a user frequently visits a particular weather forecast, a link may be automatically provided upon entry by the user at the beginning of a search query.

An enhanced user experience speculation on what an uncommitted search query was originally and based on speculatively completed search queries, proactively searches. For example, a database may be indexed by a partially formed search query to infer what the completed search query may be. Alternatively, user-specific information (e.g., address or phone book) may be searched through the partially formed search query to infer what the completed search query may be. For example, if the phrase "John telep" is entered by the user as an uncommitted search query, the user's phone/address book may be searched for the phone number of any person named John. In response to the non-submitted search query, a telephone number is provided to the user. Other user databases may also be searched, such as e-mail, notes, favorite places, history, and the like.

Exemplary search results

Embodiments of the present invention analyze a keyword's search query to determine which search to perform. For example, FIG. 4 shows an example of a search 501 in which the user has entered "sf map," where a map 502 of san Francisco is provided when the user types in the search query 501. In addition, other useful links 504 are provided in the speculative search results.

Overview of predictive search queries

Techniques for providing an interface to a search engine are provided. The interface of the search engine assists the user 1) in predicting what the user is searching for based on one or more characters that the user has entered into the query area of the interface, and 2) provides the user with search results via the interface without requiring the user to formally post the intended query. For each character entered in the query region, the entered query portion is automatically issued to a query predictor that determines a set of one or more predicted queries corresponding to the query portion. The set of predicted queries is determined based on the frequency of previously issued queries alone or also at the time of issuance of the previous queries. The most likely predicted query is processed by a search engine to obtain search results. Both the predicted query and the search results are provided to the user via an interactive user interface. When displayed to a user, the predicted queries may be ranked based on their popularity (based on frequency) alone or also based on their temporal relevance (based on time).

If the user is not interested in search results based on the most likely predicted query, the user may select any query in the set of predicted queries. When the user selects a different predicted query in the list, the search results are updated to display the search results for the different predicted query.

In addition to displaying the predicted query and search results to the user via the user interface, other dynamic data about the most likely predicted query, but not necessarily obtained through the search results, may be provided, such as advertisements and other relevant links to websites.

Overview of predictive search functionality

FIG. 6 illustrates a user interface display, a predicted query, and search results according to one embodiment of the invention. The user enters, via web browser 600, the characters that will make up the user's predetermined query in query area 602. Whenever the first character is entered and for each subsequently entered character, the portion of the predetermined query is sent to the query predictor as described later (see FIGS. 8A-8C). The query predictor determines a set of one or more predicted queries based on the partial query. The predicted query is sent back to the user and displayed, such as in drop-down box (drop box) 604. The web browser 600 also displays the selected predicted query 608 (hereinafter referred to as the "particular predicted query").

The search engine processes the particular predicted query 608 from the predetermined set of queries and sends search results 612 to the user for display, such as in results page 610. Thus, the user may only need to enter one or a few characters before determining the actual predetermined query and displaying the results of the predetermined query. Thus, the select search button 606 may never have to be pressed in order to issue a predetermined query.

Query predictor

In one embodiment of the invention, the portion of the query that has been entered by the user is transmitted from the user's web browser over the network to the query predictor. This may occur for each character or sequence of characters entered by the user. The query predictor examines one or more characters and makes one or more predictions as to what the predetermined query is. The one or more predictions are in the form of one or more completed queries, each of which is a previously issued query. The one or more predictions are transmitted and displayed on the user's computer; effectively helping the user to formulate the query before the user has finished typing the entire predetermined query in the query area.

The basic idea of a query predictor is that a user is most likely to intend to publish at least one query that others have previously published. Using this information, highly interactive search engines may help users formulate queries, or may help users refine queries by listing other various queries that may be of interest to the user. Each previously issued query is saved and recorded because if a query is valuable to one user, the query is potentially valuable to another user.

In one embodiment, the extension of the query predictor to other languages is not limited to English. The query predictor may also support other types of strings, such as product names and part numbers where the user may only know a small segment.

"Intelligent" vocabulary completion

The query predictor thus has a searchable query database that is accessed by the query predictor once the query predictor receives one or more characters from a user. Based on the partial query, the query predictor determines one or more completed queries from the lexically matched query database. However, instead of simply completing a partial query over a vocabulary and returning only those queries that begin with characters in the partial query, queries that include vocabulary completions anywhere in the predicted query may also be found. For example, if the user enters the string "th," not only may the "term of evolution" be a predictive query sent to the user, but also the "string term" or "music term" that is completed by words that are each not simply "th" may also be predictive queries.

Frequency and time

In some cases, many previously issued queries may begin with "th". It has been determined that the most useful queries may not but most often be issued (popularity) but also those that have been recently issued (temporal relevance). Thus, in one embodiment of the invention, the query predictor is based on a set of predicted queries that are offset by the frequency of predicted queries (i.e., the number of times a query is issued throughout the query database history) and how frequently they are issued within a given time (e.g., in the last week). The case where recently issued queries are biased is based on the premise that the user is likely to be more interested in objects that are many other people interested at about the same time.

As an example, while "reusable energy sources" may be issued 5 times more frequently as a query than "nuclear energy," a partial query of "ener" may cause the query predictor to generate "nuclear energy" as a specific prediction query because "nuclear energy" was issued more frequently in the last week because the congress recently announced the assumption that 100 nuclear reactors will be built.

In one embodiment, the time component is determined by searching at least two databases (one for relatively recent queries and one for relatively early queries), and then scaling (scaling) the results obtained by searching the closest database and weighting accordingly. Fig. 7 shows steps in which this embodiment may be implemented. Clearly, there are many ways in which such scaling and weighting may be performed, in addition to the number of "old" query databases and "new" query databases, as the present invention is not limited to this particular example. In this embodiment, the query predictor has access to a small database for all queries issued the last week and a large database for all queries issued one week ago. When searching a small database of potentially valuable predictive queries, the number of potential queries found in the small database is scaled based on a factor. The factor is the ratio of the number of medium popular queries found in the big database to the number of identical medium popular queries found in the small database. For example, assume "Yahoo" is a medium popular query in the last week and in recent years. If "Yahoo" is found 170 ten thousand times in the large database and 2.5 ten thousand times in the small database, the factor is 170 ten thousand/2.5 ten thousand or 68.

Query prediction is less effective if the moderately popular queries in both the small and large databases are not used for scaling. If the query is only popular in the large database and not popular in the small database, the scaling factor is biased. For example, if the query "floppy disk" is used as a scaling factor and is queried many times in the history of a large database, but only a few times in the last week (for reasons of simplicity, no one has produced or used a floppy disk), the ratio between the large and small databases will be large. Partial query results are biased by weighting relatively recent queries by a large amount, resulting in the loss of relatively older (and potentially more valuable) queries.

A similar problem may exist if a new query is used as a scaling factor that is only issued in the last week, but rarely in the history of a large database. For example, "nuclear" may not be mentioned often in the past. However, the query "nuclear power" may be issued thousands, if not thousands, of times, due to the recent announcements by the congress of the assumption that 100 nuclear reactors will be built. In that case, the scaling factor will be small; and when queries in a small database are weighted against queries in a large database, it is likely that relatively older predicted queries (rather than relatively newer queries) and potentially more valuable predicted queries will be returned to the user.

Thus, referring to FIG. 7, after the query predictor determines the number of times a given potentially valuable query is issued in a small (i.e., new) database in step 702, that number is scaled to 68 in step 704, based on the scaling factor determined above using "Yahoo" as the scaled query. The resulting scaling value essentially represents that the weight of the potential query in the small database is equal to the weight of the potential query in the large (i.e., old) database. Subsequently, in step 706, the query predictor determines the number of times the potential query appears in the large database of "old" queries.

In this regard, weights are applied to potential queries in a small database versus potential queries in a larger database. This is performed by multiplying 2/3 the result of scaling the number of times the small database and then adding it to the result of multiplying 1/3 the number of potential queries found in the large database (see steps 708-712). Steps 702-712 are performed for each potential query determined by the query predictor. When there are no more potential queries to process (714), then all potential queries are compared to each other based on the respective values determined for each potential query in step 712. The two or more (e.g., ten) queries with the largest value become the predicted queries that are then sent to the user.

Search engine

In one embodiment of the invention, the search engine component processes specific predicted queries (i.e., the most likely expected predicted queries) that may be of interest to the user. A particular predicted query is processed to obtain search results. Search engines that can be used for this purpose are well known to those skilled in the art and need not be further explained.

Search results obtained by the search engine are sent to and displayed on the user's computer. If the particular predicted query is the query intended by the user, search results based on the particular predicted query will appear on the user's monitor before the user enters another character in the query region, and most likely before the user is finished entering the entire intended query. If the particular predicted query is not the user's intended query, the user may select a different predicted query in the list or continue typing, at which point a new set of search results will be displayed via the user interface based on the selected or new particular predicted query.

Providing predicted queries and search results

FIG. 8A is a block diagram illustrating a method of processing a partial query and how partial query results are returned, according to one embodiment of the invention.

A user at client 800 enters a partial query in web browser 802. The partial query 812 is sent to the front end server 804 over the network 850. The front-end server 804 is not an essential element in any embodiment of the invention. Its primary purpose is to add security to an interactive search engine system. Network 850 is also not a required element in any embodiment, but is merely shown to illustrate one way in which the present invention may be implemented. The network 850 may be a Local Area Network (LAN), a Wide Area Network (WAN), or the Internet. The front-end server 804 passes the partial query 812 to the query predictor 806, which processes the partial query, as described above.

The front-end server 804, the query predictor 806, and the search engine 808, or any combination thereof, may be implemented on the same device. However, for purposes of explanation and simplicity, each of them is provided on a different device.

The query predictor 806 determines a set of one or more predicted queries based on the partial query and sends the predicted queries 814 back to the front-end server 804. Along with the set of predicted queries, the query predictor 806 sends additional data indicating which of the predicted queries in the set is the particular predicted query. The query predictor 806 determines which predicted query is a particular predicted query or gives enough information to the web browser 802 to make the determination. The front-end server 804 then transmits the predicted query 814 and data representing the particular predicted query to the client 800 over the network 850 for display on the web browser 802.

Upon receiving the set of predicted queries, the web browser 802 sends the particular predicted query 816 over the network 850 to the front-end server 804, which front-end server 816 transmits the particular predicted query 816 to the search engine 808. The search engine 808 described above processes a particular predicted query to obtain search results. The search results 818 are ultimately sent to the front end server 804, which front end server 804 transmits the search results 818 to the client 800 over the network 850.

One advantage of this embodiment is that the predicted queries are immediately transmitted to the user once they are determined. However, this embodiment also shows that for the possibility of each character user typing in the query area of their web browser, there are two full loops for the communication that must take place between the client 800 and the front-end server 804.

FIG. 8B is a block diagram illustrating different ways of processing a partial query and how results are returned to a client according to another embodiment of the invention.

A user at client 800 enters a partial query in web browser 802. The partial query 812 is sent to the front end server 804 over the network 850. The front-end server 804 passes the partial query 812 to the query predictor 806, which processes the partial query.

The query predictor 806 determines a set of one or more predicted queries based on the partial query and sends the predicted queries 814 to the front-end server 804. Instead of immediately communicating the predicted query to the client 800, the front-end server 804 retains the predicted query and sends the particular predicted query 816 to the search engine 808. Again, along with the set of predicted queries, the query predictor 806 sends additional data indicating which of the predicted queries in the set is the particular predicted query. The query predictor 806 determines which predicted query is a particular predicted query or gives the front-end server 804 sufficient information to make the determination.

The search engine 808 processes the particular predicted query to obtain search results. The search results 818 are sent to the front end server 804, at which point the front end server 804 transmits the predicted query 814 and the search results 818 to the client 800 over the network 850.

In the absence of front-end server 804, query predictor 806 sends predicted query 814 to search engine 808, which search engine 808 then sends predicted query 814 and search results 818 to client 800 over network 850.

An advantage of this embodiment is that there is less communication (i.e., traffic) between the client 800 and the front-end server 804. However, the predicted query is not displayed on the user's web browser 802 as quickly as the previous embodiments because the predicted query must "wait" to generate and send search results to the front-end server 804 before the predicted query is delivered to the client 800.

FIG. 8C is a block diagram illustrating different ways of processing a partial query and how results are returned to a client according to another embodiment of the invention.

The query predictor 806 determines a set of one or more predicted queries based on the partial query and sends the predicted queries 814 to the front-end server 804. Again, along with the set of predicted queries, the query predictor 806 sends additional data indicating which of the predicted queries in the set is the particular predicted query. The query predictor 806 determines which predicted query is a particular predicted query or gives the front-end server 804 sufficient information to make the determination.

Instead of "holding" the predicted query as in the previous embodiment, the front-end server 804 sends the predicted query 814 to the client 800 over the network 850 and sends the particular predicted query 816 to the search engine 808 at approximately the same time. For the query predictor 806, the particular predicted query may also be sent directly to the search engine 808.

The search engine 808 processes the particular predicted query to obtain search results. The search results 818 are sent to the front end server 804, at which point the front end server 804 transmits the search results 818 to the client 800 over the network 850. In the absence of front-end server 804, query predictor 806 transmits predicted query 814 and particular predicted query 816 to search engine 808, after which search engine 808 sends predicted query 814 and search results 818 to client 800 over network 850.

In the absence of the front-end server 804, the query predictor 806 transmits the predicted query 814 and the particular predicted query 816 to the search engine 808, and the search engine 808 then transmits the predicted query 814 and the search results 818 to the search engine 808 over the network 850.

An advantage of this embodiment over the embodiment depicted in fig. 8A is that there is less traffic between the client 800 and the front-end server 804. An advantage over the embodiment described in FIG. 8B is that the predicted query does not have to "wait" for search results to be generated and sent to the front-end server 804 before the predicted query is transmitted to the client 800. Thus, the predictive query is sent immediately once it is generated, and requires only little communication between the client 800 and the front-end server 804.

User interface

In one embodiment of the invention, as shown in FIG. 6, the user interface includes at least 1) a query area 602 in which the user enters the characters that will make up the partial query, 2) a drop-down box 604 listing a set of one or more predicted queries, 3) a Search results page 610, and 4) "Search" button 606. In the event that the user is not satisfied with any predicted query provided by the interactive search engine, the search button may be in the form of any mechanism that enables the user to select the query entered by the user. The set of predicted queries listed in drop-down box 604 may be represented by virtually any other type of user interface element, including but not limited to a text box, a list box, a menu, or a right-click menu. The user interface may be viewed using a web browser such as INTERNET EXPLORER or mozillafiefox.

In one embodiment, the set of predicted queries is listed in order from the most probable predicted query to the least probable predicted query, starting from the top.

Modifying

In addition to the user interface, query predictor, and search engine described above, the interactive search engine may be modified in a number of ways to change the look, feel, and responsiveness of the search experience.

Label (tab)

For example, the user interface includes a tab, such as button or link 622 in FIG. 6, where the user may select a sub-section (subsection) of a possible query and search based on the sub-section. Through a set of tags or "vertical searches" such as "web," "image," "video," and "shopping," the user can select different query settings. The data predicted by the query predictor differs according to the contents of interest of the user, and is narrowed down by using these tags. For example, if the user is interested in purchasing a product, the user may select a "shopping" tab. The user then begins entering a product name or service in the query area 602. The query predictor sends not only partial queries but also shopping selection information indicating that the user is searching for a particular product or service, wherein the query predictor returns only those predicted queries about the product and service.

Key word

Typically when a query is issued, the order of the words in the query is unimportant. As mentioned previously, the issued query need not be in English. In other embodiments, not only other natural languages are supported, but also unnatural strings are supported, e.g., a user may only know the product name and part number of a portion of the unnatural string. Thus, the term "word" as used herein may include english words, korean words, or product numbers.

When a user enters two or more words in a query region, the user does not necessarily care that the search engine return a link to a network-accessible document that includes the two or more words arranged in the order of entry. More precisely, the user is interested in network accessible documents containing only these words, regardless of the order in which they are found.

For example, the user inputs "solar wind water power" in the query area. The user is not particularly concerned with their order. The user is more concerned about queries that contain the words "solar", "wind", "water" and "power" somewhere in the query. The query predictor determines which words in the query are important and which words are not, and then instead of simply predicting the query based on matching strings, the predicted query is made based on the important words.

Delay the result

In another embodiment, the step of displaying the predicted query and/or search results is delayed. Instead of returning the predicted query immediately, the query predictor "waits" until certain criteria are met (e.g., the passage of a specific amount of time or when several characters are entered, or both) before displaying the predicted query and the search results. This additional waiting step assumes that the user will be uncertain what he/she wants to query. Thus, the predictive query is delayed until the interactive user interface determines what the user really intended to query based on the wait criteria. Once the wait criteria are met, portions of the query are processed through the query predictor and search engine as described above.

Other dynamic data

In addition to predicting expected queries and returning appropriate search results, there are other ways to assist the user. In another embodiment, the advertisements that appear on the interactive user interface change based on the particular predicted query returned from the query predictor. Thus, whenever a particular predicted query changes, new advertisements relevant to the query are displayed on the user interface, and advertisements relevant to old and irrelevant queries are deleted from the user interface. For example, if a user types "elli" and the query predictor determines "ellitical" as a particular predicted query, an advertisement related to the fitness equipment may appear on the user interface.

In addition to advertisements, other dynamic information may also be useful to a user when the user submits a query. In another embodiment, information about a particular predicted query but not found in the search results is displayed to the user via a user interface. Expanding on the "term" example used above, the query predictor determines that "term" is a particular predicted query for the partial query "th" entered by the user. The query predictor (and possibly other programs) determines that "term" is related to "string term", "music term" and "math term" and returns these related objects for display on the user interface in the form of a predicted query or in a different form. For short queries such as "theory," this additional information would happen to be the same as that generated by the query predictor.

However, if the user enters "interna" in the query region and the query predictor determines that a particular predicted query is "international trade", the query predictor will return a query that is not a lexical completion of "international trade" in addition to the predicted query, but a query about the subject of international trade. Such queries may be about GATT, WTO, UN, US trade policies, and the like. Programs other than query predictors may also perform this function.

Clearly, this aspect of the invention does not perform query prediction, but rather provides the user with dynamic, relevant and desired helpful information. The principle of providing advertisements, additional queries, and other relevant information is to keep everything displayed via the user interface consistent with the user's intent "believing" by the query predictor (as determined by the query predictor from the portion of the query).

Alternative predictive search queries: SUMMARY

Techniques have been described for predicting what a user search query is when completed. The search query thus predicted is referred to herein as a "predicted search query". According to one embodiment, after determining the predicted search query, the search engine proceeds to determine and provide to the user one or more alternative predicted search queries. Such alternative queries are referred to herein as "alternative search queries". Each alternative search query is based at least in part on the predicted search query, but differs from the predicted search query in some ways.

Unlike a predicted search query, an alternative search query is not a prediction of what the user query will likely be when completed. In fact, the alternative search query is typically a query that is unlikely to be completed by the partially formed user search query. For example, in response to a user entering the search query "brittany sp," the predicted search query may be "britney spears," but an alternative search query may be "britney spears. In this example, a complete description of "brittany sp" is most likely not "britney spears" because "britney spears" is only generated when the user returns and changes spelling.

According to embodiments of the present invention, alternative search queries are determined as follows: a search query is received from a client node. Prior to receiving an indication from the client node that the search query is fully formed, performing the steps of: 1) determining a predicted search query by predicting what the search query will be when completed; and 2) determining, based on the predicted search query, an alternative search query that is different from the predicted search query. The alternative search query is provided to the client node.

The alternative search query may be based on an alternative spelling (or spelling suggestion) of the predicted search query. The alternative search query may be a search query that is closely related to the predicted search query. For example, if the predicted search query is an acronym, the alternative search query may be an expansion of the acronym. Another example of a closely related search query is "movie times" and "show times".

Exemplary user interface

FIG. 9 illustrates an exemplary user interface 900 according to an embodiment of the present invention. The user interface has a search box 901 in which the user has entered a user search query 902 of "chicken". Below the search box 901 is a list of search queries that are provided to the user in real-time as the user enters the user search query 902. The search query list includes a mirrored version 903 of the user search query 902. Below mirrored version 903 is an area that includes a predicted search query 904 and an alternative search query 905, both of which are determined directly or indirectly based on user search query 902, in accordance with embodiments of the present invention. According to one embodiment, the predicted search query 904 and the alternative search query 905 are ranked based on expected relevance to the user search query 902. A high ranking search query may be represented higher in the list.

The predicted search queries 904 "chicken recipes," "chicken recipe," and "chicken ranch" are predictions of what the user search query 902 will be when completed. In accordance with an embodiment of the present invention, an alternative search query 905 is determined based on the predicted search query 904. As an example, the search query "chicken and rice contacts" is an alternative term based on the predictive search query "chicken contacts". Note that the alternative search query 905 is formed by adding characters except at the end of the user search query 902. Other alternative search queries 905 include "chicken wings," chicken rice contacts, "" easy chicken contacts, "and" banked chicken contacts.

User interface 900 has search results 906 that include links to documents (e.g., web pages) that satisfy one or more search queries. In this example, the search results 906 pertain to the predicted search query "chicken recipes," which has the highest relevance rank to the predicted search query 904 and the alternative search query 905. In one embodiment, these search results are provided to the user in a default form without requiring the user to ask for search results for a particular search query. However, providing search results may be provided to any search query including any of the alternative search queries 905. Note that in this exemplary user interface 900, there is no button for the user to submit a search query preparation. In one embodiment, the user may change the search results displayed by scrolling through the list of search queries (including the mirror search query 903).

User interface 900 has other areas for displaying results with respect to a search query, such as sponsor offer area 910. Results relating to predicted search query 904 or alternative search query 905 may be displayed within sponsor offering area 910.

Process for determining alternative terms for predictive search queries

FIG. 10 is a flowchart illustrating the steps of a process 1000 of determining alternative terms for a predicted search query in accordance with an embodiment of the present invention. Process 1000 will be discussed below in conjunction with the client/server system of FIG. 8A and the exemplary user interface of FIG. 9; however, process 1000 is not so limited.

In step 1002, a search query is received from a client node. For example, the exemplary user interface 900 of FIG. 9 is part of a web browser 802 or the like executing on the client node 800. As an example, a user enters a search query "chicken r" that is transmitted to server 804.

In step 1004, one or more predicted search queries are determined by predicting what the search query would be when completed. Step 1004 is performed before an indication is received from client 800 that the search query is fully formulated. For example, the query predictor 806 determines that the user search query will be "chicken recippes" or "chicken recippes" when completed.

In one embodiment, the predicted search query is determined by selecting a search query from a database of historically submitted search queries ("historical database"). For example, the historical database also stores a frequency of submitting each search query, wherein the selection of the predicted search query is based on the frequency. In this example, the frequency with which users submit search queries "chicken recipes" and "chicken recipe" is high enough to predict that the user search query will complete one of them.

In step 1006, for at least one predicted search query, at least one alternative search query that is different from the predicted search query is determined. Step 1006 is performed before client 800 provides an indication of completion of the search query. For example, an alternative search query "chicken and rice recippes" is determined based on "chicken recippes". Other exemplary alternative search queries are "chicken wind profiles", "chicken receprofiles", "easy chicken profiles", and "banked chicken profiles".

Note that in this example, the alternative search query is not formed by adding characters to the end of the user search query. For example, words such as "wing" and "wings" are inserted in the middle of the user search query "chicken r" string. It should also be noted that characters may be added in front of the user search query, as in the alternative search query "easy chicken copies". Further details of how alternative search queries are determined will be discussed below.

In step 1008, at least one alternative search query is provided to client 800. In one embodiment, potential alternative search queries are ranked according to predicted relevance to the user search query, with higher ranking alternative search queries being provided to client 800. As shown in fig. 9, the alternative search queries are then displayed in the user interface 900. Note that alternative search queries are provided to client 800 before client 800 provides an indication of completion of the search query.

In optional step 1010, search results that satisfy one or more alternative search queries are determined and provided to client 800. Other search results (e.g., results that satisfy one or more predicted search queries) may be transmitted to client 800. Results satisfying one or more alternative search queries may be displayed as search results 906 in other areas of user interface 900 (e.g., sponsor offer area 910).

Instances of alternative search queries generated based on predicted search queries

Alternative search queries may be determined in a variety of ways. The following sections describe various methods for determining alternative search queries. However, determining alternative search results to the predicted search query is not limited to these examples.

Correlation based on information related to altitude

Although structurally disparate, some search queries are related to one another. If the user enters one of these search queries, one or more related search queries may also be focused on. In some cases, a search query may produce very similar search results. One example is the search queries "movie times" and "show times". Another example is the search query "CIA" and "Central insight service". Some related search queries need not generate nearly similar results. For example, the search query "flower" and "wedding" are related, although the search results may be quite different.

A) Acronyms

One way in which search queries may be related is a method that includes acronyms for words that are spelled in another query. FIG. 11A shows a user interface 900 according to an embodiment of the invention. The search box 901 includes a user search query 902 "cia". Before the user provides an indication of completion of the search query 902, one or more predictions are made as to what the search query 902 would be when completed. In this case, predicted search query 904 includes "cia", "cia", "ciara", "cialis", "ciafacebook", "cia county facebook", and "ciaworld facebook". Note that the predicted search query 904 "cia" is the same as the user search query 902, and therefore also serves as a mirrored version of the user search query 902.

In one embodiment, analysis based on historical search queries determines what the user search query would be when completed. For example, in one embodiment, if a search query "cia" appears in the historical database with a very high frequency, it is predicted to be a completed search query. Similar processing applies to determining other predicted search queries 904.

As discussed previously, alternative search queries are determined and provided to the client by embodiments in accordance with the present invention. For example, one predicted search query 904 is "cia". In this example, one alternative search query 905 is "centralintelligence agent". The alternative search query is based on considering "CIA" as an acronym and expanding that acronym. The process may be reversed. In other words, if the predicted search query is "central intelligencagency," an alternative search query of "cia" may be provided to the client. Other alternative search queries 905 to the predicted search query 904 "cia" are "cuiline institue of america" and "ca international airport".

The user interface 900 has search results 906 of links to documents (e.g., web pages) that satisfy one or more search queries. In this example, search results 906 pertain to more than one search query. For example, search results associated with alternative search queries 905 "central inventory agent" and "cuiline institute of America" are provided.

B) Other attempts

Alternative search queries may also be based on "other try" suggestions. Other attempted suggestions are based on search queries that are closely related to each other. An example of another attempted query is suggesting a related search query "movie times" with respect to the user search query "show times". According to embodiments of the present invention, a database ("other attempt database") having closely related search query associations is used to determine alternative search queries.

FIG. 11B illustrates a user interface where the user search query 902 is "sony we". Before the user enters an indication that the user search query 902 is complete, the search query 904 that is done will be a prediction of "sony wega". Where the other predicted search queries 904 are "sony wega tv", "sony wega 42 tv", etc., a number of alternative search queries 905 are suggested to the user based on at least one of the predicted search queries 904. For example, alternatives to "sony fd trinitron wega" and "sony plasma wega" are provided as alternative search queries 905.

Note that the alternative search query may include one or more characters inserted into the body of the user search query. For example, "fd trinitron" appears in the body of the user search query 902 "sony we". Alternative terms may be determined by searching other try databases, although other techniques may be used. For example, any database that includes search queries that are related or related to each other may be searched.

The alternative search query may also include characters that guide the user in searching the body of the query. For example, if the user search query 902 is "flowers," the predicted completed search query should be "flowers. Based on the predicted search query, the alternative terms "bidding flowers," "pictures of flowers," and so forth, may be provided as alternative search queries. Note that none of these alternative search queries may be formed by merely completing the user search query by adding one or more characters to the end of the user search query.

Referring again to FIG. 9, the user search query 902 is "chicken r". In accordance with an embodiment of the present invention, an alternative search query 905 is determined based on a search query related to one of the predicted search queries 904 "chicken recipes" or "chicken recipes".

Thus, embodiments in accordance with the present invention determine alternative search queries that cannot be formed by merely adding characters to the end of a user search query.

Spelling suggestions

Spelling suggestions are used to determine alternative terms for predictive search queries, according to embodiments of the present invention. As previously described, a historical database of search queries that have been submitted by users may be generated. In one embodiment, a historical database is used to determine a prediction of how a user search query will complete. When a user submits a search query containing misspelled terms, the search query is first added to the historical database. However, in one embodiment, search queries with misspellings are removed from the historical database. Various scenarios of whether the coverage misspelled search query is in the historical database will be discussed below.

In one embodiment, a spelling database is used to determine alternative search queries for a user search query that may be misspelled. An entry in the spelling database includes a first spelling of a term and at least one alternative spelling of the term. The spelling database may further have frequency information that may be used to select alternative spellings of terms for a first spelling of terms. An example of how the spelling database may be used to determine alternative search queries is described below.

Providing alternative search queries to a predictive search query based on spelling suggestions can be performed in a number of different ways. The following are three different embodiments. However, providing alternative search queries to predictive search queries based on spelling suggestions is not limited to the following embodiments.

A) History database having entries for user search queries

In FIG. 11C, the user has entered a user search query 902 "brittany sp". The search query 902 is passed to a query predictor (FIG. 8, 806), which predicts what the user search query 902 would be when completed. For example, the predicted search query 904 is "brittany spears". In one embodiment, the prediction is based on a search of a historical search query database. In this case, the history database includes the misspelled search query "brittany spears". The predicted search query 904 is provided to the client.

Further, in the present embodiment, alternative search queries for alternative spellings of the predicted search query are determined 905. For example, in one embodiment, the alternative search query 905 is determined by searching the spelling database using the predicted search query "brittany spears" as a keyword. The alternative search query 905 "brittany spears" is provided to the client, and is thus displayed in the user interface of fig. 11C.

In this example, additional predicted search queries 904 are also provided to the client. For example, the search query "brittany span" is provided to the user. In addition, search results 906 that satisfy a suggested search query are provided to the user. In this example, search results 906 for an alternative search query 905 "Britney Spears" are provided. Sponsor provided results 910 are also provided for alternative search queries 905.

B) The historical database does not have entries for user search queries, but the spelling suggestion database has entries for user search queries

As another example, if a user enters the search query "ritney spears," the prediction of a completed search query may be "ritney spears. In this example, the prediction may be made by searching the history database and determining that the search query "ritney spears" does not exist. Although the user has submitted this misspell in the past, the entry for that particular misspell has been removed from the historical database. A prediction may be made that "ritney spears" will be a completed user search query based on the fact that the historical database does not contain the search query, or will be any search query with additional characters that the user may add to the tail.

Based on the predicted search query, an alternative search query to "britney spears" is determined and provided to the user. In one embodiment, the alternative search query is determined by searching the spelling database using the predicted search query as a keyword. In this example, the search entry "ritney spears" is in the spelling database as the first search query and is associated with "britney spears".

C) Neither the history database nor the spelling suggestion database has entries for user search queries

As another example, the user may have entered the search query "nkusp f". In this example, the history database does not include any entries that match the search query or that may match additional characters added to the tail. Thus, making this is a prediction of a full search query. To illustrate, if the search query "nkusp f" does not appear in the spelling database, spelling corrections cannot be determined using this form of the user search query. In this case, the user search query is reformulated and spelling correction of the reformulated user search query is attempted. For example, one or more characters at the right-hand end of the user search query are removed. As a specific example, the term "nkusp" is searched in the spelling database. For purposes of illustration, the spelling database associates the terms "nakusp" and "nkusp". Thus, an alternative search query "nakusp" is provided to the client as a city in british columbia.

Note that the user has been provided with an alternative search query "nakusp" before the user enters "f" into the search query. However, in some cases, the user may continue to type more characters even after a suitable alternative search query has been provided.

Determining combinations of alternative search queries

The alternative search queries may be based on one or more of the techniques discussed herein. For example, an alternative search query is formed by applying an alternative spelling to the predicted search query and then further modifying the alternative spelling. For example, the alternative spelling may be an acronym. The acronyms may be expanded to generate one or more alternative search queries.

Overview of hardware

FIG. 12 is a block diagram that illustrates a computer system 1200 upon which an embodiment of the invention may be implemented. Computer system 1200 includes a bus 1202 or other communication mechanism for communicating information, and a processor 1204 coupled with bus 1202 for processing information. Computer system 1200 also includes a main memory 1206, such as a Random Access Memory (RAM) or other dynamic storage device, coupled to bus 1202 for storing information and instructions to be executed by processor 1204. Main memory 1206 also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor 1204. Computer system 1200 also includes a Read Only Memory (ROM)1208 or other static storage device coupled to bus 1202 for storing static information and instructions for processor 1204. A storage device 1210, such as a magnetic disk or optical disk, is provided and coupled to bus 1202 for storing information and instructions.

Computer system 1200 may be coupled via bus 1202 to a display 1212, such as a Cathode Ray Tube (CRT), for displaying information to a computer user. An input device 1214, including alphanumeric and other keys, is coupled to bus 1202 for communicating information and command selections to processor 1204. Another type of user input device is cursor control 1216, such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor 1204 and for controlling cursor movement on display 1212. The input device typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), that allows the device to specify positions in a plane.

Computer system 1200 may be used to implement the techniques described herein. According to one embodiment of the invention, those techniques are performed by computer system 1200 in response to processor 1204 executing one or more sequences of one or more instructions contained in main memory 1206. Such instructions may be read into main memory 1206 from another computer-readable medium, such as storage device 1210. Execution of the sequences of instructions contained in main memory 1206 causes processor 1204 to perform the process steps described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement the invention. Thus, embodiments of the invention are not limited to any specific combination of hardware circuitry and software.

The term "computer-readable medium" as used herein refers to any medium that participates in providing instructions to processor 1204 for execution. Such a medium may take many forms, including but not limited to, non-volatile media, and transmission media. Non-volatile media includes, for example, optical or magnetic disks, such as storage device 1210. Volatile media includes dynamic memory, such as main memory 1206. Transmission media includes coaxial cables, copper wire and fiber optics, including the wires that comprise bus 1202. Transmission media can also take the form of acoustic or light waves, such as those generated during radio-wave and infra-red data communications.

Common forms of computer-readable media include, for example, a floppy disk, a flexible disk, hard disk, magnetic tape, or any other magnetic medium, a CD-ROM, any other optical medium, punch cards, paper tape, any other physical medium with patterns of holes, a RAM, a PROM, an EPROM, a FLASH-EPROM, any other memory chip or cartridge, a carrier wave as described hereinafter, or any other medium from which a computer can read.

Various forms of computer readable media may be involved in carrying one or more sequences of one or more instructions to processor 1204 for execution. For example, the instructions may initially be carried on a magnetic disk of a remote computer. The remote computer can load the instructions into its dynamic memory and send the instructions over a telephone line using a modem. A modem local to computer system 1200 can receive the data on the telephone line and use an infra-red transmitter to convert the data to an infra-red signal. An infra-red detector can receive the data carried in the infra-red signal and appropriate circuitry can place the data on bus 1202. Bus 1202 carries the data to main memory 1206, from which main memory 1206 processor 1204 retrieves and executes the instructions. The instructions received by main memory 1206 may optionally be stored on storage device 1210 either before or after execution by processor 1204.

Computer system 1200 also includes a communication interface 1218 coupled to bus 1202. Communication interface 1218 provides a two-way data communication coupling to network link 1220, which network link 1220 couples to a local network 1222. For example, communication interface 1218 may be an Integrated Services Digital Network (ISDN) card or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface 1218 may be a Local Area Network (LAN) card to provide a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation, communication interface 1218 sends and receives electrical, magnetic or optical signals that carry digital data streams representing various types of information.

Network link 1220 typically provides data communication through one or more networks to other data devices. For example, network link 1220 may provide a connection through local network 1222 to a host computer 1224 or to data equipment operated by an Internet Service Provider (ISP) 1226. ISP 1226 in turn provides data communication services through the global packet data communication network (now commonly referred to as the "internet") 1228. Local network 1222 and internet 1228 both use electrical, electromagnetic or optical signals that carry digital data streams. The signals through the various networks and the signals on network link 1220 and through communication interface 1218, which carry the digital data to and from computer system 1200, are exemplary forms of carrier waves transporting the information.

Computer system 1200 can send messages and receive data, including program code, through the network(s), network link 1200 and communication interface 1218. In the internet example, a server 1230 might transmit a requested code for an application program through internet 1228, ISP 1226, local network 1222 and communication interface 1218.

The received code may be executed by processor 1204 as it is received, and/or stored in storage device 1210, or other non-volatile storage for later execution. In this manner, computer system 1200 may obtain application code in the form of a carrier wave.

In the foregoing specification, embodiments of the invention have been described with reference to numerous specific details that may vary from implementation to implementation. The sole and exclusive indicator of what is the invention, and is intended by the applicants to be the invention, is the set of claims that issue from this application, in the specific form in which such claims issue, including any subsequent correction. Any definitions expressly set forth herein for terms contained in such claims shall govern the meaning of such terms as used in the claims. Hence, no element, property, feature, advantage or attribute that is not expressly recited in a claim should limit the scope of such claim in any way. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.

Claims

1. A computer-implemented method of providing speculative search results, comprising:

receiving a search query from a client node, wherein the search query has not been submitted;

determining speculative search results for the not yet submitted search query prior to receiving an indication from the client node that the not yet submitted search query is fully formed; and

providing the speculative search results to the client node, wherein the speculative search results identify at least one entry that satisfies the search query that has not yet been submitted;

the method further comprises the following steps: determining whether the search query that has not yet been submitted meets criteria that initiate processing of the determined speculative search results.

2. The method of claim 1, wherein the criteria comprises that the search query not yet submitted comprises a complete word.

3. The method of claim 1, wherein the criteria comprises determining whether the search query that has not yet been submitted matches a phrase in a dictionary of predefined phrases.

4. The method of claim 1, wherein the criteria includes determining that a predetermined period of time has elapsed since a last character was entered in the search query that has not yet been submitted.

5. The method of claim 1, wherein the determining speculative search results comprises performing a ranked search of different databases, wherein an order is based on expected relevance to the search query that has not yet been submitted.

6. The method of claim 5, wherein the database comprises a database of predefined search results, each predefined search result comprising an organized collection related to a search query.

7. The method of claim 5, wherein the determining a speculative search result comprises determining a navigation link related to the search query that has not yet been submitted.

8. The method of claim 5, wherein the determining a speculative search result comprises determining whether the search query that has not yet been submitted matches at least one phrase in a set of predefined phrases as a condition for further searching the speculative search result.

9. The method of claim 1, further comprising:

receiving a further portion of the search query from the client node that has not yet been submitted;

determining updated speculative search results for the further portion prior to receiving an indication from the client node that the search query that has not yet been submitted is fully formed; and

providing the updated speculative search results to the client node, wherein the updated speculative search results identify at least one entry that satisfies the search query that has not yet been submitted.

10. The method of claim 1, further comprising providing suggestions to the client node to improve the search query that has not yet been submitted before receiving an indication from the client node that the search query is fully formed.