A Flying Light Speck (FLS) is a small drone configured with light sources to illuminate different colors and textures. A swarm of FLSs illuminates complex 3D multimedia shapes in a fixed volume, a 3D display. An FLS is a mechanical device. Its failure is the norm rather than an exception, causing a point of an illumination to go dark. In this article, we use reliability groups with dark standby FLSs to minimize the duration of time a point remains dark. We introduce three techniques to prevent a dark standby FLS from obstructing the user’s Field of View (FoV). All three move the FLS out of the user’s FoV. One technique, Suspend:Closest, maximizes the utility of a standby FLS while preventing it from obstructing the user’s FoV.

This companion paper provides artifacts and instructions on replicating the experiments in the ACM Multimedia 2024 paper entitled ''Swarical: An Integrated Hierarchical Approach to Localizing Flying Light Specks.'' Swarm-based hierarchical, Swarical, is a localization technique that enables miniature drones, Flying Light Specks (FLSs), to accurately and efficiently localize and illuminate complex 2D and 3D shapes. It consists of two components, an offline planner and an online localization technique that executes on an FLS. The offline planner uses the FLS sensor specification for positioning to convert mesh files into swarms of FLSs. Some FLSs are dark and used only for localization. We reported the online localization technique to be fast and highly accurate. We describe how to reproduce this finding using our artifacts.

Swarical, a Swar m-based hierarchical localization technique, enables miniature drones, Flying Light Specks (FLSs), to accurately and efficiently localize and illuminate complex 2D and 3D shapes. Its accuracy depends on the physical hardware (sensors) of FLSs used to track neighboring FLSs to localize themselves. It uses the specification of the sensors to convert mesh files into point clouds that enable a swarm of FLSs to localize at the highest accuracy afforded by their sensors. Swarical considers a heterogeneous mix of FLSs with different orientations for their tracking sensors, ensuring a line of sight between a localizing FLS and its anchor FLS. We present an implementation using Raspberry cameras and ArUco markers. A comparison of Swarical with a state of the art decentralized localization technique shows that it is as accurate and more than 2x faster.

A Flying Light Speck, FLS, is a miniature sized drone configured with light sources to illuminate different colors and textures. A swarm of FLSs illuminates complex 3D multimedia shapes in a fixed volume, a 3D display. An FLS is a mechanical device. Its failure is the norm rather than an exception, causing a point of an illumination to go dark. In this paper, we use reliability groups with dark standby FLSs to minimize the duration of time a point remains dark. This study makes two novel contributions. First, it compares a centralized and a decentralized algorithm to form groups, demonstrating the superiority of the centralized technique. Second, it detects when the dark standby FLSs may obstruct the user's field of view and relocates them with minimal impact on their provided benefit.

Group formation is fundamental for 3D displays that use Flying Light Specks, FLSs, to illuminate shapes and provide haptic interactions. An FLS is a drone with light sources that illuminates a shape. Groups of G FLSs may implement reliability techniques to tolerate FLS failures, provide kinesthetic haptic feedback in response to a user’s touch, and facilitate a divide and conquer approach to challenges such as localizing FLSs to render a shape. This paper evaluates four decentralized techniques to form groups. An FLS implements a technique autonomously using asynchronous communication and without a global clock. We evaluate these techniques using synthetic point clouds with known optimal solutions and real point clouds. Obtained results show a technique named Random Subset (RS) is superior when constructing small groups (G ≤ 5) while a different technique named Closest Available Neighbor First (CANF) is superior when constructing large groups (G ≥ 10).

A Flying Light Speck, FLS, is a miniature sized drone configured with light sources. Swarms of FLSs will illuminate an object in a 3D volume, an FLS display. These illuminations and their data models are the novel contributions of this paper. We introduce a conceptual model of drone flight paths to render static, slide, and motion illuminations. We describe a physical implementation of the conceptual model using bag files. We evaluate this implementation using different lossless compression techniques. A key finding is that our bag file implementation is very compact when compared with the original point clouds. While compression reduces the size of a bag file, a combination that includes the use of both internal bag file compression (lz4 with chunks) and Gzip is not necessarily the most compact representation. We open source our software and its point cloud sequence data for use by the scientific community, see https://github.com/flyinglightspeck/FLSbagfile.

This paper presents techniques to display 3D illuminations using Flying Light Specks, FLSs. Each FLS is a miniature (hundreds of micrometers) sized drone with one or more light sources to generate different colors and textures with adjustable brightness. It is network enabled with a processor and local storage. Synchronized swarms of cooperating FLSs render illumination of virtual objects in a pre-specified 3D volume, an FLS display. We present techniques to display both static and motion illuminations. Our display techniques consider the limited flight time of an FLS on a fully charged battery and the duration of time to charge the FLS battery. Moreover, our techniques assume failure of FLSs is the norm rather than an exception. We present a hardware and a software architecture for an FLS-display along with a family of techniques to compute flight paths of FLSs for illuminations. With motion illuminations, one technique (ICF) minimizes the overall distance traveled by the FLSs significantly when compared with the other techniques.

Unmanned Aerial Vehicles (UAVs) have moved beyond a platform for hobbyists to enable environmental monitoring, journalism, film industry, search and rescue, package delivery, and entertainment. This paper describes 3D displays using swarms of flying light specks, FLSs. An FLS is a small (hundreds of micrometers in size) UAV with one or more light sources to generate different colors and textures with adjustable brightness. A synchronized swarm of FLSs renders an illumination in a pre-specified 3D volume, an FLS display. An FLS display provides true depth, enabling a user to perceive a scene more completely by analyzing its illumination from different angles.

The cloud infrastructure motivates disaggregation of monolithic data stores into components that are assembled together based on an application's workload. This study investigates disaggregation of an LSM-tree key-value store into components that communicate using RDMA. These components separate storage from processing, enabling processing components to share storage bandwidth and space. The processing components scatter blocks of a file (SSTable) across an arbitrary number of storage components and balance load across them using power-of-d. They construct ranges dynamically at runtime to parallelize compaction and enhance performance. Each component has configuration knobs that control its scalability. The resulting component-based system, Nova-LSM, is elastic. It outperforms its monolithic counterparts, both LevelDB and RocksDB, by several orders of magnitude with workloads that exhibit a skewed pattern of access to data.

Polygraph is a tool to quantify application anomalies attributed to violating atomicity, isolation, and linearizability properties of transactions. It is a plug-n-play framework that includes visualization tools to empower an experimentalist to (a) quickly incorporate Polygraph into an existing application or benchmark and (b) quantify the number of anomalies. We demonstrate Polygraph using existing benchmarks, including TPC-C, SEATS, TATP, YCSB, and BG. We highlight Polygraph as an on-line tool by showing it scales for almost all benchmarks to process their transaction log records faster than their rate of production.

An enumeration of RDMA messaging verbs (READ, WRITE, SEND/RECEIVE) and queue pair types creates a diverse set of message passing protocols. This paper constructs three abstract communication paradigms to quantify the performance and scalability characteristics of five protocols. With each abstraction, different protocols provide different results and the identity of the protocol that is superior to the others changes. Factors such as the number of queue pairs per node, the size of messages, the number of pending requests per queue pair, and the abstract communication paradigm dictate the superiority of a protocol. These results are important for design and implementation of algorithms and techniques that use the emerging RDMA.

An enumeration of RDMA messaging verbs (READ, WRITE, SEND/RECEIVE) and queue pair types creates a diverse set of message passing protocols. This paper constructs three abstract communication paradigms to quantify the performance and scalability characteristics of five protocols. With each abstraction, different protocols provide different results and the identity of the protocol that is superior to the others changes. Factors such as the number of queue pairs per node, the size of messages, the number of pending requests per queue pair, and the abstract communication paradigm dictate the superiority of a protocol. These results are important for design and implementation of algorithms and techniques that use the emerging RDMA.

The Cache Augmented Data Store (CADS) architecture extends a persistent data store with an in-memory cache manager. It is widely deployed to support read-intensive workloads. However, its write-around and write-through policies prevent the caching tier from absorbing write load. This means the data store layer must scale to process writes even when the extra capacity is not needed for read load. We address this limitation by devising a write-back technique to enable the caching layer to process both reads and writes. This technique preserves ACID transactions. We present a client side implementation of write-back and evaluate it using the YCSB, BG, and TPC-C benchmarks. In addition, we compare our write-back with (a) write-back policy of a data store such as MongoDB and (b) write-back policy of a host-side cache such as Flashcache.

Hoagie is a plug-n-play workload and database generator to evaluate novel system architectures, design decisions, protocols, and algorithms. It uses published specifications to create a database of data items and a workload that references these data items. Hoagie's modular design enables an experimentalist to use it either offline or online. In offline mode, Hoagie outputs a trace file that can be used to issue requests to a target system. In online mode, Hoagie is plugged into an existing benchmark that invokes it to generate requests one at a time to its target system. We have made Hoagie open source to foster its future development.

No abstract available.

No abstract available.

Polygraph is a tool to quantify system behavior that violates serial execution of transactions. It is a plug-n-play framework that operates externally to the system at the conceptual granularity of entities and their relationships.We demonstrate Polygraph's ability to plug-in to existing benchmarks including TPC-C, SEATS, TATP, YCSB, and BG. In addition, we show Polygraph processes transaction log records in realtime and characterize its scalability characteristics.

Advances in storage technology have introduced Non-Volatile Memory, NVM, as a new storage medium. NVM, along with DRAM and Disk present a system designer with a wide array of options in designing caching middleware. Moreover, design decisions to replicate a data item in more than one level of a caching memory hierarchy may enhance the overall system performance with a faster recovery time in the event of a memory failure. Given a fixed budget, the key configuration questions are: Which storage media should constitute the memory hierarchy? What is the storage capacity of each hierarchy? Should data be replicated or partitioned across the different levels of the hierarchy? We study a model of these cache configuration questions and present results from a simple algorithm to evaluate design tradeoffs in the context of a memory hierarchy for a Key-Value Store, e.g., memcached. The results show selective replication is appropriate with certain failure rates and workload characteristics. With a slim failure rate and frequent data updates, tiering of data across the different storage media that constitute the cache is superior to replication.

Diverse applications implement read and write transactions using a data store. It is challenging to evaluate whether transactions that constitute an application provide strong consistency. It requires an end-to-end testing as an application may consist of several components that impact the consistency of data. Polygraph is a conceptual plug-n-play framework to quantify the amount of anomalies produced by an application. We show several use cases of Polygraph for two major application classes: e-commerce and cloud. One long-term objective of Polygraph is to reduce the cost and time required to test a data driven application, so that developers may focus more time and effort on applications' features and requirements.

Gemini is a distributed crash recovery protocol for persistent caches. When a cache instance fails, Gemini assigns other cache instances to process its reads and writes. Once the failed instance recovers, Gemini starts to recover its persistent content while using it to process reads and writes immediately. Gemini does so while guaranteeing read-after-write consistency. It also transfers the working set of the application to the recovering instance to maximize its cache hit ratio. Our evaluation shows that Gemini restores hit ratio two orders of magnitude faster than a volatile cache. Working set transfer is particularly effective with workloads that exhibit an evolving access pattern.

We introduce the subset assignment problem in which items of varying sizes are placed in a set of bins with limited capacity. Items can be replicated and placed in any subset of the bins. Each (item, subset) pair has an associated cost. Not assigning an item to any of the bins is not free in general and can potentially be the most expensive option. The goal is to minimize the total cost of assigning items to subsets without exceeding the bin capacities. The subset assignment problem models the problem of managing a cache composed of banks of memory with varying cost/performance specifications. The ability to replicate a data item in more than one memory bank can benefit the overall performance of the system with a faster recovery time in the event of a memory failure. For this setting, the number n of data objects (items) is very large and the number d of memory banks (bins) is a small constant (on the order of 3 or 4). Therefore, the goal is to determine an optimal assignment in time that minimizes dependence on n. The integral version of this problem is NP-hard since it is a generalization of the knapsack problem. We focus on an efficient solution to the LP relaxation as the number of fractionally assigned items will be at most d. If the data objects are small with respect to the size of the memory banks, the effect of excluding the fractionally assigned data items from the cache will be small. We give an algorithm that solves the LP relaxation and runs in time $$O(\left( {\begin{array}{c}3^d\\ d+1\end{array}}\right) {\text {poly}}(d) n \log (n) \log (nC) \log (Z))$$ , where Z is the maximum item size and C the maximum storage cost.

In the generalized caching problem, items can have varying costs and sizes. We consider a variant of this problem in which the cache management policy must not only specify which items to evict to make room for an incoming item (cache replacement), but must also specify a location in memory where each object can be placed contiguously (memory allocation). The problem is motivated by current implementations of key-value stores in large commercial databases with high read-to-write ratio such as those maintained by Facebook and Twitter. We propose a simple algorithm and show that if the algorithm is given some additional memory to account for fragmentation, it is competitive against an offline optimal algorithm that does not specify memory layout. (The optimal algorithm needs only to ensure that the sum of the sizes of the items in the cache does not exceed the total capacity of the cache). On the benchmark traces in the experiments presented here, our algorithm requires approximately 10–15– additional space to be k-competitive against the optimal offline algorithm. Through trace-driven simulations, we demonstrate that the caching performance of our algorithm for cache replacement with memory allocation is close to that of competitive strategies that are not required to manage memory layout within the cache.

With object-oriented programming languages, Object Relational Mapping (ORM) frameworks such as Hibernate have gained popularity due to their ease of use and portability to different relational database management systems. Hibernate implements the Java Persistent API, JPA, and frees a developer from authoring software to address the impedance mismatch between objects and relations. In this paper, we evaluate the performance of Hibernate by comparing it with a native JDBC implementation using a benchmark named BG. BG rates the performance of a system for processing interactive social networking actions such as view profile, extend an invitation from one member to another, and other actions. Our key findings are as follows. First, an object-oriented Hibernate implementation of each action issues more SQL queries than its JDBC counterpart. This enables the JDBC implementation to provide response times that are significantly faster. Second, one may use the Hibernate Query Language (HQL) to refine the object-oriented Hibernate implementation to provide performance that approximates the JDBC implementation.

With a wide variety of big data applications, the past few years have witnessed an increasing number of data stores with novel design decisions that may sacrifice the correctness of an application's operations to enhance performance. This paper presents our work-in-progress on a framework that generates a validation component. The input to the framework is the characteristics of an application. Its output is a validation module that plugs-in to either an application or a benchmark to measure the amount of unpredictable data produced by a data store.

Cost Adaptive Multi-queue eviction Policy (CAMP) is an algorithm for a general purpose key-value store (KVS) that manages key-value pairs computed by applications with different access patterns, key-value sizes, and varying costs for each key-value pair. CAMP is an approximation of the Greedy Dual Size (GDS) algorithm in that its eviction policy is as effective as GDS. At the same time, its implementation is as efficient at LRU. Similar to an implementation of LRU using queues, it adapts to changing workload patterns based on the history of requests for different key-value pairs. It is superior to LRU because it considers both the size and cost of key-value pairs to maximize the utility of the available memory across competing applications. We compare CAMP with both LRU and an alternative that requires human intervention to partition memory into pools and assign grouping of key-value pairs to different pools. The results demonstrate CAMP is as fast as LRU while outperforming both LRU and the pooled alternative. We also present results from an implementation of CAMP using Twitter's version of memcached.

Cache augmented SQL, CASQL, systems enhance the performance of simple operations that read and write a small amount of data from big data. They do so by looking up the results of computations that query the database in a key-value store (KVS) instead of processing them using a relational database management system (RDBMS). These systems incur undesirable race conditions that cause the KVS to produce stale data. This paper presents the IQ framework that provides strong consistency with no modification to the RDBMS. It consists of two non-blocking leases, Inhibit (I) and Quarantine (Q). Ratings obtained from a social networking benchmark named BG show the proposed framework has minimal impact on system performance while providing strong consistency guarantees.

To benchmark and rate a data store, one must repeat experiments that impose a different amount of load on the data store. Workloads that modify the benchmark database may require the same database to be loaded repeatedly. This may constitute a significant portion of the time to rate a data store. This paper presents several agile data loading techniques to expedite the rating process. These techniques include generating the disk image of the database once and re-using it, restoring the updated data items to their original value, maintaining in-memory state of the database across different experiments to avoid repeated loading of the database all together, and a hybrid of the third technique in combination with the other two. These techniques are general purpose and apply to a variety of cloud benchmarks. We investigate their implementation and evaluation in the context of one, the BG benchmark. Obtained results show a factor of two to twelve speedup in the rating process. As an example, when evaluating MongoDB with a million member BG database, we show these techniques expedite BG's rating from 4 months (123 days) of continuous running to less than 11 days for the first rating experiment. Subsequent ratings of MongoDB with different workloads using the same database is much faster, in the order of hours.

This paper compares the performance of an SQL solution that implements a relational data model with a document store named MongoDB. We report on the performance of a single node configuration of each data store and assume the database is small enough to fit in main memory. We analyze utilization of the CPU cores and the network bandwidth to compare the two data stores. Our key findings are as follows. First, for those social networking actions that read and write a small amount of data, the join operator of the SQL solution is not slower than the JSON representation of MongoDB. Second, with a mix of actions, the SQL solution provides either the same performance as MongoDB or outperforms it by 20%. Third, a middle-tier cache enhances the performance of both data stores as query result look up is significantly faster than query processing with either system.

A SOcial LIve Stream, SOLIS, is a live stream produced by a device whose owner is sharing the stream with her friends, granting each friend to perform time shifted viewing for a pre-specified duration. The system buffers this chase data to facilitate its browsing and display. In the presence of many Solis, memory may overflow and prevent display of some chase data. This paper presents a novel data-aware admission control, DA-AdmCtrl, technique that summarizes chase data pro-actively to maximize the number of admissible SOLISs with no memory overflow. It is designed for use with multi-core CPUs and maximizes utility of data whenever the user's level of satisfaction (utility) with different data formats is available.

Wireless home networks are widely deployed due to their low cost, ease of installation, and plug-and-play capabilities with consumer electronic devices. A challenge of these environments is how to manage data across devices. This is specially true for continuous media (audio and video clips) which are large in size and delay sensitive. Caching of clips across wireless devices may improve user experience, measurable by different Quality of Service (QoS) metrics such as throughput and startup latency. Moreover, caching at the edge of the network reduces the demand for the infrastructure outside the home. In this study, we present Domical, a novel cooperative caching technique designed for streaming media in wireless home networks consisting of a handful of devices. Domical is novel because it considers both asymmetry of the available wireless link bandwidth and heterogeneity of available cache space. We provide a comprehensive description of Domical, presenting its key knobs, and the behavior of the algorithm with different granularity of data caching (block versus clip).

HoTMaN (HoT-standby MaNager) is a joint project between MySpace and USC Database Laboratory to design and develop a tool to ensure a 24x7 up-time and ease administration of Terabytes of storage that sits underneath hundreds of database servers. The HoTMaN tool's innovation and uniqueness is that it can, with a few clicks, perform operational tasks that require hundreds of keyboard strokes by "trusted trained" experts. With HoTMaN, MySpace can within minutes migrate the relational database(s) of a failed server to a hot-standby. A process that could take over 1 hour and had a high potential for human error is now performed reliably. A database internal to HoTMaN captures all virtual disks, volume and file configurations associated with each SQL Server and candidate hot-standby servers where SQL server processing could be migrated. HoTMaN is deployed in production and its current operational benefits include: (i) enhanced availability of data, and (ii) planned maintenance and patching.

Wireless mesh home networks are deployed widely due to their ease of installation and economical prices. A typical network may consist of a handful of devices such as PCs, laptops, wireless consumer electronic devices, and game consoles. Devices may share data by making the state of their caches dependent on one another using a cooperative caching technique such as Domical. This sharing of data at the edges of the network reduces the load on the infrastructure outside of the household, freeing it to service other requests. In this paper, we analyze two local cache replacement techniques designed to enhance average startup latency of streaming media. Both pre-stage a fraction of a clip on a device in anticipation of its future reference in order to display the prefetch portion while streaming its remainder in the background. We use a simulation study of a realistic home network to compare these two technique with one another when deployed with Domical. Obtained results show show one technique, named urgency-worthiness, is superior to the other when storage is abundant.

In an ad-hoc network of mobile devices, a device is termed a zebroid when it carries a data item residing on a server-device to a client-device referencing that item. The system employs a zebroid when its travel path intersects that of the server and the client and this information is known in advance. The motivation for use of a zebroid is to minimize the delay incurred by the client for the referenced data item, termed the availability latency. This paper considers the performance of alternative policies that manage the identity of data items assigned to a zebroid when its storage is exhausted. One novel policy is LoDeR that manages storage of zebroids based on the demographics of a geographical region where the zebroid rendezvous with the client. Experimental results demonstrate a host of tradeoffs between the different performance metrics such as the number of data items lost by a policy and the percentage of requests that reference these data items, availability latency, and number of replaced data items. The mobility model has a significant impact on these metrics for a given policy.

This study investigates alternative continuous media replication techniques and their impact on content availability in a mobile car-to-car peer-to-peer (C2P2) network of devices. Using aggregate availability latency as a metric, we compare a simple random replication mechanism with a family of techniques that compute the degree of replication for each title based on its popularity, i.e., frequency of access. We use a simulation study along with some supporting analytical analysis for this comparison. Obtained results demonstrate the following key lesson. When total storage capacity of the network is significantly larger than the clip repository size, a random replication technique is sufficient. Otherwise, there is a large parameter space where the frequency-based replication schemes provide superior performance.

Display of continuous media using self-organizing ad hoc networks of wireless communication systems are potentially used in a variety of applications. Example deployments might include disaster relief missions, conferences, and university campuses to name a few. Challenges of these environments include their mobility, and unpredictable network bandwidth and loss characteristics. This paper explores a three step science of design for applications that manipulate continuous media. This science strives to satisfy the requirements of an application. It consists of a number of principles that impact the design of algorithms. These principles guide a system designer towards parameterized algorithms that treat network bandwidth and storage as one.

This paper investigates a novel streaming architecture consisting of home-to-home online (H2O) devices that collaborate with one another to provide on-demand access to large repositories of continuous media such as audio and video clips. An H2O device is configured with a high bandwidth wireless communication component, a powerful processor, and gigabytes of storage. A key challenge of this environment is how to place data across H2O devices in order to enhance startup latency, defined as the delay observed from when a user requests a clip, to the onset of its display. Our primary contribution is a novel replication technique that enhances startup latency, while minimizing the total storage space required from an environment consisting of N H2O devices. This technique is based on the following intuition: The first few blocks of a clip are required more urgently than its last few blocks, and should be replicated more frequently in order to minimize startup latency. We develop analytical models to quantify the number of replicas required for each block. In addition, we describe two alternative distributed implementation of our replication strategy. When compared with full replication, our technique provides on average greater than 97% (i.e., several orders of magnitude) savings in storage space, while ensuring zero startup latency and a hiccup-free reception.

A number of recent technological trends have made data intensive applications such as continuous media (audio and video) servers a reality. These servers store and retrieve large volumes of data using magnetic disks. Servers consisting of multiple nodes and large arrays of heterogeneous disk drives have become a fact of life for several reasons. First, magnetic disks might fail. Failed disks are almost always replaced with newer disk models because the current technological trend for these devices is one of annual increase in both performance and storage capacity. Second, storage requirements are ever increasing, forcing servers to be scaled up progressively. In this study, we present a framework to enable parity-based data protection for heterogeneous storage systems and to compute their mean lifetime. We describe the tradeoffs associated with three alternative techniques: independent subservers, dependent subservers, and disk merging. The disk merging approach provides a solution for systems that require highly available secondary storage in environments that also necessitate maximum flexibility.

Gesture recognition techniques often suffer from being highly device-dependent and hard to extend. If a system is trained using data from a specific glove input device, that system is typically unusable with any other input device. The set of gestures that a system is trained to recognize is typically not extensible, without retraining the entire system. We propose a novel gesture recognition framework to address these problems. This framework is based on a multi-layered view of gesture recognition. Only the lowest layer is device dependent, it converts raw sensor values produced by the glove to a glove-independent semantic description of the hand. The higher layers of our framework can be reused across gloves, and are easily extensible to include new gestures. We have experimentally evaluated our framework and found that it yields comparable performance to conventional techniques, while substantiating our claims of device independence and extensibility.

This paper describes a novel cost-driven disk scheduling algorithm for environments consisting of multipriority requests. An example application is a video-on-demand (VOD) system that provides high and low quality services, termed priority 2 and 1, respectively. Customers ordering a high quality (priority 2) service pay a higher fee and are assigned a higher priority by the underlying system. Our proposed algorithm minimizes costs by maintaining one-queue and managing requests intelligently in order to meet the deadline of as many priority 1 requests as possible while maximizing the number of priority 2 requests that meet their deadline. Our algorithm is general enough to accommodate an arbitrary number of priority levels. Prior schemes, collectively termed "multiqueue" schemes maintain a separate queue for each priority level in order to optimize the performance of the high priority requests only. When compared with our proposed scheme, in certain cases, our technique provides more than one order of magnitude improvement in total cost.

In multiuser multimedia information systems (e.g., movie-on-demand, digital-editing), scheduling the retrievals of continuous media objects becomes a challenging task. This is because of both intra and inter lobject time dependencies. Intraobject time dependency refers to the real-time display requirement of a continuous media object. Interobject time dependency is the temporal relationships defined among multiple continuous media objects. In order to compose tailored multimedia presentations, a user might define complex time dependencies among multiple continuous media objects with various lengths and display bandwidths. Scheduling the retrieval tasks corresponding to the components of such a presentation in order to respect both inter and intra task time dependencies is the focus of this study. To tackle this task scheduling problem (CRS), we start with a simpler scheduling problem (ARS) where there is no inter task time dependency (e.g., movie-on-demand). Next, we investigate an augmented version of ARS (termed ARS/sup +/) where requests reserve displays in advance (e.g., reservation-based movie-on-demand). Finally, we extend our techniques proposed for ARS and ARS/sup +/ to address the CRS problem. We also provide formal definition of these scheduling problems and proof of their NP-hardness.

Moving sensors refers to an emerging class of data intensive applications that inpacts disciplines such as communication, health-care, scientific applications, etc. These applications consist of a fixed number of sensors that move and produce streams of data as a function of time. They may require the system to match these streams against stored streams to retrieve relevant data (patterns). With communication, for example, a speaking impaired individual might utilize a haptic glove that translates hand signs into written (spoken) words. The glove consists of sensors for different finger joints. These sensors report their location and values as a function of time, producing streams of data. These streams are matched against a repository of spatio-temporal streams to retrieve the corresponding English character or word.The contributions of this study are two fold. First, it introduces a framework to store and retrieve "moving sensors" data. The framework advocates physical data independence and software-reuse. Second, we investigate alternative representations for storage and retrieve of data in support of query processing. We quantify the tradeoff associated with these alternatives using empirical data RoboCup soccer matches.

This paper describes a middleware that enables its target application to dynamically incorporate heterogeneous nodes of a cluster. It distributes the objects of the application across the nodes with the objective to evenly distribute system load. As such, it eliminates the need for a system administrator to control the placement of data. We describe the architecture of the middleware that facilitates object migration and its decision making components. One aspect of this architecture is a negotiation protocol to facilitate migration of objects from one node to another. Finally, we describe an implementation of this middleware using Java and Sun's Jini framework.

Modern video servers support both video-on-demand and nonlinear editing applications. Video-on-demand servers enable the user to view video clips or movies from a video database, while nonlinear editing systems enable the user to manipulate the content of the video database. Applications such as video and news editing systems require that the underlying storage server be able to concurrently record live broadcast information, modify prerecorded data, and broadcast an authored presentation. A multimedia storage server that efficiently supports such a diverse group of activities constitutes the focus of this study. A novel real-time disk scheduling algorithm is presented that treats both read and write requests in a homogeneous manner in order to ensure that their deadlines are met. Due to real-time demands of movie viewing, read requests have to be fulfilled within certain deadlines; otherwise, they are considered lost. Since the data to be written into disk is stored in main memory buffers, write requests can be postponed until critical read requests are processed. However, write requests still have to be processed within reasonable delays and without the possibility of indefinite postponement. This is due to the physical constraint of the limited size of the main memory write buffers. The new algorithm schedules both read and write requests appropriately, to minimize the amount of disk reads that do not meet their presentation deadlines, and to avoid indefinite postponement and large buffer sizes in the case of disk writes. Simulation results demonstrate that the proposed algorithm offers low violations of read deadlines, reduces waiting time for lower priority disk requests, and improves the throughput of the storage server by enhancing the utilization of available disk bandwidth.

We introduce a new deadline driven disk scheduling algorithm designed for multimedia servers. The proposed algorithm supports real time requests with multiple priorities, e.g., those for different object classes in digital library applications. The proposed algorithm enhances utilization of disk bandwidth by: maintaining one queue for all requests; and optimizing the seek time. Prior schemes, collectively termed "multi-queue schemes", maintain a separate queue for each priority group and optimize the performance of the high priority requests only. When compared with our proposed scheme, our technique provides approximately two order of magnitude improvement in meeting the deadline of low priority requests. In addition, this algorithm provides both a better disk utilization and a better average response time. Under certain conditions, our algorithm violates the deadline of a few high priority requests (less than 5 out of a million requests).

A number of recent technological trends have made data intensive applications such as continuous media (audio and video) servers a reality. These servers are expected to play an important role in applications such as video-on-demand, digital library, news-on-demand, distance learning, etc. Continuous media applications are data intensive and might require storage subsystems that consist of hundreds of (multi-zone) disk drives. With the current technological trends, a homogeneous disk subsystem might evolve to consist of a heterogeneous collection of disk drives. Given such a storage subsystem, the system must continue to support a hiccup-free display of audio and video clips. This study describes extensions of four continuous display techniques for multi-zone disk drives to a heterogeneous platform. These techniques include IBM's Logical Track [21], HP's Track Pairing [4], and USC's FIXB [9] and deadline driven techniques [10]. We quantify the performance tradeoff associated with these techniques using analytical models and simulation studies. The obtained results demonstrate tradeoffs between the cost per simultaneous stream supported by a technique, the wasted disk space, and the incurred startup latency.

A number of recent technological trends have made data intensive applications such as continuous media (audio and video) servers a reality. These servers store and retrieve a large volume of data using magnetic disks. Servers consisting of heterogeneous disk drives have become a fact of life for several reasons. First, disks are mechanical devices that might fail. The failed disks are almost always replaced with new models. Second, the current technological trend for these devices is one of annual increase in both performance and storage capacity. Older disk models are discontinued because they cannot compete with the newer ones in the commercial arena. With a heterogeneous disk subsystem, the system should support continuous display while managing resources intelligently in order to maximize their utilization. This study describes a taxonomy of techniques that ensure a continuous display of objects using a heterogeneous disk subsystem. This taxonomy consists of: (a) strategies that p...

A structured video consists of a collection of background objects, characters, spatial and temporal constructs, and rendering features. Assuming a platform consisting of a fixed amount of memory and a magnetic disk drive, this study presents a resource scheduler for the continuous display of structured video that minimizes both the latency observed by a display and its required amount of memory.

Traditional database systems provide a user with the ability to query and manipulate one database state, namely the current database state. However, in several emerging applications, the ability to analyze “what-if” scenarios in order to reason about the impact of an update (before committing that update) is of paramount importance. Example applications include hypothetical database access, active database management systems, and version management, to name a few. The central thesis of the Heraclitus paradigm is to provide flexible support for applications such as these by elevating deltas , which represent updates proposed against the current database state, to be first-class citizens. Heraclitus[Alg,C] is a database programming language that extends C to incorporate the relational algebra and deltas. Operators are provided that enable the programmer to explicitly construct, combine, and access deltas. Most interesting is the when operator, that supports hypothetical access to a delta: the expression E when σ yields the value that side effect free expression E would have if the value of delta expression σ were applied to the current database state. This article presents a broad overview of the philosophy underlying the Heraclitus paradigm, and describes the design and prototype implementation of Heraclitus[Alg, C]. A model-independent formalism for the Heraclitus paradigm is also presented. To illustrate the utility of Heraclitus, the article presents an in-depth discussion of how Heraclitus[Alg, C] can be used to specify, and thereby implement, a wide range of execution models for rule application in active databases; this includes both prominent execution models presented in the literature, and more recent “customized” execution models with novel features.

The past decade has witnessed a proliferation of repositories that store and retrieve continuous media data types, e.g., audio and video objects. These repositories are expected to play a major role in several emerging applications, e.g., library information systems, educational applications, entertainment industry, etc. To support the display of a video object, the system partitions each object into fixed size blocks. All blocks of an object reside permanently on the disk drive. When displaying an object, the system stages the blocks of the object into memory one at a time for immediate display. In the presence of multiple displays referencing different objects, the bandwidth of the disk drive is multiplexed among requests, introducing disk seeks. Disk seeks reduce the useful utilization of the disk bandwidth and result in a lower number of simultaneous displays (throughput).This paper characterizes the impact of disk seeks on the throughput of the system. It describes REBECA as a mechanism that maximizes the throughput of the system by minimizing the time attributed to each incurred seek. A limitation of REBECA is that it increases the latency observed by each request. We quantify this throughput vs latency tradeoff of REBECA and, develop an efficient technique that computes its configuration parameters to realize the performance requirements (desired latency and throughput) of an application.

The past decade has witnessed a proliferation of respositories whose workload consists of queries that retrieve information. These repositories provide on-line access to vast amount of data and serve as an integral component of many application domains (e.g., library information systems, scientific applications, entertainment industry). Their storage subsystem is expected to be hierarchical consisting of memory, disk drives, and one or more tertiary storage devices. The database resides permanently on the tertiary storage devices and objects are swapped onto the magnetic disk drives on demand (and deleted once the disk storage capacity is exhausted). This may fragment the disk space over a period of time, resulting in a non-contiguous layout of an object across the surface of a disk drive. This is undesirable because, once the object is referenced, the disk drive is required to reposition its read head multiple times (incur seek operations) when retrieving the object, resulting in a low performance.

Parallelism is a viable solution to constructing high performance object-oriented database systems. In parallel systems based on a shared-nothing architecture, the database is horizontally declustered across multiple processors, enabling the system to employ multiple processors to speedup the execution time of a query. The placement of objects across the processors has a significant impact on the performance of queries that traverse a few objects. The paper describes and evaluates a greedy algorithm for the placement of objects across the processors of a system. Moreover, it describes two alternative availability strategies and quantifies their performance tradeoff using a trace-driven simulation study.>

The past decade has witnessed a proliferation of personal computers at homes, businesses, classrooms, libraries, etc. Most often, these systems are used to disseminate information. Recently, multimedia repositories have added to the excitement of this information age by allowing a user to retrieve and manipulate continuous media data types (audio and video objects). The design and implementation of these systems is challenging due to both the large size of objects that constitute this media type and their continuous bandwidth requirement. Compression in combination with the availability of fast CPUs (for real-time decompression) provide effective support for a continuous display of those objects with high bandwidth requirement. Hierarchical storage structures (consisting of RAM, disk and tertiary storage devices) provide a cost-effective solution for the large size of their repositories. The focus of this study is on personal computers (single user, single display) that employ fast CPUs, compression and hierarchical storage structures to support multimedia applications. Its goals are to ensure a continuous display of audio and video objects while minimizing the latency time observed by the user. Its contributions include a novel pipelining mechanism and PIRATE as a technique to manage the disk resident objects.

Multimedia information systems have emerged as an essential component of many application domains ranging from library information systems to entertainment technology. However, most implementations of these systems cannot support the continuous display of multimedia objects and suffer from frequent disruptions and delays termed hiccups. This is due to the low I/O bandwidth of the current disk technology, the high bandwidth requirement of multimedia objects, and the large size of these objects that almost always requires them to be disk resident. One approach to resolve this limitation is to decluster a multimedia object across multiple disk drives in order to employ the aggregate bandwidth of several disks to support the continuous retrieval (and display) of objects. This paper describes staggered striping as a novel technique to provide effective support for multiple users accessing the different objects in the database. Detailed simulations confirm the superiority of staggered strip...

During the past decade, parallel database systems have gained increased popularity due to their high performance, scalability, and availability characteristics. With the predicted future database sizes and complexity of queries, the scalability of these systems to hundreds and thousands of processors is essential for satisfying the projected demand. Several studies have repeatedly demonstrated that both the performance and scalability of a parallel database system are contingent on the physical layout of the data across the processors of the system. If the data are not declustered appropriately, the execution of an operation might waste system resources, reducing the overall processing capability of the system. With earlier, single-attribute partitioning mechanisms such as those found in the Tandem, Teradata, Gamma, and Bubba parallel database systems, range selections on any attribute other than the partitioning attribute must be sent to all processors containing tuples of the relation, while range selections on the partitioning attribute can be directed to only a subset of the processors. Although using all the processors for an operation is reasonable for resource intensive operations, directing a query with minimal resource requirements to processors that contain no relevant tuples wastes CPU cycles, communication bandwidth, and I/O bandwidth. As a solution, this paper describes a new partitioning strategy, multiattribute grid declustering (MAGIC), which can use two or more attributes of a relation to decluster its tuples across multiple processors and disks. In addition, MAGIC declustering, unlike other multiattribute partitioning mechanisms that have been proposed, is able to support range selections as well as exact match selections on each of the partitioning attributes. This capability enables a greater variety of selection operations to be directed to a restricted subset of the processors in the system. Finally, MAGIC partitions each relation based on the resource requirements of the queries that constitute the workload for the relation and the processing capacity of the system in order to ensure that the proper number of processors are used to execute queries that reference the relation.>

An approach and mechanism to support the sharing of objects are described, an experimental implementation is presented, and the performance of the system is analyzed and evaluated. The mechanism is based on a core set of constructs that characterize object-based database systems. The approach provides a basis for controlled sharing in a heterogeneous database environment, using a kernel object-base model as an intercomponent exchange forum. A major goal is to make the importation of nonlocal information as transparent to a component as possible.>

During the past decade, information technology has evolved to store and retrieve multimedia data (e.g., audio, video). Multimedia information systems utilize a variety of human senses to provide an effective means of conveying information. Already, these systems play a major role in educational applications, entertainment technology, and library information systems. A challenging task when implementing these systems is to support a continuous retrieval of an object at the bandwidth required by its media type. This is challenging because certain media types, in particular video, require very high bandwidths. For example, the bandwidth required by NTSC (the US standard established by the National Television System Committee) for network-quality video is about 45 megabits per second (mbps). Recommendation 601 of the International Radio Consultative Committee (CCIR) calls for a 216 mbps bandwidth for video objects. A video object based on the HDTV (High Definition Television) quality images requires approximately a 700 mbps bandwidth. Compare these bandwidth requirements with the typical 10 mbps bandwidth of a magnetic disk drive, which is not expected to increase significantly in the near future. Currently, there are several ways to support continuous display of these objects: 1) sacrifice the quality of the data by using either a lossy compression technique or a low resolution device, 2) employ the aggregate bandwidth of several disk drives by declustering an object across multiple disks [2], and 3) use a combination of these two techniques. Lossy compression techniques encode data into a form that consumes a relatively small amount of space, however, when the data is decoded, it yields a representation similar to the original (some loss of data). While it is effective, there are applications that cannot tolerate loss of data. As an example consider the video signals collected from space. This data may not be compressed using a lossy compression technique. Otherwise, the scientists who later uncompress and analyze the data run the risk of either observing phenomena that may not exist due to a slight change in data or miss important observations due to some loss of data.

In parallel database systems, distribution of the data among the processors has a significant impact on the response time and throughput of the system. The benefits of parallelism (using multiple processors to execute a query) must be balanced against its costs (communication, startup, and termination overhead). We formalize the problem of minimizing overhead while partitioning data uniformly across the processors. We derive lower bounds on these combinatorial problems and demonstrate how processors may be optimally assigned so as to achieve these lower bounds for a number of problem classes. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Most implementations of workstation-based multimedia information systems cannot support a continuous display of high resolution audio and video data and suffer from frequent disruptions and delays termed hiccups. This is due to the low I/O bandwidth of the current disk technology, the high bandwidth requirement of multimedia objects, and the large size of these objects, which requires them to be almost always disk resident. A parallel multimedia information system and the key technical ideas that enable it to support a real-time display of multimedia objects are described. In this system, a multimedia object across several disk drives is declustered, enabling the system to utilize the aggregate bandwidth of multiple disks to retrieve an object in real-time. Then, the workload of an application is distributed evenly across the disk drives to maximize the processing capability of the system. To support simultaneous display of several multimedia objects for different users, two alternative approaches are described. The first approach multitasks a disk drive among several requests while the second replicates the data and dedicates resources to each individual request. The trade-offs associated with each approach are investigated using a simulation model.>

During the past decade, parallel database systems have gained increased popularity due to their high performance, scalability and availability characteristics. With the predicted future database sizes and the complexity of queries, the scalability of these systems to hundreds and thousands of processors is essential for satisfying the projected demand. Several studies have repeatedly demonstrated that both the performance and scalability of a paralel database system is contingent on the physical layout of data across the processors of the system. If the data is not declustered properly, the execution of an operator might waste resources, reducing the overall processing capability of the system.

An analysis is made of the impact of three alternative declustering strategies on the performance of the selection queries using different storage/access structures in a multiuser environment. The authors quantify the tradeoffs of each organization in the context of the Gamma database machine. The response time and throughput of the system are used as the performance metric for evaluating the alternative declustering strategies.>

While in the past 20 years database management systems (DBMS) have become a critical component of almost all organizations, their behavior in a multiuser environment has surprisingly not been studied carefully. In order to help us understand the multiuser performance of the multiprocessor Gamma database machine [DEWI90], we began by studying the performance of a single processor version of this system. In this paper, we describe some of the factors that affect the performance of DBMS in a multiuser environment. We refer the interested reader to [GHAN90] for more details.

The design of the Gamma database machine and the techniques employed in its implementation are described. Gamma is a relational database machine currently operating on an Intel iPSC/2 hypercube with 32 processors and 32 disk drives. Gamma employs three key technical ideas which enable the architecture to be scaled to hundreds of processors. First, all relations are horizontally partitioned across multiple disk drives, enabling relations to be scanned in parallel. Second, parallel algorithms based on hashing are used to implement the complex relational operators, such as join and aggregate functions. Third, dataflow scheduling techniques are used to coordinate multioperator queries. By using these techniques, it is possible to control the execution of very complex queries with minimal coordination. The design of the Gamma software is described and a thorough performance evaluation of the iPSC/s hypercube version of Gamma is presented.>

This paper presents the results of an initial performance evaluation of the Gamma database machine. In our experiments we measured the effect of relation size and indices on response time for selection, join, and aggregation queries, and single-tuple updates. A Teradata DBC/1012 database machine of similar size is used as a basis for interpreting the results obtained. We also analyze the performance of Gemma relative to the number of processors employed and study the impact of varying the memory size and disk page size on the execution time of a variety of selection and join queries. We analyze and interpret the results of these experiments based on our understanding of the system hardware and software, and conclude with an assessment of the strengths and weaknesses of Gamma.