A method, system, and computer program product for processing a stream of tuples are disclosed. The method, system, and computer program product may include receiving a stream of tuples to be processed by a plurality of processing elements. Each tuple may have an associated processing history. The stream of tuples may be segmented into a plurality of partitions, each representing a subset of the stream of tuples. The method, system, and computer program product may include estimating the contribution each partition will have on a particular processing result and processing a partition if it substantially contributes to the particular processing result.