Design issues and caching strategies for CD-ROM based multimedia storage

CD-ROMs have proliferated as a distribution media for desktop machines for a large variety of multimedia applications (targeted for a single-user environment) like encyclopedias, magazines and games. With CD-ROM capacities up to 3 GB being available in the near future, they will form an integral part of Video on Demand (VoD) servers to store full-length movies and multimedia. In the first section of this paper we look at issues related to the single- user desktop environment. Since these multimedia applications are highly interactive in nature, we take a pragmatic approach, and have made a detailed study of the multimedia application behavior in terms of the I/O request patterns generated to the CD-ROM subsystem by tracing these patterns. We discuss prefetch buffer design and seek time characteristics in the context of the analysis of these traces. We also propose an adaptive main-memory hosted cache that receives caching hints from the application to reduce the latency when the user moves from one node of the hyper graph to another. In the second section we look at the use of CD-ROM in a VoD server and discuss the problem of scheduling multiple request streams and buffer management in this scenario. We adapt the C-SCAN (Circular SCAN) algorithm to suit the CD-ROM drive characteristics and prove that it is optimal in terms of buffer size management. We provide computationally inexpensive relations by which this algorithm can be implemented. We then propose an admission control algorithm which admits new request streams without disrupting the continuity of playback of the previous request streams. The algorithm also supports operations such as fast forward and replay. Finally, we discuss the problem of optimal placement of MPEG streams on CD-ROMs in the third section.

The collective dynamics of self-propelled particles

We propose a method for the dynamic simulation of a collection of self-propelled particles in a viscous Newtonian fluid. We restrict attention to particles whose size and velocity are small enough that the fluid motion is in the creeping flow regime. We propose a simple model for a self-propelled particle, and extended the Stokesian Dynamics method to conduct dynamic simulations of a collection of such particles. In our description, each particle is treated as a sphere with an orientation vector p, whose locomotion is driven by the action of a force dipole Sp of constant magnitude S0 at a point slightly displaced from its centre. To simplify the calculation, we place the dipole at the centre of the particle, and introduce a virtual propulsion force Fp to effect propulsion. The magnitude F0 of this force is proportional to S0. The directions of Sp and Fp are determined by p. In isolation, a self-propelled particle moves at a constant velocity u0 p, with the speed u0 determined by S0. When it coexists with many such particles, its hydrodynamic interaction with the other particles alters its velocity and, more importantly, its orientation. As a result, the motion of the particle is chaotic. Our simulations are not restricted to low particle concentration, as we implement the full hydrodynamic interactions between the particles, but we restrict the motion of particles to two dimensions to reduce computation. We have studied the statistical properties of a suspension of self-propelled particles for a range of the particle concentration, quantified by the area fraction φa. We find several interesting features in the microstructure and statistics. We find that particles tend to swim in clusters wherein they are in close proximity. Consequently, incorporating the finite size of the particles and the near-field hydrodynamic interactions is of the essence. There is a continuous process of breakage and formation of the clusters. We find that the distributions of particle velocity at low and high φa are qualitatively different; it is close to the normal distribution at high φa, in agreement with experimental measurements. The motion of the particles is diffusive at long time, and the self-diffusivity decreases with increasing φa. The pair correlation function shows a large anisotropic build-up near contact, which decays rapidly with separation. There is also an anisotropic orientation correlation near contact, which decays more slowly with separation. Movies are available with the online version of the paper.

How to run a campaign: Optimal control of SIS and SIR information epidemics

Information spreading in a population can be modeled as an epidemic. Campaigners (e.g., election campaign managers, companies marketing products or movies) are interested in spreading a message by a given deadline, using limited resources. In this paper, we formulate the above situation as an optimal control problem and the solution (using Pontryagin's Maximum Principle) prescribes an optimal resource allocation over the time of the campaign. We consider two different scenarios-in the first, the campaigner can adjust a direct control (over time) which allows her to recruit individuals from the population (at some cost) to act as spreaders for the Susceptible-Infected-Susceptible (SIS) epidemic model. In the second case, we allow the campaigner to adjust the effective spreading rate by incentivizing the infected in the Susceptible-Infected-Recovered (SIR) model, in addition to the direct recruitment. We consider time varying information spreading rate in our formulation to model the changing interest level of individuals in the campaign, as the deadline is reached. In both the cases, we show the existence of a solution and its uniqueness for sufficiently small campaign deadlines. For the fixed spreading rate, we show the effectiveness of the optimal control strategy against the constant control strategy, a heuristic control strategy and no control. We show the sensitivity of the optimal control to the spreading rate profile when it is time varying. (C) 2014 Elsevier Inc. All rights reserved.

Query Click and Text Similarity Graph for Query Suggestions

Query suggestion is an important feature of the search engine with the explosive and diverse growth of web contents. Different kind of suggestions like query, image, movies, music and book etc. are used every day. Various types of data sources are used for the suggestions. If we model the data into various kinds of graphs then we can build a general method for any suggestions. In this paper, we have proposed a general method for query suggestion by combining two graphs: (1) query click graph which captures the relationship between queries frequently clicked on common URLs and (2) query text similarity graph which finds the similarity between two queries using Jaccard similarity. The proposed method provides literally as well as semantically relevant queries for users' need. Simulation results show that the proposed algorithm outperforms heat diffusion method by providing more number of relevant queries. It can be used for recommendation tasks like query, image, and product suggestion.