Re: Data structure for finding min of set intersection

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 11/18/04

  • Next message: David Longley: "Re: Zenkin's paper on Cantor (reply of Dr. Zenkin)" 
    Date: Thu, 18 Nov 2004 01:45:07 +0000 (UTC)

    Nicholas King wrote:
    >David Wagner wrote:
    >> Adam Morrison wrote:
    >>>Consider the following problem: We are given $m$ subsets $S_1,...,S_m$
    >>>of ${1,...,n}$. The goal is to build a data structure that supports a
    >>>MIN_INTERSECTION(i,j) operation, which returns the minimum number in the
    >>>intersection of $S_i$ and $S_j$.
    >>
    >> I presume you've thought about the idea of sorting each set in advance,
    >> and then walking through the elements of S_i in order, checking for each
    >> one to see whether it occurs in S_j?
    >
    >Having the sets sorted gives you 0(n) worst case time ,

    Sure. It wasn't clear to me whether the original poster was asking
    about worst case asymptotic running time in theory, or about algorithmic
    techniques that might be effective (on average, etc.) in practice.
    For instance, sorting the sets might run much faster than Theta(n) time
    if sets are usually sparse. That's why I asked about likely parameters
    settings; to speed up performance in practice, it might help to know
    a little more about the common case, about the distribution on problem
    instances, that kind of thing. Maybe one can do a little better for some
    specific distributions on the inputs.

  • Next message: David Longley: "Re: Zenkin's paper on Cantor (reply of Dr. Zenkin)"

    Relevant Pages

    • Re: Hpw make lists that are easy to sort.
      ... It would become competitive to the hashing solution if the sorting would be about ten times faster. ... this case it's the sum of several copies of the uniform distribution), ... that with the fast fourier transform much more efficiently than ...
      (comp.lang.python)
    • Re: Randomize three variables subject to sum always equal to 1
      ... >> We don't know if that is a problem or not as the original problem was ... the sorting is obviously not as innocent as one would imagine. ... I really liked your pie analogy and thats why I started fiddling about ... same "common" distribution to the three "RV's" as your example above: ...
      (microsoft.public.excel.programming)
    • Re: Integer math sort
      ... > Here is a version of the math (distribution) sort for sorting ...
      (comp.programming)
    • Re: Integer math sort
      ... >> Here is a version of the math (distribution) sort for sorting ...
      (comp.programming)
    • Re: using string instead of int
      ... Other than math calculations, sorting will definitely be a problem, since ... converting to an int and then storing in an int variable. ... Do you guys see anything wrong with this practice? ...
      (microsoft.public.dotnet.framework.aspnet)