Treedy: A Heuristic for Counting and Sampling Subsets

Teppo Niinimäki, Mikko Koivisto
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:184-192, 2013.

Abstract

Consider a collection of weighted subsets of a ground set N. Given a query subset Q of N, how fast can one (1) find the weighted sum over all subsets of Q, and (2) sample a sub- set of Q proportionally to the weights? We present a tree-based greedy heuristic, Treedy, that for a given positive tolerance d answers such counting and sampling queries to within a guaranteed relative error d and total vari- ation distance d, respectively. Experimen- tal results on artificial instances and in ap- plication to Bayesian structure discovery in Bayesian networks show that approximations yield dramatic savings in running time com- pared to exact computation, and that Treedy typically outperforms a previously proposed sorting-based heuristic.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-niinimaki13a, title = {Treedy: A Heuristic for Counting and Sampling Subsets}, author = {Niinim{\"a}ki, Teppo and Koivisto, Mikko}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {184--192}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/niinimaki13a/niinimaki13a.pdf}, url = {https://proceedings.mlr.press/r11/niinimaki13a.html}, abstract = {Consider a collection of weighted subsets of a ground set N. Given a query subset Q of N, how fast can one (1) find the weighted sum over all subsets of Q, and (2) sample a sub- set of Q proportionally to the weights? We present a tree-based greedy heuristic, Treedy, that for a given positive tolerance d answers such counting and sampling queries to within a guaranteed relative error d and total vari- ation distance d, respectively. Experimen- tal results on artificial instances and in ap- plication to Bayesian structure discovery in Bayesian networks show that approximations yield dramatic savings in running time com- pared to exact computation, and that Treedy typically outperforms a previously proposed sorting-based heuristic.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Treedy: A Heuristic for Counting and Sampling Subsets %A Teppo Niinimäki %A Mikko Koivisto %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-niinimaki13a %I PMLR %P 184--192 %U https://proceedings.mlr.press/r11/niinimaki13a.html %V R11 %X Consider a collection of weighted subsets of a ground set N. Given a query subset Q of N, how fast can one (1) find the weighted sum over all subsets of Q, and (2) sample a sub- set of Q proportionally to the weights? We present a tree-based greedy heuristic, Treedy, that for a given positive tolerance d answers such counting and sampling queries to within a guaranteed relative error d and total vari- ation distance d, respectively. Experimen- tal results on artificial instances and in ap- plication to Bayesian structure discovery in Bayesian networks show that approximations yield dramatic savings in running time com- pared to exact computation, and that Treedy typically outperforms a previously proposed sorting-based heuristic. %Z Reissued by PMLR on 04 October 2026.
APA
Niinimäki, T. & Koivisto, M.. (2013). Treedy: A Heuristic for Counting and Sampling Subsets. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:184-192 Available from https://proceedings.mlr.press/r11/niinimaki13a.html. Reissued by PMLR on 04 October 2026.

Related Material