Re: efficient compare

From: Bob Badour <bbadour_at_pei.sympatico.ca>
Date: Sun, 23 Apr 2006 03:18:56 GMT
Message-ID: <AmC2g.64505$VV4.1215130@ursa-nb00s0.nbnet.nb.ca>

Andersen wrote:

> Bob Badour wrote:
>

>> I don't see how you are going to get log(N).

>
> log(N) message exchanges! Not bit complexity (i.e. size of the messages).

You are not going to get log(N) in messages either.

>> Consider A & B are equal each with 65535 tuples. Insert a tuple into A 
>> at the beginning of the sort order. Insert a tuple into B at the end 
>> of the sort order.
>>
>> None of your subdivided sets are going to give matching checksums 
>> except in error until you get down to individual tuples.

>
>
> Here is a different solution to that problem. Keep N bins, where N is
> some very large constant. Hash every tuple to an integer between 1-N and
> put it in the corresponding bin. Now run the divide and conquer on this.
>
> I.e, first send checksum of the value of all bins

But you said N is a large number which means you have to send a large number of checksums. Received on Sat Apr 22 2006 - 22:18:56 CDT