Abstract:
The search engine provides a method and apparatus for receiving long queries, assigning a weight to each relevant word of the query, allowing a user to reformulate the query before and/or after search on the basis of the weight of each word computed by the algorithm. The search engine further provides methods for decomposing a long query into several short queries based on the importance of terms computed by the algorithm. These generated queries are submitted to existing search engine(s) producing several ranked outputs, and the obtained ranked outputs are merged into one final ranked output.

Description:
FIELD OF THE INVENTION  
         [0001]    This invention pertains to an internet-based search engine that can use long queries in order to obtain more satisfactory search results.  
         BACKGROUND OF THE INVENTION  
         [0002]    The last decade has seen an introduction of the world wide web and search engines to help users find pages on the web that are relevant to users&#39; information needs. A prior art typical search engine presents a user with a small box into which the query is typed (or pasted) by the user and a search engine returns a ranked list of links to pages together with their titles and short summaries. Over the years the quality of the returned results was substantially improved in most engines. However, for many queries the results are still very poor. One of the reasons for this phenomenon is the quality of an input from the user. This input is a representation of user&#39;s information need and if the user&#39;s information need is not described properly it is very difficult (and often impossible) to provide good results. A search engine should be capable of: 1) accepting a representation of user&#39;s information need without limiting it (either explicitly or implicitly) to a small number of terms; and 2) providing good search results if a user specifies long coherent query. The prior art search engines do not deal with these problems adequately. For example, they do not allow to type or paste a query past certain number of characters and do not allow to paste a text after carriage return. In cases where an engine allows a longer query, the existing algorithms generate output results that are often less than satisfactory.  
           [0003]    Another important consideration in improving the quality of search results is to incorporate user&#39;s feedback into a search process. Most prior art search engines do not provide capabilities to include user&#39;s feedback and in few cases where some form of feedback is used it is not designed for long queries.  
         SUMMARY OF THE PRESENT INVENTION  
         [0004]    It is therefore an object of the present invention to provide a search engine for long queries in a web environment.  
           [0005]    It is therefore a further object of the present invention to provide a search engine that gives improved quality searches.  
           [0006]    It is therefore a still further object of the present invention to provide a search engine which can be used in intranet and extranet environments.  
           [0007]    It is therefore a still further object of the present invention to provide a search engine which has an intuitive, user-friendly interface.  
           [0008]    It is therefore a still further object of the present invention to provide a search engine which includes user feedback processing especially designed for long queries.  
           [0009]    These and other objects are attained by providing a search engine which initially presents the user with a large box to enter the user&#39;s query, which is typically a long query. The user is presented with an opportunity to reformulate the query before search on the basis of the weight of each word computed by the search engine.  
           [0010]    The search algorithms include query parsing which removes common words from the query; computing the weights of terms in the parsed query; creating an ordered list of terms by sorting the terms of the parsed query in descending order of their computed weights; presenting the ordered list of terms to the user prior to the search; decomposing the long query into a set of short queries using algorithms described herein below, submitting each constructed short query to the chosen search engine, obtaining a predefined number of documents in each query&#39;s output, and merging all the outputs into one ranked output by applying a ranking algorithm described herein below.  
           [0011]    Additionally, the user is given the option for feedback before and/or after the search. In this feedback, the user is presented with a list of words in descending order of their weights. This order tells the user which words are considered the most important in the search. The user is then given the option of changing the order of the words, removing words, adding words, and/or constructing phrases. The resulting ordered set of words is then used by the search algorithm to perform a new search. 
       
    
    
     DESCRIPTION OF THE DRAWINGS  
       [0012]    Further objects and advantages of the invention will become apparent from the following description and claims, and from the accompanying drawings, wherein:  
         [0013]    [0013]FIG. 1 is a flowchart of the present invention.  
         [0014]    [0014]FIG. 2 is a plan view of a typical initial screen of the present invention as presented to the user.  
         [0015]    [0015]FIG. 3 is a flowchart of the user&#39;s query processing in present invention.  
         [0016]    [0016]FIG. 4 is a flowchart of the query refinement process in present invention.  
         [0017]    [0017]FIG. 5 is a flowchart of the search process in present invention  
         [0018]    [0018]FIG. 6 is a plan view of a typical ordered list of search terms presented to the user by the present invention before and/or after a search is performed.  
         [0019]    [0019]FIG. 7 is a flowchart of the process for constructing short queries in present invention 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT  
       [0020]    Referring now to the drawings in detail wherein like numerals refer to like elements throughout the several views, one sees a flowchart of the present invention in FIG. 1. Firstly, as shown in block  100 , the user is presented with a relatively large Query Window  205  on computer screen  200  (see FIG. 2) into which the user enters a relatively long search query. Query Window  205  can accept pasted text from a document, Web page or e-mail. This provides the ability to find information based upon the example of an existing document. The size of Query window  205  allows the user to see the entire query, or at least a very large portion of the query.  
         [0021]    Reset button  215  (which is actually a portion of the screen  200  which the user can “click” with a mouse or similar pointing instrument, as is known to those skilled in the art) allows a user to clear the prior query from Query Window  205 .  
         [0022]    Once the user initiated the search process by clicking the Search Button  210  via mouse or similar pointing instrument the engine processes the user&#39;s query (see FIG. 3).  
         [0023]    In block  300 , common words (sometimes referred to as “stopwords”) are removed from the query. The user may maintain a special list of common words pertaining to a specific industry or application. In block  305 , a computation of the word&#39;s weights in the parsed query is performed. The weight of the word represents the importance of the word in a search process and is typically computed as the product of TF (term frequency) and IDF (inverse document frequency). In Block  310  a list of all query terms with their computed weights is created and in Block  315  this list is ordered in descending order of computed weights.  
         [0024]    In Block  110  the user is given a choice whether to refine the query. Block  115  provides the user with the Refine Query process (see FIG. 4).  
         [0025]    In block  400 , the user is presented with the list of query words on computer screen  600  (see FIG. 6) in descending order of their weights (this order indicates which words are considered the most important in the search). At this point  405 , the user is given an opportunity to refine the query  410 . Refinement can be accomplished in one of several ways: change the order of the words (for example, by dragging the word  605  into a new position—higher or lower to make it more or less important), remove a word from the list by marking it ( 610 ), add a new word into the list with a position chosen by the user, and/or construct phrases in the Phrase Window ( 615 ) from the words on the list and choose the positions into which they are inserted. To review the changes again, the user may click the Refresh Button ( 620 ) and return to Block  415  which updates the word order (internally) and display the updated list again  400 . At this point the user may continue with query refinements or proceed to the search process.  
         [0026]    In Block  120  the user can start the search process by clicking Search Button  210  (which is actually a portion of the screen  200 ) with a mouse or similar pointing instrument. In Block  125  the actual search process takes place (see FIG. 5).  
         [0027]    In block  500  a set of short queries is composed. This can be implemented in at least two different ways by choosing a variable subset of search terms (see FIG. 7-A) or fixed subset of search terms (see FIG. 7-B). Specific approach could vary depending upon computational resources and some additional information about the user&#39;s preferences.  
         [0028]    The first approach is to use a variable number of terms from the original query but fix the number of queries to be constructed. A typical algorithm for such variable term decomposition of a long query sets M as the number of queries to be constructed. A typical value of M is four, but other values can be used depending upon the application, hardware capabilities and other circumstances. The construction of the first query starts with the first term (Block  700 ) in the ordered list of terms and iteratively adds more terms (Block  705 ) from the ordered list to construct a conjunctive query of the chosen terms. At each step of the iteration, the resulting query is submitted to an existing search engine (Block  710 ) which is typically internet or extranet-based. The choice of a search engine could be automatic by defaulting it to predefined search engine or the user may be given a choice to select an engine from a predefined list of search engines. The algorithms described in the present invention could be applied to any of the existing search engines. The iteration stops (Block  725 ) when the number of returned documents is less than some predefined number (such as, for instance, twenty), and the output results are stored for future use (Block  730 ). If a newly added term causes no results to be returned (Block  715 ), the newly added term is discarded (Block  720 ) and the next term on the list is used (Block  705 ). Construction of Queries  2  through M is similar to the construction of the Query 1  (i.e., the first query). That is, the i th  query starts with the i th  term from the ordered list of terms.  
         [0029]    The second approach is to use a fixed number of consecutive search terms from the ordered list of query terms and a variable number of queries to be constructed. A typical algorithm for such approach accepts from the user query formulation parameters (Block  750 ). The first parameter N is the maximum number of terms from the ordered list to be used in short query construction and the second parameter L is the minimum number of terms in query. A typical value for N is 7 and L is 3, but other values can be used depending upon the application, hardware capabilities and other circumstances. The maximum number of documents to be used from the ranked outputs obtained from the constructed queries is represented by K. Block  755  computes the number of all possible subsets of terms from the list of N terms, where each subset has E elements (where L− 1 &lt;E &lt;M+ 1 ). The number of L-element subsets of a set with N elements, denoted by C(N, E), is equal to N!/(E! * (N-E)!). For instance, with an implementation of N=7 and L=3, then the total number of subsets is equal to C( 7 ,  3 )+C( 7 ,  4 )+C( 7 ,  5 )+C( 7 ,  6 )+C( 7 ,  7 )=99. This number of subsets can be indicated as M. Block  760  generates all possible such subsets. For each subset i (wherein 0&lt;i&lt;M+1), a conjunctive query (that is Query i ) of all the terms in the subset is constructed. Regardless of the approach used to generate short queries the resulting queries are submitted to a search engine (Block  505 ). Typically this is going to be the same search engine as the one in block  710 . After the search results are obtained (block  510 ), the top K documents are used to form a ranked output RLD i  (0&lt;i&lt;M+1).  
         [0030]    The outputs or search results obtained in block  510  are merged into one ranked output by applying a ranking algorithm (block  515 ). The inputs to the ranking algorithm are the M queries (Query 1 , . . . , Query M ) and corresponding ranked search results (RLD 1 , . . . RLD M ) obtained in block  510 . Each of the ranked output RLD i  contains, at most, K URL addresses ranked by the search engine. Firstly, the weight of each URL is calculated (within the output RLD i ) using its relative position from the top of the output RLD i  and the weight of Query i  that produced this output. The weight of Query i , denoted by W Qi , is the arithmetic average of the weights of its component terms and is calculated as follows:  
         W     Q   i       =         ∑     j   =   1     m          W     t   j         m                           
 
         [0031]    where W tj  is the weight of search term t j  as calculated in Block  305  using typical TFxIDF measure and m is the number of search terms in Query i . All duplicate URLs are eliminated. However, the sum of the weights of the duplicate URLs is used as a new weight for the one remaining copy of the URL. The URLs are then arranged in descending order according to the respective weights. These search results are then presented to the user in block  130 .  
         [0032]    The user is then given a choice at decision block  130  to go to block  115  to refine the query and reformulate the search or at decision block  135  to clear the query window and return to block  100  to perform a new search. Thus the several aforementioned objects and advantages are most effectively attained.  
         [0033]    Although preferred embodiments of the invention have been disclosed and described in detail herein, it should be understood that this invention is in no sense limited thereby.