text:
|Publication number
|Publication type
|Application number
|Publication date
|Dec 16, 2003
|Filing date
|Aug 21, 1998
|Priority date
|Aug 21, 1998
|Fee status
|Publication number
|Minos N. Garofalakis, Yannis E. Ioannidis, Banu Ozden
|Original Assignee
|Lucent Technologies Inc.
|Export Citation
|BiBTeX, EndNote, RefMan
|Patent Citations (12), Non-Patent Citations (20), Referenced by (26), Classifications (18), Legal Events (6)
|External Links: USPTO, USPTO Assignment, Espacenet
This invention relates to the scheduling, within multimedia database servers, of resources for storing or transmitting composite multimedia objects that contain various forms of multimedia data such as images, video, and audio.
Next generation database systems will need to provide support (for example, identify the storage (memory) and disk or transmission bandwidth requirements) for various forms of multimedia data such as images, video, and audio. These new data types differ from conventional alphanumeric data in their characteristics, and hence require different techniques for their organization and management. A fundamental issue is that digital video and audio streams consist of a sequence of media quanta (for example, video frames and audio samples) which convey meaning only when presented continuously in time. Hence, a multimedia database server needs to provide a guaranteed level of service for accessing such continuous media (CM streams in order to satisfy their pre-specified real-time delivery rates and ensure intra-media continuity. Given the limited amount of resources (for example, memory and disk or transmission bandwidth), it is a challenging problem to design effective resource scheduling algorithms that can provide on-demand support for a large number of concurrent continuous media clients.
An important requirement for multimedia database systems is the ability to dynamically compose new multimedia objects from an existing repository of CM streams. Temporal and spatial primitives specifying the relative timing and output layout of component CM streams provide perhaps the most powerful and natural method of authoring such composite multimedia presentations. Thus, to compose tailored multimedia presentations, a user might define temporal dependencies among multiple CM streams having various length and display bandwidth requirements. For example, a story for the evening news can start out by displaying a high resolution video clip with concurrent background music and narration added after an initial delay. After some time into the story, the video screen is split and a new video clip starts playing on the left half of the screen. After the second video clip ends, the narration stops and the story comes to a conclusion with the display of the first clip and the background music.
In the presence of such composite multimedia objects, a scheduling algorithm must ensure that the inter-media synchronization constraints defined by the temporal relationships among CM components are met. Handling these synchronization constraints requires a task model that is significantly more complex than the models employed in scheduling theory and practice. See, Soumen Chakrabarti and S. Muthukrishnan, "Resource Scheduling for Parallel Database and Scientific Applications", Proceedings of the Eighth Annual ACM Symposium on Parallel Algorithms and Architectures, pages 329-335, Padua, Italy, June 1996; M. R. Garey and R. L. Graham, "Bounds for Multiprocessor Scheduling with Resource Constraints", SIAM Journal on Computing, 4(2):187-200, June 1975; and M. R. Garey, R. L. Graham, D. S. Johnson, and Andrew Chi-Chih Yao, "Resource Constrained Scheduling as Generalized Bin Packing", Journal of Combinatorial Theory (A), 21:257-298, 1976. More specifically, composite multimedia objects essentially correspond to resource-constrained tasks with time-varying resource demands. Resource constraints come from the limited amount of server resources available to satisfy the requirements of CM streams and time-variability stems from the user-defined inter-media synchronization requirements. We believe that this is a task model that has not been previously studied in the context of deterministic scheduling theory. Furthermore, despite the obvious importance of the problem for multimedia database systems, our work appears to be the first systematic study of the problems involved in scheduling multiple composite multimedia objects. We suspect that this may be due to the difficulty of the problems, most of which are non-trivial generalizations of NP-hard optimization problems.
It appears that today's multimedia storage servers offer no clever scheduling support for composite multimedia presentations. The approach typically employed is to reserve server resources based on the maximum (that is, worst-case) resource demand over the duration of a composite presentation. Examples of systems using this worst-case resource reservation method include the Fellini and CineBlitz multimedia storage servers developed at Bell Laboratories and discussed in Cliff Martin, P. S. Narayanan, Banu �zden, Rajeev Rastogi, and Avi Silberschatz, "The Fellini Multimedia Storage Server", Multimedia Information Storage and Management, pages 117-146, (S. M. Chung ed., Kluwer Academic Publishers 1996); Starlight's StarWorks (http://www.starlight.com/); and Oracle's Media Server (http://www.oracle.com/). Conceptually, this approach is equivalent to identifying the resource requirements of the presentation over time with their enclosing Minimum Bounding Rectangle MBR). Although this simplification significantly reduces the complexity of the relevant scheduling problems, it suffers from two major deficiencies.
The volume (that is, resource-time product as in Chakrabarti et al. and in our Minos N. Garofalakis and Yannis E. Ioannidis, "Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources", Proceedings of the 23rd International Conference on Very Large Data Bases, pages 296-305, Athens, Greece, August 1997. ) in the enclosing MBR can be significantly larger than the actual requirements of the composite object. This can result in wasting large fractions of precious server resources, especially for relatively "sparse" composite objects.
The MBR simplification "hides" the timing structure of individual streams from the scheduler, making it impossible to improve the performance of a schedule through clever use of memory buffers.
A number of conceptual models have been developed for capturing the temporal aspects of multimedia data. They can be roughly classified into three categories, namely: 1) graph-based models (for example, object composition petri nets as in Thomas D. C. Little and Arif Ghafoor, "Synchronization and Storage Models for Multimedia Objects", IEEE Journal on Selected Areas in Communications, 8 (3):413-427, April 1990 and presentation graphs as in Kingsley C. Nwosu, Bhavani Thuraisingham, and P. Bruce Berra, eds., Multimedia Database Systems: Design and Implementation Strategies, Kluwer Academic Publishers, 1996); 2) language-based models (for example, HyTime as in Steven R. Newcomb, Neill A. Kipp, and Victoria T. Newcomb, "The HyTime Hypermedia/Time-based Document Structuring Language", Communications of the ACM, 34 (11), November 1991 and MHEG as in R. Price, "MHEG: An Introduction to the Future International Standard for Hypermedia Object Interchange", Proceedings of ACM Multimedia '93, pages 121-128, Anaheim, Calif., August 1993.), and 3) temporal abstraction models (for example, temporal intervals and relations as in J. F. Allen, "Maintaining Knowledge About Temporal Intervals", Communications of the ACM, 26(11):832-843, November 1983, and Thomas D. C. Little and Arif Ghafoor, "Interval-Based Conceptual Models for Time-Dependent Multimedia Data", IEEE Transactions on Knowledge and Data Engineering, 5(4):551-563, August 1993). Candan et al. present a method based on linear difference constraints for defining flexible inter-media synchronization requirements and show how these constraints can be solved and/or modified to ensure consistency in K. Selcuk Candan, B. Prabhakaran and V. S. Subrahmanian, "Retrieval Schedules Based on Resource Availability and Flexible Presentation Specifications", Technical Report CS-TR-3616, University of Maryland, College Park, 1996. Thimm et al. describe a feedback-based architecture for adapting a multimedia presentation to the changes in resource availability by modifying the presentation quality in Heiko Thimm and Wolfgang Klas, "δ-Sets for Optimized Reactive Adaptive Playout Management in Distributed Multimedia Database Systems", Proceedings of the Twelfth International Conference on Data Engineering, pages 584-592, New Orleans, La., February 1996. In our earlier work, Minos N. Garofalakis and Yannis E. Ioannidis, "Scheduling Issues in Multimedia Query Optimization": ACM Computing Surveys, 27(4):590-592, December 1995 (Symposium on Multimedia), we present a scheduling framework for simple (independent) CM streams based on the resource-constrained list-scheduling methodology of Garey and Graham discussed above.
Articles which address some of the issues in scheduling composite multimedia objects include Surajit Chaudhuri, Shahram Ghandeharizadeh and Cyrus Shahabi, "Avoiding Retrieval Contention for Composite Multimedia Objects", Proceedings of the 21st International Conference on Very Large Data Bases, pages 287-298, Zurich, Switzerland, September 1995; and Cyrus Shahabi, Shahram Ghandeharizadeh and Surajit Chaudhuri, "On Scheduling Atomic and Composite Multimedia Objects", Technical Report USC-CS-95-622, University of Southern California, 1995, (to appear in IEEE Transactions on Knowledge and Data Engineering). However, their research on composite objects focuses on (1) using memory to resolve the problem of "internal contention", which occurs when the temporal synchronization constraints cause stream retrievals for a single object to collide; and, (2) developing heuristic memory management policies to distribute a fixed amount of server memory among multiple competing objects. More specifically, Chaudhuri et al. suggest a conservative and a greedy heuristic for allocating memory among multiple binary composite objects, under the assumption of regular, round-robin striping of component streams. However, extending their heuristics to general, n-ary objects appears to be problematic. Shahabi et al. show how these conservative and greedy methods can be adapted to the problem of resolving internal contention in a single n-ary composite object, again assuming round-robin layout. Although the authors outline some ideas on how to actually schedule multiple composite objects, they offer no concrete algorithmic solutions for the problem. Furthermore, their development is based on the assumption of a round-robin distribution of stream fragments across disks, whereas we assume a more abstract "black-box" model of server disk bandwidth.
Thus, there remains in the art a need to implement a composite multimedia object scheduling system that permits the efficient and reliable scheduling of the composite multimedia objects to ensure that the inter-media synchronization constraints between the CM streams are met.
We formulate resource scheduling problems for composite multimedia objects and develop novel efficient scheduling algorithms, drawing on a number of techniques from pattern matching and multiprocessor scheduling. Our formulation is based on a novel sequence packing problem, where the goal is to superimpose numeric sequences (representing the objects' resource needs as a function of time) within a fixed capacity bin (representing the server's resource capacity). We propose heuristic algorithms for the sequence packing problem using a two-step approach. First, we present a "basic step" method for packing two object sequences into a single, combined sequence. Second, we show how this basic step can be employed within different scheduling heuristics to obtain a playout schedule for multiple composite objects. More specifically, we examine greedy scheduling heuristics based on the general list-scheduling (LS) methodology of Graham in R. L. Graham, "Bounds on Multiprocessing Timing Anomalies", SIAM Journal on Computing, 17(2):416-429, March 1969; and in Garey and Graham. We show that although LS schemes are provably near-optimal for packing monotonic sequences, they can have poor worst-case performance when the monotonicity assumption is violated. A "monotonic" sequence is a sequence in which the bandwidth requirement of the sequence can either increase or decrease over time, but it can not do both. Based on this result, we propose: (1) inventive methods for improving the behavior of simple LS through the use of extra memory buffers; and, (2) a novel family of more clever scheduling algorithms, termed list-scheduling with backtracking (LSB), that try to improve upon simple LS by occasional local improvements to the schedule.
Results with randomly generated composite objects show that our LS strategy offers excellent average-case performance compared to both an MBR-based approach and the optimal solution. Finally, we show how the idea of stream sharing can be exploited to improve the quality of a schedule. "Stream sharing" occurs when we allow several presentations to share component streams from separate composite objects.
Although our invention is primarily geared towards composite objects, our task model also exactly captures the problem of scheduling the retrievals of variable bit rate streams, that is, CM streams whose bandwidth requirements can vary over time. This is a very important application of our scheduling framework, since real-life CM data is nearly always variable rate.
Therefore, there is a need for our inventive method of scheduling the provision of composite multimedia objects, each comprising one or more continuous media streams of audio data, video data and other data, where the continuous media streams are of varying bandwidth requirement and duration; generating composite multimedia objects from the continuous media streams; and determining a run-length compressed form for each of the generated composite multimedia objects. Where the other data can be still images (for example, photographs), other images (for example, graphic and scanned images), animations, text, and program code data files)
Other advantages and features of the present invention will be understood from studying FIGS. 1-12 and the detailed description of a preferred embodiment.
In the drawings,
FIG. 1 illustrates a typical prior art arrangement of a composite multimedia object.
FIG. 2 illustrates the composite object sequence corresponding to the prior art composite multimedia object in FIG. 1.
FIG. 3 illustrates the prior art composite multimedia object from FIG. 1 with one of the continuous multimedia streams upslided by some number of time units.
FIG. 4 illustrates the prior art composite multimedia object from FIG. 1 with one of the continuous multimedia streams downslided by some number of time units.
FIG. 5 illustrates a collision between two normalized object sequences.
FIG. 6 illustrates a sequence packing solution for the two normalized object sequences in FIG. 1.
FIG. 7 illustrates a worst case example composite object schedule created using the list-scheduling (LS) algorithm.
FIG. 8 illustrates the optimal schedule of the composite objects in FIG. 7.
FIG. 9 illustrates a 5-ary composite multimedia object.
FIG. 10 illustrates a non-increasing object sequence of the composite multimedia object in FIG. 9 created using "naive" stream upsliding.
FIG. 11 illustrates a non-increasing object sequence of the composite multimedia object in FIG. 9 created using "clever" stream upsliding.
FIG. 12(a) illustrates the first backtracking point in the operation of the list-scheduling with k-object backtracking LSB(k) algorithm.
FIG. 12(b) illustrates the results of the LSB(k) algorithm on the composite multimedia object schedule in FIG. 12(a).
FIG. 12(c) illustrates the schedule after the LS algorithm places the sixth and seventh composite multimedia objects in the schedule in FIG. 12(b).
FIG. 12(d) illustrates the final schedule after the LS algorithm places the eighth and ninth composite multimedia objects in the schedule in FIG. 12(c).
A composite multimedia object consists of multiple continuous media (CM) streams tied together through spatial and temporal primitives. "Continuous media streams" are digital video and audio streams that consist of a sequence of media quanta (for example, video frames and audio samples) which convey meaning only when presented continuously in time. Since the spatial layout of the output is predetermined by the user and does not affect the resource bandwidth requirements of CM streams, we concentrate on the temporal aspects of CM composition. Following the bulk of the multimedia systems literature, we also concentrate on the server disk bandwidth resource which is typically the bottleneck for multimedia applications. To simplify the presentation, we assume that the stream resource demands have been normalized to [0,1] using the aggregate disk bandwidth of the server B.
We also assume that the time scale is discrete so that both the lengths of CM streams and their lag parameters have integer values. This is usually the case in practice, since most multimedia storage servers employ a round-based data retrieval scheme and thus timing can only be specified at the granularity of a round's length, which is typically very small (a few seconds). Of course, finer-grain synchronization can always be implemented using extra memory buffering.
Following Chaudhuri et al., we define an ni-ary composite multimedia object Ci as a (2ni−1)-tuple<Xi
FIG. 1 illustrates a typical prior art arrangement of a composite multimedia object 100. The composite multimedia object 100 is a 4-ary composite multimedia object representation of a news story. The composite multimedia object 100 consists of four overlapping continuous media (CM) streams. A CM stream can contain any combination of digital video and audio samples. The first of these CM streams, X1 110, contains a high resolution video clip that starts at time T1 150 and continues until time T7 195. The second of these CM streams, X2 120, contains the related narration for X1 110 that starts at time T2 160 and is played concurrently with X1 110 until time T6 190. The third CM stream, X3 130, starts at time T3 170 and contains the related music for X1 110 that plays concurrently with X1 110 and X2 120 until time T6 190 when X2 120 terminates and then X3 130 continues concurrently with X1 110 until time T7 195 when both X1 110 and X3 130 terminate and the object ends. The fourth CM stream, X4 140, starts at time T4 180 and contains a second high resolution video clip that is played in a split screen next to X1 110. X4 140 plays concurrently with X1 110, X2 120, and X3 130 until time T5 185 when X4 terminates and the split screen disappears and only a single screen with X1 110 remains. The height of each stream in FIG. 1 corresponds to its bandwidth requirement and the length corresponds to its duration.
For each component CM stream Xi
Aggregate server disk bandwidth
(in bit per sec -- bps)
Length of a time unit (that is, round) (in sec)
Composite multimedia object
Number of component streams in Ci
Length (that is, time duration) of Ci
Bandwidth requirement of Ci at time slot t
(0 ≦ t < l(Ci))
Max. bandwidth requirement of Ci
The jth component stream of Ci
Length and bandwidth requirement of stream Xi
Number of constant bandwidth "blocks" in the
run-length compressed form of Ci
Length and bandwidth requirement of the
jth run-length "block" of Ci
Volume (that is, total resource-time product) of Ci
Density of Ci
FIG. 2 illustrates the composite object sequence 200 corresponding to the prior art composite multimedia object 100 in FIG. 1. A "composite object sequence" is a graphical representation of a composite multimedia object's 100 bandwidth requirement during at any given time. The rising edges at T1 150, T2 160, T3 170, and T4 180 correspond to the start of the individual CM streams, X1 10, X2 120, X3 130, and X4 140, respectively. Likewise, the falling edges at T5 185, T6 190, and T7 195 correspond to the end of the individual CM streams, X4 140, X2 120, and X1 110 and X3 130, respectively.
The bandwidth requirements of our example news story object can be represented as the composite object sequence depicted graphically in FIG. 2, where each element of the sequence corresponds to the object's bandwidth demand at that point in time (that is, during that time unit). Note that the rising and falling edges in a composite object sequence correspond to CM streams starting and ending, respectively. Essentially, the object sequence represents r(Ci, t), that is, the (varying) bandwidth requirements of the object as a function of time t. Since our scheduling problem focuses on satisfying the bandwidth requirements of objects, we will treat the terms "composite object" and "sequence" as synonymous hereinafter.
Typically, CM streams tend to last for long periods of time. This means that using the full-length, l(Ci)-element object sequence for representing and scheduling a composite multimedia object is a bad choice for the following two reasons. First, these full-length sequences will be very long (for example, a 2-hour presentation will typically span thousands of rounds/time units). Second, full-length object sequences will be extremely redundant and repetitive since they only contain a small number of transition points.
For our purposes, a more compact representation of composite objects can be obtained by using the run-length compressed form of the object sequences. Essentially, the idea is to partition the composite object into "blocks" of constant bandwidth requirement and represent each such block by a pair (li
We define the volume (V) of a composite object Ci as the total resource-time product over the duration of Ci. More formally, V(Ci)=Σj=1 k i li
Although inter-media synchronization constraints completely specify the relative timing of streams at presentation time, the scheduler can use extra memory buffers to alter an object's retrieval sequence. This assumes the round-based retrieval of streams with a round length of T, and each stream, Xi j, requires a minimum buffering of 2�T�B�r(Xi
FIG. 3 illustrates the prior art composite multimedia object 100 from FIG. 1 with one of the CM streams upslided by some number of time units, x. In FIG. 3, CM stream X4 140 is upslided from time T4, denoted by 180, to time T4−x, denoted by 310.
Similarly, the server may also choose to downslide a stream, which means that the retrieval of the stream starts after its designated playout time in the presentation (FIG. 4). Downsliding introduces latency in the composite object presentation, since it is clearly impossible to start the playout of a stream before starting its retrieval. Thus, in FIG. 4, the entire presentation must be delayed by y time units. This also means that once a stream is downslided, all the other streams must be buffered unless they are also downslided by the same amount. As a result, upsliding is preferable to downsliding, whenever both options are available.
FIG. 4 illustrates the prior art composite multimedia object 100 from FIG. 1 with one of the CM streams downslided by some number of time units, y. "Downsliding" is defined as the retrieving of a CM stream after it is actually needed in the presentation. Downsliding introduces latency in the composite multimedia object presentation, since it is impossible to start the playout of a stream before it is retrieved. In FIG. 4, CM stream X4 140 is downslided from time T4, denoted by 180, to time T4+y, denoted by 410. Thus, the entire presentation must be delayed by y time units. This means that once a stream is downslided, all other streams must be buffered unless they are also downslided by the same amount of time y, as shown in FIG. 4 by the dotted outlines on X1 10, X2 120, and X3 130.
Given a collection of composite objects to be scheduled using the server's resources, a schedule is an assignment of start times to these objects so that, at any point in time, the bandwidth and memory requirements of concurrent presentations (to, perhaps, different users) do not violate the resource capacities of the server. We concentrate on the problem of off-line makespan (that is, response time) minimization, in which the objective is to minimize the overall schedule length for a given collection of objects (tasks). Prior scheduling theory research has shown how to employ solutions to this problem for both on-line response time minimization (where tasks arrive dynamically over time) and on-line average response time minimization.
Ignoring the flexibilities allowed in stream synchronization through additional memory buffering (that is, sliding), the bandwidth requirements of each object to be scheduled are completely specified by its resource demand sequence in FIG. 2. Thus, assuming sliding is not an option, our scheduling problem can be abstractly defined as follows.
Given: A collection of(normalized) composite object sequences {Ci} over [0,1].
Find: A start time slot s(Ci) for each i, such that for each time slot t
and maxi{s(Ci)+l(Ci)} is minimized.
Conceptually, this corresponds to a sequence packing problem, a non-trivial generalization of traditional NP-hard optimization problems like bin packing and multiprocessor scheduling that, it appears, has not been previously studied in the combinatorial optimization literature. In bin packing terminology, we are given a set of items (normalized object sequences) that we want to pack within unit-capacity bins (server bandwidth) so that the total number of bins (makespan, used time slots) is minimized. Our sequence packing problem also generalizes multidimensional bin packing models known to be intractable, like orthogonal rectangle packing (a rectangle is a trivial, constant sequence) and vector packing (vectors are fixed length sequences with start times restricted to bin boundaries). Note that rectangle packing algorithms are directly applicable when the MBR simplification is adopted. However, it is clear that this simplification can result in wasting large fractions of server bandwidth when the object densities are low. Given the inadequacy of the MBR simplification and the intractability of the general sequence packing formulation, we propose novel efficient heuristics for scheduling composite object sequences using a combination of techniques from pattern matching and multiprocessor scheduling.
Sliding further complicates things, since it implies that the scheduler is able to modify the composite object sequences at the cost of extra memory. Given a set of object sequences and a finite amount of memory available at the server, the problem is how to utilize memory resources for sliding various object streams around (that is, modifying the object sequences) so that the scheduler can effectively minimize some scheduling performance metric such as schedule length or average response time. This is obviously a very complex problem that, in many ways, generalizes recently proposed malleable multiprocessor scheduling problems. Apparently, the general sliding problem, as outlined above, has yet to be addressed in the scheduling or multimedia literature.
Our results for the sequence packing problem indicate that simple, greedy scheduling algorithms based on Graham's list-scheduling method can guarantee provably near-optimal solutions, as long as the sequences are monotonic. On the other hand, we show that list-scheduling can perform poorly when the monotonicity assumption is violated. Based on this result, we examine the problem of exploiting extra memory and sliding to make object sequences monotonic. Although this problem is itself NP-hard, we propose a polynomial-time approximate solution.
Our approach is based on the observation that the result of packing a subset of the given object sequences is itself an object sequence. Thus, we begin by presenting a "basic step" algorithm for obtaining a valid packing of two sequences. We then show how this method can be employed within two different scheduling heuristics to obtain a playout schedule for multiple composite objects.
Our basic algorithmic step problem can be abstractly described as follows. Given two (normalized) object sequences Co (a new object to be scheduled) and Cp (the partial schedule constructed so far) over [0,1]. We want to determine a valid packing of the two sequences, that is, a way to superimpose Co over Cp that respects the unit capacity constraint (that is, all elements of the combined sequence are less than or equal to 1). Given that our overall scheduling objective is to minimize the length of the resulting composite sequence, the presentation of this section assumes a "greedy" basic step that searches for the first point of Cp at which Co can be started without causing capacity constraints to be violated. Since the full-length representation of the object sequences is very inefficient, we assume that both object sequences are given in their run-length compressed form. That is, Co=<(lo
Since our composite object sequences can be seen as patterns over the alphabet [0,1], it is natural to ask whether or not ideas from the area of pattern matching can be used to make our basic algorithmic step more efficient. As in most pattern matching problems, the requirement that all "characters" of both patterns must be examined imposes a linear, that is, O(ko+kp) (since we are dealing with the compressed representations), lower bound on the running time of any algorithm. The question is whether or not this lower bound is attainable by some strategy. An equivalent formulation of our basic step packing problem comes from considering the complementary sequence {overscore (Cp)} of the partial schedule Cp, which informally, corresponds to the sequence of free server bandwidth over time. More formally, {overscore (Cp)} is determined by defining r({overscore (Cp)}, t)=1−r(Cp, t), for each time slot t. Thus, our problem is equivalent to finding the earliest time slot at which Co is completely "covered" (dominated) by {overscore (Cp)}. This is a problem that has received some attention from the pattern matching research community. Amir and Farach define the above problem for uncompressed patterns as the "smaller matching" problem and give an algorithm that runs in time O(l(Cp)�{square root over (l(Co))}�log l(Co)), where l( ) denotes uncompressed sequence lengths. Muthukrishnan and Palem show that this is in fact a lower bound on the time complexity of the problem in a special, yet powerful convolution-based model; their result implies that faster algorithms for the smaller matching problem would imply a faster method than the Fast Fourier Transform for certain generalizations of convolutions.
None of these papers address the problem encountered when run-length compressed forms of the patterns are used. Furthermore, it is not clear whether the rather complicated algorithm of Amir and Farach will outperform a straightforward O(l(Cp)�l(Cp)) solution in a practical implementation. Finally, even if the "optimal" method of Amir and Farach could be extended to run-length compressed patterns, the asymptotic performance improvement with respect to FINDMIN would only be
a small gain since the number of streams in a single composite object ko is typically bounded by a small constant.
Thus, prior results from the pattern matching community assure us that our "brute-force" FINDMIN algorithm is a reasonably good strategy for the basic sequence packing step for general object sequences. However, for special cases of object sequences (Co), we may still be able to come up with faster algorithms. One such algorithm for the special case of bitonic object sequences, for purposes of the following discussion, is called BITONIC-FINDMIN.
FIG. 5 illustrates a collision between two normalized object sequences, an object sequence Co 510 and the partial schedule Cp 520 of all previously scheduled object sequences. In FIG. 5, Co 510 is a bitonic object sequence. A "bitonic" object sequence is a sequence that can be partitioned into a monotonically increasing prefix followed by a monotonically decreasing prefix. This means that no new component streams can be initiated after the end of a stream in the presentation.
FIG. 6 illustrates a sequence packing solution for the collision of the two normalized object sequences, Co 510 and Cp 520, in FIG. 5. To align any given object sequence with any given Cp, we can use the algorithm FINDMIN. However, since Co 510 is a bitonic object sequence, we can also use the faster BITONIC-FINDMIN algorithm to align it with Cp 520. The result shown in FIG. 6 is the resolution of the collision by align-ing using the BITONIC-FINDMIN algorithm.
Although one can argue that bitonic objects are rather common in multimedia practice (for example, our example news story composite object shown in FIG. 1 is bitonic), our method can also be used within more complex basic step algorithms for general sequences. The idea is to partition objects into a (small) number of bitonic components and schedule each component using our improved strategy for bitonic objects.
The basic operation of our improved algorithm for bitonic objects is similar to that of the Knuth-Morris-Pratt string matching algorithm, in that it shifts the Co pattern over Cp until a "fit" is discovered. The crucial observation is that, for bitonic Co patterns, we can perform this shifting in an efficient manner, without ever having to backtrack on Cp. This is done as follows. Consider a particular alignment of Co and Cp and let (lp
The time complexity of algorithm BITONIC-FINDMIN is O(ko+kp�log ko). The first term comes from the preprocessing step for Co. The second term is based on the observation that both the partial sums vector sj and the bandwidth requirements vector for the increasing segment of Co are sorted, which means that the "find the least/largest index such that <condition>" steps of BITONIC-FINDMIN can be performed in time O(log ko), using binary search. More elaborate search mechanisms (for example, based on Thorup's priority queue structures from Mikkel Thorup, "On RAM Priority Queues", Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 59-67, Atlanta, Ga., January 1996) can be employed to reduce the asymptotic complexity of BITONIC-FINDMIN to O(ko+kp�log log ko).
We present a heuristic algorithm that uses the basic packing step described above in the manner prescribed by Graham's greedy list-scheduling strategy for multiprocessor scheduling. The operation of our heuristic, termed LS, is as follows. Let L be a list of the composite object sequences to be scheduled. At each step, the LS algorithm takes the next object from L and (using FINDMIN or BITONIC-FINDMIN) places it at the earliest possible start point based on the current schedule. This rule is identical to Graham's list-scheduling rule for an m-processor system, when all objects have a constant bandwidth requirement of 1/m throughout their duration.
Unfortunately, this simple list-scheduling rule does not offer a good guaranteed worst-case bound on the suboptimality of the obtained schedule. Even for the special case of bitonic objects, it is easy to construct examples where the makespan of the list schedule is Ω(min{l, |L|}) times the optimal makespan, where |L| is the number of objects and l is the length (in rounds) of an object sequence. One such bad example for LS is depicted in FIG. 7. Note that as the example object sequences become more "peaked", the behavior of LS compared to the optimal schedule becomes even worse. However, even for this bad example, LS will behave significantly better than MBR scheduling, which would not allow any overlap between consecutive "columns" in the schedule.
Algorithm BITONIC-FINDMIN(Co, Cp)
Sequences Co, Cp over [0,1] in run-length compressed form
(that is,
Sequence Co is assumed to be bitonic.
The least 0 ≦ k ≦ l(Cp) such that Co can be validly
superimposed over Cp starting at time slot k. description
Preprocess Co to obtain a "partial sums" vector
Initialize: align(0,0), j = i = 0, lcov = 0.
while (lcov < l(Co)) do
Find the least ij such that si
To check for a collision at block (lp
distinquish two cases.
Co is decreasing after lcov. (We just need to check the
first block of Co placed over (lp
(that is, no collision) then set
lcov = lcov + lp
Else, find the largest block index m in the increasing
part of Co such that ro
align(j,m), and set i = m, j = j + 1, lcov = sm.
Co is increasing after lcov. If the block index ij is in
the decreasing part of Co then check if
If the condition holds set lcov = lcov + lp
i = ij. Else, find the largest block index m in the
increasing part of Co such that ro
align(j,m), and set i = m, j = j + 1, lcov = sm.
Return the starting time slot for the current placement of Co.
FIG. 7 illustrates a worst case example composite object schedule created using the list-scheduling (LS) algorithm. In FIG. 7, the composite object sequence 710 represents the shape of all the individual objects in a list of composite object sequences in the schedule 720. The schedule 720 is produced using the LS algorithm and either FINDMIN or BITONIC-FINDMIN to place each object, in turn, at the earliest possible starting point based on the current schedule. As can be seen in FIG. 7, the schedule 720 is less than optimal.
Thus, in the worst case, the behavior of LS can be arbitrarily bad compared to the optimal schedule. Furthermore, note that since all the objects in the example of FIG. 7 are identical, ordering the list L in any particular order (for example, by decreasing object "height") will not help worst-case behavior. Assuming the maximum resource requirements of objects (that is, rmax(Ci)'s) to be bounded by some small constant (a reasonable assumption for large-scale CM servers) also does not help, as long as the objects are sufficiently "peaky".
However, as the following theorem shows, the situation is much better when the object sequences in L are appropriately constrained.
Theorem 1. Let L be a list of monotonically non-increasing composite object sequences Ci and assume that rmax(Ci)≦λ<1, for each i. Also, let lmax(L)=maxi{l(Ci)} and V(L)=ΣiV(Ci) (that is, the total volume in L), and let TOPT(L) be the makespan of the optimal schedule for L. Then, the makespan returned by LS, TLS(L), satisfies the inequality:
It is easy to see that a slightly modified version of LS can guarantee the same worst-case performance bound for any list of monotonically non-decreasing objects, as well. The basic idea is to "time-reverse" each object sequence and schedule these reversed (non-increasing) sequences using LS. Of course, the schedule obtained is then played out in reverse (that is, from end to start). We can combine these observations with algorithm LS to obtain the following simple strategy, termed Monotonic LS (MLS), for scheduling monotonic objects. First, schedule all non-increasing sequences using LS. Second, reverse all remaining objects and schedule them using LS. Third, concatenate the two schedules. It is easy to prove the following corollary.
Corollary 1. For any list L of monotonic composite objects Ci with rmax(Ci)≦λ<1, for each i, algorithm MLS guarantees a makespan TMLS(L) such that:
With respect to the time complexity of our list-scheduling algorithms, it is easy to see that the decisive factor is the complexity of the basic packing step discussed above. Using the FINDMIN algorithm for general object sequences implies an overall time complexity of O(N2), where N=ΣC
FIG. 8 illustrates the optimal schedule for the composite objects in FIG. 7.
Informally, we define a monotonic cover of a composite object Ci as another composite object Ĉi that (a) is monotonic, and (b) completely "covers" Ci at any point in time. More formally:
Definition 1. A monotonic cover for Ci=<(li
Corollary 1 suggests an immediate improvement over the simplistic MBR assumption for scheduling composite multimedia objects: Instead of using the MBR of an object Ci, use a minimal monotonic cover of Ci, that is, a monotonic cover that minimizes the extra volume. List-scheduling the monotonic covers of composite objects (using MLS) is an attractive option because of the following two reasons. First, compared to scheduling the object sequences unchanged, using the covers implies a simpler placement algorithm (a special case of BITONIC-FINDMIN), with reduced time complexity. Second, compared to using MBRs, minimal monotonic covers can significantly reduce the amount of wasted volume in the cover. (Note that a MBR is itself a trivial monotonic cover.) For example, in the case of a bitonic object, a minimal monotonic cover wastes at most half the volume that would be wasted in an MBR cover. Also note that the minimal monotonic cover of a compressed composite object sequence can be easily computed in linear time.
A different way of employing our near-optimality results for list-scheduling in the case of monotonic objects is through the use of the stream sliding techniques described above. The idea is to use extra server memory to turn non-monotonic object sequences into monotonic ones. We now address the problem of efficiently utilizing server memory to make composite object sequences monotonic. More specifically, we concentrate on the use of stream upsliding to convert an object sequence to a non-increasing sequence with minimal extra memory. Our techniques are also applicable to the dual problem (that is, making sequences non-decreasing by stream downsliding). However, as we discussed, downsliding introduces latencies into the schedule and should therefore be avoided. Possible techniques that combine both upsliding and downsliding are left as an open problem for future work.
A straightforward way of making an object sequence non-increasing is to simply upslide all streams with a non-zero lag to the beginning of the composite object. Given an object Ci, this naive approach will obviously require a total memory of
where we define lti
FIG. 9 illustrates a 5-ary composite multimedia object 900. The 5-ary composite multimedia object 900 is composed of CM object streams X1 910, X2 920, X3 930, X4 940, and X5 950. Each of these streams starts at different times and creates a monotonically increasing composite multimedia object 900.
FIG. 10 illustrates a non-increasing composite multimedia object sequence 1000 of the composite multimedia object 900 in FIG. 9 created using naive stream upsliding. In this sequence, we upslide all streams with a non-zero lag (X2 920, X3 930, X4 940, and X5 950) to the beginning of the composite object to create a non-increasing composite multimedia object.
However, we can do significantly better than simple upsliding. The idea is that, depending on the object's structure, it may be possible for some stream to "shield" the starting edge of another stream, without requiring the second stream to be upslided all the way to the beginning of the object. This is depicted graphically in FIG. 11. Note that the use of such clever upsliding methods not only reduces the amount of memory required for making the object monotonic, but it also reduces the maximum bandwidth requirement of the object (that is, rmax(Ci)). This is obviously important since it implies smaller λ's in Theorem 1 and, consequently, better worst-case performance guarantees for LS.
FIG. 11 illustrates a non-increasing composite multimedia object sequence 1100 of the composite multimedia object 900 in FIG. 9 created using clever stream upsliding. In FIG. 11, X2 920 and X3 930 are upslid to the beginning of the composite multimedia object 1100. X4 940, is then upslid so that the starting edge of X4 945 abuts and is shielded by the back edge of X3 935. Similarly, X5 950 is upslid so that the starting edge of X5 955 abuts and is shielded by the back edge of X4 945.
Unfortunately, as the following theorem from M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979 teaches, this problem of optimal (that is, minimum memory) stream upsliding is NP-hard. This result can be proved using the observation that each stream can shield multiple streams to give a reduction from PARTITION.
Theorem 2. Given a composite object sequence Ci, determining an optimal (that is, minimum memory) sequence of stream upslides to make Ci non-increasing is NP-hard.
Given the above intractability result, we now propose a simple heuristic strategy for improving upon the naive "upslide everything" method. Our solution is based on the following definition that simply states the above observations in a more formal manner.
Definition 2. Consider a composite object Ci. We say that stream Xi
The intuition behind Definition 2 can be seen from FIGS. 12(a)-(d). The benefit b(j,k) is exactly the gain in server memory (compared to the naive "upslide everything" solution) by using Xi
Our heuristic method for stream upsliding builds the shield graph SG(CI) for object CI and determines a maximum weighted matching M on SG(CI). Essentially, this matching M is a collection of node-disjoint edges of SG(CI) with a maximum total weight w(M)=Σe
that is, the memory required by the naive approach minus the weight of the matching.
The problem with the stream sliding approach outlined above is that it may often require large amounts of memory per object that the server simply cannot afford. In such cases, we are still faced with the general sequence packing problem. The sequence packing results indicate that using a simple list-scheduling approach for general object sequences can result in arbitrarily bad sequence packings, leading to severe underutilization of the server's bandwidth resources. The main problem of LS is that by making greedy (that is, earliest start time) decisions on the placement of objects at each step, it may end up with very "sparse" sequence packings (that is, schedules with very poor density). This is clearly indicated in the example of FIG. 7. Thus, it appears that a better scheduling rule would be, instead of trying to minimize the start time of the new object in the current schedule, try to maximize the density of the final, combined sequence. However, maximizing density alone also does not suffice. Returning to the example of FIG. 7, it is fairly easy to see that the placement that maximizes the density of the final object is one that simply juxtaposes all the object peaks (that is, it never places one peak on top of another). Since our goal is to minimize the overall schedule length, this is not satisfactory. Instead of trying to maximize density alone, the scheduler should also make sure that the entire bandwidth capacity of the server (that is, height of the bin) is utilized. (Note that using the server's bandwidth capacity instead of rmax to define object density does not help; since the bandwidth is fixed, placing objects to maximize this new density is equivalent to trying to maximize their overlap with the current schedule, that is, the LS rule.)
Therefore, to solve this problem, we propose a novel family of scheduling heuristics for sequence packing, termed list-scheduling with k-object backtracking (LSB(k)). Informally, these new algorithms try to improve upon simple LS by occasional local improvements to the schedule. More specifically, the operation of LSB(k) is as follows. The algorithm schedules objects using simple LS, as long as the incoming objects can be placed in the current schedule without causing the length of the schedule to increase. When placing a new object results in an increase in the makespan, LSB(k) tries to locally improve the density of the schedule and check if this results in a better schedule. This is done in four steps. First, the last k objects scheduled are removed from the current schedule. Second these k object sequences are combined into a single sequence in a manner that tries to maximize the density of the resulting sequence. Third, the "combined" sequence is placed in the schedule using simple LS. Finally, the length of this new schedule is compared to that of the original schedule, and the shorter of the two is retained. The second step in the above procedure can be performed using a slightly modified version of FINDMIN (Table 2). The main idea is to maintain some additional state with each interval of candidate start times (step 1) and update this state accordingly when taking interval intersections (step 2). We term the resulting basic step algorithm FINDMIN-D. Similar modifications can also be defined for the BITONIC-FINDMIN algorithm for bitonic object sequences Co. The complete LSB(k) algorithm is provided in Table 4 below.
Algorithm LSB(k, L).
A list of composite object sequences L = <Cl, . . . , Cn> and a
backtracking parameter k.
A valid packing of the object sequences in L.
Set Tcurr = 0, Cp = φ.
For i = 1 to n do
Schedule Ci at time slot FINDMIN(Ci, Cp).
Let T′curr be the length of the resulting schedule.
If T′curr = Tcurr continue. Else, do the following.
Remove Ci and the k − 1 objects from Cp.
(If k exceeds the number of objects in Cp,
remove all objects from Cp.)
Set C = φ and schedule each object Cj
removed from Cp using FINDMIN − D(Cj,C).
Schedule C over the remainder of Cp using
FINDMIN(Ci,Cp). Let T″curr be the length of the
resulting schedule.
If T′curr ≦ T″curr, set Tcurr = T′curr, restore
the original Cp, and continue with the next Ci. Else,
leave Cp, as is, set Tcurr = T″curr, record that C is
now a single object, and continue with the next Ci.
The extra effort involved in backtracking to improve schedule density translates to increased time complexity for LSB(k) compared to simple LS. Specifically, the complexity of LSB(k) can be shown to be O(|L|�N2) , where |L| is the number of objects to be scheduled and N is the total number of component streams. This, of course, is assuming general object sequences that cannot employ the more efficient basic step algorithms.
FIGS. 12(a)-12(b) show the operation of the LSB(k) algorithm, where k=3, on our "bad" example for LS shown in FIG. 7. FIG. 12(a) illustrates the first backtracking point in the operation of the list-scheduling with k-object backtracking LSB(k) algorithm. More specifically, FIG. 12(a) shows the schedule after the placement of the fifth object 1210, at which point the algorithm is first forced to backtrack, trying to locally improve schedule density.
FIG. 12(b) illustrates the results of the LSB(k) algorithm on the composite multimedia object schedule in FIG. 12(a). The result of the improved density packing (after using FINDMIN-D to combine the last three objects) is depicted in FIG. 12(b). Since this schedule is shorter than the one in FIG. 12(a), it is retained and LSB(3) goes back to using LS.
FIG. 12(c) illustrates the schedule after the LS algorithm places the sixth and seventh composite multimedia objects in the schedule in FIG. 12(b). FIG. 9(c) shows the schedule after LS places the sixth and seventh objects, 1220 and 1230 respectively.
FIG. 12(d) illustrates the final schedule after the LS algorithm places the eighth and ninth composite multimedia objects, 1240 and 1250 respectively, in the schedule in FIG. 12(c). FIG. 12(d) shows the final schedule obtained by LSB(3), which is in fact the optimal schedule. Further, note that LSB(3) had to backtrack only once during the whole scheduling process.
Until now, we have implicitly assumed that the composite multimedia objects to be scheduled are disjoint, in the sense that their component streams correspond to different data objects in the underlying repository. However, it is quite possible for distinct composite objects to have one or more components in common. Examples of such non-disjoint composite objects range from simple movie presentations, where the same video needs to be displayed with different soundtracks (e.g., in different languages), to complex news stories authored by different users, that can share a number of daily event clips.
In the presence of such common components, it is possible that exploiting stream sharing can lead to better schedules. The basic idea of "stream sharing" is that by appropriately scheduling non-disjoint composite objects, the streams delivering their common component(s) can be shared by all the composite object presentations. Clearly, stream sharing can reduce the aggregate resource requirements of a set of non-disjoint objects and it is easy to construct examples for which exploiting stream sharing can drastically improve the response time of a presentation schedule. On the other hand, stream sharing possibilities also increase the complexity of the relevant scheduling problems. Even simple cases of the problem (e.g., when all streams and composite objects are of unit length) give rise to hard scheduling problems that, to the best of our knowledge, have not been addressed in the scheduling literature. The problem becomes even more challenging when extra memory is available, since stream sliding and caching techniques can be used to increase the possibilities for stream sharing across composite objects. Finally, note that our stream sharing problem also appears to be related to the problem of exploiting common subexpressions during the simultaneous optimization of multiple queries. However, the use of a schedule makespan optimization metric (instead of total plan cost) makes our problem significantly harder to formulate and solve.
What has been described is merely illustrative of the application of the principles of the present invention. All United States patents and articles cited herein should be deemed to be incorporated by reference as to their entire contents in the event one of ordinary skill in the art wishes to obtain a more thorough understanding of the subject matter of the present invention. Other arrangements and methods can be implemented by those skilled in the art without departing from the spirit and scope of the present invention and the invention should only be deemed to be limited by the scope of the claims that follow.
|Cited Patent
|Filing date
|Publication date
|Sep 6, 1995
|Dec 2, 1997
|Starguide Digital Networks, Inc.
|Method and apparatus for electronic distribution of digital multi-media information
|Mar 15, 1995
|Mar 31, 1998
|The Chinese University Of Hong Kong
|Method for compression of loss-tolerant video image data from multiple sources
|Feb 1, 1996
|May 19, 1998
|Digital Equipment Corporation
|Apparatus and method for interleaving timed program data with secondary data
|Nov 30, 1994
|Aug 11, 1998
|Realnetworks, Inc.
|Audio-on-demand communication system
|Jun 27, 1997
|Dec 1, 1998
|Lucent Technologies Inc.
|Scheduling resources for continuous media databases
|May 10, 1996
|Nov 30, 1999
|Learn2.Com, Inc.
|System and method for streaming multimedia data
|Dec 14, 1995
|Mar 28, 2000
|Time Warner Cable, A Division Of Time Warner Entertainment Company, L.P.
|Method and apparatus for utilizing the available bit rate in a constrained variable bit rate channel
|Mar 21, 1997
|Apr 18, 2000
|Scientific-Atlanta, Inc.
|Using a receiver model to multiplex variable-rate bit streams having timing constraints
|Nov 20, 1997
|Apr 17, 2001
|International Business Machines Corporation
|Method and apparatus for delivering multimedia content based on network connections
|Oct 27, 1998
|Aug 7, 2001
|Kencast, Inc.
|Method and system for reliable broadcasting of data files and streams
|Nov 7, 1997
|Dec 11, 2001
|Lucent Technologies, Inc.
|Admission control system and method for media-on-demand servers
|Jan 14, 1998
|Feb 26, 2002
|Skystream Networks Inc.
|Brandwidth optimization of video program bearing transport streams
|Amihood Amir et al., Chapter 24, Efficient 2-dimensional Approximate Matching of Non-rectangular Figures, In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, California, Jan. 1991, pp. 212-223.
|Banu Ozden et al., A Framework For the Storage And Retrieval Of Continuous Media Data, In Proceedings of the 1995 International Conference on Multimedia Computing and Systems, Wshington, D.C., May 1995, pp. 2-13.
|Banu Ozden et al., A Low-Cost Storage Server For Movie On-Demand Databases, In Proceedings of the 20th International Conference on VLDB, Sep. 1994, pp. 1-12.
|Brenda S. Baker et al., Orthogonal Packings in Two Dimensions, Siam J. Comput, vol. 9, No. 4, Nov. 1980, pp. 846-855.
|Brenda S. Baker et al., Shelf Algorithms For Two-Dimensional Packing Problems, Siam J. Comput. vol. 12, No. 3, Aug. 1993, pp. 508-525.
|Cyrus Shahabi et al., On Scheduling Atomic And Composite Multimedia Objects, Technical Report USC-CS-95-622, University of Southern California, 1995, pp. 1-35.
|E. G. Coffman, Jr., et al., Performance Bounds For Level-Oriented Two-Dimensional Packing Algorithms Siam J.Comput, vol. 9, No. 4, Nov. 1980, pp. 808-826.
|Heiko Thimm et al., delta-Sets For Optimized Reactive Adaptive Playout Management in Distributed Multimedia Database Systems, In Proceedings of the Twelfth International Conference on Data Engineering, New Orleans, Louisiana, Feb. 1996, pp. 1-9.
|Heiko Thimm et al., δ-Sets For Optimized Reactive Adaptive Playout Management in Distributed Multimedia Database Systems, In Proceedings of the Twelfth International Conference on Data Engineering, New Orleans, Louisiana, Feb. 1996, pp. 1-9.
|John Turek et al., Approximate Algorithms For Scheduling Parallelizable Tasks, SPAA 1992, pp. 323-332.
|John Turek, et al., Scheduling Parallelizable Tasks to Minimize Average Response Time, SPAA 1994. Cape May, New Jersey, pp. 200-209.
|K. Selcuk Candan et al., Retrieval Schedules Based on Resource Availability And Flexible Presentation Specifications, Technical Report CS-TR-3616, University of Maryland, College Park, 1996, pp. 1-30.
|Leslie A. Hall et al., Scheduling To Minimize Average Completion Time: Off-line and On-line Approximation Algorithms, May 1996, revised Mar. 1997, pp. 1-32.
|M. R. Garey et al., Bounds For Multiprocessor Scheduling With Resource Constraints, Siam J. Comput, vol. 4, No. 2, Jun. 1975, pp. 187-200.
|M. R. Garey et al., Resource Constrained Scheduling As Generalized Bin Packing, Journal Of Combinatorial Theory (A) 21, 1976, pp. 257-298.
|Minos N. Garofalakis et al., Parallel Query Scheduling And Optimization With Time -and Space-Shared Resources, Proceedings of the 23rd VLDB Conference, Athens, Greece, Aug. 1997, pp. 296-305.
|Roger Price, MHEG: An Introduction To The Future International Standard For Hypermedia Object Interchange, In Proceedings of ACM Multimedia '93, Anaheim, California, Aug. 1993, pp. 121-128.
|Soumen Chakrabarti et al., Improved Scheduling Algorithms For Minsum Criteria, In Proceedings of the 23rd International Coloquium on Automata, Languages, and Programming (ICALP '96), Paderborn, Germany, Jul. 1996 pp. 646-657.
|Soumen Chakrabarti et al., Resource Scheduling For Parallel Database And Scientific Applications, SPAA 1996, Padua, Italy, pp. 329-335.
|Surajit Chaudhuri et al., Avoiding Retrieval Contention For Composite Multimedia Objects, Proceedings of the 21st VLDB Conference, Zurich, Switzerland, 1995, pp. 287-298.
|Citing Patent
|Filing date
|Publication date
|Jul 31, 2002
|Aug 23, 2005
|Nilanjan Mukherjee
|Scheduling the concurrent testing of multiple cores embedded in an integrated circuit
|Apr 12, 2002
|Dec 5, 2006
|Microsoft Corporation
|File server system and method for scheduling data streams according to a distributed scheduling policy
|Mar 5, 2003
|Jan 29, 2008
|The Board Of Trustees Of The Leland Stanford Junior University
|Adaptive playout scheduling for multimedia communication
|Dec 3, 2003
|May 13, 2008
|International Business Machines Corporation
|Channel merging method for VOD system
|Mar 6, 2000
|Jun 3, 2008
|Mitsubishi Electric Research Laboratories
|Method for representing and comparing multimedia content according to rank
|May 9, 2003
|Nov 11, 2008
|Fujitsu Limited
|Data compression program, data compression method, and data compression device
|Dec 17, 2004
|Mar 24, 2009
|International Business Machines Corporation
|Workload periodcity analyzer for autonomic database components
|Oct 25, 2007
|Mar 2, 2010
|International Business Machines Corporation
|Channel merging method for VOD system
|Mar 31, 2000
|May 25, 2010
|Avid Technology, Inc.
|Authoring system for combining temporal and nontemporal digital media
|Mar 2, 2000
|Aug 31, 2010
|Qwest Communications International Inc.
|System and method for automated download of multimedia files
|Oct 26, 2010
|Coppergate Communications Ltd.
|Maximal resource utilization in networks
|Dec 19, 2008
|Aug 23, 2011
|International Business Machines Corporation
|Workload periodicity analyzer for autonomic database components
|Jul 17, 2012
|Advanced Simulation Technology, Inc.
|Processing data using continuous processing task and binary routine
|Dec 19, 2008
|May 10, 2016
|Velocee Ltd.
|Optimizing content and communication in multiaccess mobile device exhibiting communication functionalities responsive of tempo spatial parameters
|Apr 12, 2002
|Oct 3, 2002
|Microsoft Corporation
|File server system and method for scheduling data streams according to a distributed scheduling policy
|Jul 31, 2002
|Oct 9, 2003
|Nilanjan Mukherjee
|Scheduling the concurrent testing of multiple cores embedded in an integrated circuit
|May 9, 2003
|Dec 4, 2003
|Fujitsu Limited
|Data compression program, data compression method, and data compression device
|Dec 3, 2003
|Sep 2, 2004
|International Business Machines Corporation
|Channel merging method for VOD system
|Jul 14, 2004
|Jan 19, 2006
|Ron Sterenson
|Maximal resource utilization in networks
|Dec 17, 2004
|Jun 22, 2006
|International Business Machines Corporation
|Workload periodicity analyzer for autonomic database components
|Oct 25, 2007
|Feb 28, 2008
|Pei Yun Z
|Channel merging method for vod system
|Aug 23, 2007
|Jul 24, 2008
|Sporny Manushantha Manu
|Computer System and Method For Processing Data Using Continuous Processing Task
|Dec 19, 2008
|Apr 23, 2009
|International Business Machines Corporation
|Workload periodicity analyzer for autonomic database components
|Dec 19, 2008
|Jun 24, 2010
|David Haas
|Optimizing content and communication in multiaccess mobile device exhibiting communication functionalities responsive of tempo spatial parameters
|Sep 1, 2011
|Comcast Cable Communications, LLC.
|Program Segmentation of Linear Transmission
|Apr 25, 2014
|Oct 29, 2015
|Qualcomm Incorporated
|Determining whether to use sidx information when streaming media data
|U.S. Classification
|709/247, 709/232, 709/233, 709/231
|International Classification
|Cooperative Classification
|European Classification
|Oct 29, 1998
Owner name: LUCENT TECHNOLOGIES INC., NEW JERSEY
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:GAROFALAKIS, MINOS N.;IOANNIDIS, YANNIS E.;OZDEN, BANU;REEL/FRAME:009561/0475;SIGNING DATES FROM 19981013 TO 19981021
|Jun 8, 2007
|Fee payment
Year of fee payment: 4
|Jun 9, 2011
|Fee payment
Year of fee payment: 8
|Jul 24, 2015
|Maintenance fee reminder mailed
|Dec 16, 2015
|Lapse for failure to pay maintenance fees
|Feb 2, 2016
|Expired due to failure to pay maintenance fee
Effective date: 20151216


text:
Scrooge & Marley
|No Rating
|Drama, Family
|Release Date:
|November 21, 2012
|David Pevsner, Tim Kazurinsky, Rusty Schwimmer, Bruce Vilanch, Megan Cavanagh
|Richard Knight Jr., Peter Neville
|Richard Knight Jr., Peter Neville, Ellen Stoneking, Ronnie Kroell
|Ellen Stoneking, Richard Knight Jr.
|Independent Pictures
Web Site: http://www.scroogeandmarleymovie.com/Scrooge_%26_Marley/HOME.html
Description: A modern day variation on Charles Dickens' classic story of the holidays, "A Christmas Carol." On Christmas Eve, Ben Scrooge, the man who hates the holidays, is given the chance to begin again when he is visited by three spirits - the Ghosts of Christmas Past, Present and Future. Revisiting the tragic missteps of his life enables Scrooge to rediscover the joy of the holiday season and make a journey back to love. Recounted from a gay sensibility with heart, comedy and music, the magic of Dickens' timeless tale comes alive from a fresh perspective that will appeal to audiences of all persuasions.
Movie summaries and listings powered by Cinema-Source

subset: commoncrawl


text:
Burnout Paradise: Party
Share your Burnout experiences with your friends as you gather around the TV for this new multi-player game mode. Compete against up to 7 friends as you try to showcase your skills across multiple challenges featuring all of your favourite Burnout cars and locations. For this game addition to work you need to ensure your copy of Burnout Paradise is updated to the latest version. (Burnout Paradise 1.6)
If you're stuck in Burnout Paradise: Party, ask your fellow GameFAQs members for help.
Game List Statistics
Now Playing
0 Users
Wish List
1 Users
Hot List
0 Users


text:
OSI-Approved Open Source (294)
- GNU General Public License version 2.0 (188)
- GNU Library or Lesser General Public License version 2.0 (35)
- BSD License (32)
- Apache Software License (16)
- Apache License V2.0 (11)
- MIT License (10)
- GNU Library or Lesser General Public License version 3.0 (6)
- Mozilla Public License 1.1 (5)
- Open Software License 3.0 (5)
- Academic Free License (4)
- Artistic License (4)
- GNU General Public License version 3.0 (4)
- PHP License (4)
- Common Public License 1.0 (3)
- Mozilla Public License 1.0 (3)
- Public Domain (13)
- Other License (11)
- Creative Commons Attribution License (4)
- Grouping and Descriptive Categories (322)
- Windows (322)
- Linux (172)
- Modern (154)
- Mac (79)
- Other Operating Systems (31)
HTTP Servers Software
- OS: All 32-bit MS Windows (95/98/NT/2000/XP) ×
microCODE is a PHP module that allows inclusion of encrypted PHP sourcecode instead of plain PHP scripts. Protect your intellectual property using standard encryption algorithms like DES or AES.4 weekly downloads
NIA PHP ASP Encoder
NIA Encoder. The objective of this project is to provide a full featured multi-platform php and asp script encoder. It´s to protect your source code when creating commercial software with asp or php language.
Pi3Web is a multithreaded, highly configurable multiple platform HTTP 1.0/1.1 web server written in C++. Pi3Web 2.0 supports among other things CGI, FCGI, Win-CGI, SSI, directory indexing, SSL, embedded perl, PHP4, Servlets, JSP and XSLT.1 weekly downloads
FoxServ Win32 & Linux Edition
FoxServ is an Apache / mySQL / PHP installer package for Windows and Linux. Unlike NuShpere or PHPTriad, FoxServ features the latest version of all included pacakges, user defined configuration during installation, PHP as a module, PEAR, and the Zend Opt12 weekly downloads
SiteMesh is filter plugin for web-servers that provides presentation and web-app application integration. It is easy to use and requires no modification to existing code (HTML, CGI, PHP, etc).
Soma Web Server
Soma is a powerful, multi-threaded, HTTP 1.1-compliant Web server written in Java. It features an advanced, modular design, CGI support, built-in scripting support (currently Python only), and is under constant development.1 weekly downloads
Slashthemes is a skin and themes repository for the phpslash project. Yet another stuff themes.org doesn't do...1 weekly downloads
Ranquel webserver
Ranquel is a lightweight http server written in Perl that can serve static files and execute CGI applications. Originally based on DNHTTPD, the main goal is to make a simple, portable and minimum webserver (no extra Perl modules, no SSI, no SSL).1 weekly downloads
Wheat is a language and environment for creating dynamic web sites like blogs and portals: Every object has a URI, the virtual machine is a web server, and the development environment is a Wiki!1 weekly downloads
Restaurant Order System
Restaurant Order System This is a restaurant order system based J2EE framework. Our object is transfer order information between restaurant and client. We do not plan implementing all business in restaurant. It is agility, can cooperate with in existen
The Embedded Web Server is designed for use in embedded systems with limited resources (eg, no disk). It supports both static (converted from a standard web tree, including graphics and Java class files) and dynamic pages. It is written in GCC Ada. The software is issued under the GPL Version 3 with the additional permissions granted by the GCC Runtime Library Exception version 3.1.6 weekly downloads
Anastasia is a SGML/XML publication tool which allows the processing and searching of large documents using tcl scripting.1 weekly downloads
Do you want to install Apache, PHP and MySQL on your windows-box? And you don`t like to read? It`s for you. Поставить Apache, PHP и MySQL на windows? Чтение — зло? Вам сюда!1 weekly downloads
Oxide WebServer
Oxide is an opensource webserver, currently written in Visual Basic 6. It will work under most versions of Windows. We are considering converting it to C++ when it is finished so that it will run on *nix as well as Windows.1 weekly downloads
PSOProxy is a web server application designed to work with the Gamecube web browser. Its main purpose is to allow Phantasy Star Online snapshot files to be copied to a PC and converted to a common image file format.15 weekly downloads
Jaxmao 是基于开源Tomcat的JSP/Servlet服务器。多年的开发使Tomcat已越来越完善,被越来越多的网站采用。Jaxmao(中文版Tomcat)项目的任务是开发一个中文界面,推广JSP/Serlet 在中文开发者中的使用。1 weekly downloads
A C++ multi-threaded application for viewing network IP cameras, and other video device supported by v4l2. It uses TrollTech QT, V4L2 and HTTP protocol.
A multi-platform .htaccess file management system for the Apache web server software which enables the user to administer both .htaccess and .htpasswd files to setup password protected directories and to add and remove users.8 weekly downloads
Local web server for PHP, Node.js, MongoDB, MySQL developers1 weekly downloads
FusionLeaf is a powerful website and web server package.4 weekly downloads
Embedded C/C++ Web Server73 weekly downloads
acWEB - HTTP server for Win32
acWEB is an OpenSource replacement for MS IIS and other proprietary WEB servers for Windows. Unlike IIS, acWEB is not affected by viruses like CodeRed, Nimda, etc :).1 weekly downloads
Savant Web Server
Savant is a full-featured open source web server for computers running any version of Windows 95/NT or greater. It's fast, secure, and easy-to-use.113 weekly downloads
ac Free Proxy Server for Win32
Free Proxy Server for Win32 - supports HTTP, HTTPS, FTP protocols and TCP-mapping7 weekly downloads


text:
Definición de closed book en inglés:
closed book
A subject or person about which one knows nothing: accounting has always been a closed book to me
Más ejemplos en oraciones
- The political parties are closed books as far as the majority is concerned.
- She explained: 'I still think to this day that there is more to it than what came out but you are dealing with the army and it is a closed book.'
- I don't like it, and though I don't consider myself a public person, there is no aspect of my life that is a closed book.
Definición de closed book en:
¿Qué te llama la atención de esta palabra o frase?
Los comentarios que no respeten nuestras Normas comunitarias podrían ser moderados o eliminados.
Muy popular en Reino Unido
Muy popular en Australia
= de moda


text:
King Room - One king bed. Sofa. Internet. TV. AC. Bath with tub/shower. Handicap facilities on request. In room movies for a fee. Refrigerator on request for a fee.
Description not provided
Double Bed Room - two double beds. One overstuffed chair. Internet. TV. AC. Bath with tub and shower. Refrigerator on request for a fee.
1 Bedroom Suite - Living room. One king bed. Full sofa bed. Two TV. Wet bar. Refrigerator. Internet. AC. Bath with tub/shower. In room movies. Seating area.
City Center
Ebbets Field
Sports themed bar and grill.
Gilardis Restaurant
Nicola Gilardi began his career in the culinary arts at the family s restaurant in Italy. Upon learning the importance of a strong work ethic he decided to pursue his dream of owning his own restaurant. He was accepted to Crotto Caurga I Pas a culinary school in Italy. After completion of his train
Downtown Springfields premier business and social club The award-winning Tower Club is located on the 21st and 22nd floor of The Hammons Tower in the heart of the downtown business and entertainment district. The Tower Club offers Members and guests a remarkable view of the entire city of Springfield- se
Rates quoted in currencies other than hotel's base currency are subject to the rate of international exchange.Rates may change throughout the stay. Rate may reflect average nighly rate. Extra charges may apply for children. Incidental charges, such as room service, are not included in the rate.
The ameneties and/or facilities may not be located at this hotel. but within a reasonable distance and additional charges may apply for use. All information has been provided by this hotel.


text:
You are currently signed in as .
0 Items in Your Cart
Vault Guides are THE source for insider insight on career information and employer reviews. Shop Vault Guides
Three First National PlazaSuite 4100
Chicago, IL 60602
Phone: (312) 558-6600
Fax: (312) 558-6538
Complete your Vault Profile and get seen by top employers


text:
Elizabeth RiceMay 27,2013Elizabeth Rice
The graveside service for Elizabeth Betty Rice, 77, of Rutland, who died Dec. 30, 2012, will be held at 10 a.m. Thursday, May 30, 2013, in Calvary Cemetery and officiated by the Rev. Claire Longtin.
Arrangements are under the direction of the Clifford Funeral Home in Rutland.MORE IN ObituariesWillis R. Full StoryMartha A. Weeks
BENNINGTON A memorial service for Martha A. Full StoryElinor Crossman rites
Funeral services for Elinor Marcella Heslin Crossman, 94, of... Full Story
- Most Popular
- Most Emailed


text:
Im trying to install Arch Linux on Windows 98, the computer has the spec to run it. I brought the a disc with Arch Linux on and when I insert the disc nothing happens, I opened the disc and none of the files will open.
Sorry as its properly a stupid question but im not that good with computers:confused:.


text:
This promoted post is an advertisement generated with our self-serve advertisement tool.
Use of this tool is open to all members of reddit.com, and for as little as $5.00 you can advertise in this area. Get started ›
This is a new ad format that we are currently testing. We often try new types of ads in a limited capacity. If you have feedback, please let us know in the ads subreddit.
This area shows new and upcoming links. Vote on links here to help them become popular, and click the forwards and backwards buttons to view more.
Enter a keyword or topic to discover new subreddits around your interests. Be specific!
You can access this tool at any time on the /subreddits/ page.
submitted by furious_bobcat to /r/Parley
new kde edu site launched (edu.kde.org)
submitted by nsaibot to /r/linux
new kde edu site launched (edu.kde.org)
submitted by nsaibot to /r/kde
Virtual Globe and World Atlas (edu.kde.org)
submitted by based2 to /r/opensource
Parley is a program to help you memorize things. (edu.kde.org)
submitted by DocHollidaysMustache to /r/linux


text:
2008 Summer Reading Challenge ~ a few pictures of the some of the prizes.
Due to the ceiling failure, we are unable to properly display the many terrific 2008 Young Adult/Adult Summer Reading Challenge Raffle Prizes. Please keep track of your completed challenges, stop by and visit us in our temporary location (the Children's Activity Room in the lower level of the Clapp Memorial Library) and fill out your earned raffle tickets!
Jul 14, 2008
Photos: 8
Pigout 2008: The Big Smooch!
Farmer Minor and Daisy help kick-off the Clapp Memorial Library's Summer Reading Program~
Wild Reads @ Your Library
May 28, 2008
Photos: 75
Profile Photos
Album for profile photos
Dec 13, 2004
Photos: 1


text:
Is it possible to have separate registration forms on a multisite setup--one for users across the network, and another for those setting up their own site?
The way the registration form for the people wanting to setup the site could automatically populate a template page on the new site. I am new to multisite, so help is sincerely appreciated


text:
Melissa ForstromMuseums. They are great. From Museum of Mathematics to Museum of Glass, there's so much to see and to learn about these topics in our shared history. Whenever I visit a new town or country, I am always eager to check out their local or national museums; they offer a glimpse of their cultural histories, identities and accomplishments.
However, some exhibitions can also showcase contested and controversial materials. Take for example the
Chat with a librarian now


text:
62 honored at USDA headquarters for their efforts in Iraq and Afghanistan
WASHINGTON, June 12, 2012 – Agriculture Secretary Tom Vilsack recently recognized the efforts of 62 U.S. Department of Agriculture (USDA) employees who have helped revitalize the agricultural sectors in Afghanistan and Iraq. Among those honored during a ceremony June 4 was James F. Helm of Fairbanks, Alaska, who served as a senior agricultural advisor in Diyala Province, Iraq, from 2009 to 2011.
"I'm honored to recognize these brave and devoted men and women for their tremendous service to the people of Afghanistan and Iraq," said Vilsack. "These USDA employees have played a vital role in furthering political and social stability throughout the world by building a foundation on which the economies of these countries will prosper."
USDA agricultural advisors began serving in Afghanistan in 2003 and Iraq in 2006. Their goal has been to help Afghanistan and Iraq rebuild their agricultural sectors by planning and implementing reconstruction and agricultural development projects. Activities vary depending on the needs of the area, but can range from mentoring local agricultural officials to improving food and animal production and marketing systems to veterinary infrastructure, soil and water conservation, and reclamation programs. Advisors working at the national government level help build the capacity of government ministries and collaborate with ministry staff to develop long-term strategies for agricultural development.
In Iraq, Helm helped develop a plan to assist internally displaced persons. This plan created jobs and promoted reconciliation among religious sects. He also helped establish a poultry farmers association and develop a business plan for a $2-million U.S. Agency for International Development grant. This project helped reduce the cost of feed by consolidating orders and developing economies of scale, which improved feed quality and poultry health. Helm is a retired resource conservationist with USDA's Natural Resources Conservation Service in Fairbanks, Alaska. He received his Bachelor of Science degrees in resource development and crop and soils science from Michigan State University, East Lansing, Mich.
Since 2003, more than 250 USDA personnel have deployed to Afghanistan and Iraq. More than 50 agricultural advisors are currently assigned there.
To learn more about USDA's efforts in those countries, visit
Contact: Linda Habenstreit (202) 720-9442
USDA is an equal opportunity provider and employer. To file a complaint of discrimination, write: USDA, Office of the Assistant Secretary for Civil Rights, Office of Adjudication, 1400 Independence Ave., SW, Washington, DC 20250-9410 or call (866) 632-9992 (Toll-free Customer Service), (800) 877-8339 (Local or Federal relay), (866) 377-8642 (Relay voice users).


text:
We found 1 that has recently dropped in price.
Sign up to see this price drop and to receive future price drop notifications.
Total Reviews
Write a
Sort by
1990 Toyota Camry LE V6 4dr Wagon
I'm at the point where I have to decide if it's time to let go and the truth is I just don't want to! I can't even find a kbb value for a 1990, but mine still looks pretty good and only has 140,000. miles. It needs a little work now, but for 6 years I didn't put a drop of money into her, except oil changes.I was the second owner.
smooth ride. I've been test driving cars that are ten years older and I still prefer how mine feels. I drive a v-6
it's old so of course it's not the prettiest of cars!
I bought this car from the original owner who took great care of it about 6 weeks ago. I have to say this is the best used car I have ever bought. I can't believe this car is 16 years old. I have owned newer cars that were not as "modern" as this feels. Solid as the day it was built. With only 130,000 miles it's still got a LOT of life left in it. It runs like new, looks great. Everything about the feel of this car is great.
Gas mileage could be better.
I bought this car brand new in 1990. The
car lasted forever without ever having
anything wrong with it. I had 168,000
miles on the car when i slid off the
road into a tree. I was doing about 30
and no injurys except a minor bruise.
The car only had one problem. the ac
went @ 140,000 on it. The car is
comfortable and was drivin from ny to
florida a bunch of times and was great.
miss the car alot and wish toyota
brought back the camry wagon.
Comfort, Excellent reliablity, velvet
like seats, power from the 156HP V-6.
Not a thing. The car was made absolutely
perfect. If you liked camry wagons, buy
a highlander. that what i did and its
just like it. great on gas for an suv,
reliable, and safe
It's now December 2003 and I am proud
to say my Camry just passed the 217,000
mileage marker and she still runs
I purchased a 1990 Toyota Camry LE
Wagon in 1990. I just sold it and it
was the best car I ever had. No
trouble no crashes nothing. I drive to
New York and back everyday and it never
gave up on me. When I finally sold it,
it had 240,000 miles on it. It was sad
to let it go but I bought a new car.
The way it held on for so long.
Help |
About Us |
Contact Us |
Careers |
Affiliate Program |
Dealer Center |
Privacy Statement |
Visitor Agreement |
Membership Agreement
Your Ad Choices
| Site Map
| Glossary
| Mobile
| Developers
Follow Edmunds
© Edmunds.com, Inc.


text:
Definición de enforce en inglés:
verbo[with object]
1Compel observance of or compliance with (a law, rule, or obligation): the role of the police is to enforce the law
Más ejemplos en oraciones
- Damages were being sought for compensation as a result of the council's negligent advice and not primarily to enforce a public law right.
- And how the Supreme Court decides them will be a telling indicator of its commitment to enforcing the rule of law.
- The letter then went on to give instances in which the government authorities enforced the rule of law.
impose, apply, carry out, administer, implement, bring to bear, discharge, fulfil, execute, prosecute
rare effectuate
force, compel, exact, extort, demand, insist on, require, necessitate
archaic constrain
1.1Cause (something) to happen by necessity or force: there is no outside agency to enforce cooperation between the players
Más ejemplos en oraciones
- It's been a force for enforcing peace.
- The teenager's death prompted Stanwell residents to join forces to try to enforce a new traffic calming scheme in Long Lane.
- The good news is that most political forces are willing to enforce the changes.
compulsory, obligatory, mandatory, involuntary, forced, exacted, coerced, imposed, demanded, required, requisite, stipulated, contractual, binding, necessitated, necessary, unavoidable, inescapable, obliged, impelled, constrained, dictated, ordained, prescribed;
French de rigueur
1.2 archaic Press home (a demand or argument): my father spoke like a preacher enforcing a precept of religion
Más ejemplos en oraciones
- The argument only enforced his strong will and I knew he hated me.
- Nor is it just a question of enforcing one demand.
- He enforced his argument by adding details.
Middle English (in the senses 'strive' and 'impel by force'; formerly also as inforce): from Old French enforcir, enforcier, based on Latin in- 'in' + fortis 'strong'.
Palabras que riman con enforcecoarse, corse, course, divorce, endorse (US indorse), force, gorse, hoarse, horse, morse, Norse, perforce, reinforce, sauce, source, torse
For editors and proofreaders
Saltos de línea: en|force
Definición de enforce en:
¿Qué te llama la atención de esta palabra o frase?
Los comentarios que no respeten nuestras Normas comunitarias podrían ser moderados o eliminados.
Muy popular en Reino Unido
Muy popular en Australia
= de moda


text:
Get Everything for the Renaissance Italian Nobleman in One Discounted Package!
Get all the patterns you need to make yourself a Renaissance Italian Nobleman's outfit! We've made it easy for you with this Reconstructing History Pattern Package. The package includes all the patterns needed to make a full outfit for a noble man living in Italy in the 1570s through 1600.
- Package includes:
- RH001 -- Cloth Hose
- RH104 -- 1600s Shirts and Shifts
- RH205 -- 1570s-1600 Doublet
- RH206 -- 1570s-1600 Trunkhose
A $95.00 Value for $85.00!
Let us help you!
At Reconstructing History, we want to see you wearing the best garments you are capable of making. Email us anytime at email@example.com and we will answer any questions you might have!
No posts found


text:
On this day: June 20
POSTED: 5:25 PM Jun 18 2013 UPDATED: 1:00 AM Jun 20 2016
Text Size:
Lizzie Borden is acquitted of giving her mother "40 whacks," the U.S. Army Air Force is formed, the "red telephone" hotline is established, "Leave it to Beaver" airs its final episode, and "Jaws" has moviegoers reconsidering their beach vacations, all on this day.
The views expressed are not those of this site, this station or its affiliated companies. By posting your comments you agree to accept our terms of use, which are located at the bottom of this page.


text:
High school football: Wide-open race expected in Region 2 this season
Jeffrey D. Allred, Deseret News
The scoreboard never lies, and it told some sad tales for Region 2 teams last season
Even though Taylorsville's resurgence was one of the most captivating stories of the entire 2014 high school football season, collectively the region got punched in the gut once the playoffs rolled around.
The first-round massacres included four blowouts that were out of hand by halftime. Taylorsville lost to Alta 49-21, Hunter lost to Jordan 56-28, West lost to Bingham 41-10, and Cottonwood lost to Brighton 42-15.
There were similar lopsided results in the preseason too, with Region 2 schools getting clobbered by 5A elites like Davis, Bingham and Brighton.
When it was all said and done, Region 2 teams were outscored by an average of four touchdowns.
Who knows if anything will change in 2014, but one thing is for certain, the race for the region title could be wide open.
Region co-champion Taylorsville was extremely senior-heavy and faces an almost certain rebuilding year. Conversely, fellow co-champion Hunter returns a boatload of experience and should be vastly improved this year, while Cottonwood also expects to be better with an outstanding defensive line.
"Last year, we just came up short in some areas, but this year I think we've got a lot better leadership," said Hunter coach Scott Henderson. "I think we've got a greater nucleus; we were really young last year. The seniors in charge are stepping up and leading by example, but they're also being vocal leaders, and the biggest thing is they're being responsible."
For Taylorsville coach Rod Wells, this is his third year in charge of the program, and he hopes that continuity starts to make a difference on Friday nights.
"The things the staff's been able to accomplish in a short time has helped us to move into that next phase where eventually we hope we'll be like the Binghams and the Rivertons and the Davises that don't rebuild, they reload," said Wells. "This building process we're going through eventually we won't have to talk about rebuilding. Maybe we can talk about just reloading ourselves. That's the goal."
Cottonwood is the X-factor in this region. One through 11, coach Greg Croshaw believes he has one of the best defenses in 5A led by Colorado-bound T.J. Fehoko. The depth, however, drops off quickly.
"That's been the key since I've been here," he said. "When you don't have the depth, it goes downhill in a hurry. I don't know how you avoid injuries. It's part of the game, but that's what you gotta hope for, is to have some luck there and keep them healthy, and if we're healthy we can play with anybody."
West finished fourth in Region 2 last season, beating Granger and Taylorsville the last two weeks to qualify for the playoffs. Even though Bingham quickly sent the Panthers packing, the handful of returning starters have tried to build on the positives from those October wins over Granger and Taylorsville.
Granger and Hillcrest both have new head coaches after missing the playoffs a year ago, but neither believes past failures at their programs predicts future failures.
"Our goals and expectations are to get better. We hear that all the time. Everybody has expectations; I read all these things all the time," said Granger coach Mike Morgan. "We want to take pride in being physical, in representing this community and being tough young men. But it comes down to taking pride in being physical."
Morgan coached at West Jordan from 1999 to 2012 before taking last season off.
CONTRIBUTING: Ryan Love and Ryan McDonald.
Deseret News projections for Region 2 football teams in 2014


text:
From €135 pps
From €309 pps
From €199 pps
€80 per person
From €150 pps
From €100 per night
From €89pps
From €337,50 pps
From €422 pps
From €35 pps
From €279 pps
From €412 pps
From €475 pps
From €89 pps
From €438 pps
From €95 pps
From €190 pps
From €92.50 pps
From €232 pps
From €75 pps
From €1,140 per stay
From €120 pps
From €1,539 pps
Can we help you with anything else? Find out how to get in touch by email, Facebook and more.
For more information on travel, accommodation and attractions have a look at our brochures and maps.
If you're a visitor from the island of Ireland you may want to visit one of these sites… Otherwise proceed to Ireland.com
Ireland.com uses cookies to ensure that we give you the best experience on our website. If you continue without changing your settings, we'll assume that you are happy to receive all cookies from Ireland.com.


text:
Top Definition
A pandemic malady afflicting most anyone who uses hardware, software, and an operating system together. Add a network operating system or proprietary Internet connection software, and you have an acute case on your hands.
Abbreviation: DCS
Abbreviation: DCS
Ever since I installed SP2, this blasted PC exhibits DCS by lipping off, (see lip off}, at me about the stupidest things instead of doing the task I gave it.
by Downstrike September 13, 2004
Trending Now


text:
Hi There, lovely plug in! Thank you!
I am trying to use it and so far its been successfully. My problem is that when i tried testing it, the paypal landing page that came up was the "donations" one. Do you have any idea on how I can update the code so the standard payment one comes up?
Your help is greatly appreciated.


text:
Posts Tagged 'duncan fegredo'
C2E2 2013: Dark Horse Comics Announces Duncan Fegredo's Return to Hellboy in New Graphic Novel
During the C2E2 weekend, Dark Horse Comics announced Duncan Fegredo's return to Hellboy in, Hellboy: The Midnight Circus. In the graphic novel, Hellboy runs away from the B.P.R.D and stumbles upon a circus inhabited by a few demons from hell. Hellboy: The Midnight Circus will arrive on shelves October 23, 2013 at an SRP of $14.99. The […]


text:
Part Two: Bike Fitting for Comfort, Efficiency and Reduced...
- News & Features
- Opinion
- Christopher Jones October 9, 2014
Think about each of your contact points on a bike: backside, feet and hands. While they each play a different role, they need to be considered as an entire system […]
Italian Bicycle Line Cycle Wear Targets Pole Position for...
- Reviews & Tech
- Road Cycling
- Michael Bachman August 16, 2013
Many of the well established players in the clothing market have loyal customer followings, so how do new entrants break into that group? Some do it with flair and styling […]
Northwave Evolution Summer Cycling Gloves
- Reviews & Tech
- Road Cycling
- James Hutchison August 1, 2013
I was at BNA House recently, performing for the cameras, when BNA Overlord, Christopher Jones, handed me a pair of Northwave gloves. The magic word "review" was said and… well, […]


text:
Skip to Main Content
IEEE membership options for an individual and IEEE Xplore subscriptions for an organization offer the most affordable access to essential journal articles, conference papers, standards,
eBooks, and eLearning courses.
Learn more about:
IEEE membership
IEEE Xplore subscriptions
The two methods in current use for the transient simulation of high-voltage DC (HVDC) power systems are electromagnetic transient programs and state variable analysis. A hybrid algorithm which combines the two methods, selecting their best features, is described. The relative performances of conventional and hybrid algorithms are discussed. Simulation results of typical back-to-back HVDC links show that the hybrid representation provides more stable, accurate and efficient solutions.<>
A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity.© Copyright 2016 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.


text:
One Step Ahead
|Land 50 First Attacks in a match. (Arcade/Xbox LIVE only)
Be the first person to connect with a hit in a match 50 times. Make sure it actual connects with your opponent and they aren't blocking. The words "First Attack" will appear on your side if it connected.
This can be done in Arcade Mode or in an Xbox Live match.
|Rate this achievement
|Average Rating
|You need to register before being able to post comments.
|You need to log in or register to use MyAchievements.
|You need to log in or register to rate games.
User Score is based on 370 user ratings.


text: Motorola introduced the Motorola H690 Bluetooth headset today, which is a successor to the Motorola H680 from last year. It looks almost the same design-wise, but the H690 boasts noise-reduction technology that was absent from the H680. It has dual microphones and echo cancellation, which promises better audio performance. The H690 also comes with "TrueComfort" ear buds for better comfort, as well as the usual headset features like voice dialing and a battery status indicator. The rated talk time is 5.5 hours and standby time is up to eight days. The H690 is expected to debut in Q2, though pricing is not yet known.


text:
This plugin is great, however the notification emails are always sent to the default email address.
Instead we want these messages to be delivered to a separate mailbox, i.e. firstname.lastname@example.com.
It would be a great improvement if the email address could be set or overridden in the plugin settings instead of always using the default email address.


text:
MNGOPers blocked some senators from attending marriage equality bill signing [VIDEOS]
Some marriage equality-supporting senators couldn't be there to take in this scene.
Andy Mannix
Yesterday, Sen. Scott Dibble, D-Minneapolis and chief sponsor of the gay marriage bill signed into law by Governor Dayton on Tuesday, criticized his Republican colleagues for using an esoteric procedural rule to prevent some of his colleagues from attending the bill-signing ceremony.
:::: UPDATE :::: MNGOP Sen. Pratt: Gay marriage ceremony had nothing to do with move to lock Senate doors
At the time Tuesday's bill-signing ceremony began, the Senate was in the midst of what turned out to be a 17-hour debate about a bill to "allow union organizing votes by in-home child care workers who receive government subsidies, and by in-home attendants who care for the elderly and disabled." The Senate could've temporarily adjourned to let everyone who wanted to attend be there for the historic signing ceremony, but instead, Prior Lake MNGOP Sen. Eric Pratt and other Republicans invoked an obscure rule requiring Senate doors to be locked while debate was ongoing.
Here's video from the Senate floor of that rule being invoked by a group of MNGOPers:
Talk about passive aggressive!
During remarks on the Senate floor the following day, Dibble said MNGOPers' tactics "diminished what was really a remarkable occasion."
"I just wanted to express ... an extreme sense of disappointment at what happened yesterday," he added.
Here's the video:
Dibble and Majority Leader Tom Bakk were among a group of Democrats who were in attendance during the bill-signing ceremony, though others who were on the floor at the time Pratt invoked the rule were blocked from leaving. A majority vote could've overruled the MNGOPers' move.
-- Follow Aaron Rupar on Twitter at @atrupar. Got a tip? Drop him a line at [email protected]
Get the This Week's Top Stories Newsletter
Every week we collect the latest news, music and arts stories — along with film and food reviews and the best things to do this week — so that you'll never miss City Pages' biggest stories.
In Case You Missed It
Popular Stories
Sponsor Content


text:
ODT Online
ODT /directory
Two teenage boys have been robbed at knifepoint of six boxes
of doughnuts in Adelaide's northwest.
Police say a man approached the victims as they got into
their car in West Croydon on Wednesday night, having just
bought doughnuts from a business on Port Road.
The man threatened them with what looked like a knife and
took the doughnuts but did not demand anything else and the
victims were not physically hurt.
The sweet-toothed thief is described as a Caucasian man aged
16 to 20, about 165cm tall and wearing a black hooded jumper
and black trackpants.
Doughnut chain Krispy Kreme this week opened its first South
Australian chain on Port Road, with some customers queueing
outside for days before the opening.
A name, residential address, and (preferably residential) telephone number is required from readers who comment on ODT Online. These details will not be visible to site visitors.
Login or Register
to add your business to the ODT/directory. Quick link to
Submit your news & photos - Login or
Opinion? Have your say - Login or Register
Submit your
event or notice
Add a photo
Bookmark ODT
Make ODT my
Otago Daily Times print and digital edition, The
Star - Dunedin, The News - Central Otago, The
Ensign - Gore, Southland Express -
Invercargill, Southern Rural Life - Otago and
Southland, The Courier - Timaru, Courier Country - Canterbury and
West Coast, Queenstown Times - Queenstown, Mountain Scene -
Queenstown, The Oamaru Mail - Oamaru, The
Greymouth Star - Greymouth, Hokitika Guardian - Hokitika,
West Coast Messenger - West Coast, The Ashburton Courier -
Ashburton, The News - North Canterbury, Extra! schools
publication, Property
Times South Canterbury