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_at_ursa-nb00s0.nbnet.nb.ca>
>
> log(N) message exchanges! Not bit complexity (i.e. size of the messages).
>
>
> 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
Date: Sun, 23 Apr 2006 03:18:56 GMT
Message-ID: <AmC2g.64505$VV4.1215130_at_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 Sun Apr 23 2006 - 05:18:56 CEST