COMPOSITE LOCALITY SENSITIVE HASH BASED PROCESSING OF DOCUMENTS

• US 20110087669A1
• Filed: 05/21/2010
• Published: 04/14/2011
• Est. Priority Date: 10/09/2009
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Stratify, Inc. (Open Text Corporation)
• Inventors: Thomas, Joy, Bakshi, Ankita, Maddali, Kumar, Goli, Rajashekhar, Ancin, Hakan
• Granted Patent: US 8,244,767 B2
• Time in Patent Office: Days
• US Class Current: 707/740
• CPC Class Codes: G06F 16/325 Hash tables
• CPC Class Codes: G06F 16/9014 hash tables

Abstract

Reliable identification of highly similar documents allows such documents to be treated as identical for purposes of document analysis. Identification of highly similar documents can be based on a composite hash value or other value for which the likelihood of two documents having the same value is high if and only if the documents have a high degree of similarity. Prior to performing content based analysis, the composite hash value for the current document is determined and compared to composite hash values of previously analyzed documents. If a match is found, the results of the analysis of the previous document can be applied to the current document. If no match is found, the current document is analyzed.

Claims

1. A method of analyzing documents belonging to a corpus, the method comprising:

computing a composite hash value for a current document from the corpus;

determining whether a previous document having the same composite hash value as the current document has been analyzed;

in the event that a previous document having the same composite hash value as the current document has not been analyzed, analyzing the current document, wherein analyzing the current document includes determining one or more items of analytic metadata to be associated with the current document;

in the event that a previous document having the same composite hash value as the current document has been analyzed, associating the current document with one or more items of analytic metadata determined from analyzing the previous document; and

storing a representation of the association between the one or more items of analytic metadata and the current document.

2. The method of claim 1 wherein computing the composite hash value for the current document includes:

transforming the current document to a content vector having a plurality of components;

for each of a number N of subsets of the components of the content vector, computing a hash vector component by applying a hash function to that subset of the components of the content vector; and

applying a hash function to the N hash vector components.

3. The method of claim 2 wherein transforming the document to a content vector includes creating a count vector indicating a number of occurrences within the current document of each of a plurality of terms.

4. The method of claim 3 wherein transforming the document to a content vector further includes weighting each term of the count vector based on term frequency statistics determined from a plurality of documents in the corpus.

5. The method of claim 1 wherein analyzing the current document includes performing at least one of the following operations:

determining a language of the current document;

determining whether any other document is a near duplicate of the current document;

or

categorizing the document as belonging to one or more of a plurality of semantic clusters.

6. The method of claim 1 wherein the composite hash value is represented as a plurality of groups of digits, the method further comprising:

defining a folder hierarchy comprising a plurality of folders arranged in a plurality of levels, each level corresponding to a different one of the groups of digits, wherein the folders within each level correspond to different values for the one of the groups of digits;

selecting a folder from the folder hierarchy based on the composite hash value of the current document; and

storing the current document in the selected folder.

7. The method of claim 1 wherein the composite hash value is represented as a plurality of groups of digits, the method further comprising:

defining a folder hierarchy comprising a plurality of folders arranged in a plurality of levels, each level corresponding to a different one of the groups of digits, wherein the folders within each level correspond to different values for the one of the groups of digits;

selecting a folder from the folder hierarchy based on the composite hash value of the current document; and

storing a reference to a location of the current document in the selected folder.

8. A computer-readable storage medium containing program instructions that, when executed by a computer system, cause the computer system to execute a method of analyzing a plurality of documents in a corpus of documents, the method comprising:

selecting a current document from the corpus;

computing a composite hash value for the current document;

determining whether a previous document having the same composite hash value as the current document has been analyzed;

in the event that a previous document having the same composite hash value as the current document has not been analyzed, analyzing the current document, wherein analyzing the current document includes determining one or more items of analytic metadata to be associated with the current document;

in the event that a previous document having the same composite hash value as the current document has been analyzed, associating the current document with one or more items of analytic metadata determined from analyzing the previous document;

storing a representation of the association between the one or more items of analytic metadata and the current document; and

repeating the acts of selecting, computing, determining, either analyzing or associating, and storing until all of the plurality of documents have been analyzed.

9. The computer-readable storage medium of claim 8 wherein the method further comprises:

transforming the current document to a content vector having a plurality of components;

for each of a number N of subsets of the components of the content vector, computing a hash vector component by applying a hash function to that subset of the components of the content vector; and

applying a hash function to the N hash vector components.

10. The computer-readable storage medium of claim 9 wherein transforming the document to a content vector includes creating a count vector indicating a number of occurrences within the current document of each of a plurality of terms.

11. The computer-readable storage medium of claim 10 wherein transforming the document to a content vector further includes weighting each term of the count vector based on term frequency statistics determined from a plurality of documents in the corpus.

12. The computer-readable storage medium of claim 8 wherein analyzing the current document includes performing at least one of the following operations:

determining a language of the current document;

determining whether any other document is a near duplicate of the current document;

or

categorizing the document as belonging to one or more of a plurality of semantic clusters.

13. A computer system comprising:

a storage subsystem configured to maintain a document information data store; and

a processor coupled to the storage subsystem, the processor being configured to perform one or more content-based analysis operations on documents in a corpus of documents and to store results of the analysis in the document information data store,

wherein the processor is further configured to;

compute a composite hash value for each of the documents;

assign each document to one of a plurality of groups, wherein all documents in a same group have a same composite hash value;

perform the one or more content-based analysis operations on one document from each of the plurality of groups; and

store a result of the one or more content-based analysis operations in the document information data store in association with each of the documents in the group.

14. The computer system of claim 13 wherein the processor is further configured to compute the composite hash value for each document by:

generating a content vector for the document, the content vector having a plurality of components;

for each of a number N of subsets of the components of the content vector, computing a hash vector component by applying a hash function to that subset of the components of the content vector; and

applying a hash function to the N hash vector components.

15. The computer system of claim 14 wherein generating the content vector includes creating a count vector indicating a number of occurrences within the document of each of a plurality of terms.

16. The computer system of claim 15 wherein transforming the document to a content vector further includes weighting each term of the count vector based on term frequency statistics determined from a plurality of documents in the corpus.

17. The computer system of claim 13 wherein the one or more content-based analysis operations include at least one of the following operations:

a language-determining operation;

a near-duplicate detection operation;

or

a semantic clustering operation.

18. The computer system of claim 13 wherein the composite hash value is represented as a plurality of groups of digits and wherein the storage subsystem is configured to store the plurality of documents in a folder hierarchy comprising a plurality of folders arranged in a plurality of levels, each level corresponding to a different one of the groups of digits, wherein the folders within each level correspond to different values for the one of the groups of digits.

19. The computer system of claim 13 wherein the composite hash value is represented as a plurality of groups of digits and wherein the document information data store is configured as a hierarchical data structure comprising a plurality of levels, each level corresponding to a different one of the groups of digits.

20. The computer system of claim 13 wherein the processor is further configured to receive new documents to be added to the corpus, wherein when a new document is received, the processor is configured to:

compute a composite hash value for the new document;

determine whether the composite hash value for the new document matches a composite hash value associated with one of the groups of documents;

add the new document to the one of the groups of documents in the event that the composite hash value matches the composite hash value associated with the one of the groups of documents; and

perform the content-based analysis operation on the new document in the event that the composite hash value does not match the composite hash value associated with any of the groups of documents.