Method and system for using keywords to merge document clusters

• US 8,843,494 B1
• Filed: 04/23/2013
• Issued: 09/23/2014
• Est. Priority Date: 03/28/2012
• Status: Active Grant

• Current Assignee: Open Text Corporation
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Sampson, Steven
• Primary Examiner(s): NGUYEN, PHONG H
• Application Number:
  US13/868,314
• Time in Patent Office: 518 Days
• Field of Search: 707/737, 707/749, 707/758, 707/748, 707/E17.089
• US Class Current: 707/737
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06V 30/196 using sequential comparisons of the image signals with a plurality of references
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text
• CPC Class Codes: G06V 30/418 Document matching, e.g. of document images

Abstract

Using keywords to merge document clusters is described. Documents are distributed into document clusters that include a first document cluster of first documents and a second document cluster of second documents. A template associated with the first document cluster is created. The template includes keywords associated with most of the first documents. A distance is calculated between keyword location information associated with the template and word location information associated with a document in the second document cluster. The keyword location information includes information indicating a location of a keyword in the template relative to other keywords in the template. The word location information includes information indicating a location of a word in the document relative to other words in the document. A determination is made whether the distance is less than a threshold value. The second document cluster is merged with the first document cluster in response to the determination that the distance is less than the threshold value.

Claims

1. A system for using keywords to merge document clusters, the system comprising:

one or more processors; and

a non-transitory computer readable medium storing a plurality of instructions, which when executed, cause the one or more processors to;

distribute a plurality of documents into a plurality of document clusters, wherein the plurality of document clusters comprise a first document cluster comprising a first plurality of documents and a second document cluster comprising a second plurality of documents;

create a template associated with the first document cluster, wherein the template comprises a plurality of keywords associated with at least most of the first plurality of documents;

calculate a distance between keyword location information associated with the template and word location information associated with a document in the second document cluster, wherein the keyword location information comprises information indicating a location of a keyword in the template relative to other keywords in the template, and wherein the word location information comprises information indicating a location of a word in the document relative to other words in the document;

determine whether the distance is less than a threshold value; and

merge the second document cluster with the first document cluster in response to a determination that the distance is less than the threshold value.

2. The system of claim 1, wherein distributing the plurality of documents into the plurality of document clusters comprises:

generating a plurality of word pairs, wherein each word pair comprises a first word from a first document and a corresponding second word from a second document;

computing, for each word pair, first location information for the first word that indicates a location of the first word in the first document relative to other words in the first document;

computing, for each word pair, second location information for the corresponding second word that indicates a location of the corresponding second word in the second document relative to other words in the second document; and

comparing the first location information to the second location information.

3. The system of claim 1, wherein the word location information comprises top location information and bottom location information, wherein the top location information is associated with a top portion of the document and comprises a locations of a specific word in the top portion relative to other words in the top portion, and wherein the bottom location information is associated with a bottom portion of the document and comprises a location of another specific word in the bottom portion relative to other words in the bottom portion.

4. The system of claim 1, wherein the plurality of instructions, when executed, further cause the one or more processors to:

calculate a first vector from the keyword in the template to another keyword in the template, wherein the first vector indicates the location of the keyword relative to the other keyword; and

calculate a second vector from the word in the document to another word in the document, wherein the second vector indicate the location of the word in the document relative to the other word in the document.

5. The system of claim 1, wherein the plurality of instructions, when executed, further cause the one or more processors to:

calculate a horizontal distance from the keyword in the template to another keyword in the template; and

calculate a vertical distance from the keyword in the template to the other keyword in the template, wherein the horizontal distance and the vertical distance indicate a location of the keyword relative to the other keyword.

6. The system of claim 1, wherein the template comprises a first area value associated with the keyword that indicates an area occupied by the keyword in the template, and the plurality of instructions, when executed, further cause the one or more processors to:

calculate a second area value that indicates an area occupied by the word in the document;

determine whether a difference between the first area value and the second area value is below an area threshold value; and

identify the keyword in the template as being a keyword for a word pair and identify the word in the document as being a corresponding word for the word pair based upon a determination that the difference is below the area threshold value.

7. The system of claim 1, wherein the plurality of instructions, when executed, further cause the one or more processors to:

calculate a Levenshtein distance between the keyword in the template and the word in the document;

determine whether the Levenshtein distance is below a distance threshold value; and

identify the keyword in the template as being a word for a word pair, and identify the word in the document as being a corresponding word for the word pair based upon a determination that the difference is below the distance threshold value.

8. A computer-implemented method for using keywords to merge document clusters, the method comprising:

distributing a plurality of documents into a plurality of document clusters, wherein the plurality of document clusters comprise a first document cluster comprising a first plurality of documents and a second document cluster comprising a second plurality of documents;

creating a template associated with the first document cluster, wherein the template comprises a plurality of keywords associated with at least most of the first plurality of documents;

calculating a distance between keyword location information associated with the template and word location information associated with a document in the second document cluster, wherein the keyword location information comprises information indicating a location of a keyword in the template relative to other keywords in the template, and wherein the word location information comprises information indicating a location of a word in the document relative to other words in the document;

determining whether the distance is less than a threshold value; and

merging the second document cluster with the first document cluster in response to a determination that the distance is less than the threshold value.

9. The computer-implemented method of claim 8, wherein distributing the plurality of documents into the plurality of document clusters comprises:

generating a plurality of word pairs, wherein each word pair comprises a first word from a first document and a corresponding second word from a second document;

computing, for each word pair, first location information for the first word that indicates a location of the first word in the first document relative to other words in the first document;

computing, for each word pair, second location information for the corresponding second word that indicates a location of the corresponding second word in the second document relative to other words in the second document; and

comparing the first location information to the second location information.

10. The computer-implemented method of claim 8, wherein the word location information comprises top location information and bottom location information, wherein the top location information is associated with a top portion of the document and comprises a locations of a specific word in the top portion relative to other words in the top portion, and wherein the bottom location information is associated with a bottom portion of the document and comprises a location of another specific word in the bottom portion relative to other words in the bottom portion.

11. The computer-implemented method of claim 8, wherein the method further comprises:

calculating a first vector from the keyword in the template to another keyword in the template, wherein the first vector indicates the location of the keyword relative to the other keyword; and

calculating a second vector from the word in the document to another word in the document, wherein the second vector indicate the location of the word in the document relative to the other word in the document.

12. The computer-implemented method of claim 8, wherein the method further comprises:

calculating a horizontal distance from the keyword in the template to another keyword in the template; and

calculating a vertical distance from the keyword in the template to the other keyword in the template, wherein the horizontal distance and the vertical distance indicate a location of the keyword relative to the other keyword.

13. The computer-implemented method of claim 8, wherein the template comprises a first area value associated with the keyword that indicates an area occupied by the keyword in the template, and the method further comprises:

calculating a second area value that indicates an area occupied by the word in the document;

determining whether a difference between the first area value and the second area value is below an area threshold value; and

identifying the keyword in the template as being a keyword for a word pair and identify the word in the document as being a corresponding word for the word pair based upon a determination that the difference is below the area threshold value.

14. The computer-implemented method of claim 8, wherein the method further comprises:

calculating a Levenshtein distance between the keyword in the template and the word in the document;

determining whether the Levenshtein distance is below a distance threshold value; and

identifying the keyword in the template as being a word for a word pair, and identify the word in the document as being a corresponding word for the word pair based upon a determination that the difference is below the distance threshold value.

15. A computer program product, comprising a non-transitory computer-readable medium having a computer-readable program code embodied therein, the computer-readable program code adapted to be executed by one or more processors, the program code comprising instructions to:

distribute a plurality of documents into a plurality of document clusters, wherein the plurality of document clusters comprise a first document cluster comprising a first plurality of documents and a second document cluster comprising a second plurality of documents;

create a template associated with the first document cluster, wherein the template comprises a plurality of keywords associated with at least most of the first plurality of documents;

calculate a distance between keyword location information associated with the template and word location information associated with a document in the second document cluster, wherein the keyword location information comprises information indicating a location of a keyword in the template relative to other keywords in the template, and wherein the word location information comprises information indicating a location of a word in the document relative to other words in the document;

determine whether the distance is less than a threshold value; and

merge the second document cluster with the first document cluster in response to a determination that the distance is less than the threshold value.

16. The computer program product of claim 15, wherein distributing the plurality of documents into the plurality of document clusters comprises:

generating a plurality of word pairs, wherein each word pair comprises a first word from a first document and a corresponding second word from a second document;

computing, for each word pair, first location information for the first word that indicates a location of the first word in the first document relative to other words in the first document;

computing, for each word pair, second location information for the corresponding second word that indicates a location of the corresponding second word in the second document relative to other words in the second document; and

comparing the first location information to the second location information.

17. The computer program product of claim 15, wherein the word location information comprises top location information and bottom location information, wherein the top location information is associated with a top portion of the document and comprises a locations of a specific word in the top portion relative to other words in the top portion, and wherein the bottom location information is associated with a bottom portion of the document and comprises a location of another specific word in the bottom portion relative to other words in the bottom portion.

18. The computer program product of claim 15, wherein the program code comprises further instructions to:

calculate a first vector from the keyword in the template to another keyword in the template, wherein the first vector indicates the location of the keyword relative to the other keyword; and

calculate a second vector from the word in the document to another word in the document, wherein the second vector indicate the location of the word in the document relative to the other word in the document.

19. The computer program product of claim 15, wherein the program code comprises further instructions to:

calculate a horizontal distance from the keyword in the template to another keyword in the template; and

calculate a vertical distance from the keyword in the template to the other keyword in the template, wherein the horizontal distance and the vertical distance indicate a location of the keyword relative to the other keyword.

20. The computer program product of claim 15, wherein the template comprises a first area value associated with the keyword that indicates an area occupied by the keyword in the template, and the program code comprises further instructions to:

calculate a second area value that indicates an area occupied by the word in the document;

determine whether a difference between the first area value and the second area value is below an area threshold value; and

identify the keyword in the template as being a keyword for a word pair and identify the word in the document as being a corresponding word for the word pair based upon a determination that the difference is below the area threshold value.