Abstract:
An underlying schema is discovered for an HTML document or a set of HTML documents, authored in various styles. Prior domain knowledge regarding punctuation, keywords, synonyms and HTML tags is used to 1) break a document up into separate objects, 2) identify the objects corresponding to keywords, 3) regroup objects: into hierarchical layers of abstraction, 4) logically order objects at the same level of abstraction, and 5) finally remove any non-keyword related information from the document&#39;s discovered schematic structure. The discovered schema supports structural queries from search engines that locate data that are more semantically related to the requested information than data located by simple keyword searching.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of Invention 
     The present invention generally relates to document processing. The method and apparatus of the present invention have particular application to extracting schematic information from a set of documents. 
     2. Discussion of Prior Art 
     The world wide web (throughout this specification,web, www, and world wide web are used interchangeably) is presently growing at an average of 1 million pages per day and is an amazing source of information. All of this information is buried in HTML documents authored by a wide variety of people with differing skills, culture, and purpose and using a wide variety of tools to author these pages. HTML does give structure to the authored documents, but mainly for viewing purposes. HTML has a fixed set of tags which are mostly used to enhance the visual appeal of the documents. Thus, it often happens that HTML pages for the same purpose have a different set of tags. For instance, people often mark-up their resumes in HTML on their home pages. Depending on the styles, these resume documents look significantly different from each other. This difference is acceptable for viewing purposes, but presents great difficulties to automatic programs which try to extract pertinent information from them. 
     The web is not just used for browsing anymore; automatic programs, like web crawlers, visit web sites and extract information to serve search engines, or push engines. Comparison shopping engines visit web sites describing similar information, such as prices, and extract semantic information from these sites. Given the format variances possible between topically related web pages, retrieved data is often unhelpful, unrelated or difficult to extract. 
     However, the present invention addresses this need to build search engines that allow users to formulate structural queries like “find a student with a Master&#39;s degree and a GPA of 3.5 or more and skills in Java.” The present invention allows the extraction of structural information buried in HTML pages which cater to the same topic but are authored with significantly different styles. 
     Some specific prior art related to the present invention is discussed below. These references describe methods of investigating the structure of documents and retrieving documents from large databases in response to user queries. 
     Two articles which describe attempts to discover structure from semi-structured data are “Identifying Aggregates in Hypertext Structures”, Proceedings of ACM Hypertext &#39;91, pp. 63-74, and “Structural Properties of Hypertext”, Proceedings of the Ninth ACM Conference on Hypertext, pp. 180-187, 1998. These attempts, however, focus on the organization of a set of hypertext documents by following their links rather than considering the schematic nature of the individual documents. 
     Three other articles describing related investigations are: “Inferring Structure in Semistructured Data”, Workshop on Management of Semistructured Data, 1997; “Extracting Schema from Semistructured Data”, SIGMOD98, pp. 295-306; and “Discovering Association of Structure from Semistructured Objects”, IEEE Trans. on Knowledge and Data Engineering, 1999. However, these articles do not consider the schematic structure of individual documents or documents which have different schemas. 
     The patent to Driscoll (U.S. Pat. No. 5,694,592) teaches a method of querying and retrieving documents from a database using semantic knowledge about the query string to determine document relevancy. 
     The patent to Ishikawa (U.S. Pat. No. 5,848,407) describes a method of presenting potentially related hypertext document summaries to a user who is using a search engine that indexes a plurality of hypertext documents. 
     Whatever the precise merits and features of the prior art in this field, the earlier art does not achieve or fulfill the purposes of the present invention. The prior art does not provide for automatically identifying schematic structural and tag information from HTML documents and then converting these documents according to the extracted information. 
     SUMMARY OF THE INVENTION 
     The present invention describes a system and method that extracts keywords and structural information from hypertext or mark-up language documents (e.g. HTML) and then reformulates them as documents with a common structure and common set of tags. One underlying goal is to convert a collection of HTML documents, written in different styles, into XML documents following a common schema. XML, eXtended Markup Language, defines a web standard for describing schemas for different domains. For instance, one domain might be resumes, and a schema can be defined for describing all resumes. Thus all resume documents are written using the structure and tags described by this schema. Thereafter, keyword based search engines will be able to support queries and retrieve documents that are schematically and semantically closer to the information users are looking for. Using a five-stage process, the common schematic structures are discovered for the set of HTML documents authored in various styles. Prior domain knowledge regarding punctuation, keywords, synonyms and HTML tags is used to 1) break a document up into separate objects, 2) identify the objects corresponding to keywords, 3) regroup objects into hierarchical layers of abstraction, 4) logically order objects at the same level of abstraction, and finally 5) remove any non-keyword related information from the document&#39;s discovered schematic structure. The discovered schema supports structural queries from search engines that locate data that are more semantically related to the requested information than data located by simple keyword searching. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 illustrates an overview of an example web-based environment for the present invention. 
     FIG. 2 illustrates an overview of a five step schema extraction process according to the present invention. 
     FIG. 3 illustrates an example HTML formatted resume used by the present invention. 
     FIG. 4 a  illustrates the structural effect of the tokenization function of the present invention on an example XML document. 
     FIG. 4 b  illustrates the effect of the tokenization function of the present invention on an example XML document&#39;s coding. 
     FIG. 5 a  illustrates the structural effect of the keywording function of the present invention on an example XML tree. 
     FIG. 5 b  illustrates the effect of the keywording function of the present invention on an example XML document&#39;s coding. 
     FIG. 6 a  illustrates the structural effect of the phrasing function of the present invention on an example XML tree. 
     FIG. 6 b  illustrates the effect of the phrasing function of the present invention on an example XML document&#39;s coding. 
     FIG. 7 a  illustrates the structural effect of the heading function of the present invention on an example XML tree. 
     FIG. 7 b  illustrates the effect of the heading function of the present invention on an example XML document&#39;s coding. 
     FIG. 8 a  illustrates an extracted schema from an example XML tree resulting from applying the consolidation function of the present invention. 
     FIG. 8 b  illustrates the coding of an extracted schema from an example XML tree resulting from applying the consolidation function of the present invention. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     While this invention is illustrated and described in a preferred embodiment, the invention may be produced in many different configurations, forms and materials. There is depicted in the drawings, and will herein be described in detail, a preferred embodiment of the invention, with the understanding that the present disclosure is to be considered as an exemplification of the principles of the invention and the associated functional specifications of the materials for its construction and is not intended to limit the invention to the embodiment illustrated. Those skilled in the art will envision many other possible variations within the scope of the present invention. 
     FIG. 1 illustrates an overview of the flow of the present invention, in an example environment of a web-based search engine. This example of the present invention works in the following manner. 
     A web crawler  104  traverses the web  102  and retrieves a number of HTML documents  106 . These HTML documents  108  are converted, using known methods, to XML documents  110  by HTML-to-XML filter  108 . This filter converts the HTML document to “well-formed” XML documents, as defined by present and future versions of the XML specification. Also, representations of domain knowledge such as keywords and matching information  112  as well as HTML tag knowledge  114  are constructed by the users of the present system. 
     HTML tag annotations  114 , keyword knowledge  112 , and XML documents  110  are provided to extractor  116  which extracts schematic information  118  from XML documents  110 . The schematic information extractor  116  uses a five step process to extract schematic information from a set of input documents. FIG. 2 illustrates an overview of schematic information extractor  116  operating on a single XML document. 
     Knowledge regarding token separators  202 , keyword matching information  204 , HTML phrase tags  206 , and HTML header tags  208  are used appropriately during the five steps of the extraction process: tokenizing  210 , keywording  212 , phrasing  214 , heading  216  and consolidating  218 . 
     The input to and the output from these five steps is depicted on the left hand side of FIG.  2  and include either an XML document  220  or an XML tree  222 . 
     Each of the five steps of the schematic extraction process are discussed below in detail. Also, FIG. 3, and FIGS. 4 a  through  8   a  depict an example document and how its structure is transformed by each step of the process. FIGS. 4 b  through  8   b  depict the HTML and XML code of an example document as it is transformed by each step of the process. The example document, illustrated in FIG. 3, is as follows. Note that the node h 2  is incorrectly marked up to denote the incorrect tag usage found in many web documents. 
     &lt;html&gt;&lt;body&gt; 
     &lt;h 1 &gt;Resume of John Dole&lt;/h 1 &gt; 
     &lt;h 2 &gt;Education 
     &lt;table&gt;&lt;tr&gt;&lt;td&gt; 
     Ph.D. in Comp. Sci., University of California, 
     Sept 1996-Present 
     &lt;/td&gt;&lt;/tr&gt; 
     &lt;tr&gt;&lt;td&gt; 
     B.S. (Computer Science), Stanford University, 
     Sept 1993-Jun 1996, GPA 3.9/4.0 
     &lt;/td&gt;&lt;/tr&gt;&lt;/table&gt; 
     &lt;h 2 &gt;Experience&lt;/h 2 &gt; 
     &lt;ul&gt;&lt;li&gt; 
     Research Assistant, University of California, 
     Sept 1997-Present &lt;/li&gt; 
     &lt;li&gt; 
     Teaching Assistant, University of California, 
     Sept 1996-Jun 1997 
     &lt;/li&gt;&lt;/ul&gt;&lt;/h 2 &gt;&lt;/body&gt;&lt;/html&gt; 
     Hypertext documents, as exemplified above, generally follow an ordered tree model. In formal notation, an ordered tree with root root and immediate children c 1 , . . . , c n , is represented as 
     T(root)≡&lt;root, &lt;ST(c 1 ), . . . , ST(c n )&gt;&gt; 
     where          ST        (     c   i     )       ≡     {           T        (     c   i     )             if                   c   i                   is                 an                 internal                 node               c   i           if                   c   i                   is                 a                 leaf                 node                                    
     and an empty tree or node is denoted by ⊥. 
     This formal notation will be relied upon in describing some of the activities of each of the five steps of the schematic information extraction process. In addition to this formal definition, there are also tree functions which represent manipulations that are routinely performed on tree structures. Some of the ones that are used by the present invention include: 
     Function Label: transforms a node into a string by computing the label of the markup tag of a node. 
     Function Value: transforms a node into a string by computing the string value of a node if it is a text node. Otherwise it is ⊥. 
     Function Root: computes the root of the tree to which a node belongs. 
     Function Parent: computes the parent of a node. 
     Function PrevSibling: computes the previous sibling of a node, or ⊥ if the node is the first child of its parent. 
     Function Children: computes the sequence of immediate child nodes of a node. 
     Function Descendants: computes the set of descendant nodes of a node at all levels. 
     Function Replace: replaces a subtree of a tree by another, Specifically, Replace(T(node), c, c′) returns the tree the same as T(node) but with the subtree rooted at c, T(c) replaced by the subtree rooted at c′, T(c′). If T(c′)=⊥, subtree T(c) is deleted. Typically, the shorthand Replace(T(node), &lt;c 1 , . . . , c n &gt;, &lt;c′ 1 , . . . , c′ n &gt;) is used to denote that Replace function is applied consecutively to the tree to replace nodes c i  with c′ i  in the order specified in the sequence. 
     Function Delete: deletes a subtree from a tree. Specifically, Delete(T(node), c) deletes the subtree rooted at c from tree T(node). The shorthand Delete(T(node), {c i }) is used to denote that the Delete function is applied consecutively, in any order, to the tree to remove the subtrees specified in {c i }. 
     Function Insert: inserts a subtree into a tree. Specifically, Insert(T(node), c, c′) inserts the subtree (T(c′) into T(node) as the previous sibling of c. If c=⊥, c′ is inserted as the first child of node. If c′ ∉ Descendants(Root(node)), Delete(T(Parent(c′)), c′) is applied before Insert(T(node), c, c′). 
     Function Parent: computes the parent of a node. 
     Function PrevParent: computes the previous parent for a node. PrevParent(node) is Parent(node) if no tree reordering function has been applied to T(node). If Replace is applied, PrevParent(node) is the replaced node; in the case of Insert, it is ⊥. 
     Tokenize Function 
     In the step of tokenization, a set of punctuation is used to extract structural information from each block of text in the XML document  220 . The tokenize function gets a set of punctuation marks (e.g. {“;”,“,”, “:”}) and uses them to separate out each block of text into smaller blocks of text. This separating results in unrelated phrases being placed in separate subblocks of text. 
     The above list of punctuation marks is one group of marks that handles most general HTML documents expected to be encountered by an information gatherer for a search engine. If a particular domain of documents has particular punctuation marks that are specific to that domain, then the set of applicable marks is modified to include these specific marks. 
     A high level object or concept is often described by several objects which are separated by punctuation. For example, in a resume document, if a topic sentence about the educational background is “University of California at Davis, B.Sci. (Computer Science), Awarded June 1996, GPA 3.8/4.0.” The four pieces of information are: 
     Organization: University of California at Davis 
     Degree: B.Sci. (Computer Science) 
     Date: Awarded June 1996 
     GPA: GPA 3.8/4.0 
     and all are separated by the punctuation “,”. Hence, this heuristic states that a sentence be divided into tokens according to the punctuation. These tokens are then grouped together under a new node labeled item to preserve the fact that the corresponding objects describe the same concept or object of a higher level of abstraction. 
     A formal definition of this tokenizing function, Θ(T(node)), is: 
     Let T(node)≡&lt;node, &lt;T(t 1 ), . . . , T(t n )&gt;&gt;, let TS be a set of punctuation, and let node be tokenized into tokens x={x 1 , . . . , x j }.          Θ        (     T        (   node   )       )       ≡     {               &lt;        item     ,       &lt;          x   1       ,   …              ,       x   j          &gt;&gt;                     If                                node                 is                 a                 text                 node                 and                 x     ≠   0                 &lt;        node        &gt;                   If                 node                 is                 a                 text                 node                 and                 x     =   0                   &lt;        node     ,       &lt;          Θ   (       T        (     t   1     )       ,   …              ,       Θ        (     T        (     t   n     )       )            &gt;&gt;                       Otherwise                                             
     Function Θ states that if a node is a text node, it is tokenized into text nodes x 1 , . . . , x j  according to TS. The text nodes are grouped under a new node labeled item. If the node is not a text node, function Θ is recursively applied to its child nodes. 
     FIGS. 4 a  and  4   b  illustrate how this function transforms the example document from FIG.  3 . 
     Keywording Function 
     This function starts with a set of keywords, their synonyms and certain rules for identifying these keywords from blocks of HTML text and markup. The end result is that these keywords are enhanced to create XML elements with these keywords as element names. 
     Keywords, as used in the present invention, describe important concepts. Formally, let KI={&lt;k i , {s i,j }, whole i , case i &gt;} be the domain knowledge about keywords. It consists of a set of keywords K={k i } and associated with keyword k i  is a set of synonyms {s i,j }. Keyword k i  is identified from a string by matching its synonyms against words in a string; and words are sequences of characters separated by the space character. If case i  is true, pattern matching is case sensitive; otherwise, it is case insensitive. If whole i  is true, then a string must match exactly in order to identify k i ; otherwise only a portion of the string has to match in order to identify k i . 
     Since tokenization partially identifies the component objects describing a higher level object, applying keyword identification after tokenization typically improves the accuracy of identifying the information the keywords describe. For example, the text “University of California, State University of Fresno” is described by two objects—the names of two universities. Assuming there is a keyword Organization with associated synonym “university”, application of keywording before tokenization results in two Organization keywords being identified. However, which Organization the keyword “State” belongs to is ambiguous without using sophisticated parsing mechanisms. No such complex and sophisticated parsing is needed when keyword identification is applied after tokenization. 
     A formal definition of this keywording function Γ(T(node), is: 
     Let KI={&lt;k i , {s i,j }, whole i , case i &gt;} define a set of keywords K={k i } and their information. Keyword function, Γ(T(node), creates keyword nodes for any keywords identified. A node node is termed as a keyword node if Label(node) ∈ K. It is a non-keyword node otherwise. The switches whole i  and case i  are boolean operators which control how a keyword (and its synonyms) are matched as described above. 
     Using a function IK(s), which identifies the set of keywords in a string s; let IK(Value(t i ))={k i,1 , . . . , k i,n }. 
     Γ(T(node)≡&lt;node, &lt;T′(t 1 ), . . . , T′(t n )&gt;&gt;where            T   ′          (     t   i     )       ≡     {               &lt;        item     ,       &lt;          k     i   ,   1         ,   …              ,       k     i   ,   n            &gt;&gt;                     if                   t   i                   is                 a                 text                 node                 and                   Label        (   node   )         ≠   item                   &lt;          k     i   ,   1         ,   …              ,       k     i   ,   n   ,   i            &gt;&gt;                     if                   t   i                   is                 a                 text                 node                 and                   Label        (   node   )         =   item               Γ   (     T        (     t   i     )                 Otherwise                                  
     Function Γ states that if the child node t i  of node is a text node with keywords k i,1 , . . . , k i,n,i  identified, a node labeled with the same keyword is created. These keyword nodes are grouped under a node labeled item. Node item is created if it does not exist. If node item exists (because of tokenization), keyword nodes are grouped under the same item node since all of them descend from the same node. If t i  is not a text node, function Γ is recursively applied to its subtree. 
     FIGS. 5 a  and  5   b  show the effect of the keywording function on the tokenized tree from FIGS. 4 a  and  4   b . In this example, K={Education, Experience, Degree, GPA, Organization, Date, Title}. 
     Phrasing Function 
     In this step, certain HTML tags, which are often used to break a document into sections, are identified and used to restructure the document. 
     The system identifies tags such as p, hr, h 1 , h 2 , etc. as phrase tags. This list of tags is just an example list and various additions and deletions of other HTML tags are also contemplated within the scope of the present invention. 
     The set of mark-up tags M, termed “phrase tags”, give hints to the grouping of semantically related nodes in a hypertext document. Block elements (e.g. p, hr), list elements (e.g. dl, ul), heading elements (e.g. h 1 , h 4 ), and table elements (e.g. tr, td) are often used to divide data into paragraphs or sections. Phrase tags are used to aggregate semantically related nodes by grouping everything between two consecutive nodes, labeled with the same phrase tag, into one new node labeled group. 
     A formal definition of the phrasing function, φ(T(node)), is: 
     Let P  ⊂  M be a set of phrase tags. 
     Define          p   1     ≡     {           t   k           if                   ∃         t   k                   such                 that                   Label        (     t   k     )         ∈     P                 and                                 (     ∄         t   j                   such                 that                   t   j       ∈       P                 and                 j     &lt;   k         )             ⊥       otherwise                                  
     p≡{p 1 , . . . , p m |Label(p k )=Label(p 1 ), p k ∈Children(node)} where p 1  is the first child node of node labeled with a phrase tag and p is the set of child nodes of node with the same label as p 1 . 
     Define function MakeChild:          MakeChild        (       t   i     ,     t   j       )       ≡     {               &lt;          t   i       ,               &lt;        group     ,       &lt;          T        (     c   1     )         ,   …              ,       T        (     c   p     )            &gt;&gt;       ,                             T        (     t     i   +   1       )       ,   …              ,         T        (     t     j   -   1       )            &gt;                   if                 i     &lt;   j                 T        (     t   i     )               if                 i     =   j             ⊥       otherwise                                  
     Function MakeChild makes the subtrees rooted from t i+1 , . . . , t j−1  child nodes of t i . The original children nodes of t i , c 1 , . . . , c p , are grouped under a new node with the tag group. 
     Define phrasing function, φ:          ϕ        (     T        (   node   )       )       ≡     {               &lt;        node     ,               &lt;          t   1       ,              …              ,     PrevSibling        (     p   1     )       ,                             ϕ        (       T   ′          (     p   1     )       )       ,              …              ,       ϕ        (       T   ′          (     p   m     )       )            &gt;&gt;                 if         p   ≠   0               T        (   node   )           otherwise                                  
     where            T   ′          (     p   i     )       ≡     {           MakeChild        (       p   i     ,     p     i   +   1         )               if                 1     ≤   i   ≤     m   -   1                 MakeChild        (       p   i     ,     t   n       )               if                 i     =   m                                    
     Function φ states that if node has child nodes labeled with a phrase tag, for such a node p i , nodes from its next sibling until the next node with the same label (or the last sibling if there is none) become its child nodes. Function φ is recursively applied to the subtree rooted at p i , and nodes before p 1  remain the same. 
     FIGS. 6 a  and  6   b  illustrate the operation of function φ on the example document with P={h 1 , h 2 }. The result, shown in FIG. 6 a , is that h 2   606  and all its children nodes descend from newly created group node  604  which, itself is a child node of h 1   602 . Also, group node  610  is created under h 2   608  and nodes  612  and  614  and their children are moved under group node  610 . 
     Heading Function 
     This function reformats any header tags that are nested under identical header tags. Header tags are typically used to structurally divide HTML documents into separate sections. By requiring that no two-header tags of the same label can be on the same path from the root of the document, this heuristic modifies every such occurrence such that the two occurrences become siblings of each other. 
     These header tags divide data of a document into sections of the same level of abstraction regardless of their markup style. Hence, this heuristic states that objects under nested header tags of the same label are re-ordered to be siblings of each other. 
     A formal definition of this heading function, Ψ(T(node)), is: 
     Let H  ⊂  M be a set of header tags. Heading function Ψ reorders the tree so that there are no two nodes with the same header tags along the same path from the root. 
     Given a node t i  with Label(t i ) ∈ H, define 
     
       
         
               
               
               
             
           
               
                   
               
             
             
               
                 h 
                 = 
                 {t i,1 , . . ., t i,h,i } 
               
               
                   
                 = 
                 {t h |t h  ∈ Descendants (T(t i )) and 
               
               
                   
                   
                 Label(t h ) = Label(t i ) ∈ H and 
               
               
                   
                   
                 (t h′  ∈ Descendants(T(t i )) such that Label(t h′ ) = Label(t i ) and 
               
               
                   
                   
                 t h  ∈ Descendants(T(t h′ ))) } 
               
               
                   
               
             
          
         
       
     
     where {t i,1 , . . . , t i,h,i } is the set of child nodes of t i , labeled with the same header tag which do not have an ancestor labeled with the same header tag except t i  itself, in the subtree T(t i ). 
     
       
         Ψ( T (node))≡&lt;node, &lt; T ′( t   1 ), Ψ( T ( t   1,1 )), . . . , Ψ( T ( t   1,h,1 )), . . . ,  T ′( t   n ), Ψ( T ( t   n,1 )), . . . , Ψ( T ( t   n,h,n )&gt;&gt; 
       
     
     where            T   ′          (     t   i     )       ≡     {           Ψ        (     T        (     t   i     )       )                   If                   t   i       ∉     H                 and                   t   i                   is                 an                 internal                 node                 T        (     t   i     )                   If                   t   i       ∉     H                 and                   t   i                   is                 a                 leaf                 node                 Ψ        (     Delete        (       T        (     t   i     )       ,     {       t     t   ,   1       ,   …              ,     t     i   ,   h   ,   i         }       )       )                   If                   t   i       ∈   H                                    
     Function Ψ states that if a child node t i  is not labeled with a header tag, function Ψ is recursively applied to its subtree. Otherwise, all subtrees under root t i  rooted with the same header tag T(t i,1 ), . . . , T(t i,h,i ) become siblings of t i . Function Ψ is applied recursively to all these subtrees. 
     The result of applying the heading function to the example document is illustrated in FIGS. 7 a  and  7   b . As an example, H={h 2 }, and as a result, in FIG. 7 a , the h 2  nodes  702  and  704  become siblings. 
     Consolidation Function 
     For a document being analyzed by the present invention, the non-keyword nodes do not necessarily provide critical schematical information regarding the document; however, the structure of the keyword nodes are of prime importance. The consolidation function replaces non-keyword nodes with keyword nodes and this heuristic is driven by the following observations. 
     First, very often, the first object of a group of semantically related objects describes the topic of this group of objects. This is analogous to the topic sentence of a paragraph. The heuristic, therefore, replaces a non-keyword node by its first keyword child., Second, an object or concept is often described by a set of objects sharing similar schema and these objects frequently start with the same keyword. Third, if the parent node is a tag known to exhibit list structure (e.g. ul, dl, table), its child nodes are very likely to be objects at the same level of abstraction. Hence, if a sibling of the chosen keyword node is labeled with the same keyword, or their parents have the same tag label, or their parent is a list structure, sibling relationship with the chosen keyword is maintained. 
     For example, given the following hypertext document: 
     &lt;ul&gt; 
     &lt;Degree/&gt; 
     &lt;University/&gt; 
     &lt;Thesis/&gt; 
     &lt;Degree/&gt; 
     &lt;University/&gt; 
     &lt;/ul&gt; 
     with its corresponding schematic structure: 
     &lt;ul&gt; 
     &lt;Degree/&gt; 
     &lt;University/&gt; 
     &lt;Thesis/&gt; 
     &lt;Degree/&gt; 
     &lt;University/&gt; 
     &lt;/ul&gt; 
     the schematic structure is identified based on the following: 
     1) &lt;ul&gt; is a tag known to exhibit list structure, so it is likely that it contains a set of child nodes of similar schematic structure; 
     2) node Degree describes the topic of the nodes under &lt;ul&gt; because it is the first keyword child node of &lt;ul&gt;, and 
     3) two of the child nodes of &lt;ul&gt; are labeled with the same keyword Degree, and these nodes are likely to be “topic sentences” for other nodes. 
     Also, if the previous parents (i.e. the non-keyword nodes replaced) of two sibling nodes have the same tag label, it is likely that they are marked-up in the same way and hence, share similar schematic structure. Sibling relationship is thus maintained for these nodes. For example, using this heuristic, the HTML fragment: 
     
       
         
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 &lt;ul&gt; 
               
             
          
           
               
                   
                 &lt;li&gt; 
               
             
          
           
               
                   
                 &lt;Job/&gt; 
               
               
                   
                 &lt;Organization/&gt; 
               
               
                   
                 &lt;Date/&gt; 
               
             
          
           
               
                   
                 &lt;/li&gt; 
               
               
                   
                 &lt;li&gt; 
               
             
          
           
               
                   
                 &lt;Title/&gt; 
               
               
                   
                 &lt;Organization/&gt; 
               
               
                   
                 &lt;Date/&gt; 
               
             
          
           
               
                   
                 &lt;/li&gt; 
               
             
          
           
               
                   
                 &lt;/ul&gt; 
               
               
                   
                   
               
             
          
         
       
     
     becomes 
     
       
         
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 &lt;ul&gt; 
               
             
          
           
               
                   
                 &lt;Job&gt; 
               
             
          
           
               
                   
                 &lt;Organization/&gt; 
               
               
                   
                 &lt;Date/&gt; 
               
             
          
           
               
                   
                 &lt;/Job&gt; 
               
               
                   
                 &lt;Title&gt; 
               
             
          
           
               
                   
                 &lt;Organization/&gt; 
               
               
                   
                 &lt;Date/&gt; 
               
             
          
           
               
                   
                 &lt;/Title&gt; 
               
             
          
           
               
                   
                 &lt;/ul&gt; 
               
               
                   
                   
               
             
          
         
       
     
     The two &lt;li&gt; nodes are replaced by Job and Title respectively. These consecutive sibling keyword nodes have the same previous parent &lt;li&gt;, which hints that they contain information sharing similar schematic structure. 
     A formal definition of this consolidation function, Δ(T(node)), is: 
     Let L  ⊂  M be a set of list tags whose child nodes contain information at the same level. Define function beSibling:          beSibling        (       k   i     ,     k   j       )       ≡     {         True           if                   Label        (     k   i     )         =       Label        (     k   j     )                     or                               Label        (     PrevParent        (     k   i     )       )       =                             Label        (     PrevParent        (     k   j     )       )       ≠   ⊥   or                             Parent        (     k   i     )       ∈   L             False       otherwise                                             
     Function beSibling states that if node k i , k j  have the same label, or their previous parents have the same label, or their parent is labeled with a list tag, then the two nodes maintain their sibling relationship. 
     Let k≡{k 1 , . . . , k p |Label(k i )∈K, k i ∈Children(node), k i &lt;k i+1 , beSibling(k 1 , k i )=true} 
     where k is the set of child nodes of node which need to maintain sibling relationship.          (     T        (   node   )       )     ≡     {           T        (   node   )                   If                   Label        (   node   )         ∈   K               Δ   (     Replace        (       T        (     Parent        (   node   )       )       ,   node   ,       &lt;            T   ′          (     k   1     )         ,   …              ,         T   ′          (     k   p     )            &gt;         )                     If                   Label        (   node   )         ∉       K                 and                   Parent        (     Parent        (   node   )       )         ≠   ⊥                 Replace        (       T        (     Parent        (   node   )       )       ,   node   ,       &lt;            T   ′          (     k   1     )         ,   …              ,         T   ′          (     k   p     )            &gt;         )               Otherwise                                  
     where            T   ′          (     k   i     )       ≡     {           MakeChild        (       k   i     ,     k     i   +   1         )               if                 i     &lt;   p               T        (     k   i     )               if                 i     =   p                                    
     Function Δ states that a non-keyword node is replaced by its first keyword child node, k 1 , and the other child nodes k 1 , . . . , k p  whose sibling relationship with k 1  must also be maintained. Nodes between k i , k j+1 , become child nodes of k i  in the new subtree T′(k i ). Function Δ is recursively applied to the new tree until a root which is not replaced by any keyword node is reached. 
     FIGS. 8 a  and  8   b  show the final form of the example document after applying the consolidation function with L={ul}. The discovered schematic form of this document, as depicted in FIG. 8 b , is now: 
     
       
         
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
             
           
               
                   
               
             
             
               
                 &lt;html&gt; 
               
               
                 &lt;Education&gt; Education 
               
             
          
           
               
                   
                 &lt;Degree&gt; Ph.D. in Comp. Sci. 
               
             
          
           
               
                   
                 &lt;Organization&gt; University of California &lt;/Organization&gt; 
               
               
                   
                 &lt;Date&gt; Sept 1996-Present &lt;/Date&gt; 
               
             
          
           
               
                   
                 &lt;/Degree&gt; 
               
               
                   
                 &lt;Degree&gt; B.S.(Computer Science) 
               
             
          
           
               
                   
                 &lt;Organization&gt; Stanford University &lt;/Organization&gt; 
               
               
                   
                 &lt;Date&gt; Sep 1993-Jun 1996 &lt;/Date&gt; 
               
               
                   
                 &lt;GPA&gt; GPA 3.9/4.0 &lt;/GPA&gt; 
               
             
          
           
               
                   
                 &lt;/Degree&gt; 
               
             
          
           
               
                   
                 &lt;/Education&gt; 
               
               
                   
                 &lt;Experience&gt; Experience 
               
             
          
           
               
                   
                 &lt;Title&gt; Research Assistant 
               
             
          
           
               
                   
                 &lt;Organization&gt; University of California &lt;/Organization&gt; 
               
               
                   
                 &lt;Date&gt; Sep 1997-Present &lt;/Date&gt; 
               
             
          
           
               
                   
                 &lt;/Title&gt; 
               
               
                   
                 &lt;Title&gt; Teaching Assistant 
               
             
          
           
               
                   
                 &lt;Organization&gt; University of California &lt;/Organization&gt; 
               
               
                   
                 &lt;Date&gt; Sep 1996-Jun 1997 &lt;/Date&gt; 
               
             
          
           
               
                   
                 &lt;/Title&gt; 
               
             
          
           
               
                   
                 &lt;/Experience&gt; 
               
             
          
           
               
                 &lt;/html&gt; 
               
               
                   
               
             
          
         
       
     
     One useful application of the schematic structure discovered is to support structural queries in search engines. These search engines are able to use the schematic structure of keywords to locate data that are more semantically related to the information users are searching for. For example, using simple keyword searching, a job recruiter looking for candidates who hold a masters degree from University of California may uncover candidates who have simply lived in California and received a masters degree elsewhere. 
     However, using the discovered schematic structure 
     &lt;University&gt; 
     &lt;Degree/&gt; 
     &lt;Date/&gt; 
     &lt;/University&gt; 
     the recruiter is now able to locate only those candidates holding masters degrees from University of California by specifying a match of both the degree and university. 
     Very often a set of related hypertext documents share similar schematic structure but their common schema is not explicitly specified. The schematic structure, once discovered using the present invention, from this set of related hypertext documents will serve as the input to discover this common schema. For example, a common schema for a set of hypertext documents similar to the example document, expressed as an XML DTD, would be: 
     &lt;!ELEMENT html (Education, Experience)&gt; 
     &lt;!ELEMENT Education (Degree, (Organization, Date, GPA*))&gt; 
     &lt;!ELEMENT Experience (Title, Organization, Date))&gt; 
     &lt;!ELEMENT Degree #PCDATA&gt; 
     &lt;!ELEMENT Organization #PCDATA&gt; 
     &lt;!ELEMENT Date #PCDATA&gt; 
     &lt;!ELEMENT GPA #PCDATA&gt; 
     &lt;!ELEMENT Title #PCDATA&gt; 
     CONCLUSION 
     A system and method have been shown in the above embodiment for the effective implementation of identifying keywords and their schematic structure from hypertext documents using heuristics guided by domain knowledge. While various embodiments have been shown and described, it will be understood that there is no intent to limit the invention by such disclosure, but rather, it is intended to cover all modifications and alternate constructions falling within the spirit and scope of the invention as defined in the appended claims. For example, the present invention should not be limited by computer operating system, computer hardware platform, specific document source language, or specific document target language, In addition, the present invention can be implemented locally on a single PC, connected workstations (i.e. networked-LAN), across extended networks such as the Internet or using portable equipment such as laptop computers or wireless equipment (RF, microwaves, infrared, photonics, etc.). 
     APPENDIX A 
     Computational Complexity 
     Below we give an analysis on the computational complexity of the structuring functions. We show that each structuring function is applied to the nodes in the tree at most once, which implies that the running time of our heuristics is linear to the size of the tree. We also prove that applying each heuristic more than once does not change the tree structure. Hence, we only need to apply the heuristics once to attain stability. 
     Theorem  1  (One Pass Property) In computing F(T(node)), F ∈ {Θ, Γ, Φ, Ψ, Δ}, F is recursively applied to each node in T(node) at most once. 
     Proof 
     F is only recursively applied to the child nodes of node satisfying the conditions defined by F. Since a node cannot be a child of itself, once the function is applied, it is never applied to it again. 
     Theorem  2  (One Time Property) F(F(T(node)))=F(T(node)), F ∈ {Θ, Γ, Φ, Ψ, Δ}. Hence, we only need to apply each structuring function to the tree once. Applying each function more than once does not change the tree structure. 
     Proof 
     Case I: F=Θ 
     Θ changes the tree structure of text nodes only. Once a text node is tokenized into tokens, the tokens cannot be further tokenized. Hence, when applying Θ to Θ(T(node))), Θ is not recursively applied to node. The tree structure of the node remains unchanged thereafter. 
     Case II: F=Γ 
     This is similar to Case I. 
     Case III: F=Φ 
     In Φ(T(node)), a child p i  of node is either labeled with a phrase tag or its next sibling is labeled with the same phrase tag. Hence, in computing Φ(Φ(T(node))), T 1 (p i )=T(p i ). The tree structure of T(node) is unchanged. 
     Case IV:F=Ψ 
     This is similar to Case III. 
     Case V: F=Δ 
     Δ reorders the tree by replacing all non keyword nodes (except the root) by keyword nodes. Hence in Δ(T(node) all nodes except the root are keyword nodes. Applying Δ to Δ(T(node) does not have any effect on the tree. 
     Empirical Results 
     Experiment Environment 
     We implement the heuristics by combining them into two passes, one top down tree traversal for tokenization, keywording, phrasing and heading, one bottom up tree traversal for consolidation. 
     Domain knowledge specifies the following annotation of hypertext markup tags: 
     TS={′,′,′.′,′,} 
     P={h 1 , h 2 , h 3 , h 4 , h 5 , h 6 , h 4 , div, p, tr, dt, dd, li, title, u, strong, b, ern, i} 
     H={h 1 , h 2 , h 3 , h 4 , h 5 , h 6 , hr, div, center} 
     L={body, table, dl, ul, ol, dir, menu} 
     There are 24 keywords and a total of 233 synonyms specified in domain knowledge. 
     The data is obtained from a collection of resumes available as HTML in the web. A web crawler was used to quickly obtain these resumes. The original hypertext documents are first converted to well formed XML documents before their schematic structure is extracted. Hypertext markup tags not considered in the domain knowledge, such as font, a, meta, dir, are ignored. 
     We ran our experiment on a Pentium 266 MHz processor with 196 MB main memory and 512 B cache. 
     Efficiency 
     We ran the algorithm on 100 hypertext documents to evaluate the average running time of one hypertext document. The average number of nodes of a hypertext document in the dataset is 203 of which 52 are keyword nodes. The average file size is 11.7 KB. The average running time was found to be 0.53 seconds. 
     We measure the scalability of our heuristics with respect to the sizes of the hypertext documents, the number of nodes in the hypertext documents and the number of keyword nodes. 
     The heuristics scaled linearly with the sizes of the documents which estimates the total length of text nodes and the number of nodes in the documents. Tokenize and keywording functions depend on the total length of all text nodes, and all structuring functions depend on the number of keyword nodes. Therefore, the experimental results confirm the One Pass Property. 
     Also, the running time does not bear very strong linear relationship with the number of nodes. This may seem to contradict One Pass Property. However, the running time of tokenize and keywording functions depends on the total length of all the text nodes, not just the number of nodes. Running time of other functions like phrasing, heading and consolidation functions depends on the number of keyword nodes, not the number of nodes in the hypertext documents. Hence, we expect the running time to scale linearly with the number of keyword nodes instead, which was indeed observed. 
     In sum, the heuristics scales linearly with the document sizes and the number of keyword nodes.