Storage control method and apparatus for an interactive television terminal

• US 5,355,480 A
• Filed: 10/13/1992
• Issued: 10/11/1994
• Est. Priority Date: 12/23/1988
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Scientific-Atlanta Incorporated (Cisco Systems, Inc.)
• Inventors: Johnson, Lee R., Smith, Elizabeth A.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Chaki, Kakali
• Application Number:
  US07/960,261
• Time in Patent Office: 728 Days
• Field of Search: 364/DIG. 1, 364/DIG. 2, 395/600
• US Class Current: 715/718
• CPC Class Codes: H04N 21/2143 located in a single building, e.g. hotel, hospital or museum arrangements specially adapted for plural spots in a confined site in broadcast systems H04H20/63; adaptations for transmission by electric cable for domestic distribution in television systems H04N7/106
• CPC Class Codes: H04N 21/4331 Caching operations, e.g. of an advertisement for later insertion during playback
• CPC Class Codes: H04N 21/4335 Housekeeping operations, e.g. prioritizing content for deletion because of storage space restrictions storage management, e.g. defragmentation G06F3/0604; unloading stored programs G06F9/445; storage management in file systems G06F16/10; buffering arrangements in a network node or in an end terminal in packet networks H04L49/90
• CPC Class Codes: H04N 21/47 End-user applications
• CPC Class Codes: H04N 21/478 Supplemental services, e.g. displaying phone caller identification, shopping application
• CPC Class Codes: H04N 7/085 the inserted signal being digital
• CPC Class Codes: H04N 7/0888 Subscription systems therefor
• CPC Class Codes: H04N 7/165 Centralised control of user terminal subsequent to an upstream request signal H04N7/17345; Registering at central by two-way working H04N7/17309
• CPC Class Codes: H04N 7/1675 Providing digital key or authorisation information for generation or regeneration of the scrambling sequence pseudo-random number generators in general G06F7/58
• CPC Class Codes: H04N 7/173 with two-way working, e.g. subscriber sending a programme selection signal
• CPC Class Codes: H04N 7/17318 Direct or substantially direct transmission and handling of requests

Abstract

An interactive terminal comprises a processor, a local data store connected to the processor, a character generator responsive to processor control for generating a television signal output to an associated television receiver, a key pad or remote control for inputting information to the processor, and a power supply input. The terminal is coupled, via 2-way RF communications, to a central location designated as the system manager, where the terminal is accessed by polling for monitoring and servicing terminal user requests. The interactive terminal has a local storage capacity for storing a number of character screen commands, accessed from a central data base at the system manager, for use in generating prompting screens displayed on the television receiver. In use, a user may call for a variety of services by operating the input keys of the key pad to cause a prompting screen to be displayed. Screen commands are stored at the terminal according to an assigned priority. The stored screen commands also include pointers which are used by the terminal processor to prefetch screens which will likely follow the current screen in a decision tree structure manner. Thus, screens may be prefetched from the central data base and downloaded for storage at the terminal so that they are available for display if and when called for. If a particular branch of a decision tree is not selected, screens associated with the unselected branch are deleted from terminal memory as needed to make room for new screens. The terminal memory is also controlled so that data is swapped in and out of memory based on its relative priority.

Claims

1. A two-way interactive system comprising:

a host data processor;

a central data store controlled by the host data processor for storing a central data base, said central data base comprising a plurality of data items, each of said data items having a relative priority preassigned within said central data base; and

at least one local terminal subsystem connectable to the host data processor for accessing data items stored in the central data base, each of said at least one local terminal subsystem comprising;

a local processor for controlling access to the host data processor;

memory means controlled by the local processor and comprising a first memory area for storing data items accessed from the central data base;

locating means, operable when the first memory area has no vacant space for storing a newly accessed data item, for locating a data item in said first memory area for deletion according to criteria relating to the data items which includes locating one data item wherein the preassigned relative priority of the located data item is lower than the preassigned relative priority of at least one of the other data items stored in the first memory area, the criteria further including tie-breaking criteria to select one data item when more than one data item is located having preassigned relative priorities lower than the preassigned relative priority of the at least one of the other data items; and

deleting means responsive to said locating means for deleting the data item located by the locating means to create space in the first memory area for the newly accessed data item.

2. The system of claim 1 wherein said memory means further comprises a second memory area for storing a plurality of directory entries, each directory entry corresponding to one of said data items stored in the first memory area and specifying a memory address in said first memory area for the corresponding data item, the directory entries being stored as a priority list in said second memory area in a sorted order according to the relative priority of the data items in the first memory area.

3. The system of claim 2 wherein each of said at least one local terminal subsystem further comprises sorting means for updating and sorting said directory entries whenever the contents of the first memory area are changed.

4. The system of claim 2 wherein said locating means locates a data item to be deleted by accessing said second memory area.

5. The system of claim 1 wherein each of said at least one local terminal subsystem further comprises a keyboard having a plurality of keys for inputting information to the local processor.

6. The system of claim 5 wherein the system is characterized by a plurality of system features and said local processor separately activates a system feature in response to actuation of a predetermined key of the keyboard.

7. The system of claim 1, wherein the preassigned relative priority of the newly accessed data item is lower than the preassigned relative priority of one of the other data items.

8. A two-way interactive system characterized by a plurality of system features, the system comprising:

a host data processor;

a central data store controlled by the host data processor for storing a central data base, said central data base comprising a plurality of data items, each of said data items having a relative priority preassigned within said central data base; and

at least one local terminal subsystem connectable to the host data processor for accessing data items stored in the central data base, each of said at least one local terminal subsystem comprising;

a local processor for controlling access to the host data processor;

a keyboard having a plurality of keys for inputting information to the local processor, the local processor activating a system feature of the plurality of system features in response to actuation of a predetermined key of the keyboard;

a character screen generator capable of generating a plurality of character display screens;

memory means controlled by the local processor and comprising a first memory area for storing data items accessed from the central data base, the data items stored in the first memory area including a plurality of character screen commands, said character screen generator being responsive to said local processor and a predetermined character screen command for generating a respective character display screen viewable on an associated display device;

locating means, operable when the first memory area has no vacant space for storing a newly accessed data item, for locating a data item in said first memory area for deletion according to criteria related to the data items which includes locating one data item wherein the preassigned relative priority of the located data item is lower than the preassigned relative priority of at least one of the other data items stored in the first memory area, the criteria further including tie-breaking criteria to select one data item when more than one data item is located having preassigned relative priorities lower than the preassigned relative priority of the at least one of the other data items; and

deleting means responsive to said locating means for deleting the data item located by the locating means to create space in the first memory area for the newly accessed data item.

9. The system of claim 8 wherein said memory means further comprises a second memory area for storing a channel map containing a plurality of channel items, one of the channel items associating the predetermined keyboard key and the predetermined character screen command with a respective system feature, the predetermined character screen command being accessed by said local processor in response to actuation of the predetermined keyboard key for generating the respective character display screen.

10. The system of claim 8 wherein each of the character screen commands has a preassigned feature number corresponding to a respective system feature.

11. The system of claim 10 wherein while said first memory area is full and said local processor processes the activated system feature, said locating means locates a data item in said first memory area for deletion, the located data item being one of the character screen commands having a preassigned feature number different from the preassigned feature number of the character screen command corresponding to the activated system feature.

12. The system of claim 10 wherein:

said character screen generator, responsive to said local processor and the predetermined character screen command as a first character screen command, generates the respective character display screen as a first character display screen requesting a keyboard response; and

said first character screen command includes a pointer specifying a second character screen command to be accessed by the local processor in response to a response to the requested keyboard response.

13. The system of claim 12 wherein:

the data items further include at least one non-character screen command; and

while the preassigned feature number of said first character screen command corresponds to the activated system feature and no space is available in said first memory area for storing the newly accessed data item and the preassigned feature number of each of the character screen commands stored in said first memory area equals the preassigned feature number of said first character screen command, said locating means locates a data item in said first memory area, the located data item being a non-character screen command.

14. The system of claim 10 wherein:

a cannibal bit is associated with each character screen command;

when no space is available in said first memory area for storing the newly accessed data item and the newly accessed data item is a new character screen command having a cannibal bit in a first state, one of the character screen commands in said first memory area having a preassigned feature number corresponding to the activated system feature is deletable; and

when no space is available in said first memory area for storing the newly accessed data item and the newly accessed data item is the new character screen command having the cannibal bit in a second state, each of the character screen commands in said first memory area having a preassigned feature number corresponding to the activated system feature is undeletable.

15. In a two-way interactive system comprising a host data processor, a central data store controlled by the host data processor for storing a central data base, said central data base comprising a plurality of data items, each of the data items having a relative priority preassigned within the central data base, and at least one local terminal subsystem connectable to the host data processor for accessing data items stored in the central data base, each of said at least one local terminal subsystem comprising a local processor for controlling access to the host data processor and memory means controlled by the local processor comprising a first memory area for storing data items accessed from the central data base, a method for controlling the storage of data items in said first memory area comprising steps of:

determining whether said first memory area contains vacant space for storing a newly accessed data item accessed from said central data base;

storing said newly accessed data item in said first memory are when vacant space exists in the first memory area; and

when vacant space does not exist, locating a data item in said first memory area for deletion, the preassigned relative priority of the located data item being lower than the preassigned relative priority of at least one of the other data items stored in the first memory area, tie-breaking criteria being used to select one data item when more than one data item is located having preassigned relative priorities lower than the preassigned relative priority of the at least one of the other data items; and

replacing the located data item with the newly accessed data item when no vacant space exists in the first memory area.

16. The method for controlling storage of data items according to claim 15, wherein the memory means further comprises a second memory area, the method further comprising a step of storing a plurality of directory entries, each directory entry in the second memory area corresponding to one data item stored in the first memory area for the corresponding data item, the directory entries being stored as a priority list in the second memory area in a sorted order according to the relative priority of the data items.

17. The method for controlling storage of data items according to claim 16 further comprising a step of updating and sorting the directory entries whenever the contents of the first memory area are changed.

18. The method for controlling storeage of data items according to claim 16 wherein the step of locating includes accessing the second memory area for locating the data item to be deleted.

19. The method for controlling storage of data items according to claim 15, wherein the two-way interactive system is characterized by a plurality of system features and the local terminal further comprises a keyboard having a plurality of keys for inputting information to the local processor, the method further comprising a step of activating a system feature in response to actuation of a predetermined key of the keyboard.

20. A terminal for accessing data items stored in a central data base of a two-way interactive system, each data item having a relative priority preassigned within said central data base, the terminal comprising:

a processor for controlling access to the plurality of data items stored in the central data base;

memory means controlled by the processor and comprising a first memory area for storing data items accessed from the central data base;

locating means, operable when the first memory area has no vacant space for storing a newly accessed data item, for locating a data item in the first memory area for deletion according to criteria related to the data items which includes locating one data item wherein the preassigned relative priority of the located data item is lower than the preassigned relative priority of at least one of the other data items stored in the first memory area, the criteria further including tie-breaking criteria to select one data item when more than one data item is located having preassigned relative priorities lower than the preassigned relative priority of the at least one of the other data items; and

deleting means responsive to the locating means for deleting the data item located by the locating means to create space in the first memory area for the newly accessed data item.

21. The terminal of claim 20 wherein the memory means further ;

comprises a second memory area for storing a plurality of directory entries, each directory entry corresponding to one of the data items stored in the first memory area and specifying a memory address in the first memory area for the corresponding data item, the directory entries being stored as a priority list in the second memory area in a sorted order according to the relative priority of the data items in the first memory area.

22. The terminal of claim 21 further comprising sorting means for updating and sorting the directory entries whenever the contents of the first memory area are changed.

23. The terminal of claim 21 wherein the locating means locates a data item to be deleted by accessing the second memory area.

24. The terminal of claim 20 further comprising a keyboard having a plurality of keys for inputting information to the processor.

25. The terminal of claim 24 wherein the two-way interactive system is characterized by a plurality of system features and the processor separately activates a system feature in response to actuation of a predetermined key of the keyboard.

26. The terminal of claim 20, wherein the preassigned relative priority of the newly accessed data item is lower than the preassigned relative priority of one of the other data items.

27. A terminal for accessing a plurality of data items stored in a central data base of a two-way interactive system characterized by a plurality of system features, each data item having a relative priority preassigned within said central data base, the terminal comprising:

a processor for controlling access to the plurality of data items stored in the central data base;

a keyboard having a plurality of keys for inputting information to the processor, the processor activating a system feature of the plurality of system features in response to actuation of a predetermined key of the keyboard;

a character screen generator capable of generating a plurality of character display screens;

memory means controlled by the processor and comprising a first memory area for storing data items accessed from the central data base, the data items stored in the first memory area including a plurality of character screen commands, the character screen generator being responsive to the processor and a predetermined character screen command for generating a respective character display screen viewable on an associated display device;

locating means, operable when the first memory area has no vacant space for storing a newly accessed data item, for locating a data item in the first memory area for deletion according to criteria related to the data items which includes locating one data item wherein the preassigned relative priority of at least one of the other data items stored in the preassigned relative priority of at least one of the other data items stored in the first memory area, the criteria further including tie-breaking criteria to select one data item when more than one data item is located having preassigned relative priorities lower than the preassigned relative priority of the at least one of the other data items; and

deleting means responsive to the locating means for deleting the data item located by the locating means to create space in the first memory area for the newly accessed item.

28. The terminal of claim 27 wherein the memory means further comprises a second memory area for storing a channel map containing a plurality of channel items, one of the channel items associating the predetermined keyboard key and the predetermined character screen command with a respective system feature, the predetermined character screen command being accessed by the processor in response to actuation of the predetermined keyboard key for generating the respective character display screen.

29. The terminal of claim 27 wherein each of the character screen commands has a preassigned feature number corresponding to a respective system feature.

30. The terminal of claim 29 wherein while the first memory area is full and the processor processes the activated system feature, the locating means locates a data item in the first memory area for deletion, the located data item being one of the character screen commands having a preassigned feature number different from the preassigned feature number of the character screen command corresponding to the activated system feature.

31. The terminal of claim 29 wherein:

the character screen generator, responsive to the processor and the predetermined character screen command as a first character screen command, generates the respective character display screen as a first character display screen requesting a keyboard response; and

the first character screen command includes a pointer specifying a second character screen command to be accessed by the processor in response to a response to the requested keyboard response.

32. The terminal of claim 31 wherein;

the data items further include at least one non-character screen command;

while the preassigned feature number of the first character screen command corresponds to the activated system feature and no space is available in the first memory area for storing the newly accessed data item and the preassigned feature number of each of the character screen commands stored in said first memory area equals the preassigned feature number of the first character screen command, the locating means locates a data item in the first memory area, the located data item being a non-character screen command.

33. The terminal of claim 29 wherein:

a cannibal bit is associated with each character screen command;

when no space is available in the first memory area for storing the newly accessed data item and the newly accessed data item is a new character screen command having a cannibal bit in a first state, one of the character screen commands in the first memory area having a preassigned feature number corresponding to the activated system feature is deletable; and

when no space is available in said first memory area for storing the newly accessed data item and the newly accessed data item is the new character screen command having the cannibal bit in a second state, each of the character screen commands in said first memory area having a preassigned feature number corresponding to the activated system feature is undeletable.

34. In a two-way interactive system characterized by a plurality of system features, the system comprising a host data processor, a central data store controlled by the host data processor for storing a central data base, said central data base comprising a plurality of data items, the plurality of data items including a plurality of character screen commands, each of the data items having a relative priority preassigned within said central data base, and at least one local terminal subsystem connectable to the host data processor for accessing data items stored in the central data base, each of the at least one local terminal subsystem comprising a local processor for controlling access to the host data processor, a character screen generator capable of generating a plurality of character display screens, a keyboard having a plurality of keys for inputting information to the local processor and memory means controlled by the local processor comprising a first memory area for storing data items accessed from the central data base, a method for controlling the storage of data items in said first memory area comprising steps of:

determining whether said first memory means contains vacant space for storing a newly accessed data item accessed from said central data base;

activating a system feature of the plurality of system features in response to actuation of a predetermined key of the keyboard;

generating a character display screen viewable on an associated display device in response to a predetermined character screen command;

storing said newly accessed data item in said first memory area when vacant space exists in the first memory area; and

when vacant space does not exist, locating a data item in said first memory area for deletion, the preassigned relative priority of the located data item being lower than the preassigned relative priority of at least one of the other data items stored in the first memory area, tie-breaking criteria being used to select one data item when more than one data item is located having preassigned relative priorities lower than the preassigned relative priority of the at least one of the other data items; and

replacing the located data item with the newly accessed data item when no vacant space exists in the first memory area.

35. The method for controlling storage of data items according to claim 34, wherein the memory means further includes a second memory area, the method further comprising a step of storing a channel map in the second memory area, the channel map containing a plurality of channel items, one of the channel items associating the predetermined keyboard key and the predetermined character screen command with a respective system feature.

36. The method for controlling storage of data items according to claim 34, wherein each of the character screen commands has a preassigned feature number corresponding to a respective system feature, and the step of locating a data item in the first memory area for deletion includes locating a data item which is a character screen command having a preassigned feature number different from the preassigned feature number of the character screen command corresponding to the activated system feature when the newly accessed data item is accessed from the central data base while the first memory area is full.

37. The method for controlling storage of data items according to claim 36, wherein the step of generating includes:

generating a first character display screen in response to the predetermined character screen command as a first character screen command requesting a keyboard response, the first character screen command including a pointer specifying a second character screen command; and

accessing the second character screen command in response to a response to the requested keyboard response.

38. The method for controlling storage of data items according to claim 37 wherein the data items further include at least one non-character screen command and the step of locating a data item in the first memory area for deletion includes locating a non-character screen command when the preassigned feature number of each of the character screen commands stored in the first memory area equals the preassigned feature number of the first character screen command while no space is available in the first memory area for storing the newly accessed data item.

39. The method for controlling storage of data items according to claim 36, wherein a cannibal bit is associated with each character screen command, and the step of locating includes the steps of:

identifying as deletable one of the character screen commands in said first memory area having a preassigned feature number corresponding to the activated system feature when the newly accessed data item is a new character screen command having a cannibal bit in a first state and the first memory area is full; and

identifying as undeletable each of the character screen commands in said first memory area having a preassigned feature number corresponding to the activated system feature when the newly accessed data item is the new character screen command having the cannibal bit in a second state and the first memory area is full.

40. A two-way interactive system comprising:

a host data processor;

a central data store controlled by the host data processor for storing a central data base, said central data base comprising a plurality of data items, each of said data items having a relative priority preassigned within said central data base; and

at least one local terminal subsystem connectable to the host data processor for accessing data items stored in the central data base, each of said at least one local terminal subsystem comprising;

a local processor for controlling access to the host data processor;

a character screen generator;

memory means controlled by the local processor and comprising a first memory area for storing data items accessed from the central data base, the data items stored in the first memory area including a plurality of character screen commands, said character screen generator being responsive to said local processor and a character screen command for generating a character display screen viewable on an associated display device;

locating means, operable when the first memory area has no vacant space for storing a newly accessed data item, for locating a data item in said first memory area for deletion according to criteria related to the data items which includes locating one data item wherein the preassigned relative priority of the located data item is lower than the preassigned relative priority of each of the other data items stored in the first memory area, the criteria further including tie-breaking criteria to select one data item when more than one data item is located having preassigned relative priorities lower than the preassigned relative priority of the at least one of the other data items; and

deleting means responsive to said locating means for deleting the data item located by the locating means to create space in the first memory area for the newly accessed data item.

41. A terminal for accessing data items stored in a central data base of a two-way interactive system, each data item having a relative priority preassigned within said central data base, the terminal comprising:

a processor for controlling access to the plurality of data items stored in the central data base;

a character screen generator;

memory means controlled by the processor and comprising a first memory area for storing data items accessed from the central data base, the data items stored in the first memory area including a plurality of character screen commands, said character screen generator being responsive to said processor and a character screen command for generating a character display screen viewable on an associated display device;

locating means, operable when the first memory area has no vacant space for storing a newly accessed data item, for locating a data item in the first memory area for deletion according to criteria related to the data items which includes locating one data item wherein the preassigned relative priority of the located data item is lower than the preassigned relative priority of each of the other data items stored in the first memory area, the criteria further including tie-breaking criteria to select one data item when more than one data item is located having preassigned relative priorities lower than the preassigned relative priority of the at least one of the other data items; and

deleting means responsive to the locating means for deleting the data item located by the locating means to create space in the first memory area for the newly accessed data item.

42. In a two-way interactive terminal system comprising a host data processor, a central data store controlled by the host data processor for storing a central data base, said central data base comprising a plurality of data items, each of the data items having a relative priority preassigned within said central data base, and at least one local terminal subsystem connectable to the host data processor for accessing data items stored in the central data base, each of said at least one local terminal subsystem comprising a local processor for controlling access to the host data processor, a character screen generator and memory means controlled by the local processor comprising a first memory area for storing data items accessed from the central data base, a method for controlling the storage of data items in said first memory area comprising steps of:

determining whether said first memory area contains vacant space for storing a newly accessed data item accessed from said central data base;

storing said newly accessed data item in said first memory area when vacant space exists in the first memory area; and

when vacant space does not exist, locating a data item in said first memory area for deletion, the preassigned relative priority of the located data item being lower than the preassigned relative priority of each of the other data items stored in the first memory area, tie-breaking criteria being used to select one data item when more than one data item is located having preassigned relative priorities lower than the preassigned relative priority of the at least one of the other data items;

replacing the located data item with the newly accessed data item when no vacant space exists in the first memory area; and

generating a character display screen viewable on an associated display device in response to a character screen command.