1
$\begingroup$

I have X clusters of size (n1,n2...,nX) and I want to fuse small clusters with less than T members with the nearest adjacent cluster i.e. the nearest neighboring cluster.

The problem is when I've got two small neighbor clusters, A->B and B->A which create an infinite loop.

I try to avoid that by removing one of those which have this property [(A,B),(B,A)].

But is there a better way to accomplish this task in sequential way ?

Is it possible to do the trick in distributed way ( Spark ) ?

$\endgroup$
1
$\begingroup$

My suggestion is just a greedy brute force approach. I am sure that more efficient solutions may exist, but it may be a first step towards your final solution.

Store in a table, for each cluster which size is lesser than T, the distance to its closest neighbouring cluster and the ID of that closest cluster.

Now, sort the table entries in ascending distance order. Merge the cluster in the first entry with its closest neighbouring one. If the closest cluster also had an entry in the table, and its size got larger than T, remove its corresponding entry. Finally, update all the entries of the table, and sort them in ascending distance order again.

Repeat the steps above until there are not more entries in the table.

| improve this answer | |
$\endgroup$
1
$\begingroup$

I'm not really seeing the issue with an infinite loop. It seems like you are looping through your clusters and finding all the clusters that need to be merged, then in a separate loop doing the merging and are getting tripped up when two clusters are flagged in such a way that they both need to be merged into one another. Instead, you can think of this as more of a queue.

Then you can loop through one time and merge the small clusters with their neighbors and then destroy them.

Imagine you have a cluster class with attributes: membercount, members, and nearestNeighbor, and methods addMembers() and destroy().

Then you could do something like:

for (cluster in clusterList):
    if cluster.membercount<T:
        cluster.nearestNeighbor.addMembers(cluster.members)
        cluster.destroy()

This will only cycle through clusterList one time and will instantly merge and destroy the clusters that are smaller than T.

Assuming you have experience with object oriented programming, this would be pretty straightforward to implement. Even if you do this within an array, you can just pop clusters after you merge them with other clusters.

Hope this helps!

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This option is okay in a sequential way i think, but i forgot to say that i try to do the trick in a distributed way... $\endgroup$ – KyBe Aug 25 '15 at 9:18
  • 1
    $\begingroup$ This makes no difference if you loop through all of your parallel ranks and have a map of where the clusters sit on the computer cluster. Further, you hash can sort your clusters so that most communication is local. Even if you do it the way that you specified in the question. Just include some sort of if(cluster A exists and cluster B exists): fusecluster(A,B) else: findNearestCluster(A) $\endgroup$ – AN6U5 Aug 25 '15 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.