A method for selecting a picture of a multi-picture video program for display, the method comprising: determining, based at least in part on a user-specified location within a data stream or a user-specified playback rate, a target picture that is a first temporal distance away from a current picture in a presentation order; determining a decode cost for the target picture, wherein the decode cost for the target picture is based at least in part on a number of other pictures that need to be decoded in order to decode the target picture; determining whether the decode cost for the target picture is below a specified threshold; when the decode cost for the target picture is below the specified threshold, then decoding and presenting the target picture; and when the decode cost for the target picture is not below the specified threshold, then performing steps comprising: determining a particular set of other pictures that are within a second temporal distance away from the target picture in the presentation order; selecting, from the particular set of other pictures, one or more pictures that are associated with decode costs that are below the specified threshold, wherein a decode cost for each picture of the one or more pictures is based at least in part on a respective number of other pictures that need to be decoded in order to decode each such picture of the one or more pictures; and decoding and presenting at least one of the one or more pictures that are associated with the decode costs that are below the specified threshold. determining, based at least in part on a user-specified location within a data stream or a user-specified playback rate, a target picture that is a first temporal distance away from a current picture in a presentation order; determining a decode cost for the target picture, wherein the decode cost for the target picture is based at least in part on a number of other pictures that need to be decoded in order to decode the target picture; determining whether the decode cost for the target picture is below a specified threshold; when the decode cost for the target picture is below the specified threshold, then decoding and presenting the target picture; and when the decode cost for the target picture is not below the specified threshold, then performing steps comprising: determining a particular set of other pictures that are within a second temporal distance away from the target picture in the presentation order; selecting, from the particular set of other pictures, one or more pictures that are associated with decode costs that are below the specified threshold, wherein a decode cost for each picture of the one or more pictures is based at least in part on a respective number of other pictures that need to be decoded in order to decode each such picture of the one or more pictures; and decoding and presenting at least one of the one or more pictures that are associated with the decode costs that are below the specified threshold. determining a particular set of other pictures that are within a second temporal distance away from the target picture in the presentation order; selecting, from the particular set of other pictures, one or more pictures that are associated with decode costs that are below the specified threshold, wherein a decode cost for each picture of the one or more pictures is based at least in part on a respective number of other pictures that need to be decoded in order to decode each such picture of the one or more pictures; and decoding and presenting at least one of the one or more pictures that are associated with the decode costs that are below the specified threshold.