Method and system for representing hierarchical time-based data structures and to extract information therefrom

• US 6,023,703 A
• Filed: 05/24/1999
• Issued: 02/08/2000
• Est. Priority Date: 04/15/1997
• Status: Expired due to Term

• Current Assignee: Avid Technology Incorporated
• Original Assignee: Avid Technology Incorporated
• Inventors: Hill, Raymond
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): FLEURANTIN, JEAN B
• Application Number:
  US09/316,949
• Time in Patent Office: 260 Days
• Field of Search: 707/100, 707/101, 345/302, 345/335
• US Class Current: 1/1
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G11B 27/034 on discs G11B27/036, G11B27/038 take precedence
• CPC Class Codes: G11B 27/34 Indicating arrangements indicating means incorporated in magazine or cassette G11B23/046 and G11B23/0875; indicating measured values in general G01D
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• 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

Abstract

A method and system for representing hierarchical time-based data structures and to extract information therefrom comprises means to create a container, the container having one or more layers within which data elements are arranged along the container axis and to examine the container to produce virtual static graphs which represent active data elements and their interconnections within time durations represented within the container. The data elements in the container can change between active and inactive states with time and the connections between data elements can also change with time and the container represents this information. A set of constraints is defined for the container such that interconnections between data elements only occur between data elements in different layers. Specifically, a data element can only receive input from one or more other data elements which are in lower levels and a data element can only provide output to one or more data elements which are in higher levels. Transitions in a lower layer, representing changes in the active status of a data element, are propagated to each higher layer, such that a higher layer can never have less transitions that a lower layer. Each layer includes a record of which data element outputs are available in the layer at all times. When a request for information relating to the active data elements and their interconnections within a specified time period is received, the container is examined to produce a virtual static graph representing the minimal set of active data elements and their interconnections with the specified time.

Claims

1. A system for representing an arrangement of hierarchical time-based data elements, whose state can change between active and inactive states with time and wherein interconnections between said data elements can also change with time, and for extracting information from a specified time portion of said arrangement, comprising:

a container having at least one layer in which at least one of said data elements can be placed, each said at least one layer being arranged in a hierarchy;

means to arrange said data elements within said layers of said container such that any data element which is to receive data from an other element is represented in a higher layer than that of said other data element and any data element which is to provide an output to an other data element is in a lower layer than that of said other data element;

a database for each said at least one layer of said container, each said database including an indication of each duration in said layer, a duration being defined as the time period between adjacent state changes of any data element placed in said corresponding layer or any data element placed in an immediately adjacent lower layer in said hierarchy and each said database further including an indication of the connections to and from each said data element in said corresponding layer during each said duration;

means to examine said container to determine the durations occurring within said specified time portion;

means to determine those data elements which are in an active state for each said determined duration and their interconnections within each said determined duration; and

means to output a representation of the determined data elements and their interconnections within said specified time portion.

2. The system of claim 1 wherein said means to output a representation outputs a data structure representing a virtual static graph for each duration of said requested time portion, each said virtual static graph indicating said data elements that are in the active state in said duration and their interconnections.

3. The system of claim 1 wherein the state of each said data element is indicated by a time mask applied to each said data element.

4. The system of claim 1 further comprising means to specify, for each data element receiving input from an other data element, whether said data element requires a direct connection to said other data element or whether said data element can employ an indirect connections to said other data element via at least a third data element connected to said other data element.

5. The system of claim 1 wherein, upon modification of the contents of a first layer of said container, said means to arrange said data elements within said layers reprocesses said first layer and each higher layer in said hierarchy and each said corresponding database is updated to reflect said modification.

6. An article of manufacture including a computer usable medium having computer readable program code means embodied therein for operating a computer to construct, modify or play an NLE edit track composed of hierarchical time-based data elements whose state can change between active and inactive states with time and wherein interconnections between said data elements can also change with time, comprising:

computer readable code means for causing a computer to determine the data elements to be represented in said NLE edit track;

computer readable code means for causing a computer to create a container to represent the states and hierarchy of said determined data elements;

computer readable code means for causing a computer to place each data element which receives no input from other data elements in a first, bottom layer of said container, and to position each said data element with respect to a time line and indicate when each said data element is active and inactive;

computer readable code means for causing a computer to create a minimal set of one or more higher layers in which other data elements to be represented are placed, indicate when each said other data elements are active and inactive, said other data elements being placed such that they receive input only from data elements in a lower layer and that, if they provide an output to other data elements, those data elements are located in a higher layer;

computer readable code means for causing a computer to, for each layer in turn in said container, from the bottom layer to the top layer, examine the data elements in the layer to determine the transitions wherein each data element in the layer and in any adjacent lower layer changes between states;

computer readable code means for causing a computer to create for each layer a layer multiplexer to indicate each output from a data element which is available in each duration between determined transitions;

computer readable code means for causing a computer to examine the topmost layer of said container to determine for each duration in said container the outputs required for each duration and the data elements which provide said identified outputs;

computer readable code means for causing a computer to, for each data element which requires input from another data element, examine the layer multiplexers in lower layers to determine the other data elements which provide the required input; and

computer readable code means for causing a computer to, in response to a request for active data elements and their interconnections within a specified portion of time represented within said container, output a representation of said active data elements a representation of their interconnections for each duration within said portion of time.

7. An article of manufacture including a computer usable medium having computer readable program code means embodied therein for operating a computer to construct, modify or play at least a specified time portion of an NLE edit track composed of hierarchical time-based data elements whose state can change between active and inactive states with time and wherein interconnections between said data elements can also change with time, comprising:

computer readable code means for causing a computer to construct a container having at least one layer in which at least one of said data elements can be placed, each said at least one layer being arranged in a hierarchy;

computer readable code means for causing a computer to arrange said data elements within said layers of said container such that any data element which is to receive data from an other element is represented in a higher layer than that of said other data element and any data element which is to provide an output to an other data element is in a lower layer than that of said other data element;

computer readable code means for causing a computer to construct a database for each said at least one layer of said container, each said database including an indication of each duration in said layer, a duration being defined as the time period between adjacent state changes of any data element placed in said corresponding layer or any data element placed in an immediately adjacent lower layer in said hierarchy and each said database further including an indication of the connections to and from each said data element in said corresponding layer during each said duration;

computer readable code means for causing a computer to examine said container to determine the durations occurring within said specified time portion;

computer readable code means for causing a computer to determine those data elements which are in an active state for each said determined duration and their interconnections within each said determined duration; and

computer readable code means for causing a computer to output a representation of the determined data elements and their interconnections within said specified time portion.