Extensible database framework for management of unstructured and semi-structured documents

• US 6,968,338 B1
• Filed: 08/29/2002
• Issued: 11/22/2005
• Est. Priority Date: 08/29/2002
• Status: Expired due to Term

• Current Assignee: The United States of America As Represented By The Secretary of Agriculture
• Original Assignee: United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration
• Inventors: Gawdiak, Yuri O., Lin, Shu-Chun Y., Tran, Khai Peter B., La, Tracy T., Maluf, David A.
• Primary Examiner(s): Ali, Mohammad
• Assistant Examiner(s): FLEURANTIN, JEAN B
• Application Number:
  US10/232,975
• Time in Patent Office: 1,181 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 709/217, 709/219, 709/225, 709/229, 715513-515
• US Class Current: 707/741
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 16/38 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: Y10S 707/917 Text
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

Method and system for querying a collection of Unstructured or semi-structured documents to identify presence of, and provide context and/or content for, keywords and/or keyphrases. The documents are analyzed and assigned a node structure, including an ordered sequence of mutually exclusive node segments or strings. Each node has an associated set of at least four, five or six attributes with node information and can represent a format marker or text, with the last node in any node segment usually being a text node. A keyword (or keyphrase) is specified, and the last node in each node segment is searched for a match with the keyword. When a match is found at a query node, or at a node determined with reference to a query node, the system displays the context and/or the content of the query node.

Claims

1. A computer-implemented method for querying a collection of Unstructured documents, the method comprising:

(1) providing an Unstructured collection including at least one document;

(2) associating with each document in the collection a connected node structure including an ordered sequence of document nodes, with each node being labeled by a document node indicium that provides information on at least four of the following attributes associated with the node and corresponding to at least one document;

(1) a first attribute that allows identification of a unique number associated with the node;

(2) a second attribute that specifies a descriptive label for the node;

(3) a third attribute that specifies data type for the node, from among at least two selected data types, and indicates processing requirements for the node;

(4) a fourth attribute that provides text data, if any, associated with the node;

(5) a fifth attribute that specifies a node label, if any, for a node, if any, that serves as a parent node for the node; and

(6) a sixth attribute that specifies a node label, if any, for a node, if any, that serves as a sibling node for the node, where information from the fourth attribute is included in the node indicium;

(3) receiving a query, including at least one query keyword, for the collection of documents, and specifying at least one of keyword context and keyword content;

(4) determining a set of query nodes in the node structure, each of which contains at least one occurrence of the keyword in the fourth attribute;

(5) providing information on at least one selected fourth attribute containing the keyword, for at least one query node in the query node set;

(6) determining if the query specifies context for the keyword;

(7) when the query specifies context for the keyword, determining if the query node provides context for the keyword;

(8) when the query node does not provide context for the keyword, replacing the query node by a left-adjacent node as a new query node, and returning to step (7) at least once;

(9) when the query node provides context for the keyword, adding the query node to a context list, and returning to step (5) at least once;

(10) determining if the query specifies content for the keyword;

(11) when the query specifies content for the keyword, determining if the query node provides content for the keyword;

(12) when the query node does not provide content for the keyword, replacing the query node by at least one of a right-adjacent node and a selected child node as a new query node, and returning to step (11) at least once; and

(13) when the query node provides content for the keyword, adding the query node to a content list, and returning to said step (5) at least once.

2. The method of claim 1, further comprising displaying at least one of (i) said context in said context list and (ii) said content in said content list, for at least one of said query nodes.

3. The method of claim 1, further comprising providing said information on at least said first, second, fourth and sixth attributes.

4. The method of claim 1, further comprising:

labeling at least one of said document nodes with said indicium that provides information on at least five of said attributes; and

providing said information on at least said first, second, fourth, fifth and sixth attributes.

5. A computer-implemented method for querying a collection of Unstructured documents, the method comprising:

(1) providing an Unstructured collection including at least one document;

(2) associating with each document in the collection a connected node structure including an ordered sequence of document nodes, with each node being labeled by a document node indicium that provides information on no more than four of the following attributes associated with the node;

(1) a first attribute that allows identification of a unique number associated with the node;

(2) a second attribute that specifies a descriptive label for the node;

(3) a third attribute that specifies data type for the node, from among at least two selected data types, and indicates processing requirements for the document node;

(4) a fourth attribute that provides text data, if any, associated with the node;

(5) a fifth attribute that specifies a node label, if any, for a node, if any, that serves as a parent node for the node; and

(6) a sixth attribute that specifies a node label, if any, for a node, if any, that serves as a sibling node for the node, where information from the fourth attribute is included in the node indicium;

(3) receiving a query, including at least one query keyword, for the collection of documents, and specifying at least one of context and content for the keyword;

(4) determining a set of query nodes in the node structure, each of which contains at least one occurrence of the keyword in the fourth attribute;

(5) providing information on at least one selected fourth attribute containing the keyword, for at least one query node in the query node set;

(6) determining if the query specifies context for the keyword;

(7) when the query specifies context for the keyword, determining if the query node provides context for the keyword;

(8) when the query node does not provide context for the keyword, replacing the query node by a left-adjacent node as a new query node, and returning to step (7) at least once;

(9) when the query node provides context for the keyword, adding the query node to a context list, and returning to step (5) at least once;

(10) determining if the query specifics content for the keyword;

(11) when the query specifies content for the keyword, determining if the query node provides content for the keyword;

(12) when the query node does not provide content for the keyword, replacing the query node by at least one of a right-adjacent node and a selected child node as a new query node, and returning to step (11) at least once; and

(13) when the query node provides content for the keyword, adding the query node to a content list, and returning to said step (5) at least once.

6. The method of claim 5, further comprising displaying at least one of (i) said context in said context list and (ii) said content in said content list, for at least one of said query nodes.

7. The method of claim 5, further comprising providing said information on said first, second, fourth and sixth attributes.

8. A computer-implemented method for querying a collection of Unstructured documents, the method comprising:

(1) providing an Unstructured collection including at least one document;

(2) associating with each document in the collection a connected node structure including an ordered sequence of document nodes, with each node being labeled by a document node indicium that provides information on no more than five of the following attributes associated with the node;

(1) a first attribute that allows identification of a unique number associated with the node;

(2) a second attribute that specifies a descriptive label for the node;

(3) a third attribute that specifies data type for the node, from among at least two selected data types, and indicates processing requirements for the document node;

(4) a fourth attribute that provides text data, if any, associated with the node;

(5) a fifth attribute that specifies a node label, if any, for a node, if any, that serves as a parent node for the node; and

(6) a sixth attribute that specifies a node label, if any, for a node, if any, that serves as a sibling node for the node, where information from the fourth attribute is included in the node indicium;

(3) receiving a query, including at least one query keyword, for the collection of documents, and specifying at least one of context and content for the keyword;

(4) determining a set of query nodes in the node structure, each of which contains at least one occurrence of the keyword in the fourth attribute;

(5) providing information on at least one selected fourth attribute containing the keyword, for at least one query node in the query node set;

(6) determining if the query specifies context for the keyword;

(7) when the query specifies context for the keyword, determining if the query node provides context for the keyword;

(8) when the query node does not provide context for the keyword, replacing the query node by a left-adjacent node as a new query node, and returning to step (7) at least once;

(9) when the query node provides context for the keyword, adding the query node to a context list, and returning to step (5) at least once;

(10) determining if the query specifies content for the keyword;

(11) when the query specifies content for the keyword, determining if the query node provides content for the keyword;

(12) when the query node does not provide content for the keyword, replacing the query node by at least one of a right-adjacent node and a selected child node as a new query node, and returning to step (11) at least once; and

(13) when the query node provides content for the keyword, adding the query node to a content list, and returning to said step (5) at least once.

9. The method of claim 8, further comprising displaying at least one of (i) said context in said context list and (ii) said content in said content list, for at least one of said query nodes.

10. The method of claim 8, further comprising providing said information on said first, second, fourth, fifth and sixth attributes.

11. A computer-implemented system for querying a collection of Unstructured documents, the system comprising a computer that is programmed:

(1) to provide an Unstructured collection including at least one document;

(2) to associate with each document in the collection a connected node structure including an ordered sequence of document nodes, with each node being labeled by a document node indicium that provides information on at least four of the following attributes associated with the node and corresponding to at least one document;

(1) a first attribute that allows identification of a unique number associated with the node;

(2) a second attribute that specifies a descriptive label for the node;

(3) a third attribute that specifies data type for the node, from among at least two selected data types, and indicates processing requirements for the node;

(4) a fourth attribute that provides text data, if any, associated with the node;

(5) a fifth attribute that specifies a node label, if any, for a node, if any, that serves as a parent node for the node; and

(6) a sixth attribute that specifies a node label, if any, for a node, if any, that serves as a sibling node for the node, where information from the fourth attribute is included in the node indicium;

(3) to receive a query, including at least one query keyword, for the collection of documents, and specifying at least one of keyword context and keyword content;

(4) to determine a set of query nodes in the node structure, each of which contains at least one occurrence of the keyword in the fourth attribute;

(5) to provide information on at least one selected fourth attribute containing the keyword, for at least one query node in the query node set;

(6) to determine if the query specifies context for the keyword;

(7) when the query specifies context for the keyword, to determine if the query node provides context for the keyword;

(8) when the query node does not provide context for the keyword, to replace the query node by a left-adjacent node as a new query node, and to return to step (7) at least once;

(9) when the query node provides context for the keyword, to add the query node to a context list, and to return to step (5) at least once;

(10) to determine if the query specifies content for the keyword;

(11) when the query specifies content for the keyword, to determine if the query node provides content for the keyword;

(12) when the query node does not provide content for the keyword, to replace the query node by at least one of a right-adjacent node and a selected child node as a new query node, and to return to step (11) at least once; and

(13) when the query node provides content for the keyword, to add the query node to a content list, and to return to said step (5) at least once.

12. The system of claim 11, wherein said computer is further programmed to display at least one of (i) said context in said context list and (ii) said content in said content list, for at least one of said query nodes.

13. The system of claim 11, wherein said computer is further programmed to provide said information on at least said first, second, fourth and sixth attributes.

14. The system of claim 11, wherein said computer is further programmed:

to label at least one of said document nodes with said indicium that provides information on at least five of said attributes; and

to provide said information on at least said first, second, fourth, fifth and sixth attributes.

15. A computer-implemented system for querying a collection of Unstructured documents, the system comprising a computer that is programmed:

(1) to provide an Unstructured collection including at least one document;

(2) to associate with each document in the collection a connected node structure including an ordered sequence of document nodes, with each node being labeled by a document node indicium that provides information on no more than four of the following attributes associated with the node and corresponding to at least one document;

(1) a first attribute that allows identification of a unique number associated with the node;

(2) a second attribute that specifies a descriptive label for the node;

(3) a third attribute that specifies data type for the node, from among at least two selected data types, and indicates processing requirements for the node;

(4) a fourth attribute that provides text data, if any, associated with the node;

(5) a fifth attribute that specifies a node label, if any, for a node, if any, that serves as a parent node for the node; and

(6) a sixth attribute that specifies a node label, if any, for a node, if any, that serves as a sibling node for the node, where information from the fourth attribute is included in the node indicium;

(3) to receive a query, including at least one query keyword, for the collection of documents, and specifying at least one of keyword context and keyword content;

(4) to determine a set of query nodes in the node structure, each of which contains at least one occurrence of the keyword in the fourth attribute;

(5) to provide information on at least one selected fourth attribute containing the keyword, for at least one query node in the query node set;

(6) to determine if the query specifies context for the keyword;

(7) when the query specifies context for the keyword, to determine if the query node provides context for the keyword;

(8) when the query node does not provide context for the keyword, to replace the query node by a left-adjacent node as a new query node, and to return to step (7) at least once;

(9) when the query node provides context for the keyword, to add the query node to a context list, and to return to step (5) at least once;

(10) to determine if the query specifies content for the keyword;

(11) when the query specifies content for the keyword, to determine if the query node provides content for the keyword;

(12) when the query node does not provide content for the keyword, to replace the query node by at least one of a right-adjacent node and a selected child node as a new query node, and to return to step (11) at least once; and

(13) when the query node provides content for the keyword, to add the query node to a content list, and to return to said step (5) at least once.

16. The system of claim 15, wherein said computer is further programmed to display at least one of (i) said context in said context list and (ii) said content in said content list, for at least one of said query nodes.

17. The system of claim 15, wherein said computer is further programmed to provide said information on said first, second, fourth and sixth attributes.

18. A computer-implemented system for querying a collection of Unstructured documents, the system comprising a computer that is programmed:

(1) to provide an Unstructured collection including at least one document;

(2) to associate with each document in the collection a connected node structure including an ordered sequence of document nodes, with each node being labeled by a document node indicium that provides information on no more than five of the following attributes associated with the node a corresponding to at least one document;

(1) a first attribute that allows identification of a unique number associated with the node;

(2) a second attribute that specifies a descriptive label for the node;

(3) a third attribute that specifies data type for the node, from among at least two selected data types, and indicates processing requirements for the node;

(4) a fourth attribute that provides text data, if any, associated with the node;

(5) a fifth attribute that specifies a node label, if any, for a node, if any, that serves as a parent node for the node; and

(6) a sixth attribute that specifies a node label, if any, for a node, if any, that serves as a sibling node for the node, where information from the fourth attribute is included in the node indicium;

(3) to receive a query, including at least one query keyword, for the collection of documents, and specifying at least one of keyword context and keyword content;

(4) to determine a set of query nodes in the node structure, each of which contains at least one occurrence of the keyword in the fourth attribute;

(5) to provide information on at least one selected fourth attribute containing the keyword, for at least one query node in the query node set;

(6) to determine if the query specifies context for the keyword;

(7) when the query specifies context for the keyword, to determine if the query node provides context for the keyword;

(8) when the query node does not provide context for the keyword, to replace the query node by a left-adjacent node as a new query node, and to return to step (7) at least once;

(9) when the query node provides context for the keyword, to add the query node to a context list, and to return to step (5) at least once;

(10) to determine if the query specifies content for the keyword;

(11) when the query specifies content for the keyword, to determine if the query node provides content for the keyword;

(12) when the query node does not provide content for the keyword, to replace the query node by at least one of a right-adjacent node and a selected child node as a new query node, and to return to step (11) at least once; and

(13) when the query node provides content for the keyword, to add the query node to a content list, and to return to said step (5) at least once.

19. The system of claim 18, wherein said computer is further programmed to display at least one of (i) said context in said context list and (ii) said content in said content list, for at least one of said query nodes.

20. The system of claim 18, wherein said computer is further programmed to provide said information on said first, second, fourth and sixth attributes.