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).

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.

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.

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.

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.

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.

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.

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.

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 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 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.>

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...

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.>

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.>

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.