Document search engine including highlighting of confident results

Description of equivalent WO 2005001719 A1

DOCUMENT SEARCH ENGINE INCLUDING HIGHLIGHTΓNG OF CONFIDENT RESULTS

BACKGROUND OF THE INVENTION

A. Field of the Invention The present invention relates generally to document search engines and, more particularly, to highlighting select documents returned from a search engine.

B. Description of Related Art The World Wide Web ("web") contains a vast amount of information. Locating a desired portion of the information, however, can be challenging. This problem is compounded because the amount of information on the web and the number of new users inexperienced at web searching are growing rapidly. Search engines attempt to return hyperlinks to web pages in which a user is interested. Generally, search engines base their determination of the user's interest on search terms (called a search query) entered by the user. The goal of the search engine is to provide links to high quality, relevant results to the user based on the search query. Typically, the search engine accomplishes this by matching the terms in the search query to a corpus of pre-stored web pages. Web pages that contain the user's search terms are "hits" and are returned to the user. In an attempt to increase the relevancy and quality of the web pages returned to the user, a search engine may attempt to sort the list of hits so that the most relevant and/or highest quality pages are at the top of the list of hits returned to the user. For example, the search engine may assign a rank or score to each hit, where the score is designed to correspond to the relevance or importance of the web page. Existing techniques of deteπnining relevance are based on the contents of the web page. More advanced techniques determine the importance of a web page based on more than the content of the web page. For example, one known method, described in the article entitled "The Anatomy of a Large-Scale Hypertextual Search Engine," by Sergey Brin and Lawrence Page, assigns a degree of importance to a web page based on the link structure of the web page. In other words, the Brin and Page algorithm attempts to quantify the importance of a web page based on more than just the content of the web page. The goal of a search engine is to return the most desirable set of links for any particular search query. However, in addition to just re rning the most desirable set of links, it may also be beneficial to present the set of links to the user in a manner that clearly and quickly informs the user of the content associated with each of the links. One method of apprising the user of the content associated with a particular link is to also display a "snippet" of text with the link. Ideally, the snippet of text should summarize the content of the link. In practice, the snippets are typically drawn from text of the document referenced by the link. Although text snippets can be useful in summarizing the link, the quality of the snippet in accurately summarizing the link can vary based on factors such as the automated nature of snippet generation and the quality of the underlying document. Also, for snippets to be useful, the user must take time to read the snippet. There is a need in the art for improved techniques for apprising the user of the contents of links returned in response to a search query.

SUMMARY OF THE INVENTION A search engine returns a list of links to documents that are relevant to the search query. Links that refer to documents that the search engine determines to be very relevant to a user query may be displayed with visual cues that assist the user in browsing the links.

BRIEF DESCRIPTION OF THE DRAWINGS The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate the invention and, together with the description, explain the invention. In the drawings, Fig. 1 is a diagram illustrating an exemplary system in which concepts consistent with the present invention may be implemented; Fig. 2 is a diagram illustrating a document that includes links to web documents displayed in response to a search query; Fig. 3 is a flow chart illustrating operation of a search engine consistent with an aspect of the invention; and Fig. 4 is a block diagram conceptually illustrating the determination of whether a document is very relevant to a user search query.

DETAILED DESCRIPTION The following detailed description of the invention refers to the accompanying drawings. The detailed description does not limit the invention. Instead, the scope of the invention is defined by the appended claims and equivalents. As described herein, a search engine may determine that it is confident that a particular link is the link that the user intended to find. The search engine may then highlight this link with a visual cue. The visual cue allows the user to quickly locate and deteimine whether the highlighted link is the link that the user intended to find.

SYSTEM OVERVIEW Fig. 1 is a diagram illustrating an exemplary system in which concepts consistent with the present invention may be implemented. The system includes multiple client devices 102, a server device 110, and a network 101, which may be, for example, the Internet. Client devices 102 each include a computer-readable medium 109, such as random access memory, coupled to a processor 108. Processor 108 executes program instructions stored in memory 109. Client devices 102 may also include a number of additional external or internal devices, such as, without limitation, a mouse, a CD-ROM, a keyboard, and a display. Through client devices 102, users 105 can communicate over network 101 with each other and with other systems and devices coupled to network 101, such as server device 110. Similar to client devices 102, server device 110 may include a processor 111 coupled to a computer-readable memory 112. Server device 110 may additionally include a secondary storage element, such as database 130. Client processors 108 and server processor 111 can be any of a number of well known computer processors. In general, client device 102 may be any type of computing platform connected to a network and that interacts with application programs, such as a digital assistant or a "smart" cellular telephone or pager. Server 110, although depicted as a single computer system, may be implemented as a network of computer processors. Memory 112 contains a search engine program 120. Search engine program 120 locates relevant information in response to search queries from users 105. In particular, users 105 send search queries to server device 110, which responds by returning a list of relevant information to user 105. Typically, users 105 ask server device 110 to locate web pages relating to a particular topic and stored at other devices or systems connected to network 101. Search engine 120 includes document locator 121 and a ranking component 122. In general, document locator 121 finds a set of documents whose contents match a user search query. Ranking component 122 may rank the located set of documents based on relevance and may generate a relevance score for each document that indicates a level of relevance. Search engine 120 may then return a list of links pointing to the set of documents determined by document locator 121. The list of links may be sorted based on the relevance scores determined by ranking component 122. Document locator 121 may initially locate documents from a document corpus stored in database 130 by comparing the terms in the user's search query to the documents in the corpus. In general, processes for indexing web documents and searching the indexed corpus of web documents to return a set of documents containing the searched terms are well known in the art. Accordingly, this functionality of document locator 121 will not be described further herein. Ranking component 122 assists search engine 120 in returning relevant documents to the user by ranking the set of documents identified by document locator 121. This ranking may take the form of assigning a numerical value, called a relevance score, corresponding to the calculated relevance of each document identified by document locator 121. There are a number of suitable rariking algorithms known in the art, one of which is described in the article by Brin and Page, as mentioned in the Background of the Invention section of this disclosure. Alternatively, the functions of ranking component 122 and document locator 121 may be combined so that document locator 121 produces a set of relevant documents each having rank values. As used herein, a document is to be broadly interpreted to include any machine-readable and machine-storable work product. A document may be an email, a file, a combination of files, one or more files with embedded links to other files, etc. In the context of the Internet, a common document is a Web page. Web pages often include content and may include embedded information (such as meta information, hyperlinks, etc.) and/or embedded instructions (such as Javascript, etc.). OPERATION OF SEARCH ENGINE 120 Consistent with an aspect of the invention, links to sets of web documents returned by search engine 120 may include, in addition to text snippets that describe the web documents, a visual cue that informs the user that the web document is likely to be relevant to the user's search query. The visual cue may include graphic information through which the user can quickly and easily verify whether the link is the link that the user intended to locate. In one aspect of the invention, the link corresponding to a document that is determined to be "highly relevant" (i.e., a high confidence that the document is the document that the user would be most interested in viewing) to the user search query is displayed with the visual cue. Fig. 2 is a diagram illustrating a document 200 that includes links to web documents that may be displayed to a user at a client device 102 in response to a search query. The document may be generated by search program 120 in response to the user search query and displayed by a web browser at one of client devices 102. In the exemplary document shown in Fig. 2, a search query 201 entered by the user was "Stanford." Document 200 includes a number of links 210, 211, 212, 213, and 214 to web documents, such as web pages, that search engine 120 determined to be potentially relevant to search query 201. In addition to the returned links 210-214, document 200 may include other information, such as the general category 215 and current events/news links 216 that correspond to search query 201. The user may select any of links 210-214 to thereby direct the web browser to return the web document pointed-to by the links. Each of links 210-214 may also include, for example, a snippet of text 220 that describes the linked web document and a description of a category 221 in which the web document is classified. Consistent with an aspect of the invention, one or more of the links 210-214 may contain a visual cue 230 corresponding to the link. In the example shown in Fig. 2, visual cue 230 is a miniaturized ("thumbnail") rendering of the web page corresponding to link 210. In this example, search query 201 was "Stanford." Search engine 120 determined that the most highly ranked link for "Stanford" is the link to the web site of Stanford University (stanford.edu). Accordingly, search engine 120 included visual cue 230 in document 200. In some implementations, search engine 120 may only display visual cues 230 when a link is determined to be "very relevant" to the search query, where "very relevant" is defined by an objective standard for determining relevancy. For example, assume that the large majority of "Stanford" search queries eventually result in the user selecting the stanford.edu link. In this situation, search engine 120 may realize that stanford.edu is a very relevant link and therefore include visual cue 230 in document 200. By including visual cue 230 with very relevant links, users may learn to associate the visual cue with links that search engine 120 is confident matches the user's intentions. As the users begin to trust visual cue 230, the visual cue allows the user to home in on the relevant search results faster as they will not necessarily need to read the corresponding snippet 220. This may thus result in a decreased "time to satisfaction" for the user and a concomitant increase in search engine satisfaction. Fig. 3 is a flow chart illustrating operation of search engine program 120 consistent with an aspect of the invention. Search engine program 120 may begin by receiving a search query from one of users 105 (act 301). Based on the search query, document locator 121 may generate a set of links to documents that are relevant to the search query (act 302). The set of links may be sorted based on a relevance metric returned for each of the documents from ranking component 122 (act 303). Search engine program 120 may determine whether any of the links returned by document locator 121 are associated with "very relevant" documents (act 304). Documents that are determined to be very relevant may be associated with a visual cue, such as visual cue 230 (act 305). Server device 110 may then return the set of links to the user that entered the search query (act 306). The returned set of links may be transmitted as a web document formatted in a manner similar to document 200, and may particularly include visual cues 230 associated with the very relevant documents. Fig. 4 is a block diagram conceptually illustrating the determination of whether a document is very relevant by search engine program 120. Whether a particular document, D, is very relevant may depend on a number of parameters. In one implementation, these parameters may be calculated by search engine program 120 and are shown in Fig. 4 as components 401-404. These components include the position of the document D in the ranked list of documents (component 401), the observed historical user click through rate compared to the other documents in the ranked list of documents (component 402), the relevance score for the document relative to the relevance scores for the other documents in the ranked list of documents (component 403), and whether the document is detected as being a pornographic document (component 404). Component 401 may be determined directly based on the sorted set of links returned from ranking component 122. In general, a document at the top of the sorted list is more likely to be a very relevant document than a document further down on the list. Component 402 may be based on a historical click through rate of other users in response to the links in the returned set of links. For example, search engine program 120 may calculate a ratio between document D and each other document in the returned set of links. The ratio may be calculated, for each other document E, as: D E , (1) where D represents the total number of times users have selected document D and E represents the total number of times users have selected document Ε. Thus, for each document Ε, the ratio gives the popularity of document D relative to document Ε. In an alternate implementation of formula (1) for measuring historical click through rates, E* may be defined to represent the total number of times users have selected document D for a particular query Q and R may be defined as the number of times users clicked on any document for query Q. Component 403 may relate the relevance score for document D, as returned from ranking component 122, to the relevance score of each document Ε. For example, component 403 may store the differences between the relevance scores of document D and the relevance scores of the other documents. Component 404 may store determinations of whether the document D is a pornographic document. This determination can be made based on, for example, key word comparison, domain name matching, manually entered information, etc. Based on one or more of the parameters stored by components 401-404, decision component 410 determines whether to classify the document D as very relevant. This classification may be based on a number of functions that use the parameters stored by components 401-404. In one implementation, decision component 410 determines document D is very relevant when: (1) document D's position is first in the ranked list of results (determined based on component 401), (2) document D has a high click through rate, as may be determined by a pre-selected click through threshold (determined based on component 402), and (3) the relevance score for document D is significantly greater than the next highest relevance score in the returned set of documents (determined based on component 403). In some implementations, decision component 410 may additionally require that (4) document D is not classified as a pornographic document (determined based on component 404). The specific threshold values for the high click through rate (2) and the differences between relevance scores (3) may be determined by one of ordinary skill in the art via trial and error techniques. Other functions, based on one or more of components 401 -404, may be used by decision component 410 to determine whether a document is very relevant. For example, there may be a tradeoff between how high the click through rate for document D should be and how high the relevance score for document D should be. A high relevance score for document D is generally a good indication that document D is a good result. Accordingly, when document D has a high relevance score and is in the first position in the ranked list, decision component 410 may accept a moderate click through rate for document D and still classify the document as very relevant. On the other hand, if the relevance score for document D is low, decision component 410 may require a much higher click through rate and that the document is in the first position before classifying the document as very relevant. A similar tradeoff can be made with the click through rate and the difference in relevance scores between document D and the second place document in the ranked list. In general, one of ordinary skill in the art will recognize that other functions based on the parameters associated with components 401-404, or based on other parameters, can be used to determine whether a document is highly relevant. Further, one of ordinary skill in the art will recognize that a number of modifications are possible to the above-discussed techniques for displaying visual cues for select documents. For example, instead of rendering the thumbnails in real-time, the thumbnails may be pre-rendered for documents that have a high click through rate. Thus, documents that are likely to be displayed with a visual cue can be quickly returned to the user without having to first generate the thumbnail. Further, visual cues other than thumbnails may be presented to the users. For example, other forms of highlighting, such as a logo, contrasting textual fonts (e.g., text contrasted by size, color, or weight) that are designed to stand out, contrasting backgrounds, or textual labels may be used in place of thumbnails. Additionally, parameters other than the above-described parameters may be used by decision component 410. For example, a parameter related to the click through rate may be defined as the historical ratio of the number of times that users have selected document D after submitting a query to the number of times that the query was submitted. Yet another parameter that could be used by decision component 410 is based on the text of the hyperlinks that connect web documents. In particular, this parameter may be based on the number of links pointing to document D in which the text that describes the link matches the search query. This number may be compared to the number of links pointing to the other documents in the returned set of documents in which the text of the link matches the search query.

SUMMARY As described herein, a search engine includes a decision component that determines whether documents are highly relevant. A highly relevant document may indicate that the search engine is confident that the user who entered the search query will be interested in the document. Such documents may then be associated with a visual cue that draws the user's attention and assists the user in analyzing links returned in response to the search query. It will be apparent to one of ordinary skill in the art that aspects of the invention, as described above, may be implemented in many different forms of software, firmware, and hardware in the implementations illustrated in the figures. The actual software code or specialized control hardware used to implement aspects consistent with the present invention is not limiting of the present invention. Thus, the operation and behavior of the aspects were described without reference to the specific software code—it being understood that a person of ordinary skill in the art would be able to design software and control hardware to implement the aspects based on the description herein. The foregoing description of preferred embodiments of the present invention provides illustration and description, but is not intended to be exhaustive or to limit the invention to the precise foπn disclosed.

Modifications and variations are possible in light of the above teachings or may be acquired from practice of the invention. No element, act, or instruction used in the description of the present application should be construed as critical or essential to the invention unless explicitly described as such. Also, as used herein, the article "a" is intended to include one or more items. Where only one item is intended, the term "one" or similar language is used. The scope of the invention is defined by the claims and their equivalents.