CODEWITHSUNDEEP
matlabvectorindexinghash
zamazalotta
zamazalotta

Reputation: 433

Hash operator in Matlab for linear indices of vectors

I am clustering a large set of points. Throughout the iterations, I want to avoid re-computing cluster properties if the assigned points are the same as the previous iteration. Each cluster keeps the IDs of its points. I don't want to compare them element wise, comparing the sum of the ID vector is risky (a small ID can be compensated with a large one), may be I should compare the sum of squares? Is there a hashing method in Matlab which I can use with confidence?

Example data:

a=[2,13,14,18,19,21,23,24,25,27]

b=[6,79,82,85,89,111,113,123,127,129]

c=[3,9,59,91,99,101,110,119,120,682]

d=[11,57,74,83,86,90,92,102,103,104]

So the problem is that if I just check the sum, it could be that cluster d for example, looses points 11,103 and gets 9,105. Then I would mistakenly think that there has been no change in the cluster.

Upvotes: 1

Views: 531

Answers (3)

zamazalotta
zamazalotta

Reputation: 433

I found the function DataHash on FEX it is quiet fast for vectors and the strcmp on the keys is a lot faster than I expected.

Upvotes: 0

macduff
macduff

Reputation: 4685

If I understand correctly, to hash the ID's I would recommend using the matlab Java interface to use the Java hashing algorithms

http://docs.oracle.com/javase/1.4.2/docs/api/java/security/MessageDigest.html

You'll do something like:

hash = java.security.MessageDigest.getInstance('SHA');

Hope this helps.

Upvotes: 0

High Performance Mark
High Performance Mark

Reputation: 78364

This is one of those (very common) situations where the more we know about your data and application the better we are able to help. In the absence of better information than you provide, and in the spirit of exposing the weakness of answers such as this in that absence, here are a couple of suggestions you might reject.

One appropriate data structure for set operations is a bit-set, that is a set of length equal to the cardinality of the underlying universe of things in which each bit is set on or off according to the things membership of the (sub-set). You could implement this in Matlab in at least two ways:

a) (easy, but possibly consuming too much space): define a matrix with as many columns as there are points in your data, and one row for each cluster. Set the (cluster, point) value to true if point is a member of cluster. Set operations are then defined by vector operations. I don't have a clue about the relative (time) efficiency of setdiff versus rowA==rowB.

b) (more difficult): actually represent the clusters by bit sets. You'll have to use Matlab's bit-twiddling capabilities of course, but the pain might be worth the gain. Suppose that your universe comprises 1024 points, then you'll need an array of 16 uint64 values to represent the bit set for each cluster. The presence of, say, point 563 in a cluster requires that you set, for the bit set representing that cluster, bit 563 (which is probably bit 51 in the 9th element of the set) to 1.

And perhaps I should have started by writing that I don't think that this is a hashing sort of a problem, it's a set sort of a problem. Yeah, you could use a hash but then you'll have to program around the limitations of using a screwdriver on a nail (choose your preferred analogy).

Upvotes: 1

Related Questions