Min-$d$-Occur: Ensuring Future Occurrences in Streaming Sets

Vidit Jain Yahoo Labs, Sainyam Galhotra
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:284-293, 2014.

Abstract

Given a set of n elements and a corresponding stream of its subsets, we consider the problem of selecting k elements that should appear in at least $d$ such subsets arriving in the “near” future with high probability. For this min-$d$-occur problem, we present an algorithm that provides a solution with the success probability of at least $1 -O ( kd \log n D + 1 n )$ , where $D$ is a known constant. Our empirical observations on two streaming data sets show that this algorithm achieves high precision and recall values. We further present a sliding window adaptation of the proposed algorithm to provide a continuous selection of these elements. In contrast to the existing work on predicting trends based on potential increase in popularity, our work focuses on a setting with provable guarantees.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-labs14b, title = {Min-$d$-Occur: Ensuring Future Occurrences in Streaming Sets}, author = {Labs, Vidit Jain Yahoo and Galhotra, Sainyam}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {284--293}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/labs14b/labs14b.pdf}, url = {https://proceedings.mlr.press/r12/labs14b.html}, abstract = {Given a set of n elements and a corresponding stream of its subsets, we consider the problem of selecting k elements that should appear in at least $d$ such subsets arriving in the “near” future with high probability. For this min-$d$-occur problem, we present an algorithm that provides a solution with the success probability of at least $1 -O ( kd \log n D + 1 n )$ , where $D$ is a known constant. Our empirical observations on two streaming data sets show that this algorithm achieves high precision and recall values. We further present a sliding window adaptation of the proposed algorithm to provide a continuous selection of these elements. In contrast to the existing work on predicting trends based on potential increase in popularity, our work focuses on a setting with provable guarantees.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Min-$d$-Occur: Ensuring Future Occurrences in Streaming Sets %A Vidit Jain Yahoo Labs %A Sainyam Galhotra %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-labs14b %I PMLR %P 284--293 %U https://proceedings.mlr.press/r12/labs14b.html %V R12 %X Given a set of n elements and a corresponding stream of its subsets, we consider the problem of selecting k elements that should appear in at least $d$ such subsets arriving in the “near” future with high probability. For this min-$d$-occur problem, we present an algorithm that provides a solution with the success probability of at least $1 -O ( kd \log n D + 1 n )$ , where $D$ is a known constant. Our empirical observations on two streaming data sets show that this algorithm achieves high precision and recall values. We further present a sliding window adaptation of the proposed algorithm to provide a continuous selection of these elements. In contrast to the existing work on predicting trends based on potential increase in popularity, our work focuses on a setting with provable guarantees. %Z Reissued by PMLR on 04 October 2026.
APA
Labs, V.J.Y. & Galhotra, S.. (2014). Min-$d$-Occur: Ensuring Future Occurrences in Streaming Sets. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:284-293 Available from https://proceedings.mlr.press/r12/labs14b.html. Reissued by PMLR on 04 October 2026.

Related Material