Method and system for information extraction

• US 20060161531A1
• Filed: 04/25/2005
• Published: 07/20/2006
• Est. Priority Date: 01/14/2005
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: FatLens, Inc. (Meta Platforms, Inc. (f/k/a Facebook, Inc.))
• Inventors: Kakade, Vinay, Pardasani, Dhiraj, Khandelwal, Shashikant, Padmanabhan, Ranjit, Meyer, Alex
• Granted Patent: US 7,444,325 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A present invention provides a method and a system for extracting information related to a pre-defined context from data sets written in semi-structured or unstructured form, such as a natural language text. The information related to the pre-defined context is stored in an information store in accordance with a pre-defined structural arrangement. Further, the individual data values in the extracted information are assigned weights depending on their relevance to attributes of the predefined context. The operation of assigning weights to the structured information provides a measure for comparing the relevance of a plurality of structurally arranged information to the attributes of the pre-defined context.

Claims

1. A method for extracting information related to a pre-defined context from a data set, the pre-defined context having a set of attributes that define the context, the method comprising the steps of:

a. identifying a relevant data from a group of data sets, the identification of the relevant data set being based on the occurrence of attributes corresponding to the pre-defined context;

b. identifying pertinent information from the relevant data set, the pertinent information being the information that contains values of the attributes corresponding to the pre-defined context;

c. extracting values of the attributes from the pertinent information; and

d. arranging the extracted values in the form of a pre-defined data structure which logically links the attributes to each other, in accordance with their inter-relationships as per the pre-defined context.

2. The method of claim 1 wherein the method further comprises the step of filtering the data set by removing irrelevant information, the irrelevant information being information that is not related to the set of attributes corresponding to the pre-defined context.

3. The method of claim 2 wherein the data set is in an unstructured format, the unstructured format being a format in which the arrangement of data is not in accordance with a pre-defined data structure, the pre-defined data structure being a known manner of arranging data.

4. The method of claim 2 wherein the data set is in a semi-structured format, the semi-structured format being a format in which the arrangement of data is in accordance with a pre-defined data structure, the pre-defined data structure being a known manner of arranging data.

5. The method of claim 4 wherein the step of filtering the data set comprises the steps of:

a. selecting a reference data set, the reference data set being a data set comprising structural and/or textual data that is common across a group of interrelated data sets;

b. comparing the data set with the reference data set to identify the structural and/or textual data that is common between the data set and the reference data set; and

c. removing the common structural and/or textual data from the data set.

6. The method of claim 4 wherein the step of identifying the relevant data set from a group of data sets comprises the steps of:

a. identifying supporting and non-supporting features in the filtered data set, the supporting features being structural or textual features that contain information corresponding to the pre-defined context, the non-supporting features being structural or textual features that do not contain information corresponding to the pre-defined context;

b. assigning a positive weight to each supporting feature in the filtered data set, the positive weight being a positive numerical value that is calculated based on the degree of relevance of the supporting feature to the pre-defined context;

c. assigning a negative weight to each non-supporting feature in the filtered data set, the negative weight being a negative numerical value which is calculated based on the degree of digression of the non-supporting feature from the pre-defined context;

d. calculating a confidence value for the filtered data set, the confidence value being calculated as a function of the positive and negative weights of each supporting and non-supporting feature of the filtered data set, and being used as a measure to identify the relevance of the filtered data set to the pre-defined context; and

e. selecting data sets for further processing by comparing the confidence value of each data set with a threshold confidence value, the selection being done by selecting the data set that has the confidence value greater than a pre-defined threshold confidence value.

7. The method of claim 4 wherein the step of identifying pertinent information from the relevant data set comprises the steps of:

a. identifying nodes of interest in the relevant data set, each node of interest representing the data that contains values of one or more attributes corresponding to the pre-defined context;

b. identifying sub-trees of the node of interests, each sub-tree being a hierarchical structural arrangement of information related to a node of interest in the data set;

c. identifying records in the sub-trees, the record being a part of the sub-tree that contains at least one node of interest and other sub-tree nodes that contain values of the attributes corresponding to the pre-defined context

8. A system for extracting information related to a pre-defined context from a data set, the pre-defined context having a set of attributes that define the context, the system comprising:

a. a data set classifier, to identify a relevant data set from a group of data sets, the identification of the relevant data set being based on the occurrence of attributes corresponding to the pre-defined context;

b. an information identifier, to identify the pertinent information in the relevant data set, the pertinent information being the information that contains the values of the attributes corresponding to the pre-defined context; and

c. an entity extractor, to extract values of the attributes from the pertinent information.

9. The system of claim 8 wherein the system further comprises a content filter, to filter the data set by removing irrelevant information, the irrelevant information being information that is not related to the set of attributes corresponding to the pre-defined context.

10. The system of claim 9 wherein the data set is in an unstructured format, the unstructured format being a format in which the arrangement of data is not in accordance with a pre-defined data structure, the pre-defined data structure being a known manner of arranging data.

11. The system of claim 9 wherein the data set is in a semi-structured format, the semi-structured format being a format in which the arrangement of data is in accordance with a pre-defined data structure, the pre-defined data structure being a known manner of arranging data.

12. The system of claim 11 wherein the content filter comprises:

a. a reference data selector, to select a reference data set, the reference data set being a data set comprising structural and/or textual data that is common across a group of interrelated data sets;

b. a data comparison module, to compare the data set with the reference data set to identify the structural and/or textual data that is common between the data set and the reference data set; and

c. a common-section remover, to remove the common structural and/or textual data from the data set.

13. The system of claim 11 wherein the data set classifier comprises:

a. a feature identifier, to identify the supporting and non-supporting features in the filtered data set, the supporting features being structural or textual features that contain information corresponding to the pre-defined context, the non-supporting features being structural or textual features that do not contain information corresponding to the pre-defined context;

b. a weight assigner, to assign positive and negative weights to the identified supporting and non-supporting features respectively in the filtered data set, the positive weight being a positive numerical value that is calculated based on the degree of relevance of the supporting feature to the pre-defined context, and the negative weight being a negative numerical value that is calculated based on the degree of digression of the non-supporting feature from the pre-defined context;

c. a confidence value calculator, to calculate a confidence value of the filtered data set as a function of the positive and negative weights of each supporting and non-supporting feature of the filtered data set, the confidence value being a numerical value used as a measure to identify the relevance of the filtered data set to the pre-defined context; and

d. a relevance indicator, to select the filtered data set for further processing by selecting the filtered data sets that have a confidence value greater than a pre-defined threshold value.

14. The system of claim 11 wherein the information identifier comprises:

a. a node identifier, to identify nodes of interest in the relevant data set, each node of interest representing the data that contains the values of one or more attributes;

b. a sub-tree identifier, to identify sub-trees of the node of interests, each sub-tree being a hierarchical structural representation of information related to a node of interest in the data set; and

c. a record identifier, to identify records in the sub-trees, the record being a part of the sub-tree that contains at least one node of interest and other sub-tree nodes that contain values of the attributes corresponding to the pre-defined context.

15. The system of claim 11 wherein the entity extractor comprises:

a. a data extractor, to extract the values of the attributes corresponding to the pre-defined context; and

b. an index module, to store the extracted values in the form of a pre-defined data structure which logically links the attributes to each other, in accordance with their inter-relationships in the pre-defined context.

16. A computer program product for use with a computer, the computer program product comprising a computer usable medium having a computer readable program code embodied therein for extracting information related to a pre-defined context from a data set, the pre-defined context comprising a set of attributes that define the context, the data set comprising structural and textual information, the computer program code performing the steps of:

a. identifying a relevant data set from a group of data sets, the identification of the relevant data being based on the occurrence of attributes corresponding to the pre-defined context;

b. identifying pertinent information from the relevant data set, the pertinent information being information that contains the values of attributes corresponding to the pre-defined context;

c. extracting values of the attributes from the pertinent information; and

d. arranging the extracted values in the form of a pre-defined data structure which logically links the attributes to each other, in accordance with their inter-relationships in the pre-defined context.