[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]

*To*: <tribble>*Subject*: find-links-from-to-three*From*: Mark S. Miller <mark>*Date*: Thu, 24 Aug 89 16:20:35 PDT*Cc*: <us>*In-reply-to*: <Eric>,11 PDT <8908231818.AA06289@xxxxxxxxxx>

Date: Wed, 23 Aug 89 11:18:11 PDT From: tribble (Eric Dean Tribble) I just realized while talking to marcs that we can now support find-links-from-to-three-home reasonably efficiently. The current link operation corresponds to find-links-from-three-home or find-links-to-three-home. The combination of two operations (one on the from set, one on the to-set) does the full flftt operations. All that's required is a hash set to find the intersection of the two results. Well, it depends what you mean by efficiently. Your solution is O(N log N) in the maximum count of the two sets being intersected (since the sets need to be generated first). Alternatively, if you can estimate cheaply which will be the smaller of the two sets, you could do this in O(N log N) in the minimum count of the two sets being intersected. However, this would require widding southward some kind of info of what stuff more northward points at, so I think we are stuck with O(N log N) in the maximum. I would not define this as an efficient flftth operation. I would also not define the one proportional to the minimum as efficient. I like defining efficient as O(N (log N)^k) in the count of the *answer* (for some constant k). If N can be arbitrarily larger then the answer (which it can with the above algorithm), then you can spend a long time to get nothing back.

**References**:**find-links-from-to-three***From:*Eric Dean Tribble

- Prev by Date:
**Weekly Planning Meeting, 8/22** - Next by Date:
**[roger: Re: find-links-from-to-three]** - Previous by thread:
**find-links-from-to-three** - Next by thread:
**Table Set and Iterator protocol** - Index(es):