Generating and applying data extraction templates

• US 9,563,689 B1
• Filed: 08/27/2014
• Issued: 02/07/2017
• Est. Priority Date: 08/27/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Cartright, Marc-Allen, Pueyo, Luis Garcia, Josifovski, Vanja, Saikia, Amitabh, Yang, Jie, Bendersky, Mike, Viswanatha, Srinidhi
• Primary Examiner(s): Jami, Hares
• Application Number:
  US14/470,510
• Time in Patent Office: 895 Days
• Field of Search: 707/736, 707/737, 707/738
• US Class Current: 1/1
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

Methods, apparatus, and computer-readable media are provided for generating and applying data extraction templates. In various implementations, a corpus of structured communications such as emails may be grouped into clusters based on one or more similarities between the structured communications. A set of structural paths may be identified from structured communications of a particular cluster. One or more structural paths of the set may be classified as transient wherein a count of occurrences of one or more associated segments of text across the particular cluster satisfies a criterion. One or more transient paths may be assigned a semantic data type and/or a confidentiality designation based on various signals. A data extraction template may be generated to extract, from subsequent structured communications, segments of text associated with transient (and in some cases, non-confidential) structural paths.

Claims

1. A computer-implemented method for generating and applying data extraction templates to extract transient content from structured communications created automatically using templates, comprising:

grouping a corpus of structured communications into a plurality of clusters based on metadata associated with each structured communication;

identifying, from structured communications of a particular cluster, a set of structural paths;

classifying a first structural path of the set of structural paths, associated with a first segment of text, as transient in response to a determination that a count of occurrences of the first segment of text across the particular cluster satisfies a criterion;

classifying a second structural path of the set of structural paths, associated with a second segment of text, as fixed in response to a determination that a frequency of occurrences of the second segment of text across the particular cluster does not satisfy the criterion;

generating a data extraction template to extract, from one or more structured communications, one or more segments of text associated with the transient structural path;

configuring the data extraction template so that one or more segments of text associated with the fixed structural path are ignored in one or more subsequent structured communications;

associating a subsequent structured communication with the particular cluster based on metadata associated with the subsequent structured communication; and

applying the data extraction template associated with the particular cluster to the subsequent structured communication to extract one or more segments of text associated with the transient structural path.

2. The computer-implemented method of claim 1, wherein the metadata associated with each structured communication comprises a subject.

3. The computer-implemented method of claim 1, wherein the metadata associated with each structured communication comprises data indicative of a sending entity.

4. The computer-implemented method of claim 3, wherein the grouping comprises associating a plurality of different sender identifiers with a single sending entity based on one or more textual patterns shared among the plurality of different sender identifiers.

5. The computer-implemented method of claim 1, further comprising assigning a semantic data type to the transient structural path based on one or more signals related to the structured communications of the particular cluster.

6. The computer-implemented method of claim 5, wherein the one or more signals include a context of the structured communications of the particular cluster.

7. The computer-implemented method of claim 5, wherein the one or more signals include one or more fixed segments of text contained in structured communications of the particular cluster within a particular distance of the first segment of text.

8. The computer-implemented method of claim 5, wherein the one or more signals include one or more patterns detected in the first segment of text.

9. The computer-implemented method of claim 1, wherein identifying comprises identifying, based on structured communications of the particular cluster, a set of XPaths.

10. The computer-implemented method of claim 1, wherein the identifying comprises generating a bipartite graph, with the set of structural paths forming a first set of structural path nodes and corresponding textual segments forming a second set of textual segment nodes, and edges connecting structural path nodes to corresponding textual segment nodes.

11. The computer-implemented method of claim 1, wherein generating the data extraction template comprises generating the data extraction template to ignore, in one or more structured communications, one or more segments of text associated with the transient structural path in response to a determination, based on one or more signals related to structured communications of the particular cluster, that a semantic data type of the transient structural path is confidential.

12. A system that generates and applies data extraction templates to extract transient content from structured communications created automatically using templates, the system including memory and one or more processors operable to execute instructions stored in the memory, and comprising instructions to:

group a corpus of structured communications into a plurality of clusters based on one or more similarities between structured communications of the corpus;

identify, from structured communications of a particular cluster, a set of structural paths, wherein to identify the set of structural paths, a bipartite graph is generated, with the set of structural paths forming a first set of structural path nodes and corresponding textual segments forming a second set of textual segment nodes, and edges connecting structural path nodes to corresponding textual segment nodes;

classify a first structural path of the set of structural paths, associated with a first segment of text, as transient in response to a determination that a count of occurrences of the first segment of text across the particular cluster satisfies a criterion;

determine a semantic data type of the transient structural path based on one or more signals related to the structured communications of the particular cluster; and

generate a data extraction template to extract, from one or more structured communications, one or more segments of text associated with the transient structural path;

associate a subsequent structured communication with the particular cluster based on one or more similarities between the subsequent structured communication and structured communications of the particular cluster; and

apply the data extraction template associated with the particular cluster to the subsequent structured communication to extract one or more segments of text associated with the transient structural path.

13. The system of claim 12, wherein the instructions further include instructions to group the corpus of structured communications into the plurality of clusters based on metadata associated with each structured communication or textual similarity between two or more structured communications.

14. The system of claim 13, wherein the metadata associated with each structured communication comprises a subject or data indicative of a sending entity.

15. The system of claim 14, wherein the instructions further include instructions to associate a plurality of different sender identifiers with a single sending entity based on one or more textual patterns shared among the plurality of different sender identifiers.

16. The system of claim 12, wherein the one or more signals include a context of the structured communications of the particular cluster.

17. The system of claim 12, wherein the one or more signals include one or more fixed segments of text contained in structured communications of the particular cluster within a particular distance of the first segment of text.

18. A non-transitory computer-readable medium comprising instructions that, in response to execution of the instructions by a computing system, cause the computing system to generate and apply data extraction templates to extract transient content from structured communications created automatically using templates, including performing the following operations:

identifying, from a corpus of structured communications, a set of structural paths;

classifying a first structural path of the set of structural paths, associated with a first segment of text, as transient in response to a determination that a count of occurrences of the first segment of text across the corpus satisfies a criterion;

determining a semantic data type of the transient structural path based on one or more signals related to the structured communications of the corpus;

generating a data extraction template to extract, from one or more structured communications, one or more segments of text associated with the transient structural path where the semantic data type of the transient structural path is non-confidential, wherein generating the data extraction template further comprises generating the data extraction template to ignore, in one or more subsequent structured communications, one or more segments of text associated with the transient structural path in response to a determination, based on one or more signals related to structured communications of the particular cluster, that a semantic data type of the transient structural path is confidential; and

associating a subsequent structured communication with the data extraction template based on metadata associated with the subsequent structured communication; and

applying the data extraction template to the subsequent structured communication to extract one or more segments of text associated with the transient structural path.