Clustering of near-duplicate documents

• US 9,355,171 B2
• Filed: 08/27/2010
• Issued: 05/31/2016
• Est. Priority Date: 10/09/2009
• Status: Expired due to Fees

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Thomas, Joy, Goswami, Sauraj, Salaka, Vamsi
• Primary Examiner(s): LE, THU NGUYET T
• Application Number:
  US12/870,733
• Publication Number:
  US 20110087668A1
• Time in Patent Office: 2,104 Days
• Field of Search: 707/737
• US Class Current: 1/1
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification

Abstract

Documents likely to be near-duplicates are clustered based on document vectors that represent word-occurrence patterns in a relatively low-dimensional space. Edit distance between documents is defined based on comparing their document vectors. In one process, initial clusters are formed by applying a first edit-distance constraint relative to a root document of each cluster. The initial clusters can be merged subject to a second edit-distance constraint that limits the maximum edit distance between any two documents in the cluster. The second edit-distance constraint can be defined such that whether it is satisfied can be determined by comparing cluster structures rather than individual documents.

Claims

1. In a computer system having a processor and a computer-readable storage medium, a method for grouping near-duplicate documents, the method comprising:

for each document in a corpus of documents to be analyzed, computing, by the processor, a hash vector based on word count information for the document, the hash vector including a plurality of components;

assigning, by the processor, each document to one of a plurality of initial clusters of documents, wherein each of the initial clusters contains a root document and at least some of the initial clusters further contain at least one child document, and wherein each of the child documents of any one of the initial clusters satisfies a first edit-distance constraint relative to the root document of that one of the initial clusters, the first edit-distance constraint being defined as an upper limit on a number of components of the hash vectors that are different between the root document and the child document;

merging, by the processor, the initial clusters to form a plurality of final clusters based on a second edit-distance constraint; and

storing in the computer readable storage medium, by the processor, a list of the documents associated with each of the final clusters,

wherein assigning each document to one of the initial clusters includes;

for a target one of the documents, comparing the hash vector of the target document with the hash vector of the root document of the initial cluster to determine whether the first edit distance constraint is satisfied;

in response to a determination that the first edit distance constraint is satisfied, adding the target document as a child document to the initial cluster, by storing an identifier of the target document in the computer-readable storage medium in association with the initial cluster; and

in response to a determination that the first edit distance constraint is not satisfied, adding a new cluster to a list of the initial clusters in the computer-readable storage medium, wherein the target document is the root document of the new cluster.

2. The method of claim 1 wherein the storing includes storing the list of the documents associated with each of the final clusters such that all documents associated with a same one of the final clusters are accessible by reference to any one of the documents associated with that one of the final clusters.

3. The method of claim 1 wherein the components of the hash vector are orthogonal to each other.

4. The method of claim 1 wherein the first-edit distance constraint corresponds to an upper limit on the number of components of the hash vector that are different between the root document and the target document.

5. The method of claim 4 wherein the merging includes:

for each of the initial clusters that has at least one child document, grouping the child documents into one or more maps, wherein all of the child documents that are grouped within a same map have hash vectors that differ from the root document of the cluster in the same one or more of the components;

determining whether the number of maps for a first one of the initial clusters is at or below an upper bound;

determining whether the number of maps for a second one of the initial clusters is at or below an upper bound; and

in the event that the number of maps for the first initial cluster and the number of maps for the second initial cluster are at or below the upper bound;

determining whether the maps for the first initial cluster correspond to differences from the root document in the same one or more of the plurality of components of the hash vector as the maps for the second initial cluster; and

merging the first initial cluster and the second initial cluster in the event that the maps for the first cluster correspond to differences in the same one or more of the plurality of components of the hash vector as the maps for the second cluster.

6. The method of claim 5 wherein the upper limit on the number of components of the hash vector that are different is 1 and the upper bound on the number of maps is 2.

7. The method of claim 4 wherein the second edit-distance constraint is defined such that merging does not increase a diameter of a cluster.

8. The method of claim 7 further comprising selecting the second initial cluster, wherein the second initial cluster is selected from the initial clusters that have a diameter not greater than 2.

9. A system for analyzing documents, the system comprising:

a document information data store to store a vector representation of each of a plurality of documents, the vector representation being based on frequency of occurrence within the document of words from a dictionary, wherein the vector representation has a dimension that is small compared to the number of words in the dictionary;

a processor to form initial clusters of near-duplicate documents based on the vector representations in the document information data store and to store cluster information in the document information data store, the cluster information including a list of the documents associated with each of the initial clusters of near-duplicate documents,

wherein the processor is further to form final clusters of near-duplicate documents from the initial clusters by merging some or all of the initial clusters by applying a second edit-distance constraint to the initial clusters,

wherein, to form one of the initial clusters, the processor is to;

select an extant cluster from a list of extant clusters, each extant cluster including a root document;

for a target one of the documents, compare the hash vector of the target document with the hash vector of the root document of the extant cluster to determine whether the first edit distance constraint is satisfied;

in response to a determination that the first edit distance constraint is satisfied, add the target document as a child document to the extant cluster, including storing an identifier of the target document in the document information data store in association with the extant cluster; and

in response to a determination that the first edit distance constraint is not satisfied, add a new cluster to the list of extant clusters, wherein the target document is the root document of the new cluster.

10. The system of claim 9 wherein the first edit-distance constraint is based on comparing components of vector representations of different ones of the plurality of documents.

11. The system of claim 9 wherein the processor is further to generate the vector representation of each of the plurality of documents and to store the vector representations in the document information data store.

12. The system of claim 11 wherein the vector representation comprises a hash vector and wherein the processor is further to generate each component of the hash vector by applying a hash function to a different subset of the words in the dictionary.

13. The system of claim 12 wherein the dimension of the vector representation is less than 10.

14. The system of claim 9 further comprising a user interface to allow a user to select a document from the plurality of documents and to view a list of all other documents in the same final cluster as the selected document.

15. A non-transitory computer-readable storage medium containing program instructions, which when executed by a processor cause the processor to:

for each document in a corpus of documents to be analyzed, access a document vector that includes a plurality of components, each of the components being based on word count information for the document;

assign each document to one of a plurality of initial clusters of documents, wherein each of the initial clusters contains a root document and at least some of the initial clusters further contain at least one child document, and wherein each of the child documents of any one of the initial clusters satisfies a first edit-distance constraint relative to the root document of that one of the initial clusters, the first edit-distance constraint being defined as a minimum degree of similarity between the document vectors of the root document and the child document;

merge at least some of the initial clusters to form a plurality of final clusters, wherein during the merging, a first one and a second one of the initial clusters are merged in the event that the first one of the initial clusters satisfies a second edit-distance constraint relative to the second one of the initial clusters; and

store, in a document information data store, a list of the documents associated with each of the final clusters,

wherein, to assign each document to one of the initial clusters, the instructions cause the processor to;

for a target one of the documents, compare the hash vector of the target document with the hash vector of the root document of the initial cluster to determine whether the first edit distance constraint is satisfied;

in response to a determination that the first edit distance constraint is satisfied, add the target document as a child document to the initial cluster, by storing an identifier of the target document in association with the initial cluster; and

in response to a determination that the first edit distance constraint is not satisfied, add a new cluster to a list of the initial clusters, wherein the target document is the root document of the new cluster.

16. The computer-readable storage medium of claim 15, wherein to access the document vector, the processor is to compute the document vector.

17. The non-transitory computer-readable storage medium of claim 16, wherein to compute the document vector for one of the documents, the processor is to:

determine a number of occurrences within the document of each of a plurality of words from a dictionary; and

for each of a plurality of subsets of the words from the dictionary, compute a hash function of a bit field representing the number of occurrences of each of the words in that subset.

18. The non-transitory computer-readable storage medium of claim 15, wherein to access the document vector, the processor is to read the document vector from a document information data store.

19. The non-transitory computer-readable storage medium of claim 15, wherein the first edit constraint is an upper limit on the number of components of the document vectors that are different between the root document and any of the child documents within a same one of the initial clusters.

20. The non-transitory computer-readable storage medium of claim 19, wherein the second edit-distance constraint is a constraint limiting a diameter of each of the final clusters.