Performing a keyword search based on identifying exclusive lowest common ancestor (ELCA) nodes

• US 8,086,606 B1
• Filed: 07/15/2008
• Issued: 12/27/2011
• Est. Priority Date: 07/15/2008
• Status: Active Grant

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: Teradata US, Inc. (Teradata Corporation)
• Inventors: Xu, Yu
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Davanlou, Soheila
• Application Number:
  US12/173,270
• Time in Patent Office: 1,260 Days
• Field of Search: 707/602, 707/736, 707/770
• US Class Current: 707/736
• CPC Class Codes: G06F 16/80 of semi-structured data, e.g. markup language structured data such as SGML, XML or HTML content-based retrieval of web data G06F16/95

Abstract

A hierarchical arrangement of nodes is provided to represent Extensible Markup Language (XML) data. In response to a keyword search query containing query keywords, sets of nodes in the hierarchical arrangement are identified for respective query keywords. A smallest of the sets of nodes is identified, and starting with the smallest of the sets of nodes, a stack-based algorithm is applied to identify exclusive lowest common ancestor (ELCA) nodes of the hierarchical arrangement.

Claims

1. A computer comprising:

a storage to store a hierarchical arrangement of nodes representing Extensible Markup Language (XML) data;

a processor responsive to a keyword search query containing query keywords to;

identify sets of nodes in the hierarchical arrangement for respective query keywords;

identify a smallest of the sets of nodes; and

starting with the smallest of the sets of nodes, apply a stack-based algorithm to identify exclusive lowest common ancestor (ELCA) nodes of the hierarchical arrangement.

2. The computer of claim 1, wherein the storage is to further store a stack used by the stack-based algorithm to store stack entries created for respective nodes in the hierarchical arrangement.

3. The computer of claim 1, wherein the processor is to further output a result of the keyword search based on the identified ELCA nodes.

4. The computer of claim 3, wherein the processor is to identify the ELCA nodes by:

identifying candidate ELCA nodes; and

determining whether the candidate ELCA nodes are actual ELCA nodes.

5. The computer of claim 3, wherein the result of the keyword search is a set of the identified ELCA nodes that contain at least one occurrence of all of the query keywords either in labels of the ELCA nodes or in the labels of the ELCA nodes'"'"' descendant nodes, after excluding occurrences of the keywords in the subtrees of the tree that already contain at least one occurrence of all the query keywords.

6. A method, executed by a computer, of performing a keyword search in data stored within a storage in a hierarchical arrangement of nodes representing Extensible Markup Language (XML) data;

the method comprising;

executing, by a processor in communication with said storage, a keyword search query containing query keywords to;

identify sets of nodes in the hierarchical arrangement for respective query keywords;

identify a smallest of the sets of nodes; and

starting with the smallest of the sets of nodes, apply a stack-based algorithm to identify exclusive lowest common ancestor (ELCA) nodes of the hierarchical arrangement.

7. The method of claim 6, wherein said step of executing, by said processor, a keyword search query containing query keywords outputs a result of the keyword search based on the identified ELCA nodes.

8. The method of claim 7, wherein said step of executing, by said processor, a keyword search query containing query keywords identifies the ELCA nodes by:

identifying candidate ELCA nodes; and

determining whether the candidate ELCA nodes are actual ELCA nodes.

9. The method of claim 7, wherein the result of the keyword search is a set of the identified ELCA nodes that contain at least one occurrence of all of the query keywords either in labels of the ELCA nodes or in the labels of the ELCA nodes'"'"' descendant nodes, after excluding occurrences of the keywords in the subtrees of the tree that already contain at least one occurrence of all the query keywords.

10. An article comprising at least one non-transitory computer-readable storage medium containing instructions for causing a computer to executa a method for performing a keyword search in data stored within a storage in a hierarchical arrangement of nodes representing Extensible Markup Language (XML) data, the method comprising:

executing, by a processor in communication with said storage, a keyword search query containing query keywords to;

identify sets of nodes in the hierarchical arrangement for respective query keywords;

identify a smallest of the sets of nodes; and

starting with the smallest of the sets of nodes, apply a stack-based algorithm to identify exclusive lowest common ancestor (ELCA) nodes of the hierarchical arrangement.

11. The article of claim 10, wherein said step of executing, by said processor, a keyword search query containing query keywords outputs a result of the keyword search based on the identified ELCA nodes.

12. The computer of claim 11, wherein said step of executing, by said processor, a keyword search query containing query keywords identifies the ELCA nodes by:

identifying candidate ELCA nodes; and

determining whether the candidate ELCA nodes are actual ELCA nodes.

13. The article of claim 11, wherein the result of the keyword search is a set of the identified ELCA nodes that contain at least one occurrence of all of the query keywords either in labels of the ELCA nodes or in the labels of the ELCA nodes'"'"' descendant nodes, after excluding occurrences of the keywords in the subtrees of the tree that already contain at least one occurrence of all the query keywords.