find-links-from-to-three

[Mark S. Miller <mark>]

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.