A sequence of video images represented using multiple related timelines can be searched by identifying a first point on a first timeline associated with the sequence of video images, wherein the sequence of video images is comprised of one or more samples, determining a search range on a second timeline associated with the sequence of video images based on a positive offset and a negative offset associated with the one or more samples, and searching the second timeline based on the determined search range for a second point that corresponds to the identified first point. A display offset can be associated with each of the samples comprising the sequence of video images, wherein one or more of the display offsets can comprise a negative value. Additionally, the search range can be based on a maximum positive display offset and maximum negative display offset associated with the one or more samples.