Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Min-d-Occur: Ensuring Future Occurrences in Streaming Sets
Vidit Jain, Sainyam Galhotra
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 proba- log 1bility of at least 1 ‚?? O kd D n + n , where D is a known constant. Our empirical obser- vations on two streaming data sets show that this algorithm achieves high precision and re- call values. We further present a sliding win- dow adaptation of the proposed algorithm to provide a continuous selection of these ele- ments. In contrast to the existing work on predicting trends based on potential increase in popularity, our work focuses on a setting with provable guarantees.
Pages: 370-379
PS Link:
PDF Link: /papers/14/p370-jain.pdf
AUTHOR = "Vidit Jain and Sainyam Galhotra",
TITLE = "Min-d-Occur: Ensuring Future Occurrences in Streaming Sets",
BOOKTITLE = "Proceedings of the Thirtieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-14)",
ADDRESS = "Corvallis, Oregon",
YEAR = "2014",
PAGES = "370--379"

hosted by DSL   •   site info   •   help