Abstract:
This invention is related to an SNL (Structured Natural Language) based search system (SNLSS) that allows Internet users to search services (tools, database, online services, etc.) based on problem statements expressed in one or more structured natural languages.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Field of the Invention 
         [0002]    This invention is related to an SNL (Structured Natural Language) based search system (SNLSS) that allows Internet users to search services (tools, database, online services, etc.) based on problem statements expressed in one or more structured natural languages. 
         [0003]    2. Description of the Related Art 
         [0004]    The commercial world is mostly about demands and supplies. In most cases demands trigger supplies, and in some cases supplies create demands. A more general concept for needs may be problems, and that for supplies may be solutions. 
         [0005]    The Internet has provided a global infrastructure to connect problems with solutions. For example eBay has done a great job on auctions. A keyword-based search engine such as Google may be considered as a special problem solver that solves the problem: Find (Web) documents that contain the keywords provided by the user. A Question/Answering (Q&amp;A) system may be considered as another special problem solver that solves the problem: Find answers for the question (based on the documents collected by the system). 
         [0006]    Both keyword-based search engines and Q&amp;A system have done an excellent job for the problems they try to solve. But from the view point of Problem Solving, they are far from being sufficient. It can be easily seen that not every problem falls into the two general categories we talked about. Any computer scientist may easily come up the following list:
       1. Computational Problems and other Mathematical Problems. Solving such problems require computation to be involved. Some initial attempts have been made (e.g., Wolfram|Appha, http://www.wolframalpha.com/), but lots more need to be done in this space.   2. Database Search Problems such as Find the supermarkets carrying apples at less than 2 dollars a pound. Deep webs usually work by themselves and they are not connected (Not because they cannot be, but perhaps because they do not want to be.)   3. Synthesis Problems such as Build a program that takes a set of numbers and returns them in increasing order. Automatic synthesis is general is hard and remains to be a goal to be accomplished.   4. Reasoning Problems such as What can be derived from this set of facts? Like automatic synthesis, automatic reasoning may be hard.   5. Data Analysis Problems such as What are the common patterns shown in this set of images? There are a lot of approaches that we may take to solve this problem; but this is not a problem addressed by search engines or Q&amp;A systems.   6. “Personal” Problems such as I know person A and person B but they don&#39;t like each other, how can I put them to work? This may not be a scientific problem and its solution may very much reply on experiences, social considerations, etc.       
 
         [0013]    Our main point is not to classify all the problems. What actually interests us is matching problems with solutions. The Internet does provide us an infrastructure to connect problems and solutions, but we may have not fully utilized this infrastructure. So far it has been useful for trading. If we can extend the concept of trading from goods to problems and buyers to solutions, we may have a new story for the Internet. 
       SUMMARY OF THE INVENTION 
       [0014]    For purposes of summarizing the invention, certain aspects, advantages and novel features of the invention have been described herein. It should be understood that not necessarily all such aspects, advantages or features will be embodied in any particular embodiment of the invention. 
         [0015]    This invention provides an Internet search system that allows users to search for services (tools, content, online services, etc.) by composing a problem statement in a structured natural language. This is different from traditional search systems in which user needs are expressed in terms of keywords. This is also different from traditional Question and Answering (Q&amp;A) systems in which user needs are expressed as questions. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
       [0016]    The following subsections describe a semantic search system that embodies various inventive features. The various inventive features can be implemented differently than described herein. Thus, the following description is intended only to illustrate, and not limit, the scope of the present invention. 
       Architecture of SNLSS 
       [0017]    The Structured Natural Language based Search System (SNLSS) provides users with a problem-driven interface to search for a service according to users&#39; problems, where a service may be an online service, an online database, or a web service that provides its API for composing more complex services. The architecture of SNLSS is shown in  FIG. 1 :
       1. Query Sentence User Interface  110 , a query interface through which a user can pose a query sentence in a structured natural language.   2. Capability Sentence User Interface  120 , an interface through which a solution provider can pose a capability sentence in a structured natural language.   3. Capability Base  130  that sores all capability sentences provided by service providers.   4. Query-Capability Matcher  140 , that matches a query sentence with a set of capability sentences in the same structured language and returns services whose capability can match the query sentence.       
 
       Structured Natural Languages (SNL) 
       [0022]    An SNL is a subset of natural language whose sentences are imperative sentences of natural language with at least one additional constraint on its grammar. For example we can define one SNL (called SNL-1) whose structure is defined by the following, where reserved words are expressed in upper-case letters: 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 [GIVEN &lt;noun phrase&gt; [AS $&lt;variable-id&gt;]]* 
               
               
                   
                 [WITH &lt;noun phrase&gt; [AS $&lt;variable-id&gt;]]* 
               
               
                   
                 &lt;verb phrase&gt; 
               
               
                   
                 [THAT &lt;condition clause&gt; AND THAT &lt;condition clause&gt; ....] 
               
               
                   
                   
               
             
          
         
       
     
         [0023]    We will later refer to “[GIVEN &lt;noun phrase&gt;]” as a GIVEN phrase, and “[WITH &lt;noun phrase&gt;]” as a WITH phrase. In the above, a condition clause modifies a noun specified earlier in the sentence, the notation [ . . . ] means the text pattern enclosed by the pair of brackets is optional, the notation [ . . . ]*designates the text pattern enclosed by the pair of brackets may occur zero, one or more times, and “AS $&lt;variable-id&gt;” defines a variable whose name has to be preceded by ‘$’. Variables, once defined, can be used in the verb phrase and any condition clause. Any variable defined in a GIVEN phrase can be used in a WITH phrase. 
         [0024]    Following are some example sentences described in SNL-1. Note that a sentence may be a query sentence or a capability sentence, depending on who (service consumer or service provider) enters the sentence. 
         [0000]    Example 1: Given a dataset of images, classify blobs of images in a dataset.
 
GIVEN a dataset of images
 
Classify blobs of images
 
Example 2: Given an image dataset, identify blob clusters that look like a satellite.
 
GIVEN a dataset of images AS $x
 
Identify blobs of images of $x
 
THAT looks like a satellite
 
Example 3: Given a dataset, identify blob clusters not overlapping with other blob clusters.
 
GIVEN a dataset of images
 
Identify blobs of images
 
THAT are not overlapping
 
Example 4: Given a dataset, find distribution of some variables over others.
 
GIVEN a dataset of variables [x1, x2, . . . , x10]
 
Find distribution of x5 over [x1, x4]
 
Example 5: Given a set of video clips, find those containing a scene similar to a given scene.
 
GIVEN a dataset of video clips
 
GIVEN a video clip $x
 
Find clips
 
THAT are similar to $x
 
In the above, $x is a variable. In SNL, a variable is preceded by a dollar sign (‘$’) and can be created with a GIVEN phrase.
 
       Example 6: [Text] Q&amp;A? 
       [0025]    GIVEN a dataset of web pages
 
Find a web page
 
THAT containing an answer for ‘ . . . ’
 
         [0026]      FIG. 2  shows one embodiment of a computer-implemented process of composing an SNL1 sentence. If the user wants to define any GIVEN phrase, the process proceeds to a block  210 , where the user specifies a noun phrase. If the user wants to define any WITH phrase, the process proceeds to a block  220 , where the user specifies a noun phrase. At a block  230 , the process asks the user to specify a verb phrase. If the user wishes to specify a condition clause, then the process proceeds to a block  240 , where the user is prompted to specify a condition clause. 
         [0027]    Below is another SNL; let us call it SNL-2: 
       FIND PERSON 
       [0028]    [THAT &lt;condition clause&gt; AND THAT &lt;condition clause&gt; . . . ]
 
Example 7: Who invented telephone?
 
       FIND PERSON 
       [0029]    THAT invented telephone 
         [0030]    Yet below is another SNL; let us call it SNL-3: 
       FIND PLACE 
       [0031]    [THAT &lt;condition clause&gt; AND THAT &lt;condition clause&gt; . . . ] 
       Example 8: Where is California? 
     FIND PLACE 
     THAT is California 
     Service Discovery 
       [0032]    Service discovery in SNLSS contains two phases: service registration and service matching.
       1. Service Registration: To have a better chance of being discovered by SNLSS, a service provider can register in advance. Service providers have to provide service information, including URL, namespace, capability sentence(s), etc.   2. Service Matching: When user poses a query sentence, the Query-Capability Matcher handles the matching between the query sentence and the available capability sentences stored in the Capability Base that are expressed in the same SNL and determines if a service has the capability to answer the query.       
 
         [0035]      FIG. 3  shows one embodiment of a computer-implemented process of SNLSS. At a block  310 , a user chooses a structured natural language to compose a query sentence. At a block  320 , a user composes a query sentence in the structured natural language selected. The sentence is matched against the capability sentences in the same structured natural language stored in a block  330 . Finally all matched solutions are listed in a block  340 . 
       BRIEF DESCRIPTION OF THE DRAWINGS 
       [0036]      FIG. 1  illustrates one embodiment of the search system 
         [0037]      FIG. 2  illustrates one embodiment of the sentence composition process for an SNL 
         [0038]      FIG. 3  illustrates one embodiment of the control flow of the system