Abstract:
A robust search system in accordance with the invention replaces a single search keyword with a cluster of similar keywords, applies a search procedure for each similar keyword independently, and aggregates results of multiple searches into a single result. In one embodiment of the invention separate clusters of similar keywords and a separate aggregation procedure are used for placement of contextual advertisements.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS  
       [0001]     This application claims the benefit of provisional patent YKP006SRH1-030505 filed 2005 Mar. 05 by the present inventor 
     
    
     FEDERALLY SPONSORED RESEARCH  
       [0002]     Not applicable  
       SEQUENCE LISTING OF PROGRAM  
       [0003]     Not applicable  
       BACKGROUND OF THE INVENTION  
       [0004]     This invention pertains to technology used for data search, particularly data search over the Internet.  
         [0005]     In many cases search objects are described by using complex keywords consisting of multiple words or terms. For purposes hereof, such multiple word keywords are referred to as “long keywords.” Existing Internet search engines are optimized to handle short (one, two, three term) keywords and often generate very low quality search results for long keywords. Similar deficiencies exist with the semantic broad match placement of contextual advertisements (“ads”) related to long keyword searches: it is a known fact that the contextual ad placement accuracy degrades significantly when keywords consist of three or more terms.  
         [0000]     I outline below three major problems related to the long keyword search and contextual ad placement for long keywords.  
         [0006]     Monotonic search improvement problem. When a human user includes a new search term into an existing term sequence in an effort to improve results he/she is following Aristotle&#39;s principle of “monotonic improvement” which states effectively that the inclusion of additional relevant information will always increase the quality of reasoning. However, current search engine “logic” does not necessarily follow Aristotle&#39;s “monotonic improvement” principle unless the number of terms in a keyword search is fairly limited. Under current search engine logic, there is often a threshold number of terms a which point the search result relevance is maximized. When the number of terms in the keyword search surpasses that threshold number, search relevance starts to deteriorate.  FIG. 1  illustrates such effect.  
         [0007]     Semantic volatility problem. In many cases even “minimal” changes in keywords (i.e., replacing a term with its synonym, term permutation inside a keyword string, etc.) result in significant changes to the search result. In other words, semantically similar keywords may produce very different search results.  
         [0008]     The above problems describe different aspects and/or deficiencies of the robustness of search engines.  
         [0009]     The proposed invention defines a method and apparatus to improve search engine robustness and the effectiveness of contextual ad placement for long keyword searches.  
       SUMMARY  
       [0010]     The main idea of the invention is to replace a single search keyword with a group of “similar” search keywords (semantic keyword cluster), replace a single search with multiple searches and then aggregate the results using one of several [known] aggregation methods.  
         [0011]     In one embodiment of the invention similar search keywords are generated from the originally submitted keyword by manipulating the original terms.  
         [0012]     In one embodiment of the invention similar search keywords are generated by combining existing keyword terms and new terms.  
         [0013]     In one embodiment of the invention similar search keywords are generated automatically by a specific predefined algorithm.  
         [0014]     In one embodiment of the invention similar search keywords are generated using human interaction.  
         [0015]     In one embodiment of the invention similar search keywords are combined together into complex “meta-keywords” which are presented as search criterion to a search engine.  
         [0016]     In one embodiment of the invention multiple similar search keyword clusters are generated for search and for contextual advertisement (ads) placement.  
         [0017]     In one embodiment of the invention weight coefficients will be assigned to each similar keyword in the cluster and a resulting aggregation will be provided using such weight coefficients. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0018]      FIG. 1 —illustrates possible search relevance behavior as a function of the number of terms in keyword.  
         [0019]      FIG. 2 —shows a preferred embodiment system block diagram. 
     
    
     DETAILED DESCRIPTION  
       [0020]     This invention is related to  FIG. 2  which describes the preferred embodiment of the invention. In  FIG. 2 , user  200  is performing a search using a keyword sequence that consists of multiple terms {a 1 , a 2 , . . . a n } as shown in  202 . Block  204  generates a set of ordered term subsequences  206  {S 1 (k 1 ) . . . S j (k j ), . . . } from the original sequence  202 . Each term subsequence {S j (k j )} is generated using a subset of terms from {a 1 , a 2  . . . a n }.  
         [0021]     For example, let&#39;s assume that user is searching for Friends Sitcom Episode 10.07 called “The One With The Home Study”. In our example search subsequences would be {(Friends, Sitcom), (Friends, Episode), (Friends, Episode, 10.7), (Friends, Sitcom, Episode), (Friends, Home), (Friends Study), (Friends Home Study)}.  
         [0022]     Block  208  depicts a search engine accepting the term subsequences in  206  as a set of keywords and generating search results  210  for each keyword from  206 . Block  212  aggregates the search results received for each keyword together into an “aggregated search result”  214 .  
       ADDITIONAL EMBODIMENTS  
       [0023]     In one embodiment of the invention one or more terms in each term subsequence can be replaced by a term that did not exist in the original term set {a 1 , a 2  . . . a n }.  
         [0024]     For example, let&#39;s assume that user is searching for “James Bond, and he is using keyword “British Agent 007”. The patented method generates a new keyword that includes a combination of some terms from the ordinal set { British, Agent, 007} and new terms {James, Bond} to produce “James Bond Agent 007.” 
         [0025]     In one embodiment of the invention keywords will be generated automatically by a special predefined procedure or algorithm.  
         [0026]     In one embodiment of the invention keywords will be generated semi-automatically using user interaction.  
         [0027]     In one embodiment of the invention block  204  generates combined terms meta-sequences using a subsequences “combination” operator.  
         [0028]     For example, when a user is searching for Friends Sitcom Episode 10.07 called “The One With The Home Study” the keyword meta-sequence can be {(Friends, Sitcom) AND (Friends, Episode, 10.7)}.  
         [0029]     In one embodiment of the invention block  204  generates special weight coefficients (or a “relevance score”) for each similar keyword in a keyword cluster  
         [0030]     For example when a user is searching for Friends Sitcom Episode 10.07 called “The One With The Home Study” the search subsequences could be {(Friends, Sitcom), (Friends, Episode), (Friends, Episode, 10.7), (Friends, Sitcom, Episode), (Friends, Home), (Friends Study), (Friends Home Study)} and the associated relevance score or special weight coefficient list could be {70, 70, 82, 86, 31, 22, 97}.  
         [0031]     In one embodiment of the invention block  208  uses more than one search engine to generate search matches and to generate contextual advertisements.  
         [0032]     In one embodiment of the invention aggregation block  212  is simply merging search matches as follows r 1 ( 1 ), r 2 ( 1 ) . . . r k ( 1 ), r 1 ( 2 ) . . . r k ( 2 ) . . . where r k (i) is i th  search match of the search result generated for subsequence S k (.).  
         [0033]     In one embodiment of the invention the aggregation algorithm defines and computes relevance criteria T for search matches and then orders those search matches based on criteria T. For instance, for each search match r its relevance criteria T(r) can be computed as T(r)=n i (r)+ . . . +n k (r), where k is a number of used term subsequences, and n i (r) is the r th  search match order of appearance in the i th  search result. The search matches in the aggregated search result are ordered according to their relevance criteria T(r). For instance, the search matches in the aggregated search result are put in the order r 1 , r 2  . . . r m  such that T(r 1 )≦T(r 2 ) . . . ≦T(r m ).  
         [0034]     In one embodiment of the invention the search result depends on relevance coefficients assigned to each search match. The relevance criteria of a search match r can be computed as T(r)=v 1 *n 1 (r)+ . . . +v k *n k (r), where k is the number of used search subsequences, n i (r) is the r th  search match order of appearance in the i th  search result and v i  is a weight coefficient for the i th  subsequence. The search matches in the aggregated search result are ordered according their relevance criteria T(r). For instance, the search matches in the aggregated search result are put in the order r 1 , r 2  . . . r m  such that T(r 1 )≦T(r 2 ) . . . ≦T(r m ).  
         [0035]     In one embodiment of the invention contextual advertisements are considered separate entities. Separate keyword clusters are used to generate search matches and a corresponding contextual advertisement list. Separate aggregation blocks are used to generate a list of matches and a list of contextual advertisements.  
         [0036]     In one embodiment of the invention the aggregation operator is a general averaging function. A function F(x 1  . . . x n ) is called general average when min(x 1  . . . x n )≦F(x 1  . . . x n )≦max(x 1  . . . x n ).  
         [0037]     In one embodiment of the invention the keyword search sequence is filtered to remove insignificant “stop” words. Insignificant stop words could include the words “a”, “the”, “in”, “out”, “some”, “few”, “many”, etc.  
         [0038]     Although the above description contains much specificity, the embodiments described above should not be construed as limiting the scope of the invention but rather as merely illustrations of some presently preferred embodiments of this invention.