Abstract:
A method and apparatus in accordance with the invention which, for any given keyword, generate a semantic keyword cluster of meanings and associated proximity scores.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims the benefit of provisional patent filed 2006 Jun. 11 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]    Search requests are usually described by keywords or search queries. Each keyword consists of single or multiple words or terms. In many applications, it would be extremely beneficial to understand how relevant (or semantically close) two different keywords are. Such knowledge could be used to define contextual advertisement bidding strategies, generate advertisement content, reconstruct people&#39;s search intentions, discover latent ties between people and documents, and more. 
         [0006]    Successful attempts to create a method and apparatus that would numerically estimate keyword&#39;s relevance are unknown today. The problem is mathematical in nature. It may be possible to determine proximity for all single-term keywords although it would require approximately 50 billion word comparisons. Any attempt to compare all keywords of two or more terms would be virtually impossible due to the high amount of required computations. As a result, the simple question of how relevant keywords “British agent 007” and “James Bond” are to each other is still open today. 
         [0007]    The proposed invention defines a method and apparatus to compute keywords&#39; proximity by creation of a set of neighbor keywords (keyword clusters) using novel keyword proximity measurement technology. 
       SUMMARY 
       [0008]    The main idea of the invention is to find semantic neighbor keywords (referred herein as “meanings”, or “neighbors”) for a set of predefined “seed” keywords but not for all keywords (see  FIG. 1 ). As a result of such operation we will create limited size cluster of semantically close keywords (called herein a “Semantic Keyword Cluster”, or “SKC”) around each seed keyword. We also propose to compute a special proximity measure (called herein a “proximity score”, “relevance”, “proximity”, or “score”) between each SKC meaning and SKC seed keyword (see  FIG. 2 ). As a result, for every seed keyword we will generate an SKC of meanings with an assigned proximity score number for each meaning. (see  FIG. 3 ). 
         [0009]    In one embodiment of the invention an SKC is generated by crawling the Internet, collecting a specific set of Internet pages, extracting keywords from those pages, and computing keyword&#39;s proximity scores. 
         [0010]    In one embodiment of the invention an SKC is generated by sending sequences of keywords to one or more Search Engines, collecting pages with search engine matches, extracting keywords from these pages, and computing keyword&#39;s proximity scores. 
         [0011]    In one embodiment of the invention an SKC is generated by sending sequences of keywords to one or more Search Engines and one or more encyclopedia sites, collecting pages or page snippets with search engine matches and encyclopedia articles, extracting keywords from these pages and articles, and computing keyword&#39;s proximity scores. 
         [0012]    In one embodiment of the invention a seed keyword is replaced with another keyword using a pre-defined algorithm or human interaction. 
         [0013]    In one embodiment of the invention a seed keyword is replaced with a set of seed keywords accompanied by their relative weight coefficients. For each keyword a separate SKC is generated. The final SKC is computed as an aggregation of all seed keywords&#39; SKCs from the above set using associated weight coefficients and other known art aggregation procedures. 
         [0014]    In one embodiment of the invention the said set is created by at least one or a combination of the following: (i) replacing a word in the seed keyword with its plural/singular form, (ii) replacing a word in the seed keyword by stemming, (iii) replacing a word in the seed keyword with its synonym, (iv) replacing the seed keyword with a seed keyword made by permutation of words in the original seed keyword; (v) replacing the seed keyword with a seed keyword containing a subset of words in the original seed keyword. 
         [0015]    In one embodiment of the invention the SKC and meanings proximity scores are generated using statistical analysis algorithms. 
         [0016]    In one embodiment of the invention the statistical analysis algorithm creates a proximity score as a function of the frequency of occurrences of at least one of: a single word occurrence frequency, a word pair occurrence frequency, a word triple occurrence frequency, a word N-tuple occurrence frequency. 
         [0017]    In one embodiment of the invention the SKC and meaning proximity scores are generated using human interactions. 
         [0018]    In one embodiment of the invention the method and apparatus finds for a chosen seed keyword one or more different seed keywords (called “backlinks” or “reverse keywords”) that use such chosen seed keyword as their meaning in their relevant SKCs. For a backlink keyword the invention computes a backlink proximity score for the chosen keyword and aggregates backlink keywords into the chosen seed keyword&#39;s SKC as a special backlink meaning. 
         [0019]    In one embodiment of the invention SKC size can be defined dynamically based on a relative proximity score. 
         [0020]    In one embodiment of the invention SKC size can be defined statically and changed interactively based on SKC size criteria. 
         [0021]    In one embodiment of the invention the SKC of a seed keyword can be extended by aggregation with at least one of the following: (i) a SKC of the seed keyword&#39;s neighbor, (ii) a SKC of the seed keyword&#39;s neighbor&#39;s neighbor, (iii) a SKC of the seed keyword&#39;s neighbor&#39;s neighbor&#39;s neighbor etc. up to arbitrary level of indirection. The above extension is called extension by transitive closure of the keyword-neighbor (meaning) relationship. 
         [0022]    In one embodiment of the invention the SKC of a seed keyword can be extended by transitive closure of the neighbor-keyword relationship where neighbor-keyword relationship is defined as inverse relationship to the keyword-neighbor relationship. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0023]    FIG.  1 —shows an example of SKC cluster 
           [0024]    FIG.  2 —shows an example of SKC cluster with meaning&#39;s proximity scores 
           [0025]    FIG.  3 —shows two SKC cluster in a keyword space 
           [0026]    FIG.  4 —shows a preferred embodiment system block diagram 
           [0027]    FIG.  5 —shows an embodiment system with multiple suggestions block diagram. 
       
    
    
     DETAILED DESCRIPTION 
       [0028]    This invention is related to  FIG. 4  which describes the preferred embodiment of the invention. In  FIG. 4 , a user is performing a search using a seed keyword that consists of multiple terms {a 1 , a 2 , . . . a n } as shown in  FIG. 3  block  100 . Seed Keyword Analysis block  110  verifies a keyword&#39;s main parameters (possible misspellings, language of use, etc.) and generates a request sequence  120  to generate a SKC. Keyword Meanings Generator block  130  consists of four blocks and works as follows: it first collects appropriate documents by Document Collection block  131 , than it extracts the most popular keywords from these documents in Keyword Extraction block  132 , normalizes, ranks and orders such keywords in Keyword Normalization block  133 , and generates meanings and meanings&#39; proximity scores in Meanings Generation and Score Computation block  134 . The resulting SKC and meanings proximity scores  140  are used as input to the Truncation and Presentation Block  150  that truncates the SKC based on performance or other requirements and outputs the final SKC and proximity scores  160 . 
       Additional Embodiments 
       [0029]    In one embodiment of the invention related to  FIG. 4  the Data Collection block  131  is collecting keyword source documents by Internet crawling. 
         [0030]    In one embodiment of the invention related to  FIG. 4  the Data Collection block  131  is collecting keyword source documents by sending sequences of keywords to one or more Search Engines and collecting pages with search engine matches. 
         [0031]    In one embodiment of the invention related to  FIG. 4  the Data Collection block  131  is collecting keyword source documents by sending sequences of keywords to one or more Search Engines and one or more encyclopedia and Blog sites and collecting pages with search engine matches. 
         [0032]    In one embodiment of invention related to  FIG. 4  seed keyword  100  is replaced with another keyword  120  using a pre-defined algorithm or by human interaction implemented in Seed Keyword Analysis block  110 . 
         [0033]    In one embodiment of the invention presented by  FIG. 5  a seed keyword  200  is replaced in the Seed Keyword Filtering block  210  by a set of seed keywords  220  each of which have varying weight coefficients. Later each keyword is separately processed in Seed Keyword Analysis block  230  to generate keywords and their parameters  240 . Keywords and their parameters  240  are input in the Keyword Meaning Generator block  250  that consists of four blocks and works as follows: it first collects appropriate documents by Document Collection block  251 , than it extracts the most popular keywords from these documents in Keyword Extraction block  252 , normalizes, ranks and orders such keywords in Keyword Normalization block  253 , and generates meanings and meanings&#39; proximity scores in Meanings Generation and Score Computation block  254 . The resulting SKC and meanings proximity scores  260  are used as input to the Meanings Aggregation block  270  that uses existing weight coefficients as aggregation parameters. The output of block  270  is a SKC and SKC meaning&#39;s proximity scores  280 . The SKC  280  is an input into the Truncation and Presentation Block  290  that truncates a SKC based on performance or other requirements and outputs a final truncated SKC  295 . 
         [0034]    In one embodiment of the invention SKC and meanings proximity scores are generated using statistical analysis algorithms. 
         [0035]    In one embodiment of the invention SKC and meaning proximity scores are generated using human interactions. 
         [0036]    In one embodiment of the invention the method and apparatus finds for a chosen seed keyword one or more different seed keywords (called “backlink” or “reverse keywords”) that use such chosen seed keyword as their meaning in their relevant SKCs. For a backlink keyword it computes a backlink proximity score for the chosen keyword and aggregates backlink keywords into the chosen seed keyword&#39;s SKC as a special backlink meaning. 
         [0037]    In one embodiment of the invention SKC size in Truncation and Presentation blocks  150  and  290  can be defined dynamically based on relative proximity scores. 
         [0038]    In one embodiment of the invention SKC size in Truncation and Presentation blocks  150  and  290  can be defined statically and changed interactively based on SKC size criteria. 
         [0039]    In one embodiment of the invention the SKC of a seed keyword can be extended by aggregation with at least one of the following: (i) a SKC of the seed keyword&#39;s neighbor, (ii) a SKC of the seed keyword&#39;s neighbor&#39;s neighbor, (iii) a SKC of the seed keyword&#39;s neighbor&#39;s neighbor&#39;s neighbor etc. up to arbitrary level of indirection. The above extension is called extension by transitive closure of the keyword-neighbor (meaning) relationship. 
         [0040]    In one embodiment of the invention the SKC of a seed keyword can be extended by transitive closure of the neighbor-keyword relationship where neighbor-keyword relationship is defined as the inverse relationship to the keyword-neighbor relationship. 
         [0041]    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.