![[Figure: Shows one channel being viewed for long periods and
another for short periods.]](channel_fig_01.gif)
by Asata Maya, Ernst Quatsch, Naval Vohu, and Andrew Oram
Growing demands on the time and attention of technology users have led many to seek a more efficient return from information retrieval activities, including such leisure pursuits as television-watching. Simultaneously, the appearance of sophisticated software-driven devices such as the TiVo [1] has facilitated deterministic solutions to the problem of maximizing the amount of television watching that can subjectively be considered "relevant." Further forces driving the adoption of algorithms for rapid channel switching (a.k.a. "zapping") comes from the increasing number of cable television channels and rising cable rates that make viewers feel they should get their money's worth.
Current algorithms for channel switching include the relatively crude "jump forward upon encountering an advertisement" technique and variations on a simple round-robin algorithm, where channels are accessed in the order (T0,T1,T2…) mod n where n is the number of channels being sequentially accessed. Simultaneous viewing of multiple television sets represents another solution, but a hardware-intensive one that will not be considered in this paper due to its often prohibitive cost.
Figure 1 illustrates the weakeness of the "jump forward upon encountering an advertisement" approach. Two stations may allocate equal time for program segments and for advertisements, but a station whose advertisements start at a brief interval after previous station's advertisements is greatly favored. The problem is even greater when the interval between advertisements differs, as shown in Figure 2. To show a worst case scenario, we have assumed that the station with the shorter interval between advertisements allocates 50% of its time to these advertisements, which is common for long programs with very popular content. Here, "jump forward upon encountering an advertisement" could lead the viewer to miss an entire program segment at the program's climax.
Figure 1. Switching among channels with equal intervals between advertisements.
![[Figure: Shows a segment missed in one channel because
viewer is watching a long segment in another channel.]](channel_fig_02.gif)
Figure 2. Switching among channels with differing intervals between advertisements.
The round-robin algorithm, in turn, allows no tuning of the algorithm for relevance except on an ad-hoc basis during the viewing of a particularly relevant segment. There is no provision for dynamic allocation of time to channels that expand or retract in relevance. The system maintains no memory of viewer changes and cannot carry them over to further views of the same channels. These limitations are addressed by the system in this paper.
Both relevancy (often in the guise of Quality of Service) and time-division multiplexing appear extensively in the literature on wireless networking and high-bandwidth communications. For instance, Krunz and Tripathi [2] multiplexes time segments from different video streams to uphold varying QoS demands. Rose [3] uses a timer-based probabilistic algorithm to minimize the traffic required to track mobile phones. Shenker [4] performs calculations over integer values to determine QoS and buffering needs for data streams with expectations of an ATM transport.
This paper offers a deterministic model for channel switching that meets the following criteria:
The viewing of relevant ("interesting") material is maximized.
Relevancy can be redetermined on at each time interval and propagated to future cycles by time intervals.
Time alloted to each channel is incremented or decremented according to a fairness algorithm that minimizes the impact of relevancy rebalancing (redetermination).
The algorithm can be implemented in software or manually and requires only integer calculations.
Manual use can be implemented very simply, involving merely repeated pressing of the forward button on a remote control device.
We place two constraints on the amount of time devoted to each channel in order to facilitate conformance with criterion 1. First, we define a floor f for each channel, the minimum amount of time spent there before switching. We assume that, should the amount of viewing be allowed to fall below this floor, the viewer would not have to assess the relevancy of the channel during that segment. The floor is normally in the range of 5 to 90 seconds, depending on the viewer's familiarity with the programming, state of alertness, and total time available for viewing.
Second, to complement the minimum defined in f, we define a cycle C that represents the maximum amount of time that should elapse between viewings of a single channel. This choice reflects the ability of viewers to determine the plot and other characteristics of a television program by viewing discrete segments separated by large intervals of time. We assume that, should the viewer allow more than C time to elapse before revisiting a channel, relevant material may be missed.
Once C and f are chosen, viewers may increase or decrease the amount of time spent on each channel during a cycle. However, the requests must be adjusted so that no channel falls below f and so that the total amount of time spent on all channels in the cycle equals C. Rebalancing takes place at the end of each cycle; therefore, viewers can violate the two constraints during their switching behavior but be assumed that the constraints will be reapplied to all channels at the start of a new cycle. We note that no algorithm can reliably preserve the length of the current cycle without violating some of the goals of our method, should the viewer add or subtract a large number of elements.
Relevancy determination in television viewing is a subjective heuristic. The audio channel is frequently an aid to assessing the relevance of any particular moment on television. For instance, sequences meant to connote humor are marked by "laughter" and often delimited by "noisy applause," while other programs indicate through percussive and high-pitched sounds that the viewable moment is intended to embody suspense. Through cues that viewers began developing from the preverbal stage of life, they prove capable of quickly placing a television program within the nexus of familiar genres and determining its current placement on the scale of humor, suspense, and other criteria.
Our method begins with the choice of a period p corresponding to each of n channels to monitor in turn. The total of all initial p is C:
| C = p0 + p1 + … pn-1 | {1} |
We also choose a time period t that should be a subdivision of C/n to allow several periods to elapse before each switch, and a floor f that represents the minimal number of t the viewer must view in sequence in order to determine the relevancy of a current show. p is counted in units of t.
To simplify the algorithm for viewers carrying out the switches manually through remote control devices with simple forward buttons, we assume that the viewer cycles through all channels in a predetermined order, traversing the cycle in periods p0, p1…pn-1.
During the cycle, the viewer may to upgrade or downgrade any given station during a given time period. Upgrading and downgrading can occur repeatedly and in alternation, as the plot thickens or a particularly attractive character enters or leaves the screen. The viewer upgrades a program by adding any arbitrary number of units t to its current p, and downgrades a program by subtracting elements. We assume that the viewer wants the change to take effect immediately and to continue through succeeding cycles until the viewer makes another explicit change. A device can easily monitor spontaneous choices in viewing and calculate the change automatically. We store changes in an array delta, counted in units of t.
No station's p is allowed to drop below f; that is, we assume the viewer wants to continue monitoring every station among the initial choices no matter how severely he or she downgrades the program. (After all, another program may begin during the cycle.) If the viewer wishes to remove a station entirely, signifying an acceptance that the show is a real clunker, the entire viewing data must be discarded and a new cycle begun with a new choice of C, n, p, t, and f.
At the end of a cycle, since the viewer could well add a different number of elements than he or she subtracts, the current cycle may become longer or shorter than C. Hence, at the end of each cycle we carry out a calculation called rebalancing, in which elements are added or subtracted from periods to restore the previous C while keeping each p's ratio to C as close as possible to that requested by the viewer. We leave t invariant for the sake of simplicity, and assume that C and n are invariant for reasons discussed earlier.
Another way to view the algorithm is as follows. Since C and n are not allowed to change, any change made to any element of p must be accompanied by complementary changes to one or more of the other elements. For instance, if a viewer decides to add several elements to station p0, elements must be removed in a fair manner from some of the elements p1…pn-1.
To distribute the addition or removal of elements fairly, we add or remove units of t based on the ratio of the current period to the entire cycle. In other words, longer periods are assumed to tolerate the addition or removal of more units than shorter periods. We wish to avoid floating-point operations because they are less portable than integer operations and may be costly to simulate or even completely unavailable on small devices. Therefore, we simulate the ratio in integer operations as follows:
| new p = p + (D(p+D/2)/C) | {2} |
where D is the sum of all requested changes in delta during the cycle. We add D/2 to p at the start of the calculation to carry out integer rounding during the division.
Simulations (discussed next) show that the integer calculations are insufficent to rebalance p. Therefore, we perform a second rebalancing phase. We determine how far the sum of p still differs from C and store this amount in U. We then utilize a priority queue listing all elements of p from largest to smallest. We procede from the largest element toward the smallest element, incrementing or decrementing each until U has been exhausted.
The authors have simulated the algorithm for dynamic redetermination of relevance and rebalancing in a C program located in the following directory:
https://www.praxagora.com/andyo/professional/channel_switching/
The following files can be retrieved from that directory:
An overview of all the files in the directory.
A general discussion of the program and why it was written; a good place to start in the directory.
Directions on how to run and interpret the simulation.
Known problems with the algorithm and the simulation, along with information on reporting bugs and improvements.
Source file for the simulation.
Builds and runs the simulation program, offering a choice of tracing output. By default, builds a version that includes all tracing output.
Three files of sample input, used by the run in the Makefile.
Three files of output, each generated by the simulation from the corresponding file of input.
The simulation is not meant to justify the paper's wider goals or prove their subjective effectiveness. It is meant to show simply that an efficient algorithm based on integer operations can allow the viewer to adjust his or her evaluation of channels' relevance while keeping basic constraints of channel switching in place.
We believe we have demonstrated in this paper the viability of dynamic rebalancing based on relevancy criteria. Relevance-weighted switching algorithms may prove useful not only in adding value to viewer experiences with television programs, but in providing models for other decisions that users have to make throughout their day in allocating time to information, tasks, and personal interactions. Indeed, the model seen in present-day channel-switching may well be extended to a thoroughgoing reconsideration of personal interactions with the home, work, and social environment. It may someday prove useful to move from one conversation, task, or venue to another at dynamically chosen intervals that can be rebalanced in a manner like the channel switching in this paper. People who have learned to escape "dead time" during television viewing may well bring comparable come-and-go behavior to formal meetings, informal gatherings, and leisure activities.
Questions of overhead and complexity are likely to arise as the switching model is applied to a variety of contexts. Will users be willing to invest thought and effort into ongoing decisions about the value of particular activities while they are in the midst of engaging in these activities? Observation of current television channel switchers suggests that they find such effort quite reasonable even within the scope of this relatively passive endeavor. Indeed, the challenge of switching at appropriate times and of viewing televisions segments with the highest subjective relevancy ratings often seem to be of more interest to viewers than the television shows themselves.
We are therefore considering, after further research, a roll-out of training programs to impart relevance-weighted algorithms to the general public. Observers who challenge our assertion that such a topic would receive an enthusiastic response will have to justify how they got this far in the paper.
[1] TiVo is a consumer device for storing and selectively replaying content recorded from television broadcasts in whole or in part. http://www.tivo.com/home.asp
[4] "Guaranteed Quality of Service," RFC 2212, Shenker, et al., September 1997.
Comments on this paper can be delivered to Andrew Oram, email andyo at domain oreilly.com. The figures were drawn by Rob Romano.
This work is licensed under a Creative Commons Attribution 4.0 International License.