System and method for identifying a segment of a file that includes target content

• US 9,917,869 B2
• Filed: 12/19/2013
• Issued: 03/13/2018
• Est. Priority Date: 09/23/2013
• Status: Active Grant

• Current Assignee: Spotify AB (Spotify Technology SA)
• Original Assignee: Spotify AB (Spotify Technology SA)
• Inventors: Hoffert, Eric, Strigeus, Ludvig, Oman, Andreas
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Perez-Arroyo, Raquel
• Application Number:
  US14/135,225
• Publication Number:
  US 20150088899A1
• Time in Patent Office: 1,545 Days
• Field of Search: 707741
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: H04L 65/60 Network streaming of media packets
• CPC Class Codes: H04L 65/65 Network streaming protocols, e.g. real-time transport protocol [RTP] or real-time control protocol [RTCP]

Abstract

An electronic device with one or more processors, memory and a display obtains a file header for a file that corresponds to a plurality of separately indexed clusters. The file is divided into segments one or more of which include multiple sequential clusters. The file header includes a segment index that enables identification of a segment that includes requested content. The device receives a request to seek to a respective position within the file. In response, the device identifies a first segment that includes content that corresponds to the respective position based on the segment index, obtains the first segment, and obtains a content index for a respective cluster within the first segment. After obtaining the first segment and the content index, the device identifies respective content within the respective cluster that corresponds to the respective position based on a content index and provides the respective content to a user.

Claims

1. A method of seeking within media content, comprising:

at an electronic device with one or more processors and memory;

obtaining a file header for a file that corresponds to a plurality of separately indexed segments and a plurality of separately indexed clusters, wherein;

the file is divided into the plurality of segments;

one or more of the plurality of segments each include multiple sequential clusters from the plurality of clusters;

each cluster of the plurality of clusters includes respective content portions and has a respective content index, of a plurality of content indices, that indexes the respective content portions;

the file header includes a cluster index that maps positions within the file to cluster offset information for each cluster of the plurality of clusters; and

the file header includes a segment index that enables the device to identify, based on the cluster offset information, a respective segment that includes requested content;

receiving a request to seek to a position within the file;

in response to receiving the request;

identifying a first segment, including;

mapping the position to corresponding offset information for a first cluster, using the cluster index; and

mapping the corresponding offset information for the first cluster to the first segment, using the segment index, wherein the first segment includes the first cluster;

obtaining the first segment;

obtaining a first content index of the plurality of content indices that corresponds to the first cluster within the first segment; and

after obtaining the first segment, using the first content index to identify, within the first cluster, the content corresponding to the position; and

providing at least a portion of the identified content to a presentation device for presentation to a user.

2. The method of claim 1, wherein:

the file includes video data;

a respective cluster of the plurality of clusters corresponds to a group of frames with a respective keyframe; and

the identified content corresponds to one or more frames in the video data.

3. The method of claim 1, wherein:

the file includes audio data;

a respective cluster of the plurality of clusters corresponds to a group of audio samples or audio frames; and

the identified content corresponds to one or more audio samples or audio frames in the audio data.

4. The method of claim 1, wherein the file header is obtained in response to a request for content associated with the file.

5. The method of claim 1, wherein the file header further includes a global header that provides content description information that enables the device to prepare content of the file for presentation to the user.

6. The method of claim 1, wherein obtaining the first segment includes requesting the first segment from a first source using an identifier of the first segment retrieved from the segment index.

7. The method of claim 6, wherein the identifier of the first segment includes a cryptographic hash.

8. The method of claim 1, wherein:

the plurality of segments of the file are distributed among a plurality of sources; and

the first segment is available from a plurality of different sources.

9. The method of claim 1, including after obtaining the first segment, obtaining a second segment, wherein:

when the file corresponds to on-demand content, the second segment is obtained from a respective source selected from a source table that includes a plurality of sources from which the second segment is available; and

when the file corresponds to live content, the second segment is obtained from the first source.

10. The method of claim 1, wherein the plurality of segments for the file include one or more cluster-aligned segments that each include an integer number of clusters greater than or equal to one.

11. The method of claim 10, wherein:

one segment of the plurality of segments includes a first set of N clusters; and

a different segment of the plurality of segments includes a second set of M clusters, wherein the clusters in the first set of N clusters are distinct from the clusters in the second set of M clusters.

12. The method of claim 1, wherein the file header is compressed, and the method includes, prior to using the segment index, decompressing the file header and identifying the segment index in the decompressed file header.

13. The method of claim 1, wherein:

the file header is obtained from a first location; and

the content corresponding to the file is obtained from a second location distinct from the first location.

14. The method of claim 1, wherein:

the first cluster of the plurality of clusters has a first size; and

a second cluster of the plurality of clusters has a second size different from the first size.

15. The method of claim 1, wherein:

the first content index includes information that maps respective timestamps to respective positions of content portions of the first cluster; and

the cluster index does not include the information in the first content index.

16. The method of claim 1, wherein obtaining the first content index includes obtaining a cluster header associated with the first cluster based on information retrieved from the cluster index.

17. The method of claim 16, wherein:

the cluster header is obtained from a first location; and

the cluster data is obtained from one or more locations different from the first location.

18. A computer system, comprising:

one or more processors; and

memory storing one or more programs configured to be executed by the one or more processors, the one or more programs including instructions for;

obtaining a file header for a file that corresponds to a plurality of separately indexed segments and a plurality of separately indexed clusters, wherein;

the file is divided into the plurality of segments;

one or more of the plurality of segments each include multiple sequential clusters from the plurality of clusters;

each cluster of the plurality of clusters includes respective content portions and has a respective content index of a plurality of content indices, that indexes the respective content portions;

the file header includes a cluster index that maps positions within the file to cluster offset information for each cluster of the plurality of clusters; and

the file header includes a segment index that enables the device to identify, based on the cluster offset information, a respective segment that includes requested content;

receiving a request to seek to a position within the file;

in response to receiving the request;

identifying a first segment, including;

mapping the position to corresponding offset information for a first cluster, using the cluster index; and

mapping the corresponding offset information for the first cluster to the first segment, using the segment index, wherein the first segment includes the first cluster

obtaining the first segment;

obtaining a first content index of the plurality of content indices that corresponds to the first cluster within the first segment; and

after obtaining the first segment, using the first content index to identify, within the first cluster, the content corresponding to the position; and

providing at least a portion of the identified content to a presentation device for presentation to a user.

19. A non-transitory computer readable storage medium storing one or more programs, the one or more programs comprising instructions, which, when executed by an electronic device with one or more processors, cause the device to:

obtain a file header for a file that corresponds to a plurality of separately indexed segments and a plurality of separately indexed clusters, wherein;

the file is divided into the plurality of segments;

one or more of the plurality of segments each include multiple sequential clusters from the plurality of clusters;

each cluster of the plurality of clusters includes respective content portions and has a respective content index of a plurality of content indices, that indexes the respective content portions;

the file header includes a cluster index that maps positions within the file to cluster offset information for each cluster of the plurality of clusters; and

the file header includes a segment index that enables the device to identify, based on the cluster offset information, a respective segment that includes requested content;

receive a request to seek to a position within the file;

in response to receiving the request;

identify a first segment, including;

map the position to corresponding offset information for a first cluster, using the cluster index; and

map the corresponding offset information for the first cluster to the first segment, using the segment index, wherein the first segment includes the first cluster;

obtain the first segment;

obtain a first content index of the plurality of content indices that corresponds to the first cluster within the first segment; and

after obtaining the first segment, using the first content index, identify, within the first cluster, the content corresponding to the position; and

provide at least a portion of the identified content to a presentation device for presentation to a user.