1. A computer-readable memory storing an application, which, when executed on a processor in a stream-based computing system with load shedding, performs an operation, comprising: receiving streaming data to be processed by a first operator within a first processing element of the stream-based computing system; processing, at the first operator, a plurality of tuples of the streaming data; upon determining at least one workload condition for load shedding tuples has been satisfied, discarding two or more tuples of the streaming data as they are received and before being processed at the first operator; for each of the two or more discarded tuples, generating one or more respective estimated values, based on the two or more discarded tuples and the plurality of processed tuples, wherein the one or more estimated values approximate output values for the two or more discarded tuples had the two or more discarded tuples been processed at the first operator; and transmitting the estimated values to a downstream operator in the stream-based computing system, wherein the downstream operator is a punctuation operation, comprising, determining an ordinal position for at least one of the processed tuples, relative to other tuples of the plurality of incoming tuples processed; determining an ordinal position for at least one of the discarded tuples relative to other tuples of the plurality of incoming tuples processed; returning the determined ordinal positions as the result of the punctuation operation; and inserting punctuation data into the data stream for use by the downstream operator based on the determined ordinal positions.