Graph-based organization entity resolution
A novel entity resolution approach for the organization entity domain can be implemented in the MapReduce framework with low memory requirements so that it may scale to large scale datasets. A new clustering approach, sClust, significantly improves the recall of the pairwise classifier.
1. An agglomerative clustering system comprising:
a distributed memory arrangement that provides sorted edge lists for each connected component of a set of connected components; and
a distributed processing arrangement coupled to the distributed memory arrangement, the distributed processing arrangement including at least one processor being configured to generate conflict sets in a first pass, the conflict sets comprising sets of connected components that shouldn't appear together in any cluster as derived from the presence of a score that falls below a no-match threshold, and in a second pass to, in response to the generated conflict sets, agglomeratively construct clusters to partition the connected components in the conflict sets,
the distributed processing arrangement agglomeratively constructing clusters by:
setting a maximum allowed cluster size,
applying at least one matching threshold to conditionally add nodes to clusters up to the maximum allowed cluster size, and
upon the size of a cluster at least one of reaching and exceeding the maximum allowed cluster size, partitioning the cluster into smaller clusters.
2. The agglomerative clustering system of claim 1 wherein the distributed processing arrangement comprises a name node, a job submission node and plural of slave nodes.
3. The agglomerative clustering system of claim 2 wherein the plural slave nodes each include a processor that executes at least one mapper and at least one reducer.
4. The agglomerative clustering system of claim 3 wherein the plural slave nodes each include local memory coupled to the processor.
5. The agglomerative clustering system of claim 1 wherein the distributed processing arrangement is further configured to perform graph-based blocking.
6. The agglomerative clustering system of claim 1 wherein for each connected component C i ∈C, where C is the set of disjoint connected components in a graph, there exists a connection path between any two vertices v k and v l where (v k , v l )∈C i .
7. The agglomerative clustering system of claim 6 wherein for any distinct connected component (C i , C j )∈C, where C is the set of disjoint connected components in a graph, there is no path between any pair v k and v l where v k ∈C i , v l ∈C j .
8. The agglomerative clustering system of claim 1 wherein the distributed processing arrangement is further configured to recursively partition oversized clusters into smaller clusters.
9. The agglomerative clustering system of claim 1 wherein the processor arrangement checks the maximum cluster size before merging two clusters or adding a new node to an existing cluster.
10. The agglomerative clustering system of claim 1 wherein upon the size of a cluster at least one of reaching and exceeding the maximum allowed cluster size, the processor arrangement increases the threshold and uses transitive closure to further partition the cluster.
11. The agglomerative clustering system of claim 10 wherein the processor iterates the step of claim 10 until the sizes of all connected components are below the maximum allowed cluster size.
12. The agglomerative clustering system of claim 1 wherein the processor continues to apply a match/no-match threshold to selectively add nodes to clusters up to the maximum allowed cluster size, and upon the size of a cluster at least one of reaching and exceeding the maximum allowed cluster size, partitioning the cluster into smaller clusters, until each cluster corresponds to a single entity.
13. An agglomerative clustering system comprising:
a memory that provides sorted edge lists for each connected component of a set of connected components; and
at least one processor operatively coupled to the memory, the at least one processor being configured to generate conflict sets defining sets of connected components that shouldn't appear together in any cluster as derived from the presence of a score that falls below a no-match threshold and, in response to the generated conflict sets, agglomeratively construct clusters to partition the connected components in the conflict sets,
the at least one processor agglomeratively constructing clusters by:
setting a maximum allowed cluster size;
score connected components;
compare the score to a match threshold above which the connected components are declared to represent the same entity;
compare the score to the no-match threshold below which the connected components are declared to represent different entities, the no-match threshold being different from the match threshold;
using the results of the comparisons, conditionally adding nodes to clusters up to the maximum allowed cluster size; and
upon the size of a cluster at least one of reaching and exceeding the maximum allowed cluster size, partitioning the cluster into smaller clusters.