Data structure, method and apparatus providing efficient retrieval of data from a segmented information stream

• US 6,438,140 B1
• Filed: 11/19/1998
• Issued: 08/20/2002
• Est. Priority Date: 11/19/1998
• Status: Expired due to Term

• Current Assignee: Comcast IP Holdings I LLC (Comcast Corporation)
• Original Assignee: DIVA Systems Corporation
• Inventors: Nelson, Dru, Jungers, Patricia D.
• Primary Examiner(s): NGO, RICKY QUOC
• Application Number:
  US09/196,297
• Time in Patent Office: 1,370 Days
• Field of Search: 707/102, 707/103, 707/104.1, 709/201, 709/213, 709/215, 711/202, 711/206, 711/207, 711/208, 348/725, 370/470, 370/471, 370/472, 370/473, 370/476, 370/477, 370/474, 370/478, 370/480, 370/486, 370/487, 370/489, 370/490, 370/521
• US Class Current: 370/471
• CPC Class Codes: G06F 16/9017 using directory or table look-up use of a directory or look-up table in file systems G06F16/13
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A data structure, method and apparatus providing efficient retrieval of data from a segmented information stream. The invention utilizes a segmented data stream having an initial directory payload portion and a following payload portion including one or more object tables. The directory includes table descriptors associated with each object table including various field indicative of parameters of the respective object table. One of the fields comprises a bit array having at least one bit corresponding to each of the segments in the respective object table. By changing a state of a corresponding bit upon receiving a table segment, the memory and processing resources required to read the segments associated with a table are decreased.

Claims

1. A data structure for providing at least one object table from a segmented information stream, said data structure comprising:

a first portion and a remaining portion, each of said first and remaining portions comprising at least one information segment, said remaining portion including said at least one object table;

said first portion including, for each object table within said remaining portion, a respective table description record comprising a number of segments field and a segment bit array field;

said number of segments field identifying a number of segments used to provide a respective object table, said segment bit array field including at least one bit corresponding to each of said number of segments in the segmented information stream used to provide said respective object table.

2. The data structure of claim 1, wherein said respective table description record includes a table type field for identifying a type of data included within said respective object table.

3. The data structure of claim 1, wherein:

said data structure provides a plurality of object tables within said remaining portion of said segmented information stream; and

said first portion including a number of tables field indicative of a number of tables included within said remaining portion.

4. The data structure of claim 3, wherein each of said respective table description records includes a segment length field and a number of bytes in table field.

5. The data structure of claim 4, wherein said object table comprises a palette asset and a bit map asset, said palette asset defining colors used to form a bit map image, said bit map asset defining a graphical image.

6. In an information distribution system providing data objects as respective pluralities of data tables, where each data table has associated with it a predefined data object, a data structure, comprising:

a first data segment of a segmented information stream including a header portion and a payload portion, said header portion comprising a stream type identifier indicative of a type of data object being provided, and

a payload portion, including a directory and said at least one table, said directory occupying at least a first segment within said payload portion of said information stream and including, for each of said at least one tables, a respective table description record, said table description record including indicia of table type and number of table segments, said table description record also including a segment bit array field, said segment bit array field including at least one bit corresponding to each of said number of table segments;

said at least one table occupying one or more contiguous segments within said payload portion of said information stream.

7. In an information stream receiver, a method for processing a received information stream to extract an object table, comprising the steps of:

receiving a directory including a table description record associated with said object table, at least one bit within a segment bit array corresponding to each of a number of table segments being set to a first state;

iteratively performing the following steps until each corresponding bit within said segment bit array is set to a second state;

receiving a plurality of segments, including segments associated with said object table; and

changing to a second state, in response to receiving a segment associated with said object table, said bit within said segment bit array corresponding to said received segment.

8. The method of claim 7, wherein said object table is included within a data structure comprising a first portion and a remaining portion, each of said first and remaining portions comprising at least one information segment;

said remaining portion including at least said object table;

said first portion including, for each object table within said remaining portion, a respective table description record comprising a number of segments field and a segment bit array field, said number of segments field identifying a number of segments used to provide a respective object table, said segment bit array field including at least one bit corresponding to each of said number of segments used to provide said respective object table.

9. The method of claim 8, wherein said respective table description record includes a table type field for identifying a type of data included within said respective object table.

10. The method of claim 8, wherein said remaining portion of said segmented information stream comprises a plurality of object tables;

and

said first portion of said information stream includes a number of tables field indicative of a number of tables included within said remaining portion.

11. The method of claim 10, wherein each of said respective table description records includes a segment length field and a number of bytes in table field.

12. The method of claim 7, wherein said information stream receiver is capable of processing at least a sub-set of said received information stream, said subset being determined with respect to indicator fields included within said received information streams, said indicator fields being associated with respective object tables.