Reranking and increasing the relevance of the results of searches

Background of the invention The present invention relates to a technique for re-ranking and re-ranking the relevance of Internet search results, more specifically to re-rank and re-rank the relevance of Internet search results using a conceptual network. Regarding technology.

With the advent of the large number of web pages and media content available to users on the Internet and the World Wide Web, it is necessary to give users an streamlined approach to filtering the web to obtain the desired information. It came out. Search systems and processes have been developed to meet the user's need to obtain the desired information. Examples of such technologies can be accessed through Yahoo !, Google and other sites. Typically, the user enters a query and the search process returns one or more search results (links) associated with the query. The search results returned may be very relevant to what the user was actually looking for, or may be completely irrelevant. The relevance of search results to a query can, in part, be a function of the actual query entered and also a function of the robustness of the search system used (the underlying collection system).

Humans do not think in queries. They are, in part, artificial constructs that have been forced to query search engines or look up library catalogs. Humans also do not think of just one word by nature. The human way of thinking is a natural concept.

<p> Search queries usually contain several words that define one or more concepts. Typically, some of the words in a search query are more relevant than others in terms of concept definition. Search engines have no way of knowing which words in a search query are most relevant to the user's intent. As a result, search engines typically return many search results that are not relevant to the user's intent.</p><p> Search engines typically rank search results according to their relevance to search queries. Search queries often contain extra words that cause search engines to return irrelevant search results. Search engines often rank irrelevant search results high in the list of search results.</p><p> Therefore, it is desirable to provide an Internet search technique for enhancing the relevance of search results to the user's original intentions.</p>

<p> Outline of the invention The present invention provides a technique for enhancing the relevance of Internet search results to the user's intentions. The present invention also provides a technique for re-ranking the search results of a search query by determining the relevance of the search results to units, unit associations, and unit extensions in the search query.</p><p> Search queries are first parsed into individual units. Each unit corresponds to one or more words that represent the concept of nature. Associative units are two or more units that appear together in a search query, but are not related enough to form a new unit. <u style="single">(Extended)</u>Units are two or more units that appear together in a search query and are sufficiently related to form one new unit.</p><p> The present invention analyzes a conceptual network to identify unit-related concepts in search queries. A concept network connects concepts that are related to each other. Specific concepts are selected from the concept network based on their relevance to the units in the query.</p><p> According to one embodiment, a concept is selected from the concept network based on how often the concept appears in previously submitted search queries. Concepts that appear more frequently in previous search queries are selected from among the concepts selected from the concept network. An individual internet search is performed for one or more related concepts selected from the concept network.</p><p> Search results from each of the individual searches are compared to the search query and sorted according to their relevance to the query. Search results may be sorted based on their relevance to units, associative units, and extension units in the original search query.</p>

Other objectives, features and advantages of the present invention will become apparent by considering the following detailed description and accompanying drawings. In the figure, similar reference numerals represent similar features.

Detailed description of the invention FIG. 1A provides a comprehensive overview of the information acquisition and communication network 100, including the client system 120 according to an embodiment of the present invention. In computer network 100, the client system 120 is a plurality of server systems 150 over the Internet 140 or other communication networks, for example through any LAN or WAN connection.₁-150_NCan communicate with. For example, the client system 120 can communicate with the search results server 160. As described herein, the client system 120 is the server system 150.₁-150_NAnd 160 are configured in accordance with the present invention to access, receive, obtain, and display media content and other information such as web pages and websites to communicate with any of 160.

Some elements of the system shown in Figure 1A include conventional well-known elements that do not need to be described in detail here. For example, the client system 120 may include a desktop personal computer, workstation, laptop, PDA, mobile phone or any WAP capable device, or other computing device that can interface directly or indirectly to the Internet. Typically, the client system 120 is an HTTP client, such as Microsoft's Internet Explorer® browser, Netscape Navigator® browser, Modilla® browser, Opera® browser, or mobile phone, PDA. Alternatively, in the case of other wireless devices, by executing a browsing program such as a WAP-compatible browser, the user of the client system 120 can use the server system 150 via the Internet 140.₁-150_NYou can access, process and browse the information and pages available from.

The client system 120 also typically includes one or more user interface devices 122 such as a keyboard, mouse, touch screen, pen, etc., and the server system 1 50₁-150_NOr interact with a graphical user interface (GUI) provided by the browser on a display (eg, monitor screen, LCD display, etc.) in relation to pages, forms and other information provided by other servers. The present invention is suitable for use on the Internet, which refers to a particular global internetwork of networks. However, it is understood that other networks such as intranets, extranets, virtual private networks (VPNs), non-TCP / IP based networks, any LAN or WAN can be used in place of or in addition to the Internet. Will be done.

According to one embodiment, the client system 120 and all its components are centrally processed, such as Intel Pentium® (Intel Pentium®) processors, AMD Athlon® (Athlon®) processors. It can be operator configured using an application containing computer code that runs on a processor or multiple processors. As described herein, the computer code for operating and configuring the client system 120 to communicate, process, and display data and media content is preferably downloaded and stored on a hard disk. The entire or part of the program code may be stored on any other volatile or non-volatile memory medium or device known as ROM or RAM, or compact disc (CD) media, digital multifunction disc (DVD). It may be given on any medium that can store the program code, such as a medium, a floppy (registered trademark) disk, or the like.

In addition, the entire or part of the program code is a software source, eg server system 150.₁-150_NIt may be transmitted and downloaded from one of the well-known to the client system 120 over the Internet, or using any well-known communication medium and protocol (eg TCP / IP, HTTP, HTTPS, Ethernet®, etc.). As is well known, it may be transmitted through other conventional network connections (eg, extranet, VPN, LAN, etc.). The computer code to realize this aspect of the invention is on a client system, such as C, C +, HTML, XML, Java® and Java® Script, and some scripting language such as VBS script. It will be recognized that any programming language that can be run on is feasible. In some embodiments, the code is not downloaded to the client system 120 and the required code is either executed by the server or the code already in the client system 120 is executed.

According to one embodiment, the client application (represented as module 125) running on the client system 120 is the server system 150.₁-150_NIncludes instructions that control the client system 120 and its components to communicate with and 160 and process and display the data content received from it. In addition, the client application module 125 includes various software modules for processing data and media content. For example, application module 125 has search module 126 for processing search requests and search result data, and for making data and media content text, data frames, and active windows, such as browser windows and dialog boxes. It may include one or more of the user interface module 127 and the application interface module 128 for interacting and communicating with various applications running on the client 120. Further, the interface module 127 may include a browser such as the client system 120 or a default browser configured on a different browser.

According to one embodiment, the search result server 160 sends the search results to the client system 120. Configured to provide data and media content, server system 150 provides data and media content, such as web pages, to client system 120 in response to a link selected in a search result page provided by, for example, server system 160. Is configured. The server system 160 in one embodiment references various collection techniques for collecting information from the World Wide Web and populating one or more indexes, such as pages and links to pages. Such collection techniques include automatic web crawlers and spiders, as well as manual or semi-automatic classification algorithms and interfaces for classifying and ranking web pages within a hierarchical structure. In some aspects, the server 160 also consists of search-related algorithms for processing and ranking web pages, such as Google's PageRank algorithm. Server 160 is also preferably configured to record search queries in the form of query log files.

The server system 160 in one aspect is configured to provide data from the client system in response to various search requests specifically received from the search module 126. Server systems 150 and 160 are a single organization, such as Yahoo! It may be part of a single organization, such as a distributed server system as provided to users by Inc.), or part of a heterogeneous organization. Server systems 150 and 160 each include at least one server and associated database system, but may include multiple servers and associated database systems, and are shown as a single block but geographically dispersed. It may have been done. For example, all of the servers in Server System 160 may be located close to each other (eg, in a server farm located in a single building or campus) and far from each other (eg, one in City A). It may be distributed among the above servers and one or more servers in City B). As used herein, the term "server system" typically refers to one or more logically and / or physically connected servers that are distributed locally or across one or more geographic locations. Including. In addition, the term "server" typically includes computer systems and related storage systems and database applications, as is well known in the art. Here, the term "server" and the term "server system" are used interchangeably.

According to one embodiment, the server 160 includes an algorithm that provides search results to the user in response to a search query received from the client system 120. According to one embodiment of the invention, the server system 160 is configured to enhance the relevance of search queries received from the client system 120, as described in detail below.

FIG. 1B shows an outline of an Internet search system that realizes an embodiment of the present invention. Search query 170 is sent to search engine 175 to initiate an internet search (eg web search). Search engine 175 finds web content from search corpus 190 that matches search query 170. The search corpus 190 represents content that is accessible via the World Wide Web, the Internet, intranets, local networks, and wide area networks.

The search engine 175 retrieves the content that matches the search query 170 from the search corpus 190 and sends the matching content (ie, the search results) to the page assembler 180. The page assembler 180 sorts the search results according to their relevance to the search query and assembles the results in an order that is easily visible to the user. The most relevant search results are displayed to the user on the search result display screen 185.

The present invention provides a technique for enhancing the relevance of Internet search results to the user's intentions. FIG. 2 shows an example of a method according to an embodiment of the present invention. Shown in Figure 2 It should be understood that the particular steps taken are not intended to limit the scope of the invention. A number of modifications to the method of FIG. 2 are included within the scope of the invention.

A user may initiate an internet search (eg, a web search) by entering a search query. The system of the present invention receives a search query from the user in step 221 as shown in FIG. The search query is then parsed into units in step 222.

Search queries can be broken down into components called units. The query processing engine uses statistical methods to break down search queries into units. A unit is a sequence of one or more words that typically corresponds to a natural concept such as "New York City" or "Bird of Prey." Further details of the technique for generating conceptual units from search queries can be found in Shyam Kapur's November 12, 2003, co-pending, commonly assigned U.S. patent application. It is described in No. 10 / 713,576, but this is incorporated by reference.

A concept network is a structure that shows the relationships between related concepts. Each unit in the search query is located in the conceptual network. The concept network is used to identify concepts related to the search query unit. After the search query unit is located in the conceptual network, the concept in the conceptual network associated with the unit is selected in step 223.

Concept networks can connect related concepts using a number of technologies. According to one embodiment of the invention, the conceptual network connects concepts that are synonyms, concepts that have a more specific meaning, concepts that have a more general meaning, specific real-world examples of concepts, and , A well-known phrase or name that seems to be similar to the concept or uses several of the same words.

Using the example shown in Figure 3A, if the unit in the search query is a skyscraper, the system locates the concept "skyscraper" in the concept network and identifies related concepts. Figure 3A shows an example of a conceptual network for skyscrapers. In this conceptual network, the concept "skyscraper" is linked to more general terms such as "building" and "building". Skyscrapers are also linked to the similar phrase "high-rise buildings" and the famous example of skyscrapers "Empire State Building".

According to another embodiment, a previously submitted search query is analyzed to determine how often related concepts in the concept network appear together in the previously submitted search query. The concept network may be constructed by concatenating the concepts that appear together in a previously sent search query. In step 223, the most frequently co-occurring related concepts in the previously submitted search query are selected in the concept network. All previously submitted search queries are stored in memory for analysis.

The concept network may be based on the concepts that appear together in the queries sent by all users. As another example, a conceptual network or any part thereof is a session-based conceptual network that concatenates concepts that appear together in a search query submitted by one particular user (or group of users). You may. The most frequently co-appearing related concepts in a previously submitted search query are selected in step 223.

Figure 3B shows an example of a session-based conceptual network. In Figure 3B, the main concept "Jaguar" is linked to the related concepts "luxury car", "XYZ car company", and "car racing", because certain users have associated "jaguar" with cars in the past. This is because we sent a query that links to the concept of For example, a different user may have sent a previous query indicating that the user is interested in animal jaguars. For this user, the invention forms a different conceptual network that connects "jaguars" to animal-related concepts such as cats, zoos, or safaris.

According to another embodiment of the invention, a concept network can concatenate the most frequently co-appearing concepts in previous queries sent by one or more users during a particular time period. Figure 3C shows an example of a time-limited conceptual network. In this example, the concept "Jane Do" is linked to the related concepts "Jane Do Live Performance", "Jane Do Music CD" and "Instrumental Music". These related concepts are the ones that most frequently appear with "Jane Do" in previous search queries over a period of time. The particular period may be, for example, the last 24 hours, the last week, or the last month.

In the example in Figure 3C, the concept network is based on the concept associated with a singer named Joe Doe, based on the most popular search queries in the last 24 hours. During the next 24 hours, the most popular search queries, including "Jane Doe," may be associated with a politician of the same name. Figure 3D shows how the conceptual network for "Jane Do" changes to include links to related concepts "US Senator Jane Do" and "Doe Initiative". The concept network is updated with the unit "Jane Do" to include the most frequently occurring concepts in recent queries.

According to the embodiments of the present invention, the most closely related concepts are selected from the concept network. The most closely related concepts may be, for example, all concepts that are directly linked to the main concepts in the concept network. Other concepts may be indirectly linked to the main concept through one of the directly linked concepts. Figure 3C shows an example of an indirect connection between the concept "Jane Do" and the concept "Violin" through the concept "Instrumental Music".

Figures 3A through 3D show only a few examples of the relationships that connect concepts in a conceptual network. These examples are provided for illustrative purposes only and are not intended to limit the scope of the invention. Many other relationships between concepts in a concept network are possible.

The selection process performed in step 223 may be based on any criteria. For example, the top five related concepts that appear most frequently from the concept network may be selected in step 223. As another example, the top 50% or top 25% of the most frequently occurring related concepts may be selected in step 223. Many other selection techniques can be used according to this invention. The examples described herein are provided to illustrate the principles of the invention and are not intended to limit the scope of the invention.

At step 224, an independent internet search (eg, web search) is performed for one or more related concepts selected in step 223. For example, if there are four units in the search query and one related concept is selected for each unit in step 223, then four independent internet searches are performed in step 224. According to one embodiment, if a large number of related concepts are selected in step 223, the internet search will only be performed on a subset of the concepts. for example For example, if 20 concepts are selected in step 223, the internet search will be performed only on the top 5 concepts related to all the concepts of the unit in the search query.

Search engine 175 can perform an independent internet search for the concept selected in step 223. The internet search may be performed using any well-known internet search technique (eg, using Google or Yahoo search techniques).

In step 224, a separate set of search results is obtained for each individual Internet search performed by search engine 175. Search engine 175 typically sorts the search results for each Internet search according to their relevance to each related concept.

In step 225, the invention reranks the search results obtained from the internet search performed in step 224. Search results obtained from an internet search may be grouped with search results obtained from an internet search performed on the entire original search query.

Each search result is compared to the unit, unit association, and unit extension in the original search query. Each search result is ranked or scored based on its relevance to the original search query.

The relevance of the search results to the original search query can be determined by comparing the units, associative units and extension units in the query with the search results. Associative units are two or more units that appear together in a search query, but are not related enough to form one new unit. Extending units are two or more units that appear together in a search query and are sufficiently related to form one new unit.

The search results are analyzed to determine how often units, unit associations, and unit extensions from the search query appear in the search results. Search results are given new scores based on the frequency (or relative frequency) that illustrates the units, associative units, and / or extension units that appear in the search results. Search results that include more cases of units, associative units, and / or extension units are given higher scores.

According to one embodiment of the present invention, the search results obtained in the Internet search are re-ranked. According to the re-ranking process, a re-ranking score is given for each of the search results. The re-ranking score is calculated, for example, by multiplying the original ranking score given by search engine 175 by a new score calculated based on the frequency of query units, associative units and extension units in the search results. You may. The search results are then sorted based on the reranking score.

Search results obtained from certain types of search queries may be given a higher score in step 225. For example, search results obtained from a navigational query may be ranked higher than search results obtained from other types of queries. The high score given to a navigational query is based on the perception that the navigational query generally gets more relevant search results.

Once reranked scores, each search conclusion based on their relevance to the original search query Given the result, in step 225, the search results are sorted from the highest reranking score to the lowest reranking score. The highest reranking score represents the content that is most relevant to the original search query, and the lowest reranking score represents the content that is least relevant to the original search query.

The present invention enhances the relevance of search results obtained from an internet search by locating content that matches the concept associated with the unit in the search query. The concept is selected from the concept network as described above. Search results are then combined with search results from standard Internet searches based on the entire search query and sorted according to their relevance to the search query.

By increasing the number of search results using a conceptual network, at least some search results can be very relevant to the search query and the user's intent, regardless of the user's intent. .. Search results are sorted based on their relevance to the query, so the most relevant results are displayed first. Using these techniques, the invention can identify more relevant search results.

Although the present invention has been described for a particular embodiment, modifications, various modifications, and alternatives are intended in the present invention. In some examples, the features of the invention can be used without the corresponding use of other features without departing from the scope of the invention described. Thus, many modifications can be made to fit the particular configuration or method disclosed without departing from the essential scope and spirit of the invention. It is intended that the invention is not limited to the particular embodiments disclosed, but that the invention includes equivalents within the scope of all embodiments and claims.

<figref num="1A">It is a figure of the Internet communication system which can realize the Example of this invention.</figref><figref num="1B">It is a figure of the Internet search system which can realize the Example of this invention.</figref><figref num="2">It is a flowchart which shows the method for enhancing the relevance of the Internet search result according to the Example of this invention.</figref><figref num="3A">It is a figure which shows the example of the conceptual network which can be used for processing the search query according to this invention.</figref><figref num="3B">It is a figure which shows the example of the conceptual network which can be used for processing the search query according to this invention.</figref><figref num="3C">It is a figure which shows the example of the conceptual network which can be used for processing the search query according to this invention.</figref><figref num="3D">It is a figure which shows the example of the conceptual network which can be used for processing the search query according to this invention.</figref>