File formats and parsing and coding of video data are defined to promote more efficient random accessibility of coded video data. Constraints may be imposed on placement of parameter sets and the definition of sync samples in video files. Parameter set data for video data may be coded, for a non-sync sample, only in the sample entry for the sample, the sample, a previous sample in decoding order that is a sync sample, or in a sample occurring in decoding order between the sample and the previous sample in decoding order that is a sync sample.