<p>OK, I think I found something relevant: <a href="http://www.ics.uci.edu/~chenli/pub/icde08-stringsearch.pdf" rel="nofollow">this paper</a> 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).</p>

<p>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 <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.9365&amp;rep=rep1&amp;type=pdf" rel="nofollow">this other paper from the same field</a>).</p>

CC BY-SA 3.0
2012-07-10T16:14:50.870Z
2012-07-10T16:14:50.870Z
Antoine Amarilli 'a3nm'
<p>Your problem is similar to the data mining problem of finding <em>frequent itemsets</em>, also known as <a href="http://en.wikipedia.org/wiki/Association_rule_learning" rel="nofollow">Association rule learning</a>. If I understood correctly, your problem may be reduced to finding frequent itemsets of cardinality 1 (i.e., singletons) with <em>support</em> >= <em>k</em>. Of course, the available algorithms (such as Apriori, Eclat, D-CLUB etc) for the problem also allow determining frequent itemsets of cardinality > 1.</p>

CC BY-SA 3.0
2012-07-11T12:19:11.697Z
2012-07-11T12:19:11.697Z
Massimo Cafaro
<p>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$.</p>

<p>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| &lt;&lt; |S_2|$.</p>

<p>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.)</p>

CC BY-SA 3.0
2012-07-03T17:44:06.393Z
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.
Suresh Venkat
CC BY-SA 3.0
2012-07-03T20:55:03.410Z
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.
David Eppstein
<ds.algorithms>
Find items that are in at least $k$ of $n$ sets
Antoine Amarilli 'a3nm'
# Find items that are in at least $k$ of $n$ sets

(Asked by: username_0 on 2012-07-03)

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.)

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  

---

## 2 answers

### Answer by username_0 on 2012-07-10. Score: 2 | Accepted answer

OK, I think I found something relevant: [this paper](http://www.ics.uci.edu/~chenli/pub/icde08-stringsearch.pdf) 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 username_2'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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.9365&rep=rep1&type=pdf)).


---

### Answer by username_3 on 2012-07-11. Score: 1

Your problem is similar to the data mining problem of finding *frequent itemsets*, also known as [Association rule learning](http://en.wikipedia.org/wiki/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.


---

