HK1092238B - Providing a user interface with search query broadening - Google Patents

Description

Providing a user interface with search query broadening

Technical Field

The present invention relates generally to query processing, and more particularly to a system and method for providing a user interface with search query broadening.

Background

Although the internet dates back to the late 60 s of the 20 th century, the widespread availability and acceptance of personal computing and internetworking has led to an explosive growth and unprecedented advancement in information sharing technology. In particular, the world wide Web ("Web") has revolutionized the accessibility to viewers worldwide of an unlimited number of electronic information, including written, spoken (audio) and visual (image or video) information, both in archived and real-time formats, in stored electronic form. In short, the Web has provided each connected user desktop access to virtually an unlimited number of information libraries in almost every language of the world.

The exchange of information to the Web runs under a client-server model. Individual clients execute Web content retrieval and rendering applications, typically in the form of Web browsers. The Web browser sends a request message for Web content to a centralized Web server, which acts as a repository for data storage and retrieval. The Web server parses the request message and returns the requested Web content in a reply message.

Search engines have evolved in conjunction with the growing use of the Web to enable users to find and retrieve relevant Web content in an efficient and timely manner. As the number and types of Web content has increased, the sophistication and accuracy of search engines has likewise increased. In general, search engines strive to provide the highest quality results in response to a search query. However, determining quality is difficult because the relevance of retrieved Web content is subjective in nature and depends on 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 use, for example, hyperlink structure-based analysis to determine The importance of retrieved Web content, such as described in "The automation of a Large-Scale hypertext Search Engine" of s.brin and l.page (1998) and in U.S. patent No. 6,285,999 to Page on 9/4/2001, The disclosures of which are incorporated herein by reference.

Typical search query scripts begin with natural language questions or individual terms, usually in the form of keywords, that are submitted to a search engine. The search engine performs a search against a data store that describes information characteristics of potentially retrievable Web content and identifies candidate Web pages. Searches can typically return thousands or even millions of results, so most search engines typically only rank and score the most promising results. Tall Web pages are then presented to the user, typically in the form of Web content titles, hyperlinks, and other descriptive information, such as snippets of text taken from the Web page.

Providing high quality search results is complicated by several factors. First, a given search query may generally be represented in a variety of forms based on the individual terms that make up the search query. For example, a particular term may have synonyms, another spelling method, share a common root, or have semantics that are similar to other words. Likewise, a particular term may share a conceptual meaning with other related words. Also, an independent term can be part of a compound term, which can also take a variety of forms when combined with one or more other terms.

In addition, term selection, which is selected by the user submitting the search query, may affect the quality of the search results. The user may simply fail to recognize the scope of the search and may provide a separate set of terms that are not intended to limit the search to a portion of the potential responsive results. Similarly, a user may have a limited vocabulary due to, for example, unfamiliar with the subject matter of the search, resulting in poorly limited queries and even falsely generalized features of the query. Finally, the user may misinterpret the technology employed by a particular search engine and provide terms that are not suitable for the search engine.

Therefore, a method of broadening a search query is needed. Broadened search features, such as synonyms, another spelling method, terms sharing a common root, or having semantics similar to other words, and search features sharing conceptual meanings with other related words may be used. The broadened search range may result in improved search quality.

There is also a need for a method of providing a user interface that presents a broadened search query. In one example, when providing one or more broadened search features, individual search features that appear as part of a compound term will be identified and considered. Such broadened search features may be flexibly presented to a user in a variety of display formats.

Disclosure of Invention

One embodiment provides a system and method for providing a user interface with search query broadening. A query is accepted that defines a search that can be performed on potentially retrievable information. The query is parsed. A broadened query is provided. At least one broadened query and results of a search performed in accordance with the broadened query are presented.

Still other embodiments of the present invention will become readily apparent to those skilled in this art from the following detailed description, wherein it is shown the best mode contemplated for carrying out the present invention. As will be realized, the invention is capable of other and different embodiments and its several details are capable of modifications in various obvious respects, all without departing from the spirit and scope of the present invention. Accordingly, the drawings and detailed description are to be regarded as illustrative in nature and not as restrictive.

Drawings

FIG. 1 is a block diagram illustrating a system for providing a user interface with search query broadening in accordance with the present invention.

FIG. 2 is a block diagram showing a computer system used in the system of FIG. 1.

Fig. 3A-3B are diagrams illustrating, by way of example, proposed search queries relating to broadened search characteristics determined in accordance with the present invention.

FIG. 4 is a screen shot showing, by way of example, a web page containing search results retrieved through a broadened search feature.

FIG. 5 is a flow chart illustrating a method of providing a user interface with search query broadening according to the present invention.

FIG. 6 is a flow chart showing a procedure for broadening a query used in the method of FIG. 5.

FIG. 7 is a flow chart showing a procedure for presenting a broadened query for use in the method of FIG. 5.

Detailed Description

FIG. 1 is a block diagram illustrating a system 10 for providing a user interface with search query broadening in accordance with the present invention. A plurality of independent clients 12 are communicatively connected to the server 11 via an internet 13, such as the internet or other form of communications network recognized by those skilled in the art. Individual clients 12 are operated by users 19, and users 19 make requests for Web content and other operations through their respective clients 12.

In general, each client 12 may be any form of computing platform capable of connecting to a network, such as the interconnection network 13, and capable of interacting with application programs. Illustrative examples of stand-alone clients include, but are not limited to: personal computers, digital assistants, "smart" cellular telephones and pagers, lightweight clients, workstations, "dumb" terminals connected to application servers, and various arrangements and configurations thereof as recognized by those skilled in the art. The internetwork 13 includes various topologies, configurations and arrangements of network interconnectivity components arranged to interoperably connect with enterprise, wide area and local area networks, and includes, without limitation, conventional wired networks, wireless networks, satellite networks, optical networks, and equivalents thereof as recognized by those skilled in the art.

For Web content exchange, and more particularly for searching, each client 12 executes a Web browser 18 ("Web browser"), which browser 18 preferably implements a graphical user interface and through which search queries are sent to a Web server 20 running on the server 11, as will be described further below with reference to fig. 2. Each search query describes or identifies information, typically in the form of Web content, that is potentially retrievable by the Web server. The search query provides search features, typically expressed as independent terms (such as keywords, etc.) and attributes (such as language, character encoding, etc.), that enable a search engine, also running on server 11, to identify and send back web pages. Other styles, forms, or definitions of search queries and features are possible as recognized by those skilled in the art.

The Web page is sent back to the Web browser 18 to be presented as a snippet, typically a Web content title, hyperlink, and other descriptive form, such as text retrieved from the Web page. The user may view or access the web page on a graphical user interface and may output selections and responses in the form of typed text, clicks, or both. The server 11 maintains an attached storage 15 in which Web content 22 is maintained. Web content 22 may also be maintained remotely on other Web servers (not shown) interconnected directly or indirectly via the internet 13, and preferably accessible by each client 12.

The Search Engine 21 preferably identifies Web content 22 that best matches The Search characteristics to provide high quality Web pages, as described in "The atom of a target-size hypertext Search Engine" (1998) in S.Brin and L.Page and U.S. Pat. No. 6,285,999 to Page 9, 4, 2001, The disclosure of which is incorporated herein by reference. In identifying matching Web content 22, the search engine 21 operates on information features describing potentially retrievable Web content, as will be described further below with reference to fig. 2. Note that the functionality provided by server 20, including Web server 20 and search engine 21, may be arranged in a loosely coupled or tightly coupled distribution or may be in a parallel computing configuration, in addition to a single processing environment.

The individual computer systems comprising server 11 and client 12 comprise general purpose, programmed digital computing devices including a central processing unit (processors 13 and 16, respectively), random access memory (memories 14 and 17, respectively), non-volatile secondary storage 15 (such as a hard disk or CD-ROM drive), a network or wireless interface, and peripheral devices including user interface devices such as a keyboard and display. Program code and data, including software programs, are loaded into RAM for execution and processing by the CPU and results are generated for display, output, transmission, or storage. The Web browser 18 is an HTTP-compliant Web browser, such as Internet Explorer, licensed by Microsoft corporation, Redmond, WA; netscape licensed by Netscape, Mountain View, CA; or a browser driven by Mozilla or Javascript as is known in the art.

FIG. 2 is a block diagram showing a computer system 30 for use in the system 10 of FIG. 1. The computer system 30 includes a processor 31 and a visual display 32, such as a computer monitor or Liquid Crystal Diode (LCD) display as is well known in the art. The computer system 30 runs a Web browser 18 (shown in FIG. 1), and the Web browser 18 preferably implements a graphical user interface 37. When user input is generally entered into both the display area and the particular user input area, visual Web content is output within the display area defined by the graphical user interface 37. User input of text is received via the keyboard 33. Linear, non-textual input is received through an optional pointer device 34, such as a mouse, trackball, track pad, or arrow keys. Similarly, speech and sound based input is received through microphone 35. Visual output is displayed on the visual display 32 through the graphical user interface 37, while audio output is played over the speakers 36. In particular, as will be described further below with reference to FIG. 6, search queries are entered, such as for a user, each of which is dynamically broadened. As will be further described below with reference to FIG. 7, the broadened search terms may be generally represented as visual Web content and executed. Other forms of computer components may be used as are known by those skilled in the art, including a processor 31, a visual display 32, and input and output devices.

Fig. 3A-3B are diagrams illustrating, by way of example, a proposed search query 40 relating to broadened search characteristics, such as query terms 43, 44, determined in accordance with the present invention. This example search query 40 constitutes a list of independent terms 41 consisting of "car", "repair", and "help". One or more of the individual terms 41 are broadened to enable the search engine 21 to generate search results using queries formulated more loosely and more broadly than the original, non-broadened terms 41.

"broadening" refers to modifying the scope of the search query 40 such that the search results reflect an increased breadth of the search scope, rather than narrowing, limiting, or constraining the search scope. Broadening may include modifying, replacing, supplementing, removing, or restating one or more search features (such as term 41), but need not be limited to being too strict. Search features include query terms, concepts, and other forms of information that are described in or derived from a query to help identify the content sought. Broadening may also include rewriting or modifying query 40 in whole or in part. By way of example, broadening may include providing synonyms, another spelling method, a common root word, or terms with similar semantics or terms sharing conceptual meanings. Further, broadening may include varying the scope of the query through query modification, such as by excluding one broadened term in an initial search and using categorical or clustered distinctions to evaluate search results relevant to the excluded term. Broadening may also include, for example, determining a semantic or conceptual meaning of the query, or one or more search features in the query, and broadening the query based on the relevant semantic or conceptual meaning; such a broadening approach is performed using relevant search features, but this is not required. Thus, broadening includes the effect of analyzing the query 40 and introducing changes to produce wider search results and increased search quality.

By way of example, in the simplest form, one or more terms related to at least one of the original terms 41 may be added separately to the original query 40. The search engine 21 will then execute the expanded query using the broadened term list. For example, the independent term 41 "car" may be supplemented with "vehicle", and the search engine 21 will perform a search on queries that include the terms "car", "vehicle", "repair", and "help".

By way of further example, the search engine 21 may initially execute a query that excludes the original terms 41 and maps the search results into categories of related terms associated with the excluded original terms 41. For example, the independent term 41 "help" may be excluded and the search engine 21 will perform a search on a query that includes only the terms "car" and "repair". The search engine 21 then maps the resulting search results into a particular category of related terms associated with the term "help". Alternatively, rather than mapping the search results into categories, the search engine 21 may form clusters of search results. Clusters (cluster) group search results at a conceptual level, while categories (category) group related terms at a literal level.

The foregoing method of broadening the original terms 41 is provided merely as an example of a broadening technique and is not meant to limit or restrict the scope of the present invention. Other broadening techniques, other than the foregoing techniques as known by those skilled in the art, may be used or may be used in combination with the foregoing techniques, which may be selected or combined in various arrangements.

Referring to FIG. 3A, the independent term 41 "car" has been expanded to include a list of expanded terms 43 consisting of "car," autos, "and" auto. Each sample broadened term is selected from a set of words having synonymous, another spelling method, a common root word, or similar semantics, although other choices of broadened terms besides the aforementioned set of words, as known to those skilled in the art, may be used or may be used in combination with the aforementioned set of words, which may be selected and combined in various styles and arrangements.

Referring next to FIG. 3B, the independent term 41 "help" has been broadened to include a list of broadened terms 44 consisting of "guide", "tips", "tutoria 1", and "problem". The term of each sample broadening is selected from a group of words having an associated conceptual meaning, although other choices of broadening terms besides the aforementioned set of words, as known to those skilled in the art, may be used or may be used in combination with the aforementioned set of words, which may be selected and combined in various styles and arrangements.

In another embodiment, each individual term 41 that is broadened may be provided as a hyperlink, with or without the broadened term lists 43, 44. In tabular form, each broadened term 43, 44 forms part of a broadened query according to the user's selection. In non-list form, each selected term 41 is broadened according to the user's selection.

In another embodiment (not shown), the independent term 41 is logically grouped with one or more other independent terms 41 to form a composite term, and a broadened group of terms is determined for the composite term. For example, the term 41 "hot" followed by the term "dog" may be logically grouped to form a composite term "hot dog", and a broader set of terms may include the terms 41 "hamburger", "wiener", and "usage". It is feasible to identify and combine the independent terms 41 in other forms as known to those skilled in the art to form composite and complex terms.

Both of the broadened term lists 43, 44 are represented as static lists, although other representations including menus of selectable terms, lists of selectable terms, a set of check boxes, and a set of hyperlinks corresponding to each broadened term may be used, with or without the broadened term lists 43, 44, as is well known to those skilled in the art. Note that such a user interface that allows selection of one or more options may also be utilized to constrain or focus queries as opposed to broadening queries. For example, from a query containing the term "vegetarian," the options "ovo lacto," "lacto," and "vegan" may be generated, which may allow a user to select one or more options to focus the original query.

Finally, a "select all" option 42 is provided to supplement the independent term list 41. Selection of the "all selected" option 42 triggers selection of each of the broadened term lists 43, 44, although other forms of full or partial broadened term selections are possible as known to those skilled in the art.

FIG. 4 is a screen shot showing, by way of example, a web page 50 containing search results 52 retrieved through a broadened search feature. The search query constitutes a list of independent terms 41 consisting of "car", "repair" and "help". The example search results 52 match a list of terms consisting of "auto", "guide", and "documents", reflecting the broadening of the terms 41 "car" and "help". The operators 'to' are preceded by the terms "car" and "help" to clearly request query broadening with respect to a specified term. Optionally, a separator character such as a '\' character may be provided along with the operator '-' to represent the normal meaning with respect to the operator. For example, the term "\\ car" would indicate that the search engine 21 should treat the term as consisting of "\ car" without query broadening.

In another embodiment, each search feature (including term 41) in the search query 40 may be automatically broadened by including at least one occurrence of an operator within the search query 40.

In another embodiment, the use of operators is optional and search query broadening is instead requested by using hyperlinks associated with one or more independent search features that include the terms 41. Thus, the search features will be broadened according to the associated hyperlinks selected by the user. Other forms of operators and separators are possible as known to those skilled in the art.

In another embodiment, the use of the operators 'to' includes a specifiable strength, which may be, for example, a strength specified by repetition of an operator or by use of another operator. For example, the term 41 "" with the two occurrences of the operator "" indicates that the term 41 should be widened even further than the term indicated by the single occurrence of the operator "". Further types of broadening include broadening of categories or clusters based on relevant search characteristics, as well as other forms of broadening as is known in the art. Furthermore, other types and forms of operators are possible as known to those skilled in the art that indicate that a strength can be specified.

FIG. 5 is a flow chart illustrating a method 40 of providing a user interface with search query broadening according to the present invention. The method 40 is depicted as a series of operations or steps that may be performed by, for example, the search engine 21 (shown in FIG. 1).

A search query 40 is accepted from the user 19 and parsed into individual search features (block 61). The search query 40 is widened (block 62), as described further below with reference to FIG. 6. For example, one or more search features in the search query 40 may be broadened. If specified (block 63), the broadened search query is then presented to user 19 (block 64), as further described below with reference to FIG. 7. After any further query modifications by user 19, The query is executed (block 65) to identify The Web content 22 that best matches The Search characteristics, such as described in "The atom of a Large-Scale Hypertextual Search Engine" of S.Brin and L.Page (1998) and in U.S. Pat. No. 6,285,999 to Page 9, 4, 2001, referenced above. Other types and forms of query execution are possible as are known in the art. Finally, the search results 52 are presented via the browser 18 (block 66). Typically, only a portion of the search results 52 need be presented since the full set of search results 52 may exceed the available presentation space on the browser 18. The method then terminates.

Fig. 6 is a flow diagram illustrating a process 70 for broadening a query used in the method of fig. 5. The purpose of this process is to identify, broaden and provide a broadened search query 40, such as by broadening individual search features present in the search query 40 that include query terms 41.

Each search feature in the search query 40 is repeatedly processed as follows (blocks 71-77), although other forms of non-repetitive processing are possible as is known by those skilled in the art. Each search feature is evaluated to determine whether an operator, such as the operator '-', is included that explicitly requests query broadening (block 72). If no operator is included, the search feature is not widened and the next search feature is processed (block 77). If an operator is included, the search feature is further evaluated to determine whether a separator is included that represents a common meaning with respect to the operator (block 73). If a delimiter is included, the search feature is not widened and the next search feature is processed (block 77). If no separator character is included, the search feature is evaluated to determine whether the search feature should be logically grouped with one or more other search features in the search query 40 to form a composite search feature (block 74). If the search features should not be logically grouped, only a single search feature is provided with broadened search features (block 75). Otherwise, if the search features should be logically grouped, the composite search feature is provided with broadened search features (block 76).

In the described embodiments, the set of broadened search features is generated by receiving one or more example search features corresponding to each search feature to be broadened. A weight is assigned to each of the example search features, and a list of broadened search features is formed based on the example search features and the weights assigned to each of the example search features, such as described in pending related U.S. patent application No. 10/425,819 filed on month 4 30, 2003, the disclosure of which is incorporated herein by reference. Other methods of generating a broadened search feature set are possible as known by those skilled in the art.

Note that other broadening methods may be used to modify the scope of the search query 40 such that the search results reflect an increased breadth rather than narrowing, limiting, or constraining the search scope as described with reference to FIGS. 3A-3B. After the search query is widened (blocks 75 and 76), the next search feature is processed (block 77), after which the process returns.

FIG. 7 is a flow diagram of a process 60 presenting a broadened query for use in the method of FIG. 5. The goal of this process is to flexibly present the broadened set of search features to users relevant to the set of search features from the original search query 40.

Each search feature in the search query, i.e., both the original and broadened search features, is repeatedly processed as follows (blocks 81-94), although other forms of non-iterative processing are possible as is known by those skilled in the art. If a hyperlink representation is desired (block 82), the search features are presented as hyperlinks (block 83) with or without a broadened list of search features. In tabular form, each broadened search feature forms part of a broadened query depending on user selection. In the non-list form, each selected search feature is broadened according to the user selection. If a static list representation is desired (block 84), the search feature is presented as part of the static list (block 85). If a menu representation is desired (block 86), the search feature is presented as part of a menu of selectable search features (block 87), and the search feature forms part of a broadened query according to the user's selections. If a selectable list representation is desired (block 88), the search feature is presented as part of a list of selectable search features (block 89), and the search features form part of a widened query according to the user's selection. If a representation of a list of check boxes is desired (Block 90), each broadened search feature is presented as part of a list of check box selectable search features (Block 91), and the search features form part of a broadened query according to the user's selections. Finally, if the "all selected" option is included (block 92), the "all selected" option is presented (block 93). Alternatives to the expressions and selections other than or in combination with the aforementioned expressions may be provided, which may be selected and combined in various arrangements, as known by those skilled in the art. Further, the broadened query need not necessarily be presented to the user, and the broadened search results can be transparently provided without first presenting the broadened search features. After selecting the representation (blocks 82, 84, 86, 88, 90), the next search feature 41 is processed (block 94), after which the process terminates.

While the present invention has been particularly shown and described with reference to embodiments thereof, it will be understood by those skilled in the art that the foregoing and other changes in forms and details may be made without departing from the spirit and scope of the present invention.

Claims (20)

1. A computer-implemented system, comprising:

means for receiving a search query comprising a plurality of search terms from a user, wherein the search query further comprises a plurality of user-selected operators associated with one of a plurality of search terms of the search query, and the plurality of user-selected operators comprises a plurality of symbols representing search term broadening;

means for broadening one of the plurality of search terms based on the plurality of user selected operators to provide a broadened search query, wherein the means for broadening the one of the plurality of search terms based on the plurality of user selected operators to provide a broadened search query comprises:

means for expanding one of the plurality of search terms to an extent determined by a number of occurrences of the plurality of symbols; and

means for searching using the broadened search query.

2. The system of claim 1, wherein the means for broadening one of the plurality of search terms comprises: means for determining a semantic or shared conceptual meaning associated with one of the search terms.

3. The system of claim 1, wherein the means for broadening one of the plurality of search terms comprises: means for modifying, replacing, supplementing, removing, or restating one of the plurality of search terms.

4. The system of claim 1, wherein the means for broadening one of the plurality of search terms comprises:

means for selecting a broadened search term associated with one of the search terms from a set of terms comprising synonyms, or alternative spellings, or having a common root, or similar semantics.

5. The system of claim 1, wherein the means for broadening one of the plurality of search terms comprises:

means for presenting at least one broadened search term associated with one of the search terms as a hyperlink, and

means for forming a broadened search query in response to a user selecting the hyperlink.

6. The system of claim 1, wherein the means for broadening one of the plurality of search terms comprises:

for presenting at least one broadened search term associated with one of the search terms as: means for selecting at least one of a static list, a menu of selectable search terms, a set of checkboxes, and a list of selectable search terms; and

means for receiving a user selection of the presented at least one widened search term.

7. The system of claim 1, wherein the search query further comprises a user-selected delimiter associated with another search term, indicating that the other search term should not be broadened.

8. The system of claim 7, wherein the user-selected separator comprises a symbol different from the plurality of symbols.

9. The system of claim 2, wherein the means for broadening one of the plurality of search terms comprises:

means for determining an associated semantic or shared conceptual meaning based on the meaning.

10. A method, comprising:

accepting a search query comprising a plurality of search terms from a user, wherein the search query further comprises a plurality of user-selected operators associated with one of the plurality of search terms of the search query, the plurality of user-selected operators comprising a same operator repeated a plurality of times, and the plurality of user-selected operators comprising a plurality of symbols representing search term broadening;

broadening one of the search terms based on the plurality of user-selected operators to produce a broadened search query, wherein broadening one of the plurality of search terms comprises:

expanding one of the plurality of search terms to an extent determined by a number of repetitions of the same operator; and

a search is conducted using the broadened search query.

11. The method of claim 10, wherein broadening one of the plurality of search terms comprises:

determining a semantic or shared conceptual meaning associated with one of the search terms.

12. The method of claim 10, wherein broadening one of the plurality of search terms comprises:

modifying, replacing, supplementing, removing, or restating one of the search terms.

13. The method of claim 10, wherein broadening one of the plurality of search terms comprises:

selecting a broadened search term associated with one of the search terms from a set of terms comprising synonyms, or alternative spellings, or having a common root, or similar semantics.

14. The method of claim 10, wherein broadening one of the plurality of search terms comprises:

presenting at least one broadened search term associated with one of the search terms as a hyperlink, an

In response to a user selecting the hyperlink, a broadened search query is formed.

15. The method of claim 10, wherein broadening one of the plurality of search terms comprises:

presenting at least one broadened search term associated with one of the search terms as at least one of: a static list, a menu of selectable search terms, a set of checkboxes, and a list of selectable search terms; and

a user selection of the presented at least one widened search term is received from the user.

16. The method of claim 10, wherein the search query further comprises a user-selected delimiter associated with another search term, indicating that the other search term should not be broadened.

17. The method of claim 11, wherein broadening one of the plurality of search terms comprises:

determining an associated semantic or shared conceptual meaning based on the meaning.

18. The method of claim 10, wherein the plurality of user-selected operators includes a first symbol representing a search term broadening.

19. The method of claim 18, wherein the first symbol comprises one of a graphical symbol or a character symbol.

20. The method of claim 18, wherein the search query further comprises a user-selected separator associated with another search term that indicates that the other search term should not be broadened, and the user-selected separator comprises a second symbol that is different from the first symbol.