11
$\begingroup$

Consider $n$ sets of values (represented as sorted arrays with no duplicates, and with a known size (ie. the size can be obtained in O(1)). The values can be tested for equality in O(1) time. I want to obtain the set of values that are present in at least $k$ different sets among the $n$.

The obvious algorithm to do this is to go through all the sets, count the number of occurrences of each value, and return those with a count higher than $k$. Yet, in some cases, you can do better: for instance, when $n = k = 2$ and when one set $S_1$ is much smaller than the other set $S_2$, it is more efficient to look at all items of $S_1$ and perform a binary search for each of them in $S_2$: the binary search approach costs $O(|S_1| \log(|S_2|))$ whereas the naive approach costs $O(|S_1| + |S_2|)$ which is worse when $|S_1| << |S_2|$.

With this in mind, in which situations can we do better than the naive algorithm? (If this is a well-known problem, I would be happy to know its usual name and have references.)

$\endgroup$
  • 3
    $\begingroup$ This comes under the general category of "top-K" results, or "heavy hitters". The latter is closer to what you're looking for. Most work in this space focuses on large data sets and sublinear memory restrictions though. $\endgroup$ – Suresh Venkat Jul 3 '12 at 17:44
  • 9
    $\begingroup$ The "search for all locations of S1 in S2" method you give can be made to run in time $O(|S_1|\log(|S_2|/|S_1|))$, always at least as good as the naive linear time algorithm. $\endgroup$ – David Eppstein Jul 3 '12 at 20:55
2
$\begingroup$

OK, I think I found something relevant: this paper mentions a "T-occurrence problem" in section III (p. 2) which is exactly our problem (where $T$ is what we called $k$), hidden behind some domain-specific jargon. The ScanCount algorithm that they propose is the naive approach I suggested in my question. The MergeOpt algorithm is a generalization of the binary search trick. Their main proposal (DivideSkip) is a combination of this binary search trick and a different trick (MergeSkip) to skip multiple values. It even seems that experimentally the clever approaches are much better than the naive approaches (look at the "No filters" column in page 8, the filters are heuristics for their domain-specific stuff).

This can be combined with David Eppstein's trick to make multiple binary searches in $S_2$ more efficient, and with the idea of using interpolation search instead of binary search (an idea from this other paper from the same field).

$\endgroup$
1
$\begingroup$

Your problem is similar to the data mining problem of finding frequent itemsets, also known as Association rule learning. If I understood correctly, your problem may be reduced to finding frequent itemsets of cardinality 1 (i.e., singletons) with support >= k. Of course, the available algorithms (such as Apriori, Eclat, D-CLUB etc) for the problem also allow determining frequent itemsets of cardinality > 1.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.