Thread Subject: algorithms for pairwise comparison (large number of comparisons)

Hi there:


I am looking for an efficient algorithm to perform a large number of
pairwise comparisons. Does anyone happen to know any utility
programs, libraries, or algorithms in MATLAB or in other languages
that can do this?


For example, say, if I have five strings of 128 bits. The goal is to
first do a bitwise comparison for every possible pair, followed by
counting how many bits that each pair has in common. This task can
become very intensive, as the number of strings increases (i.e., the
problem size is exponential, almost like N^2). Specifically, five
strings require 10 comparisons; 50 strings require 1225 comparisons;
and 50,000 strings require over one billion comparisons.


It will probably take forever using FOR LOOPS. Any insights or
comments to efficiently do a pairwise comparison for some 50,000 to
100,000 strings will be greatly appreciated.


Sincerely,
Chris

lee cronbach wrote:
> For example, say, if I have five strings of 128 bits. The goal is to
> first do a bitwise comparison for every possible pair, followed by
> counting how many bits that each pair has in common. This task can
> become very intensive, as the number of strings increases (i.e., the
> problem size is exponential, almost like N^2). Specifically, five
> strings require 10 comparisons; 50 strings require 1225 comparisons;
> and 50,000 strings require over one billion comparisons.
(exponential is something like 2^N and not N^2, so the problem size
is not really exponential(!))
The problem can be especially what you want to do. In your example,
if the number of elements is not too high, I would do the following :
- separate the strings in separate numbers (bytes, int16's) so that
it can be handled by doubles.
- use meshgrid to make an array (!N^2 number of elements!)
- do calculations on matrices
- by using the upper triangular part of the matrix,


x=....numberdata1
X=meshgrid(x);
andX=bitand(X,X'); % or other functions
numberofbits=0;
for i=0:nbits-1
   numberofbits=numberofbits+sum(bitand(andX,2^i));
end


Of course if you have to do many many combinations, you will not have
enough memory.....


Stijn

Sorry I forgot to add a line in my proposal :
> 1. x=....numberdata1
> 2. X=meshgrid(x);
> 3. andX=bitand(X,X'); % or other functions
> 4. numberofbits=0;
> 5. for i=0:nbits-1
> 6. numberofbits=numberofbits+sum(bitand(andX,2^i));
> 7. end
I forgot to extract the upper triangular part. So between lines 3
and 4 the following line can be added
andX=triu(andX,1); %extract upper part without diagonal


Stijn

"lee cronbach" <chiuwing@msu.edu> wrote in message
news:eeb05c3.-1@WebX.raydaftYaTP...
> Hi there:
>
>
> I am looking for an efficient algorithm to perform a large number of
> pairwise comparisons. Does anyone happen to know any utility
> programs, libraries, or algorithms in MATLAB or in other languages
> that can do this?
>
> For example, say, if I have five strings of 128 bits. The goal is to
> first do a bitwise comparison for every possible pair, followed by
> counting how many bits that each pair has in common. This task can
> become very intensive, as the number of strings increases (i.e., the
> problem size is exponential, almost like N^2). Specifically, five
> strings require 10 comparisons; 50 strings require 1225 comparisons;
> and 50,000 strings require over one billion comparisons.
>
>
> It will probably take forever using FOR LOOPS. Any insights or
> comments to efficiently do a pairwise comparison for some 50,000 to
> 100,000 strings will be greatly appreciated.

Hmm ... if you don't need to know _where_ the common bits are, you could
always try this:

A=[1 1 1 1;1 0 0 1;0 1 1 1;0 0 0 0]
NumOfMatches1=A*A';
NumOfMatches0=(1-A)*(1-A)';

If NumOfMatches1+NumOfMatches0=4 (or rather LENGTH_OF_STRING) then the
strings are identical.

I'll leave the n=50,000 case to you ;)

--
Steve Lord
slord@mathworks.com

I'd suggest the following algorithm:

(1) Create an array having 2^16 entries mapping each 16 bit word into
    the number of bits (for speed),
(2) Apply this array to sixteen bit segments of each 128 bit value
    obtained by doing a "bitwise and" on the two operands,
(3) Do (1) & (2) this for a random sample of operands; you can get
    arbitrarily close to the true population value by selecting a
    sufficiently large sample size.

Your message is old, so you probably already solved the problem.

Another idea - add the number of entries in each position over the
entire population. Then calculate the number of entries in every pair
or positions. Test the result for "independence."

On Wed, 31 Jul 2002 20:03:41 -0400, lee cronbach wrote:
>Hi there:
>
>
>I am looking for an efficient algorithm to perform a large number of
>pairwise comparisons. Does anyone happen to know any utility
>programs, libraries, or algorithms in MATLAB or in other languages
>that can do this?
>
>
>For example, say, if I have five strings of 128 bits. The goal is to
>first do a bitwise comparison for every possible pair, followed by
>counting how many bits that each pair has in common. This task can
>become very intensive, as the number of strings increases (i.e., the
>problem size is exponential, almost like N^2). Specifically, five
>strings require 10 comparisons; 50 strings require 1225 comparisons;
>and 50,000 strings require over one billion comparisons.
>
>
>It will probably take forever using FOR LOOPS. Any insights or
>comments to efficiently do a pairwise comparison for some 50,000 to
>100,000 strings will be greatly appreciated.
>
>
>Sincerely,
>Chris