Systems and methods for providing search query refinements

A system and method for generating query refinement suggestions may include collecting refinement data for at least one received source query. The collected refinement data is then clustered to form at least one cluster. At least one potential refinement query suggestion is identified from the refinement data within the at least one cluster.

FIELD OF THE INVENTION

The present invention relates in general to query processing and, in particular, to a system and method for providing search query refinements.

BACKGROUND OF THE INVENTION

Although the Internet traces back to the late 1960s, the widespread availability and acceptance of personal computing and internetworking have resulted in the explosive growth and unprecedented advances in information sharing technologies. In particular, the Worldwide Web (“Web”) has revolutionized accessibility to untold volumes of information in stored electronic form to a worldwide audience, including written, spoken (audio) and visual (imagery and video) information, both in archived and real-time formats. In short, the Web has provided desktop access to every connected user to a virtually unlimited library of information in almost every language worldwide.

Search engines have evolved in tempo with the increased usage of the Web to enable users to find and retrieve relevant Web content in an efficient and timely manner. As the amount and types of Web content have increased, the sophistication and accuracy of search engines have likewise improved. Generally, search engines strive to provide the highest quality results in response to a search query. However, determining quality is difficult, as the relevance of retrieved Web content is inherently subjective and dependent upon the interests, knowledge and attitudes of the user.

Existing methods used by search engines are based on matching search query terms to terms indexed from Web pages. More advanced methods determine the importance of retrieved Web content using, for example, a hyperlink structure-based analysis, such as described in S. Brin and L. Page, “The Anatomy of a Large-Scale Hypertextual Search Engine,” (1998) and in U.S. Pat. No. 6,285,999, issued Sep. 4, 2001 to Page.

A typical search query scenario begins with a search query being submitted to a search engine. The search engine executes a search against a data repository of potentially retrievable Web content and identifies the candidate Web pages. Searches can often return thousands or even millions of results, so most search engines typically rank or score the results to obtain only the most promising results. The top Web pages are then presented to the user, usually in the form of Web content titles, hyperlinks, and other descriptive information, such as snippets of text taken from the Web pages.

Providing quality search results can be complicated by the literal and implicit scope of the search query itself. A poorly-framed search query could be ambiguous or be too general or specific to yield responsive and high quality search results. For instance, terms within a search query can be ambiguous at a syntactic or semantic level. A syntactic ambiguity can be the result of an inadvertent homonym, which specifies an incorrect word having the same sound and possibly same spelling, but different meaning from the word actually meant. For example, the word “bear” can mean to carry or can refer to an animal or an absence of clothing. A semantic ambiguity can be the result of improper context. For example, the word “jaguar” can refer to an animal, a version of the MACINTOSH operating system, or a brand of automobile. Similarly, search terms that are too general result in overly broad search results while search terms that are too narrow result in unduly restrictive and non-responsive search results.

Accordingly, there is a need for an approach to providing suggestions for search query refinements that will resolve ambiguities, over generalities, or over specificities occurring in search queries. Preferably, such an approach would provide refined search queries that, when issued, result in search results closely related to the actual topic underlying the intent of the original search query and provide suggestions that reflect conceptual independence and clear meanings as potential search terms.

SUMMARY OF THE INVENTION

According to one aspect, a method for generating query refinement suggestions may include collecting refinement data for at least one received source query; clustering the collected refinement data to form at least one cluster; and identifying at least one potential refinement query suggestion from the refinement data within the at least one cluster.

According to still another aspect a method includes reviewing historical query data to identify source queries and associated refinement queries to generate refinement data. The refinement data includes a number of source query/refinement query associations. The method further includes clustering the refinement data to form at least one cluster and identifying at least one potential refinement query suggestion from the refinement data within the at least one cluster.

DETAILED DESCRIPTION

The following detailed description of the invention refers to the accompanying drawings. The same reference numbers in different drawings may identify the same or similar elements. Also, the following detailed description does not limit the invention.

Overview

The quantity of documents becoming searchable via search engines is substantially increasing. Accordingly, search queries which may be submitted to locate relevant documents may more easily suffer from potential ambiguities or generalities. It is beneficial to identify and provide search query refinements which may remedy the initial query deficiencies. As described herein, search query refinements may be generated and suggested to assist the user in more quickly and more accurately identifying desirable search results. More specifically, refinement data may be collected based on a received source query. The collected refinement data may be grouped and scored to identify potential refinement suggestions.

Exemplary Network Configuration

FIG. 1is a block diagram showing a system100for providing search query refinements, in accordance with the present invention. System100may include multiple individual clients104communicatively interfaced to a server102via a network106, such as the Internet, or other form of communications network, as would be recognized by one skilled in the art. Individual clients104may be operated by users118who transact requests for Web content and other operations through their respective client104. Three clients104and one server102have been illustrated as connected to network106for simplicity. In practice, there may be more or fewer clients and servers. Also, in some instances, a client may perform the functions of a server and a server may perform the functions of a client.

In general, each client104can be any form of computing platform connectable to a network, such as network106, and capable of interacting with application programs. Exemplary examples of individual clients include, without limitation, personal computers, digital assistances, “smart” cellular telephones and pagers, lightweight clients, workstations, “dumb” terminals interfaced to an application server, and various arrangements and configurations thereof, as would be recognized by one skilled in the art. Network106may include various topologies, configurations, and arrangements of network interconnectivity components arranged to interoperatively couple with enterprise, wide area and local area networks and include, without limitation, conventionally wired, wireless, satellite, optical, and equivalent network technologies, as would be recognized by one skilled in the art. Server102may include server entities that gather, process, search, and/or maintain documents in a manner consistent with the principles of the invention.

For Web content exchange and, in particular, to transact searches, each client104may execute a Web browser application116(“Web browser”), which preferably implements a graphical user interface and through which search queries are sent to a Web server120executing on the server102. Typically, each search query describes or identifies information, generally in the form of Web content, which is potentially retrievable via the Web server102. The search query provides search characteristics, typically expressed as individual terms, such as keywords and the like, and attributes, such as language, character encoding and so forth, which enables a search engine122, also executing on the server102, to identify and send back search result documents, generally in the form of Web pages. Other styles, forms or definitions of search queries and characteristics are feasible, as would be recognized by one skilled in the art.

In response to search engine execution, the Web pages may be sent back to Web browser116for presentation, usually in the form of Web content titles, hyperlinks, and other descriptive information, such as snippets of text taken from the Web pages. The user may then view or access the Web pages on the graphical user interface and can input selections and responses in the form of typed text, clicks, or both. In one implementation, server102maintains a search database110in which Web content124is maintained. In an alternative embodiment, Web content124may also be maintained remotely on other Web servers (not shown) interconnected either directly or indirectly via the network106and which are preferably accessible by each client104. In a further embodiment, server102may maintain a cache126in which cached documents128and cached queries130are maintained. More specifically, cache126associates each cached document128with one or more cached queries130to improve searching performance, as is known in the art. Finally, in a still further embodiment, search engine122may maintain a query log132in which records of previous search queries134are tracked.

In one embodiment consistent with principles of the invention, search engine122preferably identifies Web content124best matching the search characteristics to provide high quality Web pages. In identifying matching Web content124, search engine122operates on information characteristics describing potentially retrievable Web content. Note the functionality provided by server120, including Web server120and search engine122, could be provided by a loosely- or tightly-coupled distributed or parallelized computing configuration, in addition to a uniprocessing environment.

A “document,” as the term is used herein, is to be broadly interpreted to include any traditional printed work of authorship, such as books, magazines, catalogs, newspapers, articles, etc. A “web document,” as the term is used herein, is to be broadly interpreted to include any machine-readable and machine-storable work product available via a network, such as network106. A web document may include, for example, a web site, a file, a combination of files, one or more files with embedded links to other files, a news group posting, a blog, a web advertisement, etc. In the context of the Internet, a common web document is a web page. Web pages often include textual information and may include embedded information (such as meta information, images, hyperlinks, etc.) and/or embedded instructions (such as JAVASCRIPT, etc.). A “link,” as the term is used herein, is to be broadly interpreted to include any reference to or from a web document.

Search queries can potentially be ambiguous or lack generality or specificity. Such poorly-framed search queries can be remedied through search query refinements, which can be provided in response to search query issuances. In accordance with one aspect of the invention, search query refinements may be generated and suggested to assist the user in more quickly and more accurately identifying desirable Web content124.

FIG. 12is an exemplary diagram of a graphical user interface1200containing results of a search performed on an initial source query1202according to an implementation consistent with the present invention. In this example, a search on initial source query1202has resulted in a number of refinement suggestions1204being initially presented to the user. By clicking on any of the underlined query refinement suggestions1204, the user may perform a search on the selected suggestion, thereby refining their search. In addition to refinement suggestions1204, conventional search results1206indicative of web content124may also be provided.

The individual computer systems, including server102and clients104, include general purpose, programmed digital computing devices consisting of a central processing unit (processors107and112, respectively), random access memory (memories108and114, respectively), non-volatile secondary storage, such as a hard drive or CD ROM drive, network or wireless interfaces, and peripheral devices, including user interfacing means, such as a keyboard and display. Program code, including software programs, and data is loaded into the RAM for execution and processing by the CPU and results are generated for display, output, transmittal, or storage. Web browser116may be an HTTP-compatible Web browser, such as the INTERNET EXPLORER, licensed by Microsoft Corporation, Redmond, Wash.; NETSCAPE NAVIGATOR, licensed by Netscape Corporation, Mountain View, Calif.; or other forms of Web browsers, as are known in the art.

FIG. 2is an exemplary diagram of a client or server entity (hereinafter called “client/server entity”), which may correspond to one or more of clients104and server102, according to an implementation consistent with the principles of the invention. The client/server entity may include a bus210, a processor220, a main memory230, a read only memory (ROM)240, a storage device250, an input device260, an output device270, and a communication interface280. Bus210may include a path that permits communication among the elements of the client/server entity.

Processor220may include a conventional processor, microprocessor, or processing logic that interprets and executes instructions. Main memory230may include a random access memory (RAM) or another type of dynamic storage device that may store information and instructions for execution by processor220. ROM240may include a conventional ROM device or another type of static storage device that may store static information and instructions for use by processor220. Storage device250may include a magnetic and/or optical recording medium and its corresponding drive.

Input device260may include a conventional mechanism that permits an operator to input information to the client/server entity, such as a keyboard, a mouse, a pen, voice recognition and/or biometric mechanisms, etc. Output device270may include a conventional mechanism that outputs information to the operator, including a display, a printer, a speaker, etc. Communication interface280may include any transceiver-like mechanism that enables the client/server entity to communicate with other devices and/or systems. For example, communication interface280may include mechanisms for communicating with another device or system via a network, such as network106.

As will be described in detail below, the client/server entity, consistent with the principles of the invention, may perform certain searching-related operations. The client/server entity may perform these operations in response to processor220executing software instructions contained in a computer-readable medium, such as memory230. A computer-readable medium may be defined as a physical or logical memory device and/or carrier wave.

The software instructions may be read into memory230from another computer-readable medium, such as data storage device250, or from another device via communication interface280. The software instructions contained in memory230may cause processor220to perform processes that will be described later. Alternatively, hardwired circuitry may be used in place of or in combination with software instructions to implement processes consistent with the principles of the invention. Thus, implementations consistent with the principles of the invention are not limited to any specific combination of hardware circuitry and software.

Exemplary Processing

FIG. 3is a flow diagram of exemplary processing for providing search query refinements in response to a received user query according to an implementation consistent with the principles of the invention. Initially, refinement data is collected for plurality of source queries (act300). Additional details regarding the refinement data collection process will be set forth in detail below with respect toFIG. 4. Following collection, the collected refinement data is characterized for each source query (act302). In one implementation consistent with principles of the invention, refinement data may be characterized by creating composite term vectors representing documents returned by refinement queries. Additional details regarding the characterization process will be set forth in detail below with respect toFIGS. 5-6.

Once the refinement data for each source query has been characterized, potential refinement queries identified from the refinement data may be clustered based upon the composite term vectors of act302(act304). In this manner, potential refinement queries are grouped into related clusters. Additional details regarding the clustering process will be set forth in detail below with respect toFIG. 7. Next, the most representative refinement from each cluster identified in act304is identified (act306). Additional details regarding the clustering process will be set forth in detail below with respect toFIG. 8. In one exemplary implementation, selecting representative refinements for the query clusters may include choosing the refinement query from each cluster which occurs most frequently as identified during refinement data collection. Once selected, the clusters and their representative refinements are scored and ranked for presentation to users upon entry of the respective source query (act308). Additional details regarding the scoring and ranking process will be set forth in detail below with respect toFIGS. 9 and 10. By characterizing, clustering, and scoring previously received manual refinement queries, the above-described system is able to identify the most accurate and helpful refinement queries for display to users in response to received source queries.

FIG. 4is a flow diagram illustrating exemplary processing for collecting manual refinement data initially described in act300set forth above. Initially, processing may begin when search engine122receives a search term (or a group of search terms) from a user as an initial source query for searching a document repository (act400). In one implementation, the document repository includes documents available from the Internet and/or a database (or set of databases) and the vehicle for searching this repository is a search engine, such as search engine122(FIG. 1). In one embodiment, search engine122may receive the source query via web browser software116on a client, such as client104(FIG. 1). Upon receipt of an initial source query, search engine122logs the source query in query log132(act402) and identifies Web content124that best matches the query (act404). Server102then returns the identified Web content124to client104as an initial results set (act405).

As described above, providing quality search results can be complicated by the literal and implicit scope of the search query. Accordingly, users may wish to refine an initial source query in order resolve ambiguities, over-generalities, or over specificities occurring in properly framed search queries. Preferably, such an approach would provide refined search queries that lead to better search results for the user. Ideally, the refined search queries should be conceptually independent and have clear meaning as potential search terms.

In accordance with this manual query refinement process, search engine122may receive an additional query (“refinement query”) from the user upon viewing the initially returned results set (act406). It may next be determined whether a predetermined criteria has been satisfied indicating that the additional received query is likely a refinement query to the initial source query (act408). In one implementation consistent with principles of the invention, one such criteria may be include a predetermined time limit based upon the receipt of the initial source query. One such exemplary time limit may be two minutes, however any suitable time limit may be used, such that queries received within the time limit are likely to correspond to refinements of the initial source query.

If the criteria has been satisfied, search engine122next determines whether the initial source query has been previously received (act410). If not, an association is created between the received refinement query and the initially received source query (act412). Next, a counter associated with the refinement query is initialized to 1 indicating a first instance of a source query and subsequent refinement query (act414). Next, the associated source and refinement queries are stored in database110for subsequent usage described below (act416). However, if the initial source query had been previously received, search engine122determines whether the refinement query has been previously received as a refinement to the initial source query (act418). If so, a counter associated with the refinement query is incremented to indicate the additionally received refinement query (act420). If the refinement query has not been previously received as a refinement to the initial source query the counter associated with the refinement query is initialized to 1 indicating a first instance of a received refinement query (act422). The process then returns to act406for receipt of the next refinement query (if any). The results of the repeated steps thereby populate database110with a plurality of source query/refinement query associations for subsequent usage in generating accurate suggested refinement queries. In one implementation consistent with principles of the invention, multiple receipts of the same initial source query result in incremented count totals for the respective refinement queries. These count totals may be subsequently used in clustering and scoring the potential refinement queries to identify refinement queries suitable for presentation to users.

FIG. 5is a flow diagram illustrating an alternative implementation of processing for collecting manual refinement data. Initially, processing may begin when search engine122receives a search term (or a group of search terms) from a user as an initial source query for searching a document repository (act500). Upon receipt of an initial source query, search engine122logs the source query in query log132(act502) and identifies Web content124that best matches the query (act504). Search engine122may also identify user profile or interface information that may be used to further refine returned results (act505). In one implementation consistent with principles of the invention, user profile or interface information may include language preference (e.g., English, Spanish, etc.) or country/region interface (e.g., USA, Japan, China, etc.) variables. Server102then returns the identified Web content124to client104as an initial results set (act506).

As described above, search engine122may then receive an additional query (“refinement query”) from the user upon viewing the initially returned results set (act507). It may next be determined whether a predetermined criteria has been satisfied indicating that the additional received query is likely a refinement query to the initial source query (act508).

If the criteria has been satisfied, search engine122next determines whether the initial source query, including its associated user profile or country/region interface variables, has been previously received (act510). If not, an association is created between the received refinement query and the initially received source query based on the received source query, refinement query, and user profile or country/region interface variables (act512). Next, a counter associated with the refinement query is initialized to 1 indicating a first instance of a source query and subsequent refinement query (act514). Next, the associated source and refinement queries are stored in database110for subsequent usage described below (act516).

If the initial source query had been previously received, search engine122then determines whether the refinement query has been previously received as a refinement to the initial source query having matching user profile and/or country interface variables (act518). If so, a counter associated with the refinement query is incremented to indicate the additionally received refinement query (act520). If the refinement query has not been previously received as a refinement to the initial source query the counter associated with the refinement query is initialized to 1 indicating a first instance of a received refinement query (act522). The process then returns to act506for receipt of the next refinement query (if any). By basing stored associations on user profile and/or country interface variables, subsequent distinctions to refinement data may be made which enable data more specific to a source query to be used in generating refinement suggestions.

FIG. 6is a flow diagram illustrating one exemplary implementation of processing for characterizing refinement data described briefly above with respect to act302. The characterization process may begin by performing searches for each refinement query collected in act300and more specifically illustrated inFIG. 4to generate refinement query result sets including one or more documents (act600). As described above with respect toFIG. 5, the received refinement queries may be stored based on user profile and country/region variables to facilitate additional specificity in generating refinement suggestions. Next, for each document returned in a refinement query result set, a weight is identified for each term appearing in the document (act602). Term weights may be calculated using a number of possible techniques. One exemplary technique for generating weights bases the weights on the number of occurrences of each term within each returned document. That is, for a term occurring three times within a returned document, a weight of 3 may be assigned. More advanced weighting techniques, such as a weight based on the inverse document frequency (idf), may also be used.

The inverse document frequency (idf) of a term may be defined as a function of the number f of documents in the collection in which the term occurs and the number J of documents in the collection. In the context of a web search engine, the collection may refer to the set of web documents (e.g., web pages) indexed by the search engine. More specifically, the idf may be defined as log.

(Jf+1).
Higher idf values indicate that a term is relatively more important than a term with a lower idf value. For a web search engine, J may be on the order of 1 billion documents.

If tf is the frequency (i.e., the number of occurrences) of the term in a document, then w(tf) may be the tf weight of the term in that document. More specifically, w(tf) may be just the tf itself, or 1+log(tf), or tf/(1+tf), or any other formulation. The weight of a term for any particular document of the M documents may be defined as:
w(tf)·idf,  (1)

With this weighting technique, terms used multiple times or in multiple documents are given more weight than terms used once. Also, terms that are relatively less common are given more weight.

Following term weighting, a term vector is generated for each document returned in act600(act604). In accordance with one implementation consistent with principles of the invention, term vectors may be defined as normalized vectors projected into multi-dimensional space, with each dimension corresponding to a distinct term found in a document returned in a result set associated with one of the refinement queries. Terms may be individual words or word combination. The length of each term vector in each dimension equals the sum of the weights of the corresponding term in each returned document.

Next, the term vectors are normalized (act606). In one embodiment this may be a L2 norm, however, any suitable normalization methodology, such as an L1 norm may also be implemented. In one exemplary embodiment, the term vectors may be length normalized to a length of one, although other normalizations are possible, as would be recognized by one skilled in the art.

In accordance with one implementation consistent with principles of the invention, the generation of term vectors may be limited to a predetermined number of search results within each result set, for example, the top 10 or top 50 results for each query. In this manner, only the most relevant results are used to represent each query.

Once normalized, a composite term vector is generated for each result set returned in act600(act608). In one implementation consistent with principles of the invention, the composite term vector may be generated by adding the individual term-vectors from all the documents in the result set for the query. This may be accomplished, for example, by summing the weights from identical terms in the each document term vector. These weights from the various results are not necessarily summed equally. Rather, each document term vector may be scaled according to the relevancy of that result to the query, as estimated by search engine122. This enables the term vectors of highly relevant results to contribute more to the composite term vector for the query than the term vectors of less relevant results. In one implementation consistent with principles of the invention, such scaling can be accomplished by multiplying the weights in the term vector in each result by the search engine's relevancy score for the respective document. It should be understood that the specifics of generating a relevancy score may include any number of methodologies. In an alternative embodiment, the weights of each result may be divided by that result's position a result set ranking. For example, weights for terms within the first result would be divided by one, weights for terms within the second result would be divided by two, etc.

In one implementation consistent with principles of the invention, once the composite term vector has been generated it may be compressed and pruned by excluding those terms that have a low relative weight within the term vector. This removes what is known statistically as the “tail” of the term vector distribution.

FIG. 7is a flow diagram illustrating another exemplary implementation of processing for characterizing refinement data described briefly above with respect to act302. The characterization process may begin by performing searches for each refinement query collected in act300to generate refinement query result sets including one or more documents (act700). Next, for each search document returned in a refinement query result set, a listing of discrete search queries is identified which reference the document (act702). For example, although document X may be returned in response to source query Y, it may also be returned in response to queries Q-U. The terms within each referencing query may also be used to characterize the collected refinement data.

Following identification of each search query referencing each returned document, a term vector is created for each document based upon the terms in the identified queries which reference the document (act704). As with the embodiment ofFIG. 5, term vectors may be defined as normalized vectors projected into multi-dimensional space, with each dimension corresponding to a distinct term found in a referencing query. Terms may be individual words or word combinations. The length of each term vector in each dimension equals the sum of the weights of the corresponding term in the referencing queries. Query term weighting may be performed in a similar manner as that described above with respect toFIG. 5.

Next, the term vectors are normalized (act706) and a composite term vector is generated for each result set returned in act700(act708). As above, with respect toFIG. 5, the composite term vector may be compressed and pruned by excluding those terms that have a low relative weight within the term vector.

FIG. 8is a flow diagram illustrating one exemplary embodiment of processing for clustering refinement queries based on the composite term vectors generated in act302and described inFIGS. 6-7above. Initially, upon generation of the composite term vectors for each refinement query identified in act300, clusters are formed based on the distances (e.g., Euclidian distances) of each composite term vector from each other term vector (act800). The generated clusters are then ranked based on a count total for each refinement query in the cluster (act802). The highest ranking clusters are then selected as potential refinement clusters (act804). In one exemplary implementation, the potential refinement clusters are selected based on a predefined threshold value, although other cluster selection criteria are possible, as would be recognized by one skilled in the art. Additionally, in one implementation consistent with principles of the invention, the clusters are formed using a hierarchical agglomerative clustering algorithm, although other known forms of clustering could also be applied, as would be recognized by one skilled in the art. By clustering the identified refinement queries, several distinct groups (clusters) of queries are produced that are topically related. Additionally, the clustering process also identifies clusters that, when compared to each other, are topically/semantically different.

Different clustering techniques may also be used to cluster the representations of the refinement queries. For example, “group average” and “single link” cluster distance metrics may be implemented. Moreover, alternative clustering algorithms may also be implemented, including k-means clustering, spectral clustering, and clustering based on pairwise document compressibility. Multiple clustering methods may be combined in multiple stages: for example, by running hierarchical agglomerative clustering and then running k-means clustering on the output and number of clusters generated by the hierarchical agglomerative clustering.

FIG. 9is a flow diagram illustrating one exemplary implementation of processing for selecting representative refinements for the query clusters generated in act304and described more specifically inFIG. 8above. As described above, each generated cluster potentially contains many refinements that are very closely related. Additionally, as described above with respect toFIG. 4, each refinement query is associated with a count, which is proportional to the probability that the user would refine the original query to that specific refinement. As discussed above with respect toFIG. 3, one exemplary implementation for selecting representative refinements for the query clusters includes choosing the refinement from each cluster having the maximum count. However, some clusters may comprise looser collections of queries than others. In these instances, the overlap of the queries isn't as tight, so a refinement that is closest in meaning to the majority of the queries in the cluster may be a better representative query than a refinement that simply has the highest probability of occurring as a refinement of the original query.

In order to account for this possibility, a centroid may be computed for each cluster (act900). Each centroid represents the weighted center of the term vectors for each cluster, as a normalized sum of the product of the term vectors for each refinement query within the cluster and a relevance score assigned to the search documents generated in response to the refinement queries. Other approaches to computing centroids could also be used, including using unweighted values and by varying the forms of weighting and averaging, as would be recognized by one skilled in the art. Once cluster centroids have been generated, a score is computed for each refinement query in a cluster (act902). In one implementation, the score may be based on the refinement query's count divided by the distance of its associated term vector from the centroid of the query cluster term vector. The refinement query in each cluster having the highest score is then selected as the representative refinement query (act904).

In one alternative embodiment, various statistical measurements for the “center” or “average” of the cluster may be implemented rather than the cluster centroid defined above. More specifically, a cluster medioid may be implemented. A cluster medioid may be defined as the median of the values along all the dimensions of the term vector. Alternatively, the prior probability for each refinement query in the cluster may be combined with that refinement query's distance from the centroid using a function other than division, while still maintaining the same effect of increasing the score of a refinement that is close to the center (and more representative) of the cluster. Furthermore, a different distance function may be implemented to calculate the distance of the refinement query from the cluster center, rather than Euclidian distance as described above.

FIGS. 10 and 11are flow diagrams illustrating exemplary implementations of processing for scoring and ranking the clusters and their representative refinement query as briefly described above in act308. Ranking and scoring of the clusters is then used to decide which refinement queries should be displayed to the user, since even after the selecting a representative refinement query for each cluster, there may exist more refinement queries than it is possible or useful to display.

In one exemplary implementation consistent with principles of the invention, refinement query counts for all refinement queries within a cluster are identified (act1000). Next, a cluster score is generated by summing the identified refinement query counts (act1002). In this embodiment, the resultant number is proportional to the total probability that after typing the original query, the user would manually refine the source query to a query in that query cluster. All clusters generated may then be ranked according to their respective cluster scores (act1004). Representative queries from a predetermined number of clusters may then be selected for display to users based on their respective rankings (act1006).

In the implementation ofFIG. 11, refinement query counts for all refinement queries within a cluster are also initially identified (act1100). Next, a cluster score is generating by summing the identified refinement query counts and dividing by the cluster's compactness (act1102). In one implementation consistent with principles of the invention, compactness may be defined as the standard deviation of the Euclidian distance of each refinement query term vector in the cluster from the cluster centroid. In practice, the standard deviation of refinement queries in the cluster from the centroid will be low if the cluster is a very tight cluster. Conversely, if the cluster is extremely disparate, the standard deviation will be quite high. Consequently, by dividing the score by the standard deviation, the score for clusters that are extremely tight around their centroids is elevated. Accordingly, the likelihood is increased that the higher scoring clusters have a tight coherent meaning, and are therefore more beneficial to display to users. Conversely, lower scoring clusters are more likely to contain a number of queries having high counts but which are ill-defined. The clusters are then ranked according to their respective cluster scores (act1104). Representative queries from a predetermined number of clusters may then be selected for display to users based on their respective rankings (act1106).

Although the standard deviation has been described above to define the compactness of a cluster, alternative methods for measuring or defining the cohesiveness or compactness of a cluster may also be implemented in accordance with principles of the invention. Additionally, prior probabilities of the refinement queries may be combined in a different fashion, so long as in general more refinements with greater probabilities yields a higher cluster score. In addition, a function may be implemented that integrates the distances of the queries in the cluster from the center and the individual queries' importance. Additionally, a count (or probability) divided by its distance from the cluster center may be computed for each refinement query in the cluster. The sum of these values for all refinement queries may then yield a similar cluster importance metric. It still has the effect that disparate clusters are downweighted and that clusters with queries with high counts are, in general, upweighted.

It should be understood that all of the above steps described with respect toFIGS. 3-11may be performed online as a source query comes into the search engine. However, the steps may also be performed as off-line processing and the selected refinements for a given query stored in a database. In this implementation, upon receipt of a source query, selected refinements may be looked up from the database and presented to the user.

Query Refinement Example

By way of example, a user118might submit a search query, which includes the individual word, “bikes.” This query is ambiguous because the user could have meant either bicycles or motor bikes, or various in-between variants of an unpowered or powered two wheeled vehicle. Table 1 is a listing of one example of refinement queries which may have been received following an initial source query of “bikes”. Table 1 includes indicating the refinement queries received and a count representing the number of times the particular refinement was received within a predetermined timeframe (e.g., 1 day).

As shown, there is a great deal of topical overlap in many of these refinements listed in Table 1. For other examples, there may even be more distinct overlap (in particular with celebrity-based queries where there is typically at least 10 variations on “<celebrity name> photos” in the top 50 user refinements. Furthermore, user entered query refinements in general also tend to be noisy, particularly at the lower count portion of the list. As described above, refinements below a predetermined threshold may be removed from the tail of the distribution, since they are unlikely to add anything useful in accurate generating refinement queries. In one implementation, the system may use the top-N refinements (where N is 50 to 100), and also prune out refinements with extremely low counts.

Once identified, each refinement query in Table 1 is characterized by issuing the refinement query and analyzing the returned results set. So, for example, the first refinement, “motorbikes” is issued and the result set retrieved. In this instance, the result set is composed primarily of pages about motorcycles. For each of the pages or documents returned, the terms or a subset of the terms on the page are then used to create term vectors. The term vectors for all the top-N results are summed, possibly with weighting the different results, to obtain a composite term vector representative of the refinement query as whole.

Because most of the pages returned in response to the first refinement query are about motorcycles, high-weight terms in the resultant vector for the query “motorbikes” will contain terms like “motorbikes”, “motor”, “engine”, “gasoline”, “mph”, etc. Similarly, the second query, “motorcycles”, is issued. This also returns many pages about motorcycles, and so after collecting the result set and creating a term vector for the query, the resultant vector will have many high-weight terms that are the same as the high-weight terms for “motorbikes”. However, for the third query in Table 1 “bmx bikes”, results turn out slightly different. The results for bmx bikes are almost all about small pedal bicycles that are used to perform tricks. Thus, when the result set vectors are created and summed to form the vector for the query, the high-weight terms will be different from those for “motorbikes” and “motorcycles”. They will include terms like “bicycle”, “pedaling”, “pedal”, “stunts”, etc.

After the composite term vectors are generated for each refinement query, the queries are clustered, which iteratively collapses the most similar composite term vectors into similar clusters. In one implementation, a threshold may be heuristically set to indicate where the clustering is to stop. Beyond this threshold the clusters may be deemed too dissimilar to be combined. In one embodiment, the threshold may be set to be the same for all clusterings. Table 2 is a listing of the top 5 clusters generated from a fairly aggressive clustering of the refinement queries of Table 1.

The remaining query clusters tend to be low-weight clusters of only one or two queries and can be removed from the analysis. As shown in Table 2, the generated clusters tend to group together topically similar refinement queries. After the clusters are generated, the best refinement from each cluster is then selected. For the above 5 clusters, if we simply choose the highest-weight (highest prior probability) refinement query, these would be: motorbikes (38); mountain bikes (24); motorcycles (18); bmx bikes (17); and lowrider bikes (8).

Note that, in some instances, highest-weight scoring doesn't always pick the most representative refinement query for each cluster. For example, for the general bicycle cluster (cluster2), the highest-weight refinement is “mountain bikes”, but “bicycles” is a close second. This is why in the description of the invention given above, it is indicated that cluster weights may be scored by dividing them by the query's distance from the centroid of the cluster. In the present example, “mountain bikes” is farther from the centroid than “bicycles” since the cluster is more about bicycles in general. This has the effect of boosting the more general query “bicycles”, even though it has a slightly lower weight. In this alternate system “bicycles” would be selected as the most representative refinement query rather than “mountain bikes”.

Once the query refinement clusters are named, they are ranked based on the total weight of each cluster, not the weight of the selected query. In one implementation, this involves ranking the representative queries for each cluster based on the total weight of the cluster in which they are contained. As described above, in an alternative embodiment the cohesiveness of the cluster may be accounted for by dividing the total weight by the standard deviation from the centroid. The examples provided here illustrate only a few of the many techniques known to those of ordinary skill in the art that may be employed to obtain related words for a term.

Conclusion

Systems and methods consistent with the principles of the invention may provide refinement query suggestions in response to a received source query.

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 form disclosed. Modifications and variations are possible in light of the above teachings or may be acquired from practice of the invention.

For example, while series of acts have been described with regard toFIGS. 3-10, the order of the acts may be modified in other implementations consistent with the principles of the invention. Further, non-dependent acts may be performed in parallel.