DISCUSSION
We have studied approximation algorithms for subset counting and sampling queries. After observing how any collector algorithm for approximate counting queries can be turned into a sampling algorithm, we considered four collector algorithms. These include a slow exact algorithm that serves as a reference and an "ideal" one that we cannot implement efficiently but that provides us with a lower bound of the needed work. Our experimental results suggest that the two heuristic methods, Sorted and Treedy, can yield dramatic speed-ups (by several orders of magnitude) over the exact algorithm, while not quite achieving the ideal performance. Typically, Treedy performs as well as Sorted or significantly better.
We made the assumption that the given collection of subsets is downward closed. This assumption simplified the presentation and experimental settings. The assumption is, however, not well justified in general.

### Language ###
English

### Assessment ###
The text compares performance of different algorithms, and a key finding is about the speed advantage of specific methods.

### Query ###
Tell me the scale of performance improvement achieved by the heuristic methods compared to the exact algorithm.
Tell me the scale of performance improvement achieved by the heuristic methods compared to the exact algorithm.