The recording medium includes a data structure having a navigation map. The navigation map includes a number of map entries and indicates the number of map entries. Each map entry maps presentation time with location information for a segment of the data stream stored on the recording medium. The navigation map also includes multi-path information when the data stream includes segments representing multiple reproduction paths.