## Publications of USC DataBase Lab.

You can use 'find' function with keyword or authors to search a paper. Papers are sorted in descending chronological order.
1. Shahram Ghandeharizadeh, Marwan Almaymoni, Haoyu Huang
Rejig: A Scalable Online Algorithm for Cache Server Configuration Changes.
USC Database Laboratory Technical Report Number 2018-05.

Abstract: A cache server configuration describes assignment of data fragments to cache manager instances (CMIs). This assignment may change by a load balancer that migrates fragments or an auto-scaling component that either inserts or removes CMIs. Such changes may generate stale cache entries. Rejig is a scalable online epidemic algorithm that manages configuration changes while providing read-after-write consistency. It employs clients to propagate configuration changes to one another without communicating directly. This enables Rejig to scale and support diverse application classes including those with mobile clients accessing the caching layer. When clients have intermittent network connectivity, Rejig updates their cached configuration to the latest with no performance impact on either the cache servers or other clients.
2. Shahram Ghandeharizadeh and Hieu Nguyen
A Comparison of Two Cache Augmented SQL Architectures.
USC Database Laboratory Technical Report Number 2018-04.

Abstract: Cloud service providers augment a SQL database management system with a cache to enhance system performance for workloads that exhibit a high read to write ratio. These in-memory caches provide a simple programming interface such as get, put, and delete. Using their software architecture, different caching frameworks can be categorized into Client-Server (CS) and Shared Address Space (SAS) systems. Example CS caches are memcached and Redis. Example SAS caches are Java Cache standard and its Google Guava implementation, Terracotta BigMemory and KOSAR. How do CS and SAS architectures compare with one another and what are their tradeoffs? This study quantifies an answer using BG, a benchmark for interactive social networking actions. In general, obtained results show SAS provides a higher performance with write policies playing an important role.
3. Shahram Ghandeharizadeh, Yazeed Alabdulkarim, Hieu Nguyen
RangeQC: A Framework for Caching Range Predicate Query Results
USC Database Laboratory Technical Report Number 2018-03.

Abstract: Range predicates are important to many workloads and are supported by both SQL and NoSQL data stores. This study presents RangeQC, a caching framework to expedite processing of range predicates. RangeQC is a framework that scales to a large number of cache servers. It is configurable with alternative data stores, provides read-after-write consistency and supports write-around, write-through, and write-back policies. In addition to presenting its design principles and an implementation for use in a data center, we evaluate RangeQC with both MySQL and MongoDB. Obtained results demonstrate superiority of a data store using RangeQC as long as the size of result set produced by a range predicate is small. A surprising find is the superiority of RangeQC with write-heavy workloads.
4. Yazeed Alabdulkarim, Marwan Almaymoni, Shahram Ghandeharizadeh, Haoyu Huang, Hieu Nguyen
Testing Database Applications with Polygraph
USC Database Laboratory Technical Report Number 2018-02.

Abstract: Diverse applications implement read and write {\em transactions} using a data store. Testing whether transactions of database applications provide strong consistency is challenging. 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.
5. Yazeed Alabdulkarim, Sumita Barahmand, Shahram Ghandeharizadeh
BG: A Scalable Benchmark for Interactive Social Networking Actions
USC Database Laboratory Technical Report Number 2018-01.

Abstract: BG is a benchmark that rates a data store for processing interactive social networking actions such as view a member profile and extend a friend invitation to a member. It elevates the amount of stale, inconsistent, and erroneous (termed unpredictable) data produced by a data store to a first class metric, quantifying it as a part of the benchmarking phase. It summarizes the performance of a data store in one metric, Social Action Rating (SoAR). SoAR is defined as the highest throughput provided by a data store while satisfying a pre-specified service level agreement, SLA. To rate the fastest data stores, BG scales both vertically and horizontally, generating a higher number of requests per second as a function of additional CPU cores and nodes. This is realized using a shared-nothing architecture in combination with two multi-node execution paradigms named Integrated DataBase and Disjoint DataBase. An evaluation of these paradigms shows the following tradeoffs. While the Disjoint DataBase scales superlinearly as a function of nodes, it may not evaluate data stores that employ client-side caching objectively. Integrated DataBase provides two alternative execution paradigms, Retain and Delegate, that might be more appropriate. However, they fail to scale as effectively as Disjoint DataBase. We show elements of these two paradigms can be combined to realize a hybrid framework that scales almost as effectively as Disjoint DataBase while exercising the capabilities of certain classes of data stores as objectively as Integrated DataBase.
6. Yazeed Alabdulkarim, Marwan Almaymoni, Shahram Ghandeharizadeh
Polygraph
USC Database Laboratory Technical Report Number 2017-02.

Abstract: Polygraph is a tool to quantify system behavior that violates serial execution oftransactions. It is a plug-n-play framework that includes visualization tools to em-power an experimentalist to (a) quickly incorporate Polygraph into an existing appli-cation or benchmark and (b) reason about anomalies and the transactions that producethem. We demonstrate Polygraph’s ability to plug-in to existing benchmarks includingTPC-C, SEATS, TATP, YCSB, and BG. In addition, we show Polygraph processestransaction log records in real-time and characterize its scalability characteristics.
7. Shahram Ghandeharizadeh, Haoyu Huang, Hieu Nguyen
Teleporting Failed Writes with Cache Augmented DataStores
USC Database Laboratory Technical Report Number 2017-01.

Abstract: Cache Augmented Data Stores enhance the performance of workloads that exhibita high read to write ratio by extending a persistent data store (PStore) with a cache.When the PStore is unavailable, today’s systems result infailedwrites. With the cacheavailable, we propose TARDIS, a family of techniques that teleport failed writes bybuffering them in the cache and persisting them once the PStore becomes available.TARDIS preserves consistency of the application reads and writes by processing themin the context of buffered writes. Given a fixed amount of memory, variants of TARDISmay store a different amount of buffered writes. We quantify this using the popularmemcached and Redis in-memory key-value stores.
8. Yazeed Alabdulkarim, Marwan Almaymoni, Ziwen Cao, Shahram Ghandeharizadeh, Hieu Nguyen, Lingnan Song
A Comparison of Host-Side and Application-Side Caches
USC Database Laboratory Technical Report Number 2016-01, Proceedings of the ICDE Workshop on Cloud Data Management (CloudDM), Helsinki, Finland, May 2016.

Abstract: Person-to-person cloud service providers such as Facebook use Host-side (HsC) and Application-side (AsC) caches to enhance performance. Each cache can be deployed either by itself or with the other. We quantify the tradeoff associated with these alternatives using both a read-heavy and a write-heavy workload. Obtained results show HsC provides significant benefit for I/O intensive workloads, e.g., read-heavy workloads when the application working set does not fit in memory. AsC is most suitable for those workloads that fully utilize the CPU of the server hosting the database management system. For some workloads, the performance enhancement observed with the two caches deployed together is several folds higher than the sum of the performance benefit realized by each cache.
9. Shahram Ghandeharizadeh, Jai Menon, Gary Kotzur, Sujoy Sen, and Gaurav Chawla
Host Side Caching: Solutions and Opportunities
USC Database Laboratory Technical Report Number 2015-02, Proceedings of the IEEE 12th International Baltic Conference on Databases and Information Systems (DB&IS), Riga, Latvia, July 2016.

Abstract: Host side caches use a form of storage faster than disk and less expensive than DRAM to deliver the speed demanded by data intensive applications. Today, this form of storage is NAND Flash, complementing a disk-based solution. A host side cache may integrate into an existing application seamlessly. This may be realized by using an infrastructure component (such as a storage stack middleware or the operating system) to intercept the application read and write requests for disk pages, populate the flash cache with disk pages, and use the flash to service read and write requests intelligently. This study provides an overview of host side caches, an analysis of its overhead and costs to justify its use, alternative architectures including the use of the emerging Non Volatile Memory (NVM) for the host-side cache, and future research directions. We show results using Dell's host-side caching solution named Fluid Cache. It was built to improve the performance of OLTP workloads. However, our results using a social networking benchmark named BG shows that Fluid Cache also enhances the performance of social networking workloads anywhere from a factor of 3.6 to 18.
10. S. Ghandeharizadeh, S. Irani, and J. Lam
Memory Hierarchy Design for Caching Middleware in the Age of NVM
USC Database Laboratory Technical Report Number 2015-01.

Abstract: Advances in storage technology have introduced Non-Volatile Memory, NVM, as a new storage medium. NVM, along with DRAM, NAND Flash, and Disk present a system designer with a wide array of options in designing caching middleware. This paper provides a systematic way to use knowledges about the frequencies of read and write requests to individual data items in order to determine the optimal cache configuration given a fixed budget. The approach introduced in this paper incorporates the characteristics of each type of memory to answer key design questions such as: how much will an increase in budget improve expected retrieval/update times? If it is desirable to limit the number of different types of memory in a cache, then which types of memory should be used for a particular budget and database size? When is it advantageous to store multiple copies of data objects in order to quickly recover from a memory failure? The cache configuration problem is modeled as an instance of the Multiple Choice Knapsack Problem (MCKP). Although MCKP is NP-complete, its linear programming relaxation is efficiently solvable and can be used to closely approximate the optimal solution. We use an algorithm for MCKP to evaluate design trade-offs in the context of a memory hierarchy for a Key-Value Store (e.g., memcached) as well as a host-side cache (e.g., Flashcache) to store disk pages. The results show selective replication is appropriate with certain failure rates. With a slim failure rate, tiering of data across the different storage media that constitute the cache is superior to replication.
11. S. Irani, J. Lam, and S. Ghandeharizadeh
Cache Replacement with Memory Allocation
USC Database Laboratory Technical Report Number 2014-12, Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments, ALENEX 2015, San Diego, CA, USA, January 5, 2015.

Abstract: 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.
12. S. Barahmand, S. Ghandeharizadeh, and J. Li
On Scalability of Two NoSQL Data Stores for Processing Interactive Social Networking Actions
USC Database Laboratory Technical Report Number 2014-11.

Abstract: This paper quantifies the scalability of a document store named MongoDB and an extensible store named HBase for processing simple operations using a social networking benchmark named BG (www.bgbenchmark.org). We report on the vertical and the horizontal scalability of both data stores. We quantify speedup and scaleup characteristics of each data store’s Social Action Rating (SoAR). SoAR is the highest observed throughput with a data store while satisfying a Service Level Agreement (SLA) such as 95% of requests observing a response time of 100 milliseconds or faster. While the speedup experiments maintain a fix sized social graph and vary the number of nodes, the scaleup experiments vary both the size of the social graph and the number of nodes proportionally. A system provides a superlinear SoAR speedup as a function of the number of nodes when it transitions from fully utilizing its disk bandwidth to fully utilizing either its CPU cores or network bandwidth. The speedup and scaleup of both data stores is limited with a resource such as the network interface card of one to three nodes becoming fully utilized and dictating the SoAR of a many (12) node deployment. One may configure MongoDB to use replicas of shards, enhancing its speedup characteristics and incurring a very small amount of unpredictable data with workloads consisting of writes.
13. S. Ghandeharizadeh, R. Boghrati and S. Barahmand
An Evaluation of Alternative Physical Graph Data Designs for Processing Interactive Social Networking Actions.
USC Database Laboratory Technical Report Number 2014-10. Appeared in the Sixth TPC Technology Conference on Performance Evaluation & Benchmarking (TPCTC), Hangzhou, China, September 2014.

Abstract: This study quantifies the tradeoff associated with alternative physical representations of a social graph for processing interactive social networking actions. We conduct this evaluation using a graph data store named Neo4j deployed in a client-server (REST) architecture using the BG benchmark. In addition to the average response time of a design, we quantify its SoAR defined as the highest observed throughput given the following service level agreement: 95% of actions to observe a response time of 100 milliseconds or faster. For an action such as computing the shortest distance between two members, we observe a tradeoff between speed and accuracy of the computed result. With this action, a relational data design provides a significantly faster response time than a graph design. The graph designs provide a higher SoAR than a relational one when the social graph includes large member profile images stored in the data store.
14. S. Barahmand and S. Ghandeharizadeh
On Expedited Rating of Data Stores.
USC Database Laboratory Technical Report Number 2014-09, In the Springer Transactions on Large-Scale Data and Knowledge-Centered Systems XXV, LNCS 9620, February 2016.

Abstract: To rate a data store is to compute a value that describes the performance of the data store with a database and a workload. A common performance metric of interest is the highest throughput provided by the data store given a pre-specified service level agreement such as 95% of requests observing a response time faster than 100 milliseconds. This is termed the action rating of the data store. This paper presents a framework consisting of two search techniques with slightly different characteristics to compute the action rating. With both, to expedite the rating process, the framework employs agile data loading techniques and strategies that reduce the duration of conducted experiments. We show these techniques enhance the rating of a data store by one to two orders of magnitude. The rating framework and its optimization techniques are implemented using a social networking benchmark named BG.
15. S. Ghandeharizadeh and J. Yap
SQL Query to Trigger Translation: A Novel Transparent Consistency Technique for Cache Augmented SQL Systems.
USC Database Laboratory Technical Report Number 2014-08.

Abstract: Organizations enhance the velocity of simple operations that read and write a small amount of data from big data by extending a SQL system with a key-value store (KVS). The resulting system is suitable for workloads that issue simple operations and exhibit a high read to write ratio, e.g., interactive social networking actions. A popular distributed in-memory KVS is memcached in use by organizations such as Facebook and YouTube.

This study presents SQL query to trigger translation (SQLTrig) as a novel transparent consistency technique that maintains the key-value pairs of the KVS consistent with the tabular data in the relational database management system (RDBMS). SQLTrig provides physical data independence, hiding the representation of data (either as tabular or key-value) from the application developers and their software. Software developers are provided with the SQL query language and observe the performance enhancements of a KVS without authoring additional software. This simplifies software complexity to expedite its development life cycle. We present performance results to show SQLTrig provides a performance comparable to a non-transparent consistency technique where a developer extends the application software to maintain key-value pairs consistent with the tabular data.
16. S. Ghandeharizadeh, S. Irani, J. Lam, J. Yap and H. Nguyen
CAMP: A Cost Adaptive Multi-Queue Eviction Policy for Key-Value Stores.
USC Database Laboratory Technical Report Number 2014-07. In the Proceedings of the ACM/IFIP/USENIX Middleware Conference, Bordeaux, France, December 2014.

Abstract: 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 dif- ferent access patterns, key-value sizes, and varying costs for each key-value pair. CAMP is an approximation of the Greedy Dual Size algorithm that can be implemented as efficiently as LRU. In particular, CAMP's eviction policies are as effective as those of GDS but require only a small frac- tion of the updates to an internal data structure in order to make those decisions. 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 avail- able memory across competing applications. We compare CAMP with both LRU and an alternative that requires hu- man 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 outperform- ing both LRU and the pooled alternative. We also present results from an implementation of CAMP using Twitter's version of memcached.
17. S. Ghandeharizadeh, J. Yap and H. Nguyen
Strong Consistency in Cache Augmented SQL Systems.
USC Database Laboratory Technical Report Number 2014-06. A shoter version appeared in the Proceedings of the ACM/IFIP/USENIX Middleware Conference, Bordeaux, France, December 2014.

Abstract: 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.
18. S. Barahmand and S. Ghandeharizadeh
Benchmarking Correctness of Operations in Big Data Applications.
USC Database Laboratory Technical Report Number 2014-05. A shorter version of this paper appeared in the IEEE MASCOTS, Paris, France, September 2014.

Abstract: 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.
19. S. Ghandeharizadeh and A. Mutha
An Evaluation of the Hibernate Object-Relational Mapping for Processing Interactive Social Networking Actions.
USC Database Laboratory Technical Report Number 2014-04. In Proceedings of the 16th ACM International Conference on Information Integration and Web-based Applications and Services.

Abstract: 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.
20. J. Yap
Transparent Consistency in Cache Augmented Database Management Systems.
Ph.D. thesis, Computer Science Department, USC, 2014. USC Database Laboratory Technical Report Number 2014-03.

Abstract: Cache Augmented Database Management Systems (CADBMSs) enhance the performance of simple operations that exhibit a high read to write ratio, e.g., interactive social networking actions. They are realized by extending a data store such as a Relational Database Management Systems (RDBMS) with a Key Value Store (KVS). At the time of writing, memcached is a popular in-memory KVS in use by a number of Internet service providers such as Facebook, YouTube, Wikipedia and others.

A key insight of CADBMSs is that query result lookup using the KVS is significantly faster than query processing using the RDBMS. A challenge is how to maintain these query results consistent in the presence of updates to the RDBMS. Today’s CADBMS solutions require a developer to design, implement, debug, and maintain software to address this challenge. This dissertation presents novel design decisions to realize physical data independence that hides the details of the storage structure (KVS or RDBMS) from applications and their developers. These designs simplify the complexity of application software to expedite their development life cycle.

The proposed designs can be categorized into two groups. The first group prevents race conditions that cause the KVS to produce stale data. Our primary contribution here is the IQ framework and its simple programming model that employs Inhibit (I) and Quarantine (Q) leases to provide strong consistency. We describe the compatibility of the leases when the KVS is either invalidated or refreshed in the presence of updates to the RDBMS.

The second group includes transparent techniques that invalidate the key-value pairs of the KVS in the presence of updates to the RDBMS. Our primary contribution is the SQL Query to Trigger translation (SQLTrig) technique. It provides the application developers with the SQL query language and observes the performance enhancements of a KVS without requiring additional software. It intercepts the queries issued by an application and authors software in the form of triggers that describes the template of the query. It registers these triggers with the RDBMS prior to inserting the query and its result set as a key-value pair in the KVS. An insert, delete, update command to the RDBMS invokes the trigger to compute the query (key) whose result set (value) has changed. The trigger invalidates this key-value pair from the KVS in a transactional manner.

We describe a software prototype that embodies both the SQLTrig technique and the IQ framework. We use a social networking benchmark to compare this prototype with a non-transparent consistency technique where the developer extends the application software to maintain key-value pairs consistent with the relational data. Obtained results demonstrate that both provide comparable performance.
21. S. Barahmand
Benchmarking Interactive Social Networking Actions.
Ph.D. thesis, Computer Science Department, USC, 2014. Best 2014 dissertation award in Computer Science, USC Viterbi School of Engineering. USC Database Laboratory Technical Report Number 2014-02.

Abstract: Social networking sites such as Google+, Facebook, Twitter and LinkedIn, are cloud service providers for person to person communications. There are different approaches to building these sites ranging from SQL to NoSQL and NewSQL, Cache Augmented SQL, graph databases and others. Some provide a tabular representation of data while others offer alternative models that scale out. Some may sacrifice strict ACID (Atomicity, Consistency, Isolation, Durability) properties and opt for BASE (Basically Available, Soft-state, Eventual consistency) to enhance performance. Independent of a qualitative discussion of these approaches and their merits, a key question is how do these systems compare with one another quantitatively? This dissertation investigates the viability of a benchmark to address this question.

Our primary contribution is the design and implementation of a novel benchmark for interactive social networking actions named BG (http://bgbenchmark.org). BG’s design decisions are as follows: First, it rates the performance of a system for processing interactive social networking actions by computing two values: Socialites and Social Action Rating (SoAR) using a pre-specified Service Level Agreement, SLA. An example SLA may require 95% of issued requests to observe a response time faster than 100 milliseconds. Second, BG elevates the amount of unpredictable data produced by a solution to a first class metric, including it as a key component of the SLA (similar to the average response time) and quantifying it as a part of the benchmarking process. It also computes the freshness confidence to characterize the behavior of a weak consistency technique. Third, BG’s generated workload is characterized by reads and writes of a very small amount of data from big data. Fourth, BG is a modular, extensible framework that is agnostic to its underlying data store. Fifth, BG employs a logical partitioning of data to scale both vertically and horizontally to thousands of nodes. This is essential for evaluating scalable installations consisting of thousands of nodes. Finally, BG includes a visualization tool to empower an evaluator to monitor an in-progress benchmark and identify bottlenecks.

BG’s possible use cases are diverse. One may use BG to compare and contrast various data stores with one another, characterize tradeoffs associated with alternative physical representations of data, or quantify the behavior of a data store in the presence of various failures (either CP or AP of the CAP theorem) among the others. This dissertation demonstrates use of BG in two contexts. First, to rate an industrial strength relational database management system and a document store, quantifying their performance tradeoffs. This analysis includes the use of a middle tier cache (memcached) and its impact on the performance of each system. Second, to gain insight into alternative design decisions for implementing a social action by characterizing their behavior with different social graphs and system loads. BG’s proposed framework is quite novel and opens several new research directions that benefit the systems research community.
22. S. Barahmand, S. Ghandeharizadeh, D. Montauk
Extensions of BG for Testing and Benchmarking Alternative Implementations of Feed Following.
USC Database Laboratory Technical Report Number 2014-01. A version of this paper appeared in the SIGMOD Workshop on Reliable Data Services and Systems (RDSS), June 23, 2014, Snowbird, UT.

Abstract: Social networking sites are cloud service providers for person-to-person communication. Feed following is a key service where a member follows activity streams of other members and entities such as fan pages. A follower receives a personalized fusion of streams produced by those followed. There are alternative definitions of the quality of feed displayed to a follower that might be impacted by the highly variable fan-out of the follows graphs. This makes both an implementation of feed following and a validation of its correctness as big data challenges.

This paper presents extensions of an interactive social networking benchmark named BG with feed following actions. An implementation of these actions is agnostic to a data store and can be customized for different data models and designs. We illustrate this extensibility feature of BG by evaluating two alternative implementations of feed following using an industrial strength relational database management system and a document store.
23. S. Ghandeharizadeh and S. Barahmand.
A Mid-Flight Synopsis of the BG Social Networking Benchmark.
USC Database Laboratory Technical Report Number 2013-03. A version of this paper appeared in the Fourth Workshop on Big Data Benchmarking (4th WBDB), October 9-10, 2013, San Jose, CA.

Abstract: BG is a benchmark that rates the performance of a data store for processing interactive social networking actions such as view a member's profile, invite a member to be friends, accept a friend request, and others. It is motivated by a proliferation of data stores from a variety of academic and industrial contributors including social networking companies, e.g., Voldemort by LinkedIn. BG is designed to provide a system architect with insights into alternative design principles such as the use of a weak consistency technique instead of a strong one, different physical data models such as relational and JSON, factors that impact vertical and horizontal scalability of a data store, the consistency versus availability tradeoff in the CAP theorem, among others. While BG is a recently introduced benchmark (less than a year old as of this writing), it combines elements of maturer benchmarks and extends them to simplify its use by the practitioners and experimentalists. This paper provides a synopsis of the BG benchmark by identifying its strengths and limitations in our daily use cases. The identified limitations shape our research activities and the obtained solutions shall be incorporated into future BG releases. Thus, this workshop paper is a mid-flight glimpse into our current research efforts with BG.
24. J. Yap, S. Ghandeharizadeh and S. Barahmand.
An Analysis of BG’s Implementation of the Zipfian Distribution.
USC Database Laboratory Technical Report Number 2013-02.

25. S. Barahmand and S. Ghandeharizadeh.
Expedited Benchmarking of Social Networking Actions with Agile Data Load Techniques.
USC Database Laboratory Technical Report Number 2013-01. A shorter version of this paper appeared in the ACM International Conference on Information and Knowledge Management (CIKM), San Francisco, Oct 2013.

Abstract: To benchmark and rate a data store, one might be required to repeatedly load the same benchmark database onto the data store. This may constitute a significant portion of the benchmarking process. This paper focuses on the BG benchmark (www.bgbenchmark.org) and presents three techniques to expedite loading of its database. These include generating the disk image of the database once and re-using it many times, restoring the updated data items to their original value in between experiments, and maintaining in-memory state of the database across different experiments to avoid repeated loading of the database all together. BG may use a hybrid of the proposed techniques when evaluating a data store. When evaluating MongoDB with a million member BG database, we show these techniques expedite BG's rating of MongoDB 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 will be much faster, in the order of hours (less than 1 day).
26. S. Barahmand, S. Ghandeharizadeh and J. Yap.
A Comparison of Two Physical Data Designs for Interactive Social Networking Actions.
USC Database Laboratory Technical Report Number 2012-08. A shorter version of this paper appeared in the ACM International Conference on Information and Knowledge Management (CIKM), San Francisco, Oct 2013.

Abstract: This paper compares the performance of an SQL solution using 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.
27. S. Ghandeharizadeh and J. Yap.
Cache Augmented Database Management Systems.
USC Database Laboratory Technical Report Number 2012-07. A shorter version of this paper appeared in the Third ACM SIGMOD Workshop on Databases and Social Networks (DBSocial), Co-located with ACM SIGMOD 2013, June 2013.

Abstract: Cache Augmented Database Management Systems, CADBMSs, enhance the velocity of simple operations that read and write a small amount of data from big data. They are most suitable for those applications with workloads that exhibit a high read to write ratio, e.g., interactive social networking actions. This study surveys state of the art with CADBMSs and presents physical data independence as the next step in their evolution. We detail the requirements of this evolution, technological trends and software practices, and our research efforts in this area.
28. S. Barahmand and S. Ghandeharizadeh.
BG: A Benchmark to Evaluate Interactive Social Networking Actions.
USC Database Laboratory Technical Report Number 2012-06. A shorter version of this paper appeared in the biennial Conference on Innovative Data Systems Research (CIDR), Asilomar, California, January, 2013.

Abstract: BG is a social networking benchmark that rates a data store using a pre-specified service level agreement, SLA. An example SLA may require 95% of issued actions to observe a response time faster than 100 milliseconds. BG computes two different ratings named SoAR and Socialites. In addition, it elevates the amount of unpredictable data produced by a data store to a first class metric, including it as a key component of the SLA and quantifying it as a part of the benchmarking process.

One may use BG for a variety of purposes ranging from comparing different data stores with one another, evaluating alternative physical data organization techniques given a data store, quantifying the performance characteristics of a data store in the presence of failures (either CP or AP in CAP theorem), among others. This study illustrates BG's first use case, comparing a document store with an industrial strength relational database management system (RDBMS) deployed either in stand alone mode or augmented with memcached. No one system is superior for all BG actions. However, when considering a mix of actions, the memcached augmented RDBMS produces higher ratings.
29. S. Ghandeharizadeh and J. Yap.
Materialized Views and Key-Value Pairs in a Cache Augmented SQL System: Similarities and Differences.
USC Database Laboratory Technical Report Number 2012-05.

Abstract: In the era of no one-size-fits-all", organizations extend a relational database management system (RDBMS) with a key-value store (KVS) to enhance the velocity of big data applications with a high read to write ratio. A popular in-memory KVS is memcached in use by well known Internet destinations such as YouTube and Wikipedia. Its simple interface provides put, get, and delete of key-value pairs computed using tabular data. A key question is how do these key-value pairs compare with materialized views in a RDBMS. This paper provides an answer to this question.
30. S. Barahmand and S. Ghandeharizadeh.
D-Zipfian: A Decentralized Implementation of Zipfian.
USC Database Laboratory Technical Report Number 2012-04. A shorter version of this paper appeared in the Sixth International Workshop on Testing Database Systems (DBTest), Co-located with ACM SIGMOD 2013, June 24, 2013.

Abstract: Zipfian distribution is used extensively to generate synthetic workloads to evaluate systems. With the growing processing capability of systems, a centralized single node implementation of Zipfian may become a bottleneck. This paper presents a decentralized, parallel implementation of Zipfian named D-Zipfian. D-Zipfian employs multiple nodes that reference data items independently. This scalable technique strives to produce a distribution that is independent of its degree of parallelism, i.e., number of employed nodes. Moreover, it supports heterogeneous nodes that reference data items at different rates. We characterize the behavior of D-Zipfian with different degrees of parallelism and skewness, population sizes, and heterogeneity of its employed nodes.
31. S. Barahmand and S. Ghandeharizadeh.
A Data Aware Admission Control Technique for Social Live Streams (SOLISs).
USC Database Laboratory Technical Report Number 2012-03. A shorter version of this paper appeared in the IEEE International Symposium on Multimedia (ISM 2012), Irvine, California, December 10-12, 2012.

Abstract: 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 SOLISs, 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. We use analytical models and simulation studies to quantify the tradeoff associated with DA-AdmCtrl.
32. S. Ghandeharizadeh, J. Yap, and S. Barahmand.
COSAR-CQN: An Application Transparent Approach to Cache Consistency.
USC Database Laboratory Technical Report Number 2012-02. A shorter version of this paper appeared in the Twenty First International Conference On Software Engineering and Data Engineering, Los Angeles, California, June 27-29, 2012. Recipient of best paper award.

Abstract: ACache managers speed up the performance of data intensive applications whose workload is dominated by queries. An example is memcached which is in use by very large well-known sites such as Facebook. A key challenge of such systems is how to maintain the state of the cache consistent with that of the database in the presence of updates. With SQL based database management systems (DBMSs) that support query change notification mechanism, one possible approach would require the cache manager to a) register queries used to compute a key-value pair with the DBMS to subscribe for notifications when the query result sets change, and b) delete the cached key-value pair(s) once notified of a change by the DBMS. This approach is independent of how the application updates the database, eliminating application specific software for cache consistency. This reduces the complexity of the application software and minimizes the software development cycle associated with designing, developing, and maintaining software in support of cache consistency. This paper presents the design and implementation of this approach in a cache manager named COSt AwaRe, COSAR. This approach is named Continuous Query change Notification, CQN. It is one of several cache consistency techniques implemented in COSAR. We compare CQN with these alternatives, quantifying its strengths and limitations.
33. S. Ghandeharizadeh and J. Yap.
Gumball: A Race Condition Prevention Technique for Cache Augmented SQL Database Management Systems.
USC Database Laboratory Technical Report Number 2012-01. A shorter version of this paper appeared in the Second ACM SIGMOD Workshop on Databases and Social Networks (DBSocial), Scottsdale, Arizona, May 2012. Recipient of best student paper award.

Abstract: Query intensive applications augment a Relational Database Management System (RDBMS) with a middle-tier cache to enhance performance. An example is memcached in use by very large well known sites such as Facebook. In the presence of updates to the normalized tables of the RDBMS, invalidation based consistency techniques delete the impacted key-value pairs residing in the cache. A subsequent reference for these key-value pairs observes a cache miss, re-computes the new values from the RDBMS, and inserts the new key-value pairs in the cache. These techniques suffer from race conditions that result in cache states that produce stale data. The Gumball Technique (GT) addresses this limitation by preventing race conditions. Experimental results show GT enhances the accuracy of an application hundreds of folds and, in some cases, may reduce system performance slightly.
34. S. Barahmand and S. Ghandeharizadeh.
Chase Display of Social Live Streams (SOLISs).
In Third ACM SIGMM Workshop on Social Media (WSM), Scottsdale, Arizona, November 29th 2011.

Abstract: Advances in networking, processing, and mass storage devices have enabled social live streams (SOLISs) and their chase display. This paper focuses on public SOLISs and presents the user interface of RAYS and its system architecture. In addition, we present several novel memory management techniques that produce summary data to minimize the likelihood of cache misses. One technique, named Data-Aware CLRU (DA-CLRU), stands out for both enhancing the cache hit rate and utility of data. This technique is parallelizable and ideal for multi-core CPUs.
35. S. Barahmand and S. Ghandeharizadeh.
RAYS: Recall All You See.
Grace Hopper Celebration of Women in Computing, Oregon, November 8th 2011.
36. S. Barahmand, S. Ghandeharizadeh, A. Ojha, and J. Yap.
Three Highly Available Data Streaming Techniques and Their Tradeoffs.
In ACM Workshop on Advanced Video Streaming Techniques for Peer-to-Peer Networks and Social Networking, Florence, Italy, October 2010.

Abstract: The Recall All Your Senses (RAYS) project envisions a social networking system that empowers its users to store, retrieve, and share data produced by streaming devices. An example device is the popular Apple iPhone that produces continuous media, audio and video clips. This paper focuses on the stream manager of RAYS, RAYS-SM, and its peer-to-peer overlay network. For a request that streams data from a device, RAYS-SM initiates $\alpha+1$ streams in order to minimize loss of data in the presence of node failures in its network. We present the design of 3 data availability techniques, quantifying their throughput and data availability characteristics. These two metrics highlight the tradeoff between how much resources a technique uses during normal mode of operation in order to minimize loss of data.
37. S. Ghandeharizadeh, J. Yap, S. Kalra, J. Gonzalez, E. Keshavarzian, I. Shvager, F. Carino, E. Alwagait
COSAR: A Precis Cache Manager
USC Database Laboratory Technical Report Number 2009-03.

Abstract: Precis is a class of cache managers that stores and retrieves the final results of a time consuming operation that may use data from disparate sources. Examples include the results of an aggregate query, serialized instances of a data structure that contains results of different queries and computations used to generate a dynamic HTML page, etc. It is a high throughput, low latency key-value cache manager designed to scale a large data intensive web application. Example systems include memcached and COSt AwaRe (COSAR) cache manager. In this paper, we present the implementation details of COSAR and its variants of LRU, LRU-2, and GreedyDual-Size cache replacement techniques. We compare COSAR with memcached that employs the classical LRU replacement technique, showing the merits of its proposed replacement techniques.
38. S. Ghandeharizadeh, S. Shayandeh, Y. Altowim
An Analysis of Two Cooperative Caching Techniques for Streaming Media in Residential Neighborhoods
USC Database Laboratory Technical Report Number 2009-02. A shorter version appeared in Proceedings of the 15th International Conference on Distributed Multimedia Systems (DMS 2009), San Francisco Bay, CA, September 2009.

Abstract: Domical is a recently introduced cooperative caching technique for streaming media (audio and video clips) in wireless home networks. It employs asymmetry of the available link bandwidths to control placement of data across the caches of different devices. A key research question is what are the merits of this design decision. To answer this question, we compare Domical with DCOORD, a cooperative caching technique that ignores asymmetry of network link bandwidths in its caching decisions. We perform a qualitative and quantitative analysis of these two techniques. The quantitative analysis focuses on startup latency defined as the delay incurred from when a device references a clip to the onset of its display. Obtained results show Domical enhances this metric significantly when compared with DCOORD inside a wireless home network. The qualitative analysis shows DCOORD is a scalable technique that is appropriate for networks consisting of many devices. While Domical is not appropriate for such networks, we do not anticipate a home network to exceed more than a handful of wireless devices.
39. S. Ghandeharizadeh and S. Shayandeh.
A Comparison of Block-based and Clip-based Cooperative Caching Techniques for Streaming Media in Wireless Home Networks
USC Database Laboratory Technical Report Number 2009-01. A shorter version appeared in Proceedings of the International Conference on Wireless Algorithms, Systems, and Applications (WASA2009), Boston, MA, August 2009.

Abstract: Wireless home networks are widely deployed due to their low cost, ease of installation, and plug-and-play capabilities with consumer electronic devices. Participating devices may cache continuous media (audio and video clips) in order to reduce the demand for outside-the-home network resources and enhance the average delay incurred from when a user references a clip to the onset of its display (startup latency). In this paper, we focus on a home network consisting of a handful of devices configured with a mass storage device to cache data. A cooperative caching technique may manage the available cache space at the granularity of either a clip or individual blocks of a clip. The primary contribution of this paper is to evaluate these two alternatives using realistic specifications of a wireless home network, identifying
40. S. Ghandeharizadeh, A. Goodney, C. Sharma, C. Bissell, F. Carino, N. Nannapaneni, A. Wergeles, A. Whitcomb.
Taming the Storage Dragon: The Adventures of HoTMaN (Industrial Paper)
In Proceedings of the ACM-SIGMOD Conference, Providence, RI, June 2009.

Abstract: HoTMaN (HoT-standby MaNager) is a joint research and development 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. In the future, HoTMaN can be extended to migrate relational databases when a server reaches an autonomic threshold.
41. F. Parvini, D. McLeod, C. Shahabi, B. Navai, B. Zali, and S. Ghandeharizadeh.
An Approach to Glove-Based Gesture Recognition
In 13th International Conference on Human-Computer Iteraction, San Diego, CA, July 2009.

Abstract: Nowadays, computer interaction is mostly done using dedicated devices. But gestures are an easy mean of expression between humans that could be used to communicate with computers in a more natural manner. Most of the current research on hand gesture recognition for Human- Computer Interaction rely on either the Neural Networks or Hidden Markov Models (HMMs). In this paper, we compare different approaches for gesture recognition and highlight the major advantages of each. We show that gestures recognition based on the Bio-mechanical characteristic of the hand provides an intuitive approach which provides more accuracy and less complexity.
42. S. Ghandeharizadeh and S. Shayandeh.
An Evaluation of Three Domical Block Replacement Techniques for Streaming Media in Wireless Home Networks
USC Database Laboratory Technical Report Number 2008-06. A shorter version appeared in the Proceedings of the IEEE International Symposium on Multimedia (ISM2008), Berkeley, California, December 15-17, 2008.

Abstract: 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.
43. S. Ghandeharizadeh and S. Shayandeh.
Cache Replacement Techniques for Streaming Media in Wireless Home Networks
USC Database Laboratory Technical Report Number 2008-05.

Abstract: Wireless home networks are widely deployed due to their low cost, ease of installation, and plug-and-play capabilities with consumer electronic devices. Participating devices may cache continuous media (audio and video clips) in order to reduce the demand for outside-the-home network resources and improve the average delay incurred from when a user references a clip to the onset of its display (startup latency). In this paper, we focus on a home network consisting of a handful of devices. A device may manage its cache at the granularity of either a clip or individual blocks of a clip by employing either a clip-based or a block-based cache replacement technique. It may employ a technique in either stand-alone mode to enhance a local metric such as cache hit rate or make its state dependent on other devices in the home network to enhance a global metric such as average startup latency. These two variants are named greedy and cooperative, respectively. The primary contribution of this paper is to evaluate these alternatives using realistic specifications of a wireless home network. Our key finding is as follows. Our proposed cooperative block-based technique enhances startup latency when compared with clip-based alternatives. With multiple devices where each device acts greedy, clip-based caching is superior. In addition, we show our proposed block-based replacement policy materializes appropriate fraction of each clip across devices dynamically, eliminating the need to compute and place prefetch portions statically.
44. M. Carey, S. Ghandeharizadeh, K. Mehta, P. Mork, L. Seligman, S. Srivastava, and S. Thatte.
Semantically-Assisted Integration Query Editing in the AquaLogic Data Services Platform (Demo Paper).
USC Database Laboratory Technical Report Number 2008-04. Appeared in the Proceedings of the 2nd IEEE International Conference on Semantic Computing, Santa Clara, California, August 4-7, 2008.

Abstract: This demonstration shows how semantic schema matching technology is being incorporated into the BEA AquaLogic Data Services Platform. Specifically, it demonstrates how the manually-intensive task of authoring a correct and complete integration query is enhanced by semantic guidance. It also highlights the pluggable architecture used to incorporate semantic match knowledge into ALDSP by showing the ALDSP Query Map editor interoperating with the Harmony semantic matching engine from MITRE Corporation.
45. S. Ghandeharizadeh and S. Shayandeh.
Domical Cooperative Caching: A Novel Caching Technique for Streaming Media in Wireless Home Networks.
USC Database Laboratory Technical Report Number 2008-03. A shorter version appeared in the Proceedings of the 17th International Conference on Software Engineering and Data Engineering (SEDE)}, Los Angeles, California, June 30 to July 2, 2008.

Abstract: Wireless home networks have become pervasive and widely deployed due to their low cost, ease of installation, and plug-and-play capabilities with consumer electronic devices. Caching of continuous media (audio and video clips) across devices has a significant impact on the average startup latency, defined as the average delay incurred from when a user references a clip to the onset of its display. In this paper, we focus on a home network consisting of a handful of devices and present a novel cooperative caching technique named Domical. Domical controls the placement of clips across devices based on their popularity, minimizing the likelihood of bottleneck links forming in a mesh network. We compare Domical with its predecessor, named Cont-Coop, showing that it enhances average startup latency with those networks that provide a high degree of connectivity among devices.
46. S. Ghandeharizadeh, S. Shayandeh, and T. Helmi.
To Share or Not To Share Storage in Mesh Networks: A System Throughput Perspective.
USC Database Laboratory Technical Report Number 2008-02. A shorter version appeared in International Workshop on Data Management for Wireless and Pervasive Communication (DMWPC), Okinawa, Japan, March 25-28, 2008.

Abstract: While the cost per megabyte of storage is economical, sharing storage might be expensive because delivery of a clip occupying the shared storage requires bandwidth. This is especially true for mesh networks where devices are constrained by the radio-range and bandwidth of their wireless networking card. Assuming a device, termed a peer, is configured with a mass storage device, it may share either all, a fraction, or none of its storage. When a peer does not shares its storage, it stores clips with the objective to enhance a local criterion such as number of clip requests serviced using its mass storage device. When a peer shares its storage, it may store clips to optimize a global metric such as the total number of devices that may display their clips simultaneously, termed system throughput. Using this global metric, we show the following surprising result: the throughput of certain mesh networks is enhanced when peers do not share storage. By understanding these tradeoffs, one may design adaptable software to enable a peer to monitor its environment and decide to share or not to share its storage. We demonstrate the feasibility of such a design using a simulation study.
47. S. Ghandeharizadeh and S. Shayandeh.
Cooperative Caching Techniques for Continuous Media in Wireless Home Networks.
USC Database Laboratory Technical Report Number 2008-01. A shorter version appeared in First International ACM Conference on Ambient Media and Systems, Quebec City, Canada, February 11-14, 2008.

Abstract: With wide spread deployment of wireless home networks, management of data across devices is becoming increasingly important. This is especially true for continuous media (au- dio and video clips) because they are large in size and are streamed at a pre-speci¯ed rate to support a display free from disruptions and delays. Caching of clips across de- vices is an e®ective way to improve key quality of service (QoS) metrics including the fraction of requests serviced suc- cessfully when the home's connection to the outside infras- tructure is lost (data availability), number of devices that may stream and display their referenced clips simultaneously (throughput), and the average delay incurred from when a user references a clip to the onset of its display (average startup latency). In this paper, we focus on home networks consisting of a handful of devices and present a novel co- operative caching technique named Cont-Coop. Cont-Coop controls the content of participating caches based on the asymmetric bandwidth of wireless connections between de- vices. We compare this technique with an alternative that does not control the content of cooperative caches, show- ing Cont-Coop is superior when the access pattern to clips is skewed. In addition, we show cooperative techniques en- hance all the aforementioned QoS metrics when compared with a greedy caching technique.
48. M. Carey, S. Ghandeharizadeh, K. Mehta, P. Mork, L. Seligman, and S. Thatte.
AL$MONY: Exploring Semantically-Assisted Matching in an XQuery-Based Data Mapping Tool. USC Database Laboratory Technical Report Number 2007-02. International Workshop on Semantic Data and Service Integration (SDSI 2007), co-located with VLDB, Vienna, Austria, September 23, 2007. Abstract: In this paper, we describe an in-progress effort to augment the data integration capabilities of a service-oriented data integration product with the advanced matching capabilities of a knowledge-based schema matching workbench, thereby providing a guided, interactive, and “what”-oriented design environment for use by data architects and integration engineers. The data integration product is the BEA AquaLogic Data Services Platform, which provides a declarative, XML-based foundation for integrating and service-enabling heterogeneous enterprise data sources in order to deliver data services for use by SOA applications. The schema matching tool is the Harmony system from MITRE, a state-of-the-art prototype system that maintains a growing knowledge base of matching information and employs a composite matching architecture beneath a rich UI to guide the ranking and decision-making processes involved in schema matching. We motivate this work, review the capabilities of each of the systems, and sketch the architectural approach that we are taking to combining the two systems into a synergistic whole. 49. S. Ghandeharizadeh and S. Shayandeh. Greedy Cache Management Techniques for Mobile Devices. USC Database Laboratory Technical Report Number 2007-01. First International IEEE Workshop on Ambient Intelligence, Media, and Sensing (AIMS 07)}, co-located with International Conference on Data Engineering, Istanbul, Turkey, April 20, 2007. Abstract: Mobile devices are configured with one or more wireless cards that provide limited radio-range and unreliable transmission. These energy-constrained devices are configured with a fixed amount of storage. A device may set aside a fraction of its local storage as a cache to minimize use of the network when servicing requests, enhancing metrics such as startup latency and data availability. In this paper, we focus on a repository of continuous media (audio and video) clips and study several greedy cache management techniques and their cache hit rates. This metric reflects what percentage of requests for clips is serviced when a mobile device is disconnected from the network. The device becomes network detached due to factors such as residing in a densely populated geographical location with over committed network bandwidth or travels to geographical areas with no base station coverage. We investigate repositories of both equisized and variable-sized clips, identifying limitations of the current techniques. Our primary contribution is development of three novel techniques to address these limitations. They are adaptable and provide competitive cache hit rates. One technique, called Dynamic Simple, provides a higher cache hit rate and adapts faster to changing patterns of access to clips when compared with other techniques. 50. S. Ghandeharizadeh and G. Narasimhan. Challenges of a "What"-Oriented Framework for On-the-fly Integration of Biomedical Data. USC Database Laboratory Technical Report Number 2006-06. 51. S. Ghandeharizadeh, S. Gao, C. Gahagan, and R. Krauss. An On-Line Reorganization Framework for SAN File Systems. USC Database Laboratory Technical Report Number 2006-04. Shorter version appeared in the Tenth East-European Conference on Advances in Databases and Information Systems, Thessaloniki, Hellas, September 3-7, 2006. Abstract: While the cost per megabyte of magnetic disk storage is economical, organizations are alarmed by the increasing cost of managing storage. Storage Area Network (SAN) architectures strive to minimize this cost by consolidating storage devices. A SAN is a special-purpose network that interconnects different data storage devices with servers. While there are many definitions for a SAN, there is a general consensus that it provides access at the granularity of a block and is typically used for database applications. In this study, we focus on SAN switches that include an embedded storage management software in support of virtualization. We describe an On-line Re-organization Environment, ORE, that controls the placement of data to improve the average response time of the system. ORE is designed for a heterogeneous collection of storage devices. Its key novel feature is its use of time'' to quantify the benefit and cost of a migration. It migrates a fragment only when its net benefit exceeds a pre-specified threshold. We describe a taxonomy of techniques for fragment migration and employ a trace driven simulation study to quantify their tradeoff. Our performance results demonstrate a significant improvement in response time (order of magnitude) for those algorithms that employ ORE's cost/benefit feature. Moreover, a technique that employs bandwidth of all devices intelligently is superior to one that simply migrates data to the fastest devices. 52. S. Ghandeharizadeh, T. Helmi, T. Jung, S. Kapadia and S. Shayandeh. An Evaluation of Two Policies for Placement of Continuous Media in Multi-hop Wireless Networks. USC Database Laboratory Technical Report Number 2006-03. Shorter version appeared in the Twelfth International Conference on Distributed Multimedia Systems (DMS 2006), Grand Canyon, Aug 30-Sept 1, 2006. Abstract: This paper focuses on a greedy data placement strategy for a mesh network of peer-to-peer devices that collaborate to stream continuous media, audio and video clips. The greedy placement strategy, termed Simple, strives to maximize the number of references served by the local storage of a peer. We analyze two policies to realize this placement: Frequency-based and Byte-hit. The first sorts clips based on their access frequency, assigning the frequently accessed clips to each node. Byte-hit computes the frequency of access to each byte of a clip, sorts clips based on this value, and assigns those with the highest byte-hit value to each node. Both have the same complexity and almost identical implementations. A simulation study shows Byte-hit is superior to Frequency-based for two reasons. First, it maximizes the number of peers that can simultaneously display their referenced clips. Second, it is more robust to error in access frequencies. In all our experiments, Byte-hit performs almost identical to the optimal placement strategy. 53. A. Daskos, S. Ghandeharizadeh, and R. Shahriari. SkiPeR: A Family of Distributed Range Addressing Spaces for Peer-to-Peer Systems. USC Database Laboratory Technical Report Number 2006-01. Shorter version appeared in ISCA 15th International Conference on Software Engineering and Data Engineering, (SEDE-2006), LA, CA, July 6-8, 2006. Abstract: A relational database management system based on a peer-to-peer network must support both exact-match and range selection predicates efficiently. One approach to process range predicates is to design and implement a distributed range addressing space in support of decentralized routing of predicates, insertion and removal of peers. To route predicates in O(log N) with a N peer system, two alternative approaches have been proposed. The first, Skip Graphs, employs a hierarchical order-preserving structure on the peers and their assigned ranges. The second, PePeR, constructs multiple ranges per peer and controls their assignment across the peers intelligently. The primary contribution of this paper is SkiPeR, a general purpose technique that unifies Skip Graphs and PePeR. SkiPeR consists of two key parameters whose extreme settings correspond to Skip Graphs and PePeR. There are in-between parameter settings that are a tradeoff between the amount of state information maintained by each peer, continued routing of predicates in the presence of peer removal, and the number of hops required to route a predicate. A secondary contribution of this study is to quantify these tradeoffs. This enables a system designer to choose parameters settings that fit the requirements of an application and the characteristics of the underlying peer-to-peer network. 54. S. Ghandeharizadeh, E. Alwagait, and S. Manjunath. Proteus RTI: A Framework for On-the-fly Integration of Biomedical Web Services. USC Database Laboratory Technical Report Number 2006-05. Abstract: On-the-fly integration refers to scenarios where a user, say a neuroscientist, wants to integrate a Web Service immediately after discovering it. The challenge is to significantly reduce the required information technology skills to empower the user to focus on the domain-specific problem. Proteus RTI is a first step towards addressing this challenge. It includes a graphical interface to enable a user to register and integrate Web Services together. This paper emphasizes example uses of the system from a neuroscience perspective, providing a brief overview of the system and its one time implementation of optimization techniques. 55. S. Ghandeharizadeh, S. Kapadia and B. Krishnamachari. An Evaluation of Availability Latency in Carrier-based Vehicular Ad-Hoc Networks. USC Database Laboratory Technical Report Number 2006-02. Shorter version appeared in 5th ACM International Workshop on Data Engineering for Wireless and Mobile Access (MobiDE'06), Chicago, IL, June 25, 2006. Abstract: On-demand delivery of audio and video clips in peer-to-peer vehicular ad-hoc networks is an emerging area of research. Our target environment uses data carriers, termed zebroids, where a mobile device carries a data item on behalf of a server to a client thereby minimizing its availability latency. In this study, we quantify the variation in availability latency with zebroids as a function of a rich set of parameters such as car density, storage per device, repository size, and replacement policies employed by zebroids. Using analysis and extensive simulations, we gain novel insights into the design of carrier-based systems. Significant improvements in latency can be obtained with zebroids at the cost of a minimal overhead. These improvements occur even in scenarios with lower accuracy in the predictions of the car routes. Two particularly surprising findings are: (1) a naive random replacement policy employed by the zebroids shows competitive performance, and (2) latency improvements obtained with a simplified instantiation of zebroids are found to be robust to changes in the popularity distribution of the data items. 56. S. Ghandeharizadeh, and S. Kapadia. An Evaluation of Location-Demographic Replacement Policies for Zebroids. Shorter version appeared in IEEE Consumer Communications and Networking Conference, Las Vegas, NV, Jan 8-10, 2006. Abstract: 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. 57. M. Saxena, S. Kim, E. Alwagait, A. M. Khan, G. Burns, J. Su, A. G. Watts, and S. Ghandeharizadeh. Sangam: A Data Integration Framework for Studies of Stimulus-Circuitry-Gene Coupling in the Brain. Society of Neuroscience, Neuroscience 2005, Washington D.C., November 12-16, 2005. 58. S. Ghandeharizadeh, C. Papadopoulos, M. Cai, R. Zhou, and P. Pol. NAM: A Network Adaptable Middleware to Enhance Response Time of Web Services. In International Journal of Web Services Research (JSWR), Volume 2, Issue 4, October 2005. Abstract: Web Services are an emerging software technology that are based on the concept of "software and data as a service". Binary and XML are two popular encoding/decoding mechanisms for network messages. A Web Service may employ a loss-less compression technique, e.g., Zip, XMill, etc., to reduce message size prior to its transmission across the network, minimizing its transmission time. This saving might be outweighed by the overhead of compressing the output of a Web Service at a server and decompressing it at a client. The primary contribution of this paper is NAM, a middleware that strikes a compromise between these two factors in order to enhance response time. NAM decides when to compress data based on the available client and server processor speeds, and network characteristics. When compared with today's common practice to transmit the output of a Web Service uncompressed always, our experimental results show NAM either provides similar or significantly improved response times (at times more than 90% improvement) with Internet connections that offer bandwidths ranging between 80 to 100 Mbps. 59. S. Ghandeharizadeh, S. Kapadia, and B. Krishnamachari. Comparison of Replication Strategies for Content Availability in C2P2 Networks. In Sixth International Conference on Mobile Data Management(MDM'05), Ayia Napa, Cyprus, May 9-13, 2005. Abstract: 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. 60. R. Zimmermann and S. Ghandeharizadeh Highly Available and Heterogeneous Continuous Media Storage Systems. In IEEE Transactions on Multimedia, Volume 6, Number 6, 886-896, December 2004. Abstract: 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. 61. S. Ghandeharizadeh Science of Continuous Media Application Design in Wireless Networks of Mobile Devices. In Broadband Wireless Networking Symposium (BroadNets), San Jose, October 24, 2004. Abstract: Display of continuous media using self-organizing ad hoc networks of wireless communication systems will potentially be 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. 62. S. Ghandeharizadeh, S. Kapadia, and B. Krishnamachari. PAVAN: A Policy Framework for Availability in Vehicular Ad-Hoc Networks. In First ACM Workshop on Vehicular Ad Hoc Networks (VANET), Philadelphia, PA, October 1, 2004. Abstract: Advances in wireless communication, storage and processing are realizing next-generation in-vehicle entertainment systems. Even if hundreds of different video or audio titles are stored among several vehicles in an area, only a subset of these titles might be available to a given vehicle depending on its current location, intended path, and the dynamics of its ad-hoc network connectivity. The vehicle's entertainment system must somehow predictively determine which titles are \emph{available} either immediately or within the future$\delta$time units, so that the user can select a title to view. The available title list must seek to satisfy the user by striking a delicate balance between showing far fewer titles than can actually be accessed and showing too many titles that cannot be accessed. In addition to defining this availability problem, we make two key contributions. First, a two-tier system architecture which leverages the low-rate cellular infrastructure to exchange control messages and facilitate delivery of large data transfers using the ad-hoc network of vehicular devices. Second, PAVAN as a policy framework for predicting the availability of a title. We describe several variants of PAVAN which incorporate information based on a Markov mobility model, spatio-temporal look-ahead, and title replications. Our results demonstrate that the quality of PAVAN's predictions is critically dependent on degree of title replication, as well as its display time relative to the trip duration. When degree of replication is below a certain threshold, PAVAN with content density information and the predictive mobility model is shown to provide the best overall performance. 63. E. Alwagait and S. Ghandeharizadeh A Comparison of Alternative Web Service Allocation and Scheduling Policies. In IEEE International Conference on Services Computing (SCC), Shanghai, China, September 15-18, 2004. Abstract: Web Services (WSs) are emerging as the building block of Internet scale database management systems (IDBMSs). These systems must intelligently execute plans that reference autonomous WSs. This requires policies and mechanisms for both scheduling and allocating WSs that constitute a plan. In this study, we analyze two scheduling strategies and four allocation policies. Obtained results that a dynamic scheduling with Lest Response Time (LRT) allocation policy is superior to other alternatives when the service time of a WS can be estimated accurately. The Least Recently Used (LRU) allocation policy is inferior to all other policies including Random. 64. S. Ghandeharizadeh, T. Helmi, S. Kapadia and B. Krishnamachari A Case for a Mobility Based Admission Control Policy. In Proceedings of the International Conference on Distributed Multimedia Systems, San Francisco, September 2004. Abstract: Self-organizing ad hoc networks of wireless devices such as Car-to-Car Peer-to-Peer Networks (C2P2) are an emerging technology. Entertainment applications that manipulate continuous media, audio and video clips, push the limits of these networks due to their stringent requirements. These challenges are magnified by environmental characteristics such as dynamic wireless network connections, mobility, multi-hop nature of the network and the possible lack of a fixed infrastructure. In these networks, an intelligent admission control policy enhances Quality of Service (QoS) observed by the users of the system. This paper makes the case for a decentralized Mobility based ADmission Control (MAD) policy. We develop QoS utility models to quantify the performance of this policy with an environment that employs no-admission control. Obtained results show conclusively that MAD provides orders of magnitude improvement when compared with no admission control. 65. S. Ghandeharizadeh and B. Krishnamachari C2P2:A Peer-to-Peer Network for On-Demand Automobile Information Services. In Proceedings of the First International Workshop on Grid and Peer-to-Peer Computing Impacts on Large Scale Heterogeneous Distributed Database Systems (GLOBE'04), Zaragoza, Spain, August 2004. Abstract: This short paper outlines challenges of delivering continuous media and traffic information to mobile Car-to-Car Peer-to-Peer (C2P2) network of devices. We analyze network connectivity of a C2P2 cloud as a function of radio range of each device. A novel concept introduced by C2P2 is on-demand delivery of continuous media, audio and video clips, to moving vehicles. 66. A. Aazami, S. Ghandeharizadeh, and T. Helmi Near Optimal Number of Replicas for Continuous Media in Ad-hoc Networks of Wireless Devices. International Workshop on Multimedia Information Systems, Washington D.C., August 25-27, 2004. Abstract: This study investigates replication of data in a novel streaming architecture consisting of ad-hoc networks of wireless devices. One application of these devices is home-to-home (H2O) entertainment systems where a device collaborates with others to provide each household with on-demand access to a large selection of audio and video clips. These devices are configured with a substantial amount of storage and may cache several clips for future use. A contribution of this study is a technique to compute the number of replicas for a clip based on the square-root of the product of bandwidth required to display clips$(\beta _i)$and their frequency of access$(f_i)$, i.e.,$(\beta_i\times f_i)^\alpha$where$\alpha=0.5$. We provide a proof to show this strategy is near optimal when the objective is to maximize the number of simultaneous displays in the system with string and grid (both symmetric and asymmetric) topologies. We say near optimal" because values of$\alpha$less than 0.5 may be more optimum. In addition, we use analytical and simulation studies to demonstrate its superiority when compared with other alternatives. A second contribution is an analytical model to estimate the theoretical upper bound on the number of simultaneous displays supported by an arbitrary grid topology of H2O devices. This analytical model is useful during capacity planning because it estimates the capabilities of a H2O configuration by considering: the size of an underlying repository, the number of nodes in a H2O cloud, the representative grid topology for this cloud, and the expected available network bandwidth and storage capacity of each device. It shows that one may control the ratio of repository size to the storage capacity of participating nodes in order to enhance system performance. We validate this analytical model with a simulation study and quantify its tradeoffs. 67. S. Bararia, S. Ghandeharizadeh, and S. Kapadia Evaluation of 802.11a for Streaming Data in Ad-hoc Networks. In 4th Workshop on Applications and Services in Wireless Networks, Boston, Massachusetts, USA, August 9-11, 2004. Abstract: Advances in communication and processing have made ad-hoc networks of wireless devices a reality. One application is home entertainment systems where multiple Home-to-Home (H2O) devices collaborate as peers to stream audio and video clips to a household. In this study, we investigate the feasibility of IEEE 802.11a protocol in combination with both TCP and UDP to realize a H2O device. Challenges include lossy connections, unfair allocation of bandwidth between multiple simultaneous transmissions, and the exposed node limitation. Our primary contribution is an empirical study of 802.11a to quantify these factors and their significance. Our multi-dimensional experimental design consists of the following axes: distance between participating devices, number of intermediate H2O devices used to route a stream from a producing H2O device to a consuming H2O device, and simultaneous number of active streams in the same radio range. Both operating system and application level routing were considered. Obtained results demonstrate the following lessons. First, with a multi-hop UDP transmission, in the absence of congestion control, transient bottlenecks result in a high loss rate. Hence, a transport protocol with congestion control is essential for streaming of continuous media within a H2O cloud. Second, 802.11a does not drop TCP connections in the presence of many competing transmissions (802.11b drops connections). Third, we observed fairness when transmitting several hundred Megabytes (MB) of data, among multiple competing 1-hop TCP and UDP flows. Fourth, while there is unfair allocation of bandwidth with an exposed node, the observed bandwidths are sufficient to stream a high-quality video clip (with a 4 Mbps display bandwidth requirement). These results indicate streaming of data is feasible with an ad-hoc network of wireless devices employing the 802.11a protocol 68. W. Shi and S. Ghandeharizadeh. Controlled Buffer Sharing in Continuous Media Servers. In Kluwer Multimedia Tools and Applications, Volume 32, Number 2, June 2004. Abstract: Continuous media servers manage delay sensitive data such as audio and video clips. Once a server initiates the display of a clip on behalf of a client, it must deliver the data to the client in a manner that prevents data starvation. Otherwise, its display may suffer from disruptions and delays, termed hiccups. A hiccup-free display is important to a number of applications such as video-on-demand for entertainment, distance learning, news dissemination, etc. Buffer sharing enables a server to trade memory for disk bandwidth to service multiple clients by sharing data in memory, using a single disk stream. However, an uncontrolled buffer sharing scheme may reduce system performance. This paper presents Controlled Buffer Sharing (CBS) as a novel framework that facilitates sharing and supports both a hiccup-free display and VCR operations. It includes a configuration planner and a buffer pool management technique (applied at run time). CBS trades memory for disk bandwidth in order to meet the performance objectives of an application and minimize cost per stream. It uses bridging and merges two displays referencing the same clip when they are$d_t$blocks apart. One insight of this framework is that$d_t$is determined by market forces (cost of memory and disk bandwidth) and is independent of a clip's frequency of access. We use both analytical and simulation models to quantify the characteristics of CBS 69. S. Ghandeharizadeh, B. Krishnamachari, and S. Song Placement of Continuous Media in Wireless Peer-to-Peer Networks. In IEEE Transactions on Multimedia, Volume 6, Number 4, April 2004. Abstract: This study 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. 70. E. Alwagait, and S. Ghandeharizadeh DeW: A Dependable Web Services Framework. In 14th International Workshop on Research Issues on Data Engineering (Web Services for E-Commerce and E-Goverment Applications), Boston, Massachusetts, USA, March 28-29, 2004. L Abstract: Web Services (WSs) correspond to conceptual entities with well defined interfaces published by different organizations. For example, with businesses, a WS might correspond to a business process to be invoked by other WSs and Internet applications. To increase availability of a WS, an organization might replicate it across different nodes. This study focuses on data intensive applications that (a) expose a conceptual entity as a Web Service (WS) and (b) disperse copies of their WSs across the nodes of a distributed environment to enhance both performance and availability. We describe the design and implementation of a Dependable Web services (DeW) framework to realize physical-location-independence. Physical-location-independence means a plan will execute as long as a copy of its referenced WSs is available. This concept enables the client proxy objects to continue operation in the presence of both failures and WS migrations that balance system load. 71. S. Ghandeharizadeh H2O Clouds: Issues, Challenges and Solutions. In the Fourth Pacific-Rim Conference on Multimedia (PCM), Singapore, Dec 15-18, 2003. Abstract: Home-to-Home Online (H2O) devices use their wireless communication to complement existing wired infrastructure such as Internet and provide data services to individual households. Those within the same radio range form an ad-hoc network of peers that collaborate to increase availability of data. This data might range from educational and entertainment content to personal libraries uploaded by each household. This paper describes the H2O framework and challenges posed by its design. It provides a summary of our in-progress work to date and outlines future research directions. 72. S. Ghandeharizadeh An Educational Perspective on Database Management Systems and Object-Oriented Methodology: A 12 Year Journey. In Educator's Symposium, co-located with 18th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), Anaheim, October 27, 2003. Abstract: Relational database management systems are an essential component of many data intensive applications. At USC, a course entitled "File and Database Management" introduces students to fundamental concepts in relational databases. Students are introduced to conceptual, logical and physical organization of data, use of both formal and commercial query languages, e.g., SQL, indexing techniques for efficient retrieval of data, the concept of a transaction, concurrency control and crash recovery techniques. This paper summarizes our experiences with this course and the challenges of educating students on use of object-oriented concepts and their mapping to tables. 73. S. Ghandeharizadeh, C. Papadopoulos, P. Pol, and R. Zhou NAM: A Network Adaptable Middleware to Enhance Response Time of Web Services. In the Eleventh IEEE/ACM International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS), Orlando, Florida, October 12-15, 2003. Abstract: Web Services are an emerging software technology that employ XML to share and exchange data. They may serve as wrappers for legacy data sources, integrate multiple remote data sources, filter information by processing queries (function shipping), etc. With those that interact with an end user, a fast response time might be the difference between a frustrated and a satisfied user. A Web Service may employ a loss-less compression technique, e.g., Zip, XMill, etc., to reduce the size of an XML message in order to enhance its transmission time. This saving might be outweighed by the overhead of compressing the output of a Web Service at a server and decompressing it at a client. The primary contribution of this paper is NAM, a middleware that strikes a compromise between these two factors in order to enhance response time. NAM decides when to compress data based on the available client and server processor speeds, and network characteristics. When compared with today's common practice to transmit the output of a Web Service uncompressed always, our experimental results show NAM either provides similar or significantly improved response times (at times more than 90% improvement) with Internet connections that offer bandwidths ranging between 80 to 100 Mbps. 74. S. Ghandeharizadeh and T. Helmi An Evaluation of Alternative Continuous Media Replication Techniques in Wireless Peer-to-Peer Networks. In the Third International ACM Workshop on Data Engineering for Wireless and Mobile Access (MobiDE, in conjunction with MobiCom'03), San Diego, CA, September 19, 2003. Abstract: This study investigates a novel streaming architecture consisting of home-to-home online (H2O) devices that collaborate to provide on-demand access to a large selection of audio and video clips. An H2O device consists of a high bandwidth wireless communication component, a powerful processor, and gigabytes of storage. This study investigates three families of replication strategies for a H2O cloud. We evaluate these using analytical models. The obtained results demonstrate the superiority of one strategy that determines the number of replicas for a clip i based on (a) the bandwidth required to display clip i proportional to the bandwidth required by the other clips in the database, and (b) the square root of the frequency of access to the clips. 75. S. Ghandeharizadeh Real-time Spatio-Temporal Databases in Support of Human Motor Skills. In Towards Replacement Parts for the Brain, MIT Press, Editors: Berger, Glanzman, 2003. Abstract: Advances in computer processing, communication, and storage have made multimedia information systems a reality. This paper explores haptic devices as an extension of these systems to capture the spatio-temporal data that pertains to human motor skill. We outline approaches to store and retrieve this data, along with data analysis techniques to facilitate query processing and data mining. Example applications that benefit from this research effort include patient rehabilitation, education, hand-sign recognition, and scientific applications. 76. A. Daskos, S. Ghandeharizadeh, X. An PePeR: A Distributed Range Addressing Space for P2P Systems. In Proceedings of the International Workshop on Databases, Information Systems, and Peer-to-Peer Computing (held in conjunction with VLDB), Berlin, Germany, September 2003. Abstract: This paper describes a Peer-to-Peer Range (PePeR) addressing space to process the select" relational algebra operator. We focus on the select operator because it is the most basic and fundamental operator utilized by both simple and complex relational query plans. In addition, with data flow environments, it dictates the performance of other operators by controlling when they are provided with data, impacting the overall performance of a Peer-to-Peer (P2P) system. PePeR consists of several novel design decisions. First, it constructs Z ranges per node in order to efficiently route predicates in a decentralized manner. Second, it employs interleaved range declustering to minimize mean time to data loss in the presence of node removal(s). Third, it uses innovative techniques to adjust its addressing space in the presence of node insertion. The insertion of nodes is done in a distributed manner and we present a technique that approximates a uniform distribution of records across the nodes. In addition, we present performance numbers from PePeR and compare it with a distributed hash table (DHT). The obtained results show the following. If the workload of a relation is dominated by range predicates then PePeR is a superior alternative. On the other hand, if the workload of a relation is primarily exact-match retrievals (selection predicates using the equality comparison operator), then a DHT provides better performance. Both PePeR and DHT may co-exist in a peer-to-peer system simultaneously, enabling a database specialist to employ DHT with one relation and PePeR with another. 77. Shahram Ghandeharizadeh, Craig A. Knoblock, Christos Papadopoulos, Cyrus Shahabi, Esam Alwagait, Jose Luis Ambite, Min Cai, Ching-Chien Chen, Parikshit Pol, Rolfe Schmidt, Saihong Song, Snehal Thakkar, and Runfang Zhou. Proteus: A System for Dynamically Composing and Intelligently Executing Web Services. In the First International Conference on Web Services(ICWS), Las Vegas, Nevada, June 2003. Abstract: Many organizations envision web services as an enabling component of Internet-scale computing. A final vision of web services is to realize a dynamic environment that identifies, composes and executes web services in response to a query. This vision shapes the design and implementation of Proteus. In addition to describing Proteus' novel components, this paper outlines its initial system design. 78. J. Eisenstein, S. Ghandeharizadeh, L. Golubchik, C. Shahabi, D. Yan, and R. Zimmermann Device Independence and Extensibility in Gesture Recognition. In IEEE Virtual Reality Conference (VR), LA, CA, March 2003. Abstract: 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. 79. S. Ghandeharizadeh, S. Gao, C. Gahagan, and R. Krauss High Performance Parallel Database Management Systems. In Handbook on Data Management in Information Systems, Springer Verlag, Editors: J. Blazewicz, W. Kubiak, T. Morzy, and M. Rusinkiewicz, ISBN: 3-540-43893-9, 2003. Abstract: Parallelism is the key to realizing high performance, scalable, fault tolerant database management systems. 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. This chapter describes three key components of a high performance parallel database management system. First, data partitioning strategies that distribute the workload of a table across the available nodes while minimizing the overhead of parallelism. Second, algorithms for parallel processing of a join operator. Third, ORE as a framework that controls the placement of data to respond to changing workloads and evolving hardware 80. S. Ghandeharizadeh, S. Gao, C. Gahagan A Comparison of Techniques to Estimate Response Time for Data Placement. In EurAsia-ICT: Information and Communication Technology, Shiraz, Iran, October 29-31, 2002 (730-738). Abstract: Technological advances in networking, mass storage devices, processor and information technology have resulted in a variety of data services in diverse applications such as e-commerce, health-care, scientific applications, etc. While the cost of purchasing technology is becoming cheaper, the same cannot be stated about the cost of {\em managing} an information infrastructure. In order to reduce this cost, one needs tools that empower system administrators to explain and reason about a storage subsystem's past performance, e.g., response time. Ideally, an administrator would employ these tools to speculate on both physical organization of data and hardware changes. With a hypothetical change, one may use the previously observed response times to quantify the expected enhancements. In this study, we investigate linear regression, a M/D/1 queuing model and SEER as three alternative techniques to estimate response time. All techniques enable an administrator to speculate on changes to the placement of data and its expected impact on response time. A choice between these techniques is a tradeoff between accuracy and space/computational complexity to estimate response time. In our experimental studies, SEER provides a higher accuracy by using more storage space and computational cycles. 81. S. Ghandeharizadeh, C. Papadopoulos, M. Cai, and K. Chintalapudi Performance of Networked XML-Driven Cooperative Applications. In Proceedings of Second International Workshop on Cooperative Internet Computing (CIC, held in conjunction with VLDB), August 2002. Abstract: Web services are an emerging software technology that employ XML, e.g., W3C's SOAP, to share and exchange data. They are a building block of cooperative applications that communicate using a network. They may serve as wrappers for legacy data sources, integrate multiple remote data sources, filter information by processing queries (function shipping), etc. Web services are based on the concept of software and data as a service". With those that interact with an end user, a fast response time is the difference between the following two scenarios: (1) users issuing requests, retrieving their results, and visiting the service repeatedly, and (2) users issuing requests, waiting for response and walking away prior to retrieving their results, with a lower likelihood of issuing future requests for this web service. One may employ a middleware to enhance performance by minimizing the impact of transmission time. This is accomplished by compressing messages. This paper identifies factors that this middleware must consider in order to reduce response time. In particular, it must ensure the overhead of compression (increased CPU time) does not exceed its savings (lower transmission time). 82. S. Ghandeharizadeh, F. Sommers, J. Kuntal, and E. Alwagait A Document as a Web Service: Two Complementary Frameworks. In Second International Workshop on Multimedia Data Document Engineering (MDDE'02), March 2002. Abstract: An electronic document may provide more information than its paper-based counter part. For example, in addition to text and images, a scientific document may consist of either the raw data or software that substantiates its hypothesis, ontology of its terms, a detailed comparison with its related work, etc. In this study, we explore: a) an environment that represents a document as a Web Service, and b) two alternative frameworks that facilitate discovery and retrieval of documents, namely, Jini and UDDI. We describe how each framework supports documents that reside on a cluster of nodes. These nodes might be dispersed across the Internet or in geographical proximity using an Intranet setting. In addition to detailing discovery and retrieval of documents, we describe how each framework supports data availability in the presence of load imbalance and node failures. One finding of this study is that these two frameworks are complementary and can be used in conjunction with one another. 83. S. Ghandeharizadeh, L. Huang, and I. Kamel A Cost Driven Disk Scheduling Algorithm for Multimedia Object Retrieval. To appear In IEEE Transactions on Multimedia. Abstract: This paper describes a novel cost-driven disk scheduling algorithm for environments consisting of multi-priority requests. An example application is a video-on-demand 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 multi-queue'' 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. 84. J. Eisenstein, S. Ghandeharizadeh, C. Shahabi, G. Shanbhag, and R. Zimmermann Alternative Representations and Abstractions for Moving Sensors Databases. In Proceedings of Tenth International Conference on Information and Knowledge Management (CIKM), November 2001. Abstract: Moving sensors refers to an emerging class of data intensive applications that impacts 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 hearing 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 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 folds. 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 retrieval of data in support of query processing. We quantify the tradeoff associated with these alternatives using empirical data from RoboCup soccer matches. 85. F. Sommers, S. Ghandeharizadeh, and S. Gao Cluster-Based Computing with Active, Persistent Objects on the Web. In IEEE 3rd International Conference on Cluster Computing, October 2001. Abstract: 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. 86. J. Eisenstein, S. Ghandeharizadeh, L. Huang, C. Shahabi, G. Shanbhag, and R. Zimmermann Analysis of Clustering Techniques to Detect Hand Signs. In International Symposium on Intelligent Multimedia, Video and Speech Processing, Hong Kong, May 2001. Abstract:The term multimedia has a different meaning to different communities. The computer industry uses this term to refer to a system that can display audio and video clips. Generally speaking, a multimedia system supports multiple presentation modes to convey information. Humans have five senses: sight, hearing, touch, smell and taste. In theory, a system based on this generalized definition must be able to convey information in support of all senses. This would be a step towards virtual environments that facilitate total recall of an experience. This study builds on our previous work with audio and video servers and explores haptic data in support of touch and motor skills. It investigates the use of clustering techniques to recognize hand signs using haptic data. An application of these results is communication devices for the hearing impaired. 87. S. Ghandeharizadeh Alternative Approaches to Distribute an E-Commerce Document Management System. In International Workshop on Research Issues in Data Engineering (RIDE) 2001. Abstract: This experience paper describes newsblaster.com, a commercial document management system that facilitates exchange of news worthy documents between two user communities: a) editor of newspapers and magazines who seek to publish articles, and b) member companies who want to disseminate information such as new product offerings, product recalls, alliances with other companies, etc. We focus on the Internet connection of a single node web server as the system bottleneck and discuss three alternative approaches to distribute the application across multiple nodes. The first, termed vertical, analyzes the semantics of the application and distributes it across multiple nodes based on its community of users and how they access the system. The second, termed horizontal, declusters the application's data across multiple nodes with the objective to distribute client requests evenly across these nodes. Hybrid, our third approach, considers a horizontal partitioning of services identified by a vertical partitioning. We describe the application of each approach to newsblaster. 88. W. G. Aref, I. Kamel, and S. Ghandeharizadeh Disk Scheduling in Video Editing Systems. In IEEE Transactions on Knowledge and Data Engineering, Volume 13, Number 6, 933-950, December 2001. Abstract: Modern video servers support both video-on-demand and non-linear editing applications. Video-on-demand servers enable the user to videw video clips or movies from a video database, while non-linear 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 pre-recorded 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 that treats both read and write requests in a homogeneous manner in order to ensure their deadlines are met. Due to real-time demands of movie viewing, read requests must be fullfilled 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 cast 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 imporves the throughput of the storage server by enhancing the utilization of available disk bandwidth. 89. M. L. Escobar-Molano and S. Ghandeharizadeh On the Complexity of Coordinated Display of Multimedia Objects. Theoretical Computer Science, Volume 242, Issue: 1-2, July 2000. Abstract: A multimedia presentation can be represented as a collection of objects with temporal constraints that define when the objects are rendered. The display of a presentation is termed coordinated when the display of its objects respects the pre-specified temporal constraints. Otherwise, the display might suffer from failures that translate into meaningless scenarios. For example, a chase scene between a dinosaur and a jeep becomes meaningless if the system fails to render the dinosaur when displaying the scene. A previous study introduced a resource scheduling technique that guarantees a coordinated display of a presentation for single-disk architectures. This technique minimizes both latency and memory requirements and has a worst case time complexity O(nlgn). This paper extends the previousstudy to multi-disk architectures and demonstrates the following: (1) the computation of a resource schedule that supports a coordinated display and yields the minimum latency is NP-Hard, and (2) the computation of the minimum memory requirements to support a coordinated display within a pre-specified latency is NP-Hard. 90. Roger Zimmermann, Shahram Ghandeharizadeh HERA: Heterogeneous Extension of RAID. Technical Report. Abstract: 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 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 HERA, a framework that enables parity-based data protection for heterogeneous storage systems. We describe the tradeoffs associated with three alternative HERA techniques: independent subservers, dependent subservers, and disk merging. The novel disk merging approach provides a low cost solution for systems that require highly available secondary storage. 91. Shahram Ghandeharizadeh, Seon Ho Kim Design of Multi-user Editing Servers for Continuous Media. Journal of Multimedia Tools and Applications, Kluwer Academic Publishers, Volume 11, Number 1, May 2000. Abstract: Based on a fifteen month investigation of a post production facilities for both the entertainment industry and broadcasters, we identified a number of challenges with the design and implementation of a server in support of multiple editing stations. These include, how to: share the same content among multiple editors, support continuous display of the edited content for each editor, support complex editing operations, compute the set of changes (deltas) proposed by an editor, compare the deltas proposed by multiple editors, etc. It is beyond the focus of this paper to report on each challenge and its related solutions. Instead, we focus on one challenge, namely how to support continuous display of the edited content for each editors, and techniques for physical organization of data to address this challenge. 92. I. Kamel, T. Niranjan, and S. Ghandeharizadeh A Novel Deadline Driven Disk Scheduling Algorithm for Multi-Priority Multimedia Object. In Proceedings of the IEEE Data Engineering Conference, February 2000. Abstract: In this paper, 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 (a) maintaining one queue for all requests, and (b) 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 prioirty 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). 93. S. Ghandeharizadeh and S. H. Kim A Comparison of Alternative Continuous Display Techniques with Heterogeneous Multi-Zone Disks. In Proceedings of CIKM'99. Abstract: 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, HP's Track Pairing, and USC's FIXB and dead-line driven techniques. 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. 94. S. Ghandeharizadeh and F. Sommers A Case for Deltas in Business-to-Business Electronic Commerce. DEXA'99 Abstract: At the time of this writing, the electronic commerce market place is dominated by business-to-business transactions. This paper describes one such application and our software prototype in support of this application. Our main contribution is a software solutions (using Java) that employs the concept of deltas to maintain consistency in a replicated, distributed environment. Our proposed solution strives to be independent of the schema of the business objects in order to enhance its portability across different applications. 95. Roger Zimmermann Continuous Media Placement and Scheduling in Heterogeneous Disk Storage Systems. Ph.D. thesis, USC Computer Science Dept., Dec. 1998. Abstract: 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 dissertation describes a taxonomy of techniques that ensure a continuous display of objects using a heterogeneous disk subsystem. This taxonomy consists of: (a) strategies that partition resources into homogeneous groups of disks and manage each independently, and (b) techniques that treat all disks uniformly, termed non-partitioning techniques. We introduce and evaluate three non-partitioning techniques: Disk Merging, Disk Grouping, and Staggered Grouping. Our results demonstrate that Disk Merging is the most flexible scheme while providing a competitive, low cost per simultaneous display. Finally, using an open simulation model, we compare Disk Merging with a partitioning technique. The obtained results confirm the superiority of Disk Merging. 96. Weifeng Shi Data Sharing in Interactive Continuous Media Servers. Ph.D. thesis, USC Computer Science Dept., Aug. 1998. Abstract: In a continuous media server that supports the display of audio or video clips (e.g., a video-on-demand server), requests from different clients are independent of each other and may arrive at random time. Commercial systems may strive to support hundreds, if not thousands of clients. Assigning an individual disk stream for each client may require very high disk bandwidth from a server. This makes the disk bandwidth a bottleneck resource, restricting the number of concurrent displays. One solution is to introduce additional disk drives into the server, however, this might result in a significant system cost that would render the system economically inviable. In this dissertation, we propose novel data sharing techniques to resolve the disk bandwidth bottleneck while making the overall system more cost-effective. We investigate two approaches: buffer sharing and batching. With buffer sharing, if one display of a clip lags another display of the same clip by a short time interval, then the portion between the two is retained in buffers to allow the lagging display to read data from buffers with no disk access. We propose a buffer sharing scheme that strikes a balance in trading memory for disk bandwidth to prevent system bottlenecks (either memory or disk bandwidth). Moreover, this scheme minimizes the system cost to meet a prespecified performance objective. With batching, requests are delayed in the hope of being merged with other requests for the same clip. These merged requests then form a batch and consume only one disk stream. We investigate environments that equip the client with local storage device (e.g ., rewritable DVD) to achieve data sharing among batches and support VCR operations. The local client storage reduces the disk bandwidth requirement at server side dramatically, however, it requires more resource (both disk bandwidth and memory) at client side which may diminish the cost-effectiveness of the environment. When compared with each other, batching with local storage distributes resources into each client, whereas buffer sharing centralizes resources in the server. This dissertation demonstrates that buffer sharing is a more cost-effective solution. 97. Jaber A. M. Al-Marri Variable Bit Rate Continuous Media Servers. Ph.D. thesis, USC Computer Science Dept., Aug. 1998. Abstract: Continuous media servers are increasingly used to support a number of application domains, e.g., entertainment industry, library information systems, educational applications, etc. Objects of continuous media data type are large in size and their retrieval and display are subject to real-time constraints. Servers are required to accommodate these objects and ensure their continuous display. A number of recent studies have investigated scheduling techniques in support of variable bit rate (VBR) video clips. When compared with constant bit rate (CBR) video, VBR has a lower storage and bandwidth requirement while providing the same image quality. However, a VBR video clip might exhibit a significant variance in the bit rate required to support its continuous display. In this dissertation, we propose VBR disk scheduling techniques that strive to minimize resource requirements (i.e., network bandwidth, disk bandwidth, and buffer size). Moreover, we present a taxonomy of VBR disk scheduling techniques that includes, in addition to our techniques, other techniques found in the literature. This dissertation investigates VCR functions such as fast-forward and fast-rewind viewing functions. These functions typically increase the resource requirements of a continuous media server in terms of storage space, as well as both the network and disk bandwidth. Furthermore, these functions become more challenging because of the additional constraints imposed by compression techniques such as motion pictures experts group (MPEG). In this dissertation, we propose a scalable fast-forward and fast-rewind approach for MPEG encoded video clips. Our approach minimizes resource requirements of a system. 98. Cyrus Shahabi, Ali Esmail Dashti, and Shahram Ghandeharizadeh Profile Aware Retrieval Optimizer for Continuous Media. Proceedings of the World Automation Congress (WAC98), May 1998. Abstract: One of the key components of multimedia systems is a Continuous Media (CM) server that guarantees the uninterrupted delivery of continuous media data (i.e., audio and video). Queries imposed by applications, such as customized news-on-demand, might require the retrieval of one or more continuous objects from the CM server. Traditionally, multimedia systems have opted to guarantee that the CM server can display all the objects in the set to the user with no interruptions and with very strict display timing and ordering among the objects. This results in a single possible retrieval plan. However, for a class of applications, we have observed that depending on the user query, user profile, and session profile, there are a number of flexibilities that can be exploited for retrieval optimization, namely: delay, ordering, presentation, and display-quality flexibilities. In this paper, we describe a Profile Aware Retrieval Optimizer (Prime) that utilizes these flexibilities to improve system performance by reducing retrieval contention at the CM server. 99. Cyrus Shahabi, Mohammad H. Alshayeji, and Shimeng Wang A Buffering Policy for Distributed Continuous Media Servers. Proceedings of the World Automation Congress (WAC98), May 1998. Abstract: Recent technological advances in computer, high-speed network, and data compression are accelerating the realization of media-on-demand (MOD) systems. In this paper, we investigate issues involved in the design of a distributed server to support MOD application. We describe Eager Pipelining Policy which utilizes resources, that are otherwise unused, to improve system performance. Eager Pipelining can be employed when the available bandwidth along the path from a source to a user exceeds the display bandwidth requirement of a referenced continuous media object. In this case, the policy will utilize disk and memory buffers of the intermediate nodes to deliver the object to the user efficiently. 100. Ali Esmail Dashti and Shahram Ghandeharizadeh On Configuring Hierarchical Storage Structures. Proceedings of the Joint NASA/IEEE Mass Storage Conference (Joint Sixth NASA Goddard Conference on Mass Storage Systems and Technologies, and Fifteenth IEEE Mass Storage Systems Symposium), Mar. 1998. Abstract: The rapid progress in mass storage technology is enabling designers to implement large databases for a variety of applications. The possible configurations of the hierarchical storage structures (HSS) are numerous and result in various tradeoffs, e.g., storage cost, throughput, initial latency, etc. A naive design might waste system resources and result in high cost. For example, one naive design decision is to add disk caches for those applications whose bandwidth is already satisfied by the tertiary storage device and can tolerate a high latency. In this study, we introduce a configuration planner for HSS in support of video-on-demand applications. The input to the planner are the number of simultaneous displays required by the target application (i.e., throughput), database size, and expected pattern of access to the objects. It's output are the choice of mass storage devices at each level of the hierarchy. The resulting configuration supports the application requirements at a minimum cost per display. It is possible to extend this study to consider other application requirements, such as: initial latency and storage reliability. Moreover, the presented concepts can be generalized to scientific applications. 101. Jaber Al-Marri,Shahram Ghandeharizadeh An Evaluation of Alternative Disk Scheduling Techniques in Support of Variable Bit Rate Continuous Media. Proceedings of the International Conference on Extending Database Technology (EDBT), Mar. 1998. Abstract: A number of recent studies have investigated scheduling techniques in support of variable bit rate (VBR) video. When compared with constant bit rate (CBR) video, VBR has a lower storage and bandwidth requirement while providing the same quality of images. However, a VBR video clip might exhibit a significant variance in the bit rate required to support its continuous display. The previous studies have proposed techniques to support the display of a VBR clip from two different perspectives: disk storage subsystem and the network. In this study, we propose a taxonomy of VBR disk scheduling techniques that includes those proposed for the network. The results demonstrate that a new class of disk scheduling techniques, termed Atomic-VR2 VITAL, is superior. Algorithms used to represent this class were adopted from the networking literature. 102. Weifeng Shi, Shahram Ghandeharizadeh Trading Memory for Disk Bandwidth in Video-on-Demand Servers. Proceedings of 13th ACM Symposium on Applied Computing, Feb. 1998. Abstract: In a Video-on-Demand server, requests from different clients are independent of each other and may arrive at random time. Commercial systems may contain hundreds to thousands of clients and thus providing an individual stream for each client may require very high disk bandwidth in the server. Therefore the disk bandwidth may become a bottleneck resource, restricting the number of concurrent displays in the system. In this paper, we propose a scheme that trades memory for disk bandwidth and strikes a balance in order to prevent either memory or disk bandwidth from becoming a bottleneck resource. Moreover, we obtain the balance point of trading memory for disk bandwidth which leads to the most cost-effective system configuration. 103. Mohammad H. Alshayeji, Cyrus Shahabi Object Delivery in Distributed Continuous Media Servers. Proceedings of the 8th International Workshop on Research Issues in Database Engineering (RIDE'98), Feb. 1998. Abstract: Supporting uninterrupted delivery in distributed continuous media servers is not a trivial task. In this paper, we propose an Eager Pipelining policy that allows distributed continuous media servers to utilize resources, that are otherwise unused, to support a display. We also propose a delivery technique that enables continuous media servers to delivery objects at multiple rates. 104. Seon Ho Kim, Shahram Ghandeharizadeh Design of Multi-user Editing Servers for Continuous Media. Proceedings of the 8th International Workshop on Research Issues in Database Engineering (RIDE'98), Feb. 1998. Abstract: Based on a fifteen month investigation of a post production facilities for both the entertainment industry and broadcasters, we identified a number of challenges with the design and implementation of a server in support of multiple editing stations. These include, how to: share the same content among multiple editors, support continuous display of the edited content for each editor, support complex editing operations, compute the set of changes (deltas) proposed by an editor, compare the deltas proposed by multiple editors, etc. It is beyond the focus of this paper to report on each challenge and its related solutions. Instead, we focus on one challenge, namely how to support continuous display of the edited content for each editors, and techniques for physical organization of data to address this challenge. 105. Shahram Ghandeharizadeh and Richard Muntz Design and Implementation of Scalable Continuous Media Servers In Parallel Computing, Elsevier, Volume 24, 91-122, 1998. Abstract: During the past decade, the information technology has evolved to store and retrieve continuous media data types, e.g., audio and video clips. Unlike the traditional data types (e.g., text), continuous media consists of a sequence of quanta, either audio samples or video frames, that convey meaning when presented at a pre-specified rate. A challenging task when implementing these servers is to guarantee retrieval and delivery of a clip at its pre-specified rate. Continuous media servers are expected to play a major role in many application domains including library information systems, entertainment technology, educational applications, etc. The focus of this study is on the disk subsystem of a server and techniques that both enhance its performance and ensure its scalability. By scalable, we mean that the system can grow incrementally as the requirements of an application grows in order to avoid a degradation in performance. This study details data placement techniques across both (1) the zones of a disk in order to trade bandwidth for storage, and (2) multiple disks to enable the system to scale. In addition, we describe scheduling techniques to (1) trade memory for disk bandwidth and vice versa, and (2) merge multiple requests referencing a single clip in order to increase the number of simultaneous displays supported by the system. We present performance results from Mitra, an experimental prototype that realizes an implementation of the presented techniques. These results demonstrate the feasibility of a scalable server. 106. Shahram Ghandeharizadeh, Roger Zimmermann, Seon Ho Kim, Weifeng Shi, Jaber Al-Marri Scalable Video Browsing Techniques for Intranet Video Servers. Proceedings of the 7th Workshop on Information Technologies and Systems (WITS '97), Dec. 1997. Abstract: Servers that employ scalable techniques prevent the formation of bottlenecks in order to allow the system to support a higher number of clients as function of additional hardware. They are desirable because they enable a growing organization to satisfy the increased demand imposed on its hardware platform by increasing its size (instead of replacing it with a new one which is almost always more expensive~\cite{stone86}). This study presents the design, implementation, and evaluation of scalable techniques in support of video browsing, i.e., VCR functions such as fast-forward and fast-rewind. 107. Roger Zimmermann, Shahram Ghandeharizadeh Continuous Display Using Heterogeneous Disk-Subsystems. Proceedings of ACM Multimedia Conference, Nov. 1997. Abstract: 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 partition resources into homogeneous groups of disks and manage each independently, and (b) techniques that treat all disks uniformly, termed non-partitioning techniques. We introduce three non-partitioning techniques: disk merging, disk grouping, and staggered grouping. We investigate these techniques using analytical models. Our results demonstrate that disk merging is the most flexible scheme while providing among the lowest cost per simultaneous display. Finally, using an open simulation model, we compare disk merging with a partitioning technique. The obtained results demonstrate the superiority of disk merging. 108. Amir Zarkesh, Jafar Adibi, Cyrus Shahabi, Reza Sadri, Vishal Shah. Analysis and Design of Server Informative WWW-sites. In Proceedings of CIKM'97.? Abstract: The access patterns of the users of a web-site are traditionally analyzed in order to facilitate the user access to the site's information. In this study, however, a systematic approach is introduced in order to analyze the users' navigation paths to the advantage of the web-site owner. Briefly, as users navigate through a web-site, it seems that they are transparently filling a questionnaire designed a priori by the web-site owner. To achieve this, we first cluster the users who navigate$similar$paths employing the {\em Path Mining} algorithm. Next, the correlation between a set of target questions and the structure of the WWW-site is quantified. This has been done by borrowing the concept of$channel$from information theory. Finally, we compute the probability of a user's certain answer to each question, given the user's navigation path. The accuracy of the computed probabilities highly depends on the channel parameters. Hence, we describe a learning process based on a set of training data and/or inputs from a human expert, to characterize the channel. We tested our method using a sample WWW-site and the results demonstrate reasonable error rate in predicting the responses to a set of three questions. We also show that the structure of a web-site impacts the accuracy of the predictions. Therefore, we provide a natural measure to compute the effectiveness of a WWW-site structure in answering a target questionnaire. To verify our measure, we applied it on some intuitive design rules and it successfully identified the intuitively$better$web-site as the winner. 109. Weifeng Shi, Shahram Ghandeharizadeh Buffer Sharing in Video-On-Demand Servers ACM Sigmetrics Bulletin, 1997 Abstract: This paper describes a buffer sharing technique that strikes a balance between the use of disk bandwidth and memory in order to maximize the performance of a video-on-demand server. We make the key observation that the configuration parameters of the system should be independent of the physical characteristics of the data (e.g., popularity of a clip). Instead, the configuration parameters are fixed and our strategy adjusts itself dynamically at run-time to support a pattern of access to the video clips. 110. Cyrus Shahabi, Mohammad H. Alshayeji, Shimeng Wang A Redundant Hierarchical Structure for a Distributed Continuous Media Server IEEE/ACM IDMS'97 Abstract: The growing number of digital audio and video repositories has resulted in a desperate need for effective techniques to deliver data to users in a timely manner. Due to geographical distribution of users, it is not cost effective to have a centralized media server. In this paper, we investigate issues involved in the design of a distributed video server (DVS) to support movie-on-demand (MOD) application. We propose a redundant hierarchical (RedHi) architecture for DVS where the nodes are continuous media servers and the edges are dedicated network lines. With RedHi, each node has two or more parents. We show that the redundant links in RedHi yields a more fault-tolerant and efficient system. Our simulation results demonstrate that RedHi can tolerate a single link failure with no degradation in performance while with pure hierarchy almost 2.5% of requests are rejected due to the failure. In normal mode of operation, RedHi outperforms pure hierarchy significantly (160% improvement on the average when counting the number of rejections). In the context of RedHi, we also propose and evaluate alternative object management policies, resource reservation strategies, and load balancing heuristics. 111. Ali E. Dashti, Shahram Ghandeharizadeh, James Stone, Larry Swanson, Richard H. Thompson Database Challenges in Neuroscientific Applications NeuroImage Journal, Mar. 1997. Abstract: In the scientific community, the quality and progress of various endeavors depend in part on the ability of researchers to share and exchange large quantities of heterogeneous data with one another efficiently. This requires controlled sharing and exchange of information among autonomous, distributed, and heterogeneous databases. In this paper, we focus on a neuroscience application, Neuroanatomical Rat Brain Viewer (NeuART Viewer) to demonstrate alternative database concepts that allow neuroscientists to manage and exchange data. Requirements for the NeuART application, in combination with an underlying network-aware database, are described at a conceptual level. Emphasis is placed on functionality from the user's perspective, and on requirements that the database must fulfill. The most important functionality required by neuroscientists is the ability to construct brain models using information from different repositories. To accomplish such a task, users need to browse remote and local sources and summaries of data, and capture relevant information to be used in building and extending the brain models. Other functionalities are also required, including posing queries related to brain models, augmenting and customizing brain models, and sharing brain models in a collaborative environment. An extensible object-oriented data model is presented to capture the many data types expected in this application. After presenting conceptual level design issues, we describe several known database solutions that support these requirements, and discuss requirements that demand further research. Data integration for heterogeneous databases is discussed in terms of reducing or eliminating semantic heterogeneity when translations are made from one system to another. Performance enhancement mechanisms such as materialized views and spatial indexing for three-dimensional objects are explained and evaluated in the context of browsing, incorporating, and sharing. Policies for providing the system with fault tolerance and avoiding possible intellectual property abuses are presented. Finally, two existing systems are evaluated and compared using the identified requirements. 112. Shahram Ghandeharizadeh, Roger Zimmermann, Weifeng Shi, Reza Rejaie, Doug Ierardi, Ta-Wei Li. Mitra: A Scalable Continuous Media Server. Multimedia Tools and Applications Journal, Kluwer Academic Publishers, 5(1):79-108, July 1997. Abstract: Mitra is a scalable storage manager that supports the display of continuous media data types, e.g., audio and video clips. It is a software based system that employs off-the-shelf hardware components. Its present hardware platform is a cluster of multi-disk workstations, connected using an ATM switch. Mitra supports the display of a mix of media types. To reduce the cost of storage, it supports a hierarchical organization of storage devices and stages the frequently accessed objects on the magnetic disks. For the number of displays to scale as a function of additional disks, Mitra employs staggered striping. It implements three strategies to maximize the number of simultaneous displays supported by each disk. First, the EVEREST file system allows different files (corresponding to objects of different media types) to be retrieved at different block size granularities. Second, the FIXB algorithm recognizes the different zones of a disk and guarantees a continuous display while harnessing the average disk transfer rate. Third, Mitra implements the Grouped Sweeping Scheme (GSS) to minimize the impact of disk seeks on the available disk bandwidth. In addition to reporting on implementation details of Mitra, we present performance results that demonstrate the scalability characteristics of the system. We compare the obtained results with theoretical expectations based on the bandwidth of participating disks. Mitra attains between 65% to 100% of the theoretical expectations. 113. Cyrus Shahabi, Amir Zarkesh, Jafar Adibi, and Vishal Shah Knowledge Discovery from Users Web-page Navigation. Proceedings of Research Issues in Data Engineering (RIDE) Conference, April 1997. 114. Shahram Ghandeharizadeh, Seon Ho Kim, Weifeng Shi, Roger Zimmermann On Minimizing Startup Latency in Scalable Continuous Media Servers. In the Proceedings of Multimedia Computing and Networking Conference, Feb. 1997. 115. Shahram Ghandeharizadeh,R. Hull, and D. Jacobs Design, Implementation, and Application of Heraclitus[Alg,C]. In ACM-Transactions on Database Systems, Volume 21, Number 3, 370-426, September 1996. 116. Martha L. Escobar-Molano, Shahram Ghandeharizadeh, Douglas Ierardi. An Optimal Resource Scheduler for Continuous Display of Structured Video Objects. In IEEE Transactions on Knowledge and Data Engineering, Volume 8, Number 3, 508-511, June 1996. 117. Shahram Ghandeharizadeh, Dongho Kim. On-line Reorganization of Data in Scalable Continuous Media Servers. In Proceedings of DEXA Conference, 1996. 118. Shahram Ghandeharizadeh, Seon Ho Kim, Cyrus Shahabi, Roger Zimmermann. Placement of Continuous Media in Multi-Zone Disks. A book chapter in Multimedia Information Storage and Management, Kluwer Academic Publisher, Aug. 1996. 119. Shahram Ghandeharizadeh, Doug Ierardi, Dongho Kim, Roger Zimmermann Placement of Data in Multi-Zone Disk Drives. Second International Baltic Workshop on DB and IS, June 1996. 120. Cyrus Shahabi Scheduling the Retrievals of Continuous Media Objects. Ph.D. thesis, USC Computer Science Dept., Aug. 1996. 121. S. Ghandeharizadeh Stream-Based Versus Structured Video Objects: Issues, Solutions, and Challenges. A book chapter in Multimedia Database Systems: Issues and Research Directions, Springer Verlag, 1996. 122. S. Ghandeharizadeh, D. Ierardi and R. Zimmermann. An Online Algorithm to Optimize File Layout in a Dynamic Environment. Information Processing Letters Journal, (57):75-81, 1996. 123. Shahram Ghandeharizadeh, Seon Ho Kim. Striping in Multi-disk Video Servers . In Proceedings of the SPIE High-Density Data Recording and Retrieval Technologies Conference, Oct. 1995. 124. S. Chaudhuri, S. Ghandeharizadeh and C. Shahabi. Avoiding Retrieval Contention for Composite Multimedia Objects. Proceedings of the VLDB Conference, 1995. 125. C. Shahabi and S. Ghandeharizadeh. Continuous Display of Presentations Sharing Clips. ACM Multimedia Systems Journal, May 1995. 126. S. Ghandeharizadeh, S. H. Kim, C. Shahabi. On Configuring a Single Disk Continuous Media Server. In Proceedings of the ACM SIGMETRICS/PERFORMANCE, May 1995. 127. S. Ghandeharizadeh, A. Dashti and C. Shahabi. A Pipelining Mechanism to Minimize the Latency Time in Hierarchical Multimedia Storage Managers. Computer Communications, March 1995. 128. S. Ghandeharizadeh and C. Shahabi. On Multimedia Repositories, Personal Computers, and Hierarchical Storage Systems. Proceedings of ACM Multimedia Conference, 1994. 129. S. Berson, S. Ghandeharizadeh, R. Muntz and X. Ju. Staggered Striping in Multimedia Information Systems. Proceedings of ACM SIGMOD, 1994. 130. S. Ghandeharizadeh and C. Shahabi and L. Ramos. An Overview of Techniques for Continuous Retrieval of Multimedia Data ACM SIGARCH Computer Architecture News, 21, No. 5, December 1993. 131. S. Ghandeharizadeh and C. Shahabi. Management of Virtual Replicas in Parallel Multimedia Information Systems. Proceedings of the Foundations of Data Organization and Algorithms (FODO) Conference, October 1993. 132. S. Ghandeharizadeh and L. Ramos. Continuous Retrieval of Multimedia Data Using Parallelism. IEEE Transactions on Knowledge and Data Engineering, Vol. 5, No. 4, Aug. 1993. 133. S. Ghandeharizadeh D. DeWitt and W. Qureshi. A Performance Analysis of Alternative Multi-Attribute Declustering Strategies. ACM SIGMOD 1992, 1992. Author: Shahram Ghandeharizadeh, David DeWitt and Waheed Qureshi. Title: A Performance Analysis of Alternative Multi-Attribute Declustering Strategies. Source: ACM SIGMOD, 1992. Abstract: 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 parallel 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. With earlier, single attribute declustering strategies, such as those found in Tandem, Teradata, Gamma, and Bubba parallel database systems, a selection query including a range predicate on any attribute other than the partitioning attribute must be sent to all processors containing tuples of the relation. By directing a query with minimal resource requirements to processors that contain no relevant tuples, the system wastes CPU cycles, communication bandwidth, and I/O bandwidth, reducing its overall processing capability. As a solution, several multi-attribute declustering strategies have been proposed. However, the performance of these declustering techniques have not previously been compared to one another nor with a single attribute partitioning strategy. This paper, compares the performance of Multi-Attribute GrId deClustering ({\em MAGIC}) and Bubba's Extended Range Declustering ({\em BERD}) strategies with one another and with the range partitioning strategy. Our results indicate that MAGIC outperforms both range and BERD in all experiments conducted in this study. Full Paper in Postscript. Author: S. Ghandeharizadeh, S.H. Kim, W. Shi, and R. Zimmermann. Title: On Minimizing Startup Latency in Scalable Continuous Media Servers. Source: Proceedings of Multimedia Computing and Networking Conference, Feb. 1997. Abstract: In a scalable server that supports the retrieval and display of continuous media (audio and video clips), both the number of simultaneous displays and the expected startup latency of a display increases as a function of additional disk bandwidth. This paper describes object replication and request migration as two alternative techniques to minimize startup latency. In addition to developing analytical models for these two techniques, we report on their implementation using a scalable server. The results obtained from both the analytical models and the experimental system demonstrate the effectiveness of the proposed techniques. Full Paper Author: Shahram Ghandeharizadeh, Seon Ho Kim, Cyrus Shahabi, Roger Zimmermann. Title: Placement of Continuous Media in Multi-Zone Disks Source: Book Chapter in Multimedia Information Storage and Management, 1996. Abstract: For applications with large data sets, e.g., video servers, magnetic disks have established themselves as the mass storage device of choice. A technique to increase the storage capacity of disks is zoning. A side-effect of zoning is that it introduces a disk drive with variable transfer rates. This chapter describes techniques to support a continuous display of constant-bit rate video and audio objects using a multi-zone disk drive. As compared to previous approaches, the proposed techniques harness the average transfer rate of each magnetic disk (instead of its minimum transfer rate). In addition, we describe a configuration planner that logically manipulates the zoning information of a disk drive to support the performance criteria of an application. We present performance numbers from an experimental prototype to demonstrate the feasibility of our approach. Full Paper Author: S. Ghandeharizadeh, S.H. Kim, and C. Shahabi. Title: On Configuring a Single Disk Continuous Media Server Source: In Proceedings of the ACM SIGMETRICS/PERFORMANCE, May 1995. Abstract: 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. Full Paper Author: S. Ghandeharizadeh and S.H. Kim. Title: A Unified Framework for Placement of Data in Parallel Continuous Media Servers Source: USC Technical Report USC-CS-TR95-615, University of Southern California, 1995. Abstract: A challenging task when designing a continuous media server is to support the performance criteria of its target application, i.e., both its desired number of simultaneous displays and the waiting tolerance of its clients. With parallel continuous media servers, the placement of data has a significant impact on the overall performance of the system. Two alternative organizations of data have been described in the literature: Striping and Declustering. In this study, we propose a new framework for placement of data, termed {\em unified}. Unified subsumes both striping and declustering. In addition, it supports hybrid organizations that are a combination of these two techniques. We describe a configuration planner for unified that determines the system parameters such that: 1) it supports the performance criterion of an application, and 2) it minimizes the cost of a system. The experimental results demonstrate both the superiority and flexibility of unified. Full Paper Author: S. Ghandeharizadeh, S.H. Kim, and C. Shahabi. Title: Continuous Display of Video Objects Using Multi-Zone Disks Source: USC Technical Report USC-CS-TR94-592, University of Southern California, 1994. Abstract: Video servers are expected to play an important role in a number of application domains, e.g., library information systems, entertainment industry, scientific applications, etc. A challenging task when implementing these systems is to ensure a continuous display of audio and video objects. If special precautions are not taken, the display of an object may suffer from frequent disruptions and delays, termed hiccups. A second challenging task is to configure a system to meet the performance requirements of an application: its desired number of simultaneous displays and the waiting tolerance of a display. For applications with large data sets, e.g., video servers, magnetic disks have established themselves as mass storage device of choice. A technique to increase the storage capacity of disks is zoning. A side-effect of zoning is that it introduces a disk drive with variable transfer rates. This paper describes techniques to support a continuous display of video objects using a multi-zone disk drive. As compared to previous approaches, the proposed techniques harness the average transfer rate of the magnetic disk (instead of its minimum transfer rate). In addition, we describe a configuration planner that logically manipulates the zoning information of a disk drive to support the performance criteria of an application. Full Paper Author: GHANDEHARIZADEH-S*; DASHTI-A; SHAHABI-C Title: PIPELINING MECHANISM TO MINIMIZE THE LATENCY TIME IN HIERARCHICAL MULTIMEDIA STORAGE MANAGERS Source: COMPUTER COMMUNICATIONS, vol. 18, issue 3, (MAR, 1995) : pp. 170-184. Abstract: An emerging area of database system research is to provide support for continuous media data types (digital audio and video). These data types are expected to play a major role in applications such as library information systems, scientific databases, entertainment technology, etc. They require both a high volume of storage and a high bandwidth requirement for their continuous display. The storage organization of systems that support these data types is expected to be hierarchical, consisting of one or more tertiary storage devices, several disk drives, and some memory. The database resides permanently on the tertiary storage device. The disk drives store a number of frequently accessed objects, while the memory is used to stage a small fraction of a referenced object for immediate display. When a user references an object that is tertiary resident, if the system elects to materialize the object on the disk drives in its entirety before initiating its display then the user would observe a high latency time. This paper describes a general purpose pipelining mechanism that overlaps the display of an object with its materialization on the disk drives in order to minimize the latency time of the system. The pipelining mechanism is novel because it ensures a continuous retrieval of an object to a display station (in order to support its continuous display). Full Paper Author: GHANDEHARIZADEH-S*; SHAHABI-C Title: On Multimedia Repositories, Personal Computers, and Hierarchical Storage Systems Source: Proceedings of ACM Multimedia Conference, 1994. Abstract: 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 a high bandwidth requirement. Hierarchical storage structures (consisting of RAM, disk and tertiary storage devices) provide a cost-effective solution for their large size. 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. Full Paper Author: Shahram Ghandeharizadeh Title: Stream-based Versus Structured Video Objects: Issues, Solutions, and Challenges Source: A book chapter in Multimedia Database Systems: Issues and Research Directions, Springer Verlag, 1996. Abstract: An emerging area of database system research is to investigate techniques that ensure a continuous display of video objects. As compared to the traditional data types, e.g., text, a video object must be retrieved at a prespecified rate. If it is retrieved at a lower rate then its display may suffer from frequent disruptions and delays, termed hiccups. This paper describes two alternative approaches to representing video objects (stream-based and structured) and the issues involved in supporting their hiccup-free display. For each approach, we describe the existing solutions and the future research directions from a database systems perspective. Full Paper Author: GHANDEHARIZADEH-S*; SHAHABI-C Title: Avoiding Retrieval Contention for Composite Multimedia Objects Source: Proceedings of VLDB Conference, 1995. Abstract: An important requirement for multimedia presentations is the ability to compose new multimedia objects from the existing multimedia objects using temporal relationships. When compositions of continuous media objects are specified on the fly, the task of displaying such composite objects pose new challenges. In this paper, we examine the above problem. We show that in case of a single composite object retrieval, a prefetching technique based on simple sliding provides a new approach to reduce latency and buffering requirements. We extend the prefetching technique based on sliding (buffered sliding) to the problem of retrieving multiple composite objects simultaneously. We consider several variants of the buffered sliding algorithms. Simulation-based study is used to compare their usage pattern of available memory and in determining their relative merits in reducing latency and increasing disk bandwidth utilization. Full Paper Author: Shahram Ghandeharizadeh, Seon Ho Kim Title: Striping in Multi-disk Video Servers Source: In the Proceedings of the SPIE High-Density Data Recording and Retrieval Technologies Conference, Oct. 1995. Abstract: A challenging task when designing a video server is to support the performance criteria of its target application, i.e., both its desired number of simultaneous displays and the waiting tolerance of a display. With a multi-disk video server, the placement of data has a significant impact on the overall performance of a system. This study quantifies the tradeoffs associated with alternative organization of data across multiple disks. We describe a planner that configures a system to: 1) support the performance criteria of an application, and 2) minimize the cost of a system. The experimental results demonstrate the superiority and flexibility of using the planner to configure a system. Full Paper Author: Shahram Ghandeharizadeh, Doug Ierardi, and Roger Zimmermann Title: An on-line algorithm to optimize file layout in a dynamic environment. Source: Information Processing Letters Journal, (57):75-81, 1996. Abstract: We describe an algorithm to manage the storage and layout of files cached on mechanical devices, such as magnetic disk drives. The algorithms respond in an online manner to maintain a dynamically changing working set of disk--resident files, while providing a guaranteed degree of contiguity in the layout of each file on the device, with fewer than$\lceil \lg n \rceil$breaks for each disk--resident file of$n$blocks. Full Paper Author: Shahram Ghandeharizadeh, Doug Ierardi, Dongho Kim, Roger Zimmermann Title: Placement of Data in Multi-Zone Disk Drives Source: Second International Baltic Workshop on DB and IS, June 1996. Abstract: This paper describes a placement technique for the layout of files across the surface of a multi-zone magnetic disk drive to maximize its bandwidth. It argues for a file system that monitors the frequency of access to the files and modifies the placement of files in order to respond to an evolving pattern of file accesses. Such a file system is particularly useful for repositories whose primary functionality is to disseminate information, such as the World-Wide-Web along with thousands of ftp sites that render documents, graphic pictures, images, audio clips, and full-motion video available on the Internet. Employing software techniques to enhance the disk performance is important because its mechanical nature has limited its hardware performance improvements at 7 to 10 percent a year. Full Paper Author: Shahram Ghandeharizadeh, Dongho Kim Title: On-line Reorganization of Data in Scalable Continuous Media Servers Source: DEXA 96. Abstract: The number of simultaneous displays supported by a continuous media server (e.g, Mitra) depends on the number of disk drives as well as the amount of memory in the system. To support a higher number of displays, one may increase the number of disks in the system and reorganize the placement of data to incorporate their bandwidth. This study presents alternative on-line reorganization techniques that modify the placement of data without disrupting service. We quantify the memory and disk storage requirements of these techniques using analytical models. Full Paper Author: Shahram Ghandeharizadeh, Cyrus Shahabi Title: Management of Virtual Replicas in Parallel Multimedia Information Systems Source: FODO 93. Abstract: Full Paper Author: S. Berson, S. Ghandeharizadeh, R. Muntz and X. Ju Title: Staggered Striping in Multimedia Information Systems Source: In the Proceedings of ACM SIGMOD, 1994 Abstract: Full Paper Author: S. Ghandeharizadeh, R. Hull, and D. Jacobs. Title: Design, Implementation, and Application of Heraclitus[Alg,C]. Source: In ACM-Transactions on Database Systems, Volume 21, Number 3, 370-426, September 1996. Abstract: Full Paper Author: Cyrus Shahabi Title: Scheduling the Retrievals of Continuous Media Objects. Source: USC Computer Science Ph.D. Thesis, Aug. 1996. Abstract: In multi-user multimedia information systems (e.g., {\em movie-on-demand}, {\em digital-editing}), scheduling the retrievals of continuous media objects becomes a challenging task. This is due to both$intra$and$inter$object time dependencies. Intra-object time dependency refers to the real-time display requirement of a continuous media object. Inter-object 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 having various length and display bandwidth requirement. 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 dissertation. To tackle this problem, we introduce a new class of task scheduling problems and distinguish it from the conventional scheduling problems. The uniqueness of these problems is mostly due to our assumed framework. The framework enables tasks to share resources (disk bandwidth) in a regular manner once activated. Hence, tasks compete with each other over the resources resulting in bandwidth contention. We identify two types of contention depending on the load imposed on the system. Both types of contention might be observed by any member of our class of task scheduling problems. Each scheduling problem is formally defined, and shown to be an intractable problem (NP-hard in strong sense). Subsequently, an on-line scheduling algorithm is proposed corresponding to each problem. The algorithms consist of some mechanisms and techniques that are independent of the system load. However, policies knowledgeable of the load are required to employ the mechanisms effectively. Hence, for reasonable combinations of scheduling problems and contention types, motivated by real-world applications, a number of alternative policies and heuristics are proposed. Finally, the policies are evaluated and compared by means of simulation studies. Briefly, we present and evaluate a set of mechanisms and policies to solve a new class of task scheduling problems, where a task corresponds to the retrieval of a continuous media object in a multi-disk/multi-user environment.

Full Paper

Author: Cyrus Shahabi, Amir Zarkesh, Jafar Adibi, and Vishal Shah

Title: Knowledge Discovery from Users Web-page Navigation

Source: Proceedings of Research Issues in Data Engineering (RIDE) Conference, April 1997.

Abstract:

Full Paper

Title: Continuous Display of Presentations Sharing Clips.

Source: ACM Multimedia Systems Journal, May 1995.

Abstract:

Full Paper

<

Author: Cyrus Shahabi, Mohammad H. Alshayeji, Shimeng Wang

Title: A Redundant Hierarchical Structure for a Distributed Continuous Media Server

Source: In IEEE/ACM IDMS'97

Abstract: The growing number of digital audio and video repositories has resulted in a desperate need for effective techniques to deliver data to users in a timely manner. Due to geographical distribution of users, it is not cost effective to have a centralized media server. In this paper, we investigate issues involved in the design of a distributed video server (DVS) to support movie-on-demand (MOD) application. We propose a redundant hierarchical (RedHi) architecture for DVS where the nodes are continuous media servers and the edges are dedicated network lines. With RedHi, each node has two or more parents. We show that the redundant links in RedHi yields a more fault-tolerant and efficient system. Our simulation results demonstrate that RedHi can tolerate a single link failure with no degradation in performance while with pure hierarchy almost 2.5% of requests are rejected due to the failure. In normal mode of operation, RedHi outperforms pure hierarchy significantly (160% improvement on the average when counting the number of rejections). In the context of RedHi, we also propose and evaluate alternative object management policies, resource reservation strategies, and load balancing heuristics.

Full Paper

Author: Weifeng Shi and Shahram Ghandeharizadeh

Title: Buffer Sharing in Video-On-Demand Servers

Source: ACM Sigmetrics Bulletin, 1997

Abstract: This paper describes a buffer sharing technique that strikes a balance between the use of disk bandwidth and memory in order to maximize the performance of a video-on-demand server. We make the key observation that the configuration parameters of the system should be independent of the physical characteristics of the data (e.g., popularity of a clip). Instead, the configuration parameters are fixed and our strategy adjusts itself dynamically at run-time to support a pattern of access to the video clips.

Full Paper

Title: An Evaluation of Alternative Disk Scheduling Techniques in Support of Variable Bit Rate Continuous Media

Source: International Conference on Extending Database Technology (EDBT'98), Mar. 1998.

Abstract: A number of recent studies have investigated scheduling techniques in support of variable bit rate (VBR) video. When compared with constant bit rate (CBR) video, VBR has a lower storage and bandwidth requirement while providing the same quality of images. However, a VBR video clip might exhibit a significant variance in the bit rate required to support its continuous display. The previous studies have proposed techniques to support the display of a VBR clip from two different perspectives: disk storage subsystem and the network. In this study, we propose a taxonomy of VBR disk scheduling techniques that includes those proposed for the network. The results demonstrate that a new class of disk scheduling techniques, termed Atomic-VR2 VITAL, is superior. Algorithms used to represent this class were adopted from the networking literature.

Full Paper

Author: Weifeng Shi

Title: DATA SHARING IN INTERACTIVE CONTINUOUS MEDIA SERVERS

Source: USC Computer Science Ph.D. Thesis, Aug. 1998.

Abstract: In a continuous media server that supports the display of audio or video clips (e.g., a video-on-demand server), requests from different clients are independent of each other and may arrive at random time. Commercial systems may strive to support hundreds, if not thousands of clients. Assigning an individual disk stream for each client may require very high disk bandwidth from a server. This makes the disk bandwidth a bottleneck resource, restricting the number of concurrent displays. One solution is to introduce additional disk drives into the server, however, this might result in a significant system cost that would render the system economically inviable. In this dissertation, we propose novel data sharing techniques to resolve the disk bandwidth bottleneck while making the overall system more cost-effective. We investigate two approaches: buffer sharing and batching. With buffer sharing, if one display of a clip lags another display of the same clip by a short time interval, then the portion between the two is retained in buffers to allow the lagging display to read data from buffers with no disk access. We propose a buffer sharing scheme that strikes a balance in trading memory for disk bandwidth to prevent system bottlenecks (either memory or disk bandwidth). Moreover, this scheme minimizes the system cost to meet a prespecified performance objective. With batching, requests are delayed in the hope of being merged with other requests for the same clip. These merged requests then form a batch and consume only one disk stream. We investigate environments that equip the client with local storage device (e.g ., rewritable DVD) to achieve data sharing among batches and support VCR operations. The local client storage reduces the disk bandwidth requirement at server side dramatically, however, it requires more resource (both disk bandwidth and memory) at client side which may diminish the cost-effectiveness of the environment. When compared with each other, batching with local storage distributes resources into each client, whereas buffer sharing centralizes resources in the server. This dissertation demonstrates that buffer sharing is a more cost-effective solution.

Full Paper

Author: Roger Zimmermann

Title: Continuous Media Placement and Scheduling in Heterogeneous Disk Storage Systems.

Source: USC Computer Science Ph.D. Thesis, Dec. 1998.

Abstract: 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 dissertation describes a taxonomy of techniques that ensure a continuous display of objects using a heterogeneous disk subsystem. This taxonomy consists of: (a) strategies that partition resources into homogeneous groups of disks and manage each independently, and (b) techniques that treat all disks uniformly, termed non-partitioning techniques. We introduce and evaluate three non-partitioning techniques: Disk Merging, Disk Grouping, and Staggered Grouping. Our results demonstrate that Disk Merging is the most flexible scheme while providing a competitive, low cost per simultaneous display. Finally, using an open simulation model, we compare Disk Merging with a partitioning technique. The obtained results confirm the superiority of Disk Merging.

Full Paper

Author: S. Ghandeharizadeh and S. H. Kim.

Title: A Comparison of Alternative Continuous Display Techniques with Heterogeneous Multi-Zone Disks.
Source: In Proceedings of CIKM'99.

Abstract: 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, HP's Track Pairing, and USC's FIXB and dead-line driven techniques. 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.

Full Paper

Title: Alternative Approaches to Distribute an E-Commerce Document Management System.
Source: In International Workshop on Research Issues in Data Engineering (RIDE) 2001.

Abstract: This experience paper describes newsblaster.com, a commercial document management system that facilitates exchange of news worthy documents between two user communities: a) editor of newspapers and magazines who seek to publish articles, and b) member companies who want to disseminate information such as new product offerings, product recalls, alliances with other companies, etc. We focus on the Internet connection of a single node web server as the system bottleneck and discuss three alternative approaches to distribute the application across multiple nodes. The first, termed vertical, analyzes the semantics of the application and distributes it across multiple nodes based on its community of users and how they access the system. The second, termed horizontal, declusters the application's data across multiple nodes with the objective to distribute client requests evenly across these nodes. Hybrid, our third approach, considers a horizontal partitioning of services identified by a vertical partitioning. We describe the application of each approach to newsblaster.

Full Paper

Author: J. Eisenstein, S. Ghandeharizadeh, C. Shahabi, G. Shanbhag and R. Zimmermann

Title: Alternative Representations and Abstractions for Moving Sensors Databases
Source: In CIKM 2001

Abstract: Moving sensors refers to an emerging class of data intensive applications that impacts 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 hearing 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 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 folds. 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 retrieval of data in support of query processing. We quantify the tradeoff associated with these alternatives using empirical data from RoboCup soccer matches.

Author: I. Kamel, T. Niranjan and S. Ghandeharizadeh

Title: A Novel Deadline Driven Disk Scheduling Algorithm for Multi-Priority Multimedia Objects.
Source: In International Conference on Data Engineering, February 2000.

Abstract: In this paper, 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 (a) maintaining one queue for all requests, and (b) 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 prioirty 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).

Full Paper

Author: S. Ghandeharizadeh, L. Huang and I. Kamel

Title: A Cost Driven Disk Scheduling Algorithm for Multimedia Object Retrieval
Source: In IEEE Transactions on Multimedia

Abstract: This paper describes a novel cost-driven disk scheduling algorithm for environments consisting of multi-priority requests. An example application is a video-on-demand 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 multi-queue'' 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.

Title: Delivery of Continuous Media in Ad-Hoc Networks of Wireless Devices.
Source: Distinguished Lecturer Series, Wright State University, December 8, 2004.

Abstract: Ad-hoc networks of wireless devices are essential to many civilian and military applications. An example civilian application is the "last-mile" challenge to deliver multimedia services, e.g., games/audio/video-on-demand, to households. This talk starts with the challenges of managing data and resources in an ad-hoc network of devices. It focuses on placement of data across devices and presents three alternative replication strategies: Simple, Halo-Block, and Halo-Clip. It concludes by summarizing the tradeoffs associated with these techniques, demonstrating a spectrum of placement strategies with Simple and Halo-Block at its two extreme ends.

This is joint-work with Tooraj Helmi, a Ph.D. student in the Computer Science department at USC.

Powerpoint presentation best viewed using Microsoft PowerPoint 2003.

Title: Greedy Cache Management Techniques for Mobile Devices.
Note: First International IEEE Workshop on Ambient Intelligence, Media, and Sensing (AIMS 07)}, co-located with International Conference on Data Engineering, Istanbul, Turkey, April 20, 2007.

Abstract: Mobile devices are configured with one or more wireless cards that provide limited radio-range and unreliable transmission. These energy-constrained devices are configured with a fixed amount of storage. A device may set aside a fraction of its local storage as a cache to minimize use of the network when servicing requests, enhancing metrics such as startup latency and data availability. In this paper, we focus on a repository of continuous media (audio and video) clips and study several greedy cache management techniques and their cache hit rates. This metric reflects what percentage of requests for clips is serviced when a mobile device is disconnected from the network. The device becomes network detached due to factors such as residing in a densely populated geographical location with over committed network bandwidth or travels to geographical areas with no base station coverage. We investigate repositories of both equisized and variable-sized clips, identifying limitations of the current techniques. Our primary contribution is development of three novel techniques to address these limitations. They are adaptable and provide competitive cache hit rates. One technique, called Dynamic Simple, provides a higher cache hit rate and adapts faster to changing patterns of access to clips when compared with other techniques.