Interactive video distribution systems – Video distribution system with upstream communication – Receiver
Reexamination Certificate
1998-11-10
2003-08-05
Faile, Andrew (Department: 2611)
Interactive video distribution systems
Video distribution system with upstream communication
Receiver
C725S053000, C725S139000, C725S151000
Reexamination Certificate
active
06604243
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to electronic receipt of information. In particular, the present invention relates to software filtering of information received by a set top box.
BACKGROUND OF THE INVENTION
In a data receiving system, such as an interactive television system, information, such as service information (SI), may be sent from a head end in various blocks of data, sometimes referred to as sections, via various transport mediums. For example, data sections may be sent from a head end via cable or satellite to a set top box coupled to a television set. An example of the contents of such data sections include information regarding present or following events, services which the user of the set top box may access, and the current time and date. Examples of events may include a television program, or a commercial, while an example of services may be a set of channels subscribed to by a viewer.
A particular set top box need only acquire sections which are required by that particular set top box, sections which are new, or sections which have changed. For example, if a viewer has only subscribed to a set of basic channels, then the sections specific to a special sports channel or movie channel not included in the basic channel set would not be required by the set top box. Accordingly, all sections which do not meet a particular set top boxes criteria's may be disregarded. The acceptance of a few select sections and rejection of all other sections may be accomplished though a combination of hardware and software filtering mechanisms.
A hardware filtering mechanism will typically perform a first round of filtering and pass on those sections which are accepted to a software filtering mechanism. The software filtering mechanism typically analyzes a header of the section, which is commonly the first 8 to 12 bytes of a section. When the start of a new section is detected, the section header is typically acquired form the transport stream. This section header is then passed to the software filter process which typically decides whether the remainder of the section should be acquired or rejected. If it is determined that the section is required, then the remainder of the section is acquired and passed on for further processing. Accordingly, only sections which have passed the software filter process will typically be forwarded for further processing.
A section may be uniquely identified by a number of individual fields within the section header. For example, depending of the section type, up to four individual fields may be used to identify a section. When a specific section is required, the software filter process may store the expected values of the individual data fields of the section header. When a section header is passed to the software filter, these expected values may be compared with the actual values from the section header. If no match occurs the next set of expected values may be compared until either a match occurs or no more expected values are available for comparison. Because the software filter may search a substantially large number of expected section header values, it is desirable to have a highly efficient comparison algorithm. A highly efficient comparison algorithm is particularly desirable since a problem may occur if a new section arrives before the software filter has finished evaluating a current section. This situation may cause an overflow or the new section may be lost. Additionally, a set top box may search for a variety of different sections at any one time, thus increasing the need for efficiency.
In addition to the need for efficiency, another common factor that is the need for memory. The memory usage for storage of the large number of expected values is typically a substantially large percentage of the very limited amount of memory commonly available in set top boxes.
It would be desirable to have a time efficient matching algorithm which uses a memory space efficient data structure. The present invention addresses such needs.
SUMMARY OF THE INVENTION
According to an embodiment of the present invention, a fast matching algorithm uses a memory space efficient data structure to accomplish information filtering in a system receiving information, such as a set top box used in conjunction with a television set. The data structure, according to an embodiment of the present invention, may include a node with a plurality of levels of expected values of data fields with an associated index to another node to be used when a matching identification of a particular level is not found. Additionally, according to an embodiment of the present invention, the nodes in this data structure may include a level field which identifies levels which are valid within the node.
In addition, according to an embodiment of the present invention, a section map may be used which utilizes a series of section maps, each section map including a predetermined number of bits, such as 32 bits. Each section map may include a single bit which indicates what is stored in the first 15 bits. For example, the last 16 bits of a section map may indicate whether the first 16 sections have been received. Another bit may be used to indicate what is stored in the first 15 bits. For example, the first 15 bits may indicate whether the next 15 sections have been received, or they may indicate an index pointing to the next section map.
A method according to an embodiment of the present invention for filtering information in an interactive television environment is presented. The method comprises providing a data structure, wherein the data structure includes a plurality of levels; and comparing information with a first criteria, wherein the first criteria is related to a first one of the plurality of levels. The method also compares the information with a second criteria, wherein the second criteria is related to a second one of the plurality of levels, this comparison occurring if the information matches the first criteria.
A system according to an embodiment of the present invention for filtering information in an interactive television environment is also presented. The system comprises a memory configured to provide a data structure, wherein the data structure includes a plurality of levels. The system also includes a processor coupled to the memory, the processor being configured to compare the information with a first criteria, wherein the first criteria is related to a first one of the plurality of levels. The processor is also configured to compare the information with a second criteria, wherein the second criteria is related to a second one of the plurality of levels, this comparison occurring if the information matches the first criteria.
A method according to an embodiment of the present invention for recording receipt of information is also presented. The method comprises providing a section number, and providing a first section map, wherein the first section map is associated with a number of bits. The method also determines whether the section number is less than the number of bits; and points to a second section map if the section number is not less than the number of bits.
A system according to an embodiment of the present invention for recording receipt of information is also presented. The system comprises a memory configured to provide a first section map, the first section map being associated with a number of bits, and a processor coupled to the memory. The processor is configured to provide a section number; determine whether the section number is less than the number of bits; and point to a second section map if the section number is not less than the number of bits.
REFERENCES:
patent: 5410344 (1995-04-01), Graves et al.
patent: 5600378 (1997-02-01), Wasilewski
patent: 5760821 (1998-06-01), Ellis et al.
patent: 5864358 (1999-01-01), Suzuki et al.
patent: 5909257 (1999-06-01), Ohishi et al.
patent: 5943605 (1999-08-01), Koepele, Jr.
patent: 5999216 (1999-12-01), Kaars
patent: 6002394 (1999-12-01), Schein et al.
patent: 6005631 (1999-12-01), And
Faile Andrew
Koenig Andrew Y
Madan Mossman & Sriram P.C.
Open TV
LandOfFree
System and method for information filtering does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for information filtering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for information filtering will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3087567