This paper deals with the problem of scheduling requests on disks for minimizing energy consumption. We first analyze several versions of the energy-aware disk scheduling problem based on assumptions on the arrival pattern of the requests. We show that the corresponding optimization problems are NP-complete. Then both optimal and heuristic scheduling algorithms are proposed to maximize the energy saving of a storage system. We evaluate our approach using multiple realistic I/O traces, disk simulator and energy model. The results show that we significantly reduce energy consumption up to 55 percent and achieve fewer disk spin-up/ down operations and shorter request response time as compared to other approaches. Since our approach attempts to dynamically assign each request to an energy optimized location, it can also benefit from other traditional static or semi-static solutions that rely on data placement or migration. Finally, we show that a write offloading technique can also be adapted into our solution to minimize the impact from write re quests in terms of energy consumption and request response time.

Saving energy for storage is of major importance as storage devices (and cooling them off) may contribute over 25 percent of the total energy consumed in a datacenter. Recent work introduced the concept of energy proportionality and argued that it is a more relevant metric than just energy saving as it takes into account the tradeoff between energy consumption and performance. In this paper, we present a novel approach, called FREP (Fractional Replication for Energy Proportionality), for energy management in large datacenters. FREP includes a replication strategy and basic functions to enable flexible energy management. Specifically, our method provides performance guarantees by adaptively controlling the power states of a group of disks based on observed and predicted workloads. Our experiments, using a set of real and synthetic traces, show that FREP dramatically reduces energy requirements with a minimal response time penalty.

This paper deals with the problem of scheduling requests on disks for minimizing energy consumption. We first analyze several versions of the energy-aware disk scheduling problem based on assumptions on the arrival pattern of the requests. We show that the corresponding optimization problems are NP-complete by reduction to the set cover or the independent set problem. Then both optimal and heuristic scheduling algorithms are proposed to maximize the energy saving of a storage system. Our evaluation results using two realistic traces show that our approach significantly reduces energy consumption up to 55% and achieves fewer disk spin-up/down operations and shorter request response time as compared to other approaches.

Recent studies have identified disk storage systems as one of the major consumers of power in data centers. Many disk power management (DPM) schemes were suggested where the power consumed by disks is reduced by spinning them down during long idle periods. Spinning the disks down and up results in additional energy and response time costs. For that reason, DPM schemes are effective only if the disks experience relatively long idle periods and the scheme does not introduce a severe response time penalty. In this paper we introduce a dynamic block exchange algorithm which switches data between disks based on the observed workload such that frequently accessed blocks end up residing on a few ldquohotrdquo disks thus allowing the majority of disks to experience longer idle periods. We validate the effectiveness of the algorithm with trace-driven simulations showing power savings of up to 50% with very small response time penalties.

It is anticipated that in the near future disk storage systems will surpass application servers and will become the primary consumer of power in the data centers. Shutting down of inactive disks is one of the more widespread solutions to save power consumption of disk systems. This solution involves spinning down or completely shutting off disks that exhibit long periods of inactivity and placing them in standby mode. A file request from a disk in standby mode will incur an I/O cost penalty as it takes time to spin up the disk before it can serve the file. In this paper, we address the problem of designing and implementing file allocation strategies on disk storage that save energy while meeting performance requirements of file retrievals. We present an algorithm for solving this problem with guaranteed bounds from the optimal solution. Our algorithm runs in O(nlogn) time where n is the number of files allocated. Detailed simulation results and experiments with real life workloads are also presented.

Datasets used in scientific and engineering applications are often modeled as dense multi-dimensional arrays. For very large datasets, the corresponding array models are typically stored out-of-core as array files. The array elements are mapped onto linear consecutive locations that correspond to the linear ordering of the multi-dimensional indices. Two conventional mappings used are the row-major order and the column-major order of multi-dimensional arrays. Such conventional mappings of dense array files highly limit the performance of applications and the extendibility of the dataset. Firstly, an array file that is organized in say row-major order causes applications that subsequently access the data in column-major order, to have abysmal performance. Secondly, any subsequent expansion of the array file is limited to only one dimension. Expansions of such out-of-core conventional arrays along arbitrary dimensions, require storage reorganization that can be very expensive. We present a solution for storing out-of-core dense extendible arrays that resolve the two limitations. The method uses a mapping function F*(), together with information maintained in axial vectors, to compute the linear address of an extendible array element when passed its k-dimensional index. We also give the inverse function, F*-1() for deriving the k-dimensional index when given the linear address. We show how the mapping function, in combination with MPI-IO and a parallel file system, allows for the growth of the extendible array without reorganization and no significant performance degradation of applications accessing elements in any desired order. We give methods for reading and writing sub-arrays into and out of parallel applications that run on a cluster of workstations, The axial-vectors are replicated and maintained in each node that accesses sub-array elements.

Very large multidimensional arrays are commonly used in data intensive scientific computations as well ason-line analytical processing applications referred to as MOLAP. The storage organization of such arrays on disks is done by partitioning the large global array into fixed size sub-arrays called chunks or tiles that form the units of data transfer between disk and memory. Typical queries involve the retrieval of sub-arrays in a manner that access all chunks that overlap the query results. An important metric of the storage efficiency is the expected number of chunks retrieved over all such queries. The question that immediately arises is "what shapes of array chunks give theminimum expected number of chunks over a query workload?" The problem of optimal chunking was first introduced by Sarawagi and Stonebraker [11] who gave an approximate solution. In this paper we develop exact mathematical models of the problem and provide exact solutions using steepest descent and geometric programming methods. Experimental results, using synthetic and real life workloads, show that our solutions are consistently within than 2.0% of the true number of chunks retrieved for any number of dimensions. In contrast, the approximate solution of [11] can deviate considerably from the true result with increasing number of dimensions and also may lead suboptimal chunk shapes.

Data analyses in scientific domains involve storage, retrieval, processing and visualization of large scale multidimensional datasets. The datasets incrementally grow by appending new data to the dataset without reorganizing the already allocated data storage. The datasets, typically modeled as k-dimensional arrays, are maintained in files where the array elements are allocated in a sequence of consecutive storage locations according to some ordering of an array mapping function. Such mapping functions limit the degree of extendibility of the arrays to one dimension only. To allowing new data elements to be appended to the dataset effectively implies allowing for the arbitrary extendibility of the array. We present a mapping function Fscr*(), that uses additional O(klogEscr) storage, where Escr is the number of array segments appended. The function is realized with approximately the approximately the same order of complexity as a conventional array function. The algorithm presented for addressing elements of datasets in extendible multi-dimensional array files apply equally well to addressing memory resident extendible arrays

Bitmap indices have been widely used in scientific applications and commercial systems for processing complex,multi-dimensional queries where traditional tree-based indices would not work efficiently. A common approach for reducing the size of a bitmap index for high cardinality attributes is to group ranges of values of an attribute into bins and then build a bitmap for each bin rather than a bitmap for each value of the attribute. Binning reduces storage costs,however, results of queries based on bins often require additional filtering for discarding it false positives, i.e., records in the result that do not satisfy the query constraints. This additional filtering,also known as ''candidate checking,'' requires access to the base data on disk and involves significant I/O costs. This paper studies strategies for minimizing the I/O costs for ''candidate checking'' for multi-dimensional queries. This is done by determining the number of bins allocated for each dimension and then placing bin boundaries in optimal locations. Our algorithms use knowledge of data distribution and query workload. We derive several analytical results concerning optimal bin allocation for a probabilistic query model. Our experimental evaluation with real life data shows an average I/O cost improvement of at least a factor of 10 for multi-dimensional queries on datasets from two different applications. Our experiments also indicate that the speedup increases with the number of query dimensions.

In this paper, we propose a new strategy for optimizing the placement of bin boundaries to minimize the cost of query evaluation using bitmap indices with binning. For attributes with a large number of distinct values, often the most efficient index scheme is a bitmap index with binning. However, this type of index may not be able to fully resolve some user queries. To fully resolve these queries, one has to access parts of the original data to check whether certain candidate records actually satisfy the specified conditions. We call this procedure the candidate check, which usually dominates the total query processing time. Given a set of user queries, we seek to minimize the total time required to an-swer the queries by optimally placing the bin boundaries. We show that our dynamic programming based algorithm can efficiently determine the bin boundaries. We verify our analysis with some real user queries from the Sloan Digital Sky Survey. For queries that require significant amount of time to perform candidate check, using our optimal bin boundaries reduces the candidate check time by a factor of 2 and the total query processing time by 40%.

The file-bundle caching problem arises frequently in scientific applications where jobs process several files concurrently. Consider a host system in a data-grid that maintains a disk cache for servicing jobs of file requests where a job is serviced only if all its requested files are present in the disk cache. Files must now be admitted into the cache and replaced in sets of file-bundles. We show that traditional caching algorithms based on file popularity measures do not perform well since they may hold in cache non-relevant combinations of files. We present and analyze a new caching algorithm for maximizing the throughput of jobs and minimizing data replacement costs at such data-grid hosts. We tested the new algorithm using a disk cache simulation model under a wide range of conditions of file request distributions, varying cache size, file size distribution, etc. The results show significant improvement over traditional caching algorithms.

Abstract We describe our experience with using several CORBA products to interconnect the software modules of a fairly complex system for file caching coordination from a tertiary storage. The application area that the system was designed for is High Energy and Nuclear Physics (HENP). In this application area, the volume of data reaches hundreds of terabytes per year and therefore it is impractical to store them on disk systems. Rather the data are organized into large files and stored on robotic tape systems that are managed by some Mass Storage System (MSS). The role of the Storage Access Coordination System (STACS) that we developed is to manage the caching of files from the MSS to a large disk cache that is shared by multiple HENP analysis programs. The system design involved multiple components developed by different people at different sites and the modules could potentially be distributed as well. In this paper we describe the architecture and implementation of STACS, emphasizing the inter‐module communication requirements. We describe the use of CORBA interfaces between system components, and our experience with using multi‐threaded CORBA and using hundreds of concurrent CORBA connections. STACS development was recently completed and is being incorporated in an operational environment that started to produce data in the summer of 2000 [1]. Copyright © 2001 John Wiley & Sons, Ltd.

In many scientific domains, experimental devices or simulation programs generate large volumes of data. The volumes of data may reach hundreds of terabytes and therefore it is impractical to store them on disk systems. Rather they are stored on robotic tape systems that are managed by some mass storage system (MSS). A major bottleneck in analyzing the simulated/collected data is the retrieval of subsets from the tertiary storage system. We describe the architecture and implementation of a Storage Access Coordination System (STACS) designed to optimize the use of a disk cache, and thus minimize the number of files read from tape. We achieve this by using a specialized index to locate the relevant data on tapes, and by coordinating file caching over multiple queries. We focus on a specific application area, a high energy physics data management and analysis environment. STACS was implemented and is being incorporated in an operational system, scheduled to go online at the end of 1999. We also include the results of various tests that demonstrate the benefits and efficiency gained of using the STACS.

In tertiary storage systems, the data is stored on multiple tape volumes where each tape is further divided into files. Since in many such systems the minimum unit of data transfer is a file, it is an important problem to match file sizes with the access patterns to the data. In general, if the file size is large relative to the query size it will lead to the transfer of large amounts of irrelevant data whereas small file sizes will incur an overhead penalty associated with reading each new file. In this work, we analyze the relationship between file sizes and query response times and provide a methodology to compute the optimal file size given information about the distribution of query sizes. Exact closed form solutions for the cost function are given for two common distributions.

Online analytical processing (OLAP) is becoming increasingly important as today's organizations frequently make business decisions based on statistical analysis of their enterprise data. This data is multidimensional and is derived from transactional data using various levels of aggregation. As the business model changes frequently, the multidimensional arrays must be extended in terms of the value ranges of each dimension and even new dimensions. We propose new methods to deal with disk resident extendible arrays. A new index data structure for keeping track of the extensions is introduced, and a performance analysis is conducted for array extension and retrievals.

In his paper “Should the two-headed disk be greedy? — Yes, it should” Hofri defined a “greedy policy” as follows. Assuming that the range of disk addresses is [0,1], a request at location x is served by the closest arm while the other arm jockeys to a new position, z, where z = (13)x or z = 23 + x3 depending on whether x is larger or smaller than 12. Hofri proved that this policy minimizes the expected seek distance for uniform request probabilities and conjectured that it stochastically dominates every other policy. Stochastic dominance is of practical importance in this context as it guarantees that a policy that optimizes expected seek distance also guarantees optimal seek time. The main result of this paper is a proof of Hofri's conjecture. The paper contains two proofs, the first establishes the conjecture, and the second shows that if the seek distance is stochastically minimized under a repositioning policy, then the policy must be Hofri's greedy policy and the request distribution must be uniform.

Future multimedia information systems are likely to manage thousands of videos with various lengths and display requirements. Mismatch of playback and delivery rates of compressed video data requires sophisticated buffer management algorithms to guarantee smooth playback of video data. In this paper, we address some of the many design and operational issues including buffer size requirements, refreshing policies, and support of multiple access points to the same video object. Three different buffer management strategies are proposed and analyzed to minimize the average waiting time while ensuring display without jerkiness. We also evaluate the effectiveness these buffer management strategies with a simulation study.>

This work deals with the problem of finding efficient access plans for retrieving a set of pages from a multi-disk system with replicated data. This paper contains two results related to this problem: (a) We solve the problem of finding an optimal access path by transforming it into a network flow problem. We also indicate how our method may be employed in dynamic environments where some (or all) of the disks have a preexisting load, are heterogeneous, and reside on different servers. (b) We present a lower bound for the worst case response time of a request under all replication schemes, and also discuss the replication scheme that results in this lower bound. We then use simulation to show how this replication scheme can also greatly reduce the average case response time.

We describe the design and implementation of a distributed parallel storage system that uses high-speed ATM networks as a key element of the architecture. Other elements include a collection of network-based disk block servers, and an associated name server that provides some file system functionality. The implementation is based on user level software that runs on UNIX workstations. Both the architecture and the implementation are intended to provide for easy and economical scalability. This approach has yielded a data source that scales economically to very high speed. Target applications include online storage for both very large images and video sequences. This paper describes the architecture, and explores the performance issues of the current implementation.>

Optimal arrangements of cartridges and file partitioning schemes are examined in carousel type mass storage systems using Markov decision theory. It is shown that the Organ-Pipe Arrangement is optimal under different storage configurations for both the anticipatory as well as the non-anticipatory versions of the problem. When requests arrive as per an arbitrary renewal process this arrangement is also shown to minimize the mean queueing delay and the time spent in the system by the requests.

Techniques for obtaining random point samples from spatial databases are described. Random points are sought from a continuous domain that satisfy a spatial predicate which is represented in the database as a collection of polygons. Several applications of spatial sampling are described. Sampling problems are characterized in terms of two key parameters: coverage (selectivity), and expected stabbing number (overlap). Two fundamental approaches to sampling with spatial predicates, depending on whether one samples first or evaluates the predicate first, are discussed. The approaches are described in the context of both quadtrees and R-trees, detailing the sample-first, A/R-tree, and partial area tree algorithms. A sequential algorithm, the one-pass spatial reservoir algorithm, is also described.>

The paper describes three fast loading algorithms for grid files on a parallel shared nothing architecture. The algorithms use dynamic programming and sampling to effectively partition the data file among the processors to achieve maximum parallelism in answering range queries. Each processor then constructs in parallel its own portion of the grid file. Analytical results and simulations are given for the three algorithms.

A practical join processing strategy that allows effective utilization of arbitrary degrees of parallelism in both the I/O subsystem and join processing subsystems is presented. Analytic bounds on the minimum execution time, minimum number of processors, and processor utilization are presented along with bounds on the execution time, given a fixed number of processors. These bounds assume that sufficient buffers are available. An analytic lower bound on buffer requirements as well as a practical heuristic for use in limited buffer environments are also presented. A sampling of corroborative simulation results are included.>

This paper deals with I/O throughput maximization in a single processor/multidisk database system, by means of optimal allocation of entire relations (or other nonfragmented data objects) to disks. We examine the cases in which such allocation is beneficial, and present a mathematical formulation of the problem. This formulation is shown to be flexible enough to accommodate various objectives and constraints of a typical system design.>

The authors discuss materialized views of random sampling queries of a relational database. They show how to maintain such views in the presence of insertions, deletions, and updates of the base relations. The basic idea is to reuse the maximal portion of the original sample when constructing the updated sample. The results are based on a synthesis of view update techniques and sampling algorithms. It is demonstrated that maintenance of materialized sample views may be substantially cheaper than resampling.>

The common model for analyzing seek distances on a magnetic disk uses a continuous approximation in which the range of motion of the disk arm is the interval [0,1]. In this model, both the current location of the disk arm and the location of the next request are assumed to be points uniformly distributed on the interval [0,1] and therefore the expected seek distance to service the next request is 1/3. In many types of databases including scientific, object oriented, and multimedia database systems, a disk service request may involve fetching very large objects which must be transferred from the disk without interruption. In this paper we show that the common model does not accurately reflect disk arm movement in such cases as both the assumption of uniformity and the range of motion of the disk arm may depend on the size of the objects. We propose a more accurate model that takes into consideration the distribution of the sizes of the objects fetched as well as the disk arm scheduling policy. We provide closed form expressions for the expected seek distance in this model under various assumptions on the distribution of object sizes and the capability of the disk arm to read in both directions and to correct its position before the next read is performed.

Algorithms based on grid files as the underlying spatial index are presented for spatial joins in databases which store images, pictures, maps and drawings. For typical data distributions, it is shown that the size of the index and its maintenance cost are relatively small. The effect of diagonal distributions and different densities of the two grid files on the size of the index is also studied. It is expected that similar algorithms can be employed with other types of multidimensional data structures.>

In this paper we discuss simple random sampling from hash files on secondary storage. We consider both iterative and batch sampling algorithms from both static and dynamic hashing methods. The static methods considered are open addressing hash files and hash files with separate overflow chains. The dynamic hashing methods considered are Linear Hash files [Lit80] and Extendible Hash files [FNPS79]. We give the cost of sampling in terms of the cost of successfully searching a hash file and show how to exploit features of the dynamic hashing methods to improve sampling efficiency.

The concept of precision in databases for both queries and data is introduced and formalized. Algorithms for maintaining a database at a specified degree of precision are presented and analyzed. It is shown how these algorithms can be used to choose an optimal query plan by means of a query optimizer.>

A family of practical algorithms is presented to schedule join execution in a shared-memory multiprocessor environment. The algorithms are based on page connectivity graphs and determine when to read each data page into memory and how to schedule page joins on the available processors. The goal is to overlap page reads with parallel join execution in such a way that both the number of processors and total duration of join processing time are minimized. Upper and lower bounds are derived on the number of processors required to complete join execution in optimal time. A description is given of a general strategy for generating read schedules that it is conjectured can be processed in minimal time (over all read schedules on any number of processors) and a family of practical algorithms utilizing an arbitrary number of lookahead steps to approximate this general strategy.>

Access methods for multidimensional data have attracted much research interest in recent years. In general, the data structures proposed for this problem partition the database into a set of disk pages (buckets). Access to the buckets is provided by searching a directory of some type such as a tree directory or inverted index or by computation of a multiattribute hash function. Examples of the first approach are Multidimensional B-trees[Sch82], K-D-B trees[Rob81] (see also [Sam84] for a survey of these methods) whereas multiattribute hashing methods are described for example in [Rot74],[Aho79],[Riv76] and [Ram83]. In addition, there are also hybrid methods which combine hashing with a directory of some type [Ore84],[Nie84], [Fag79].

Article Analytical modeling of materialized view maintenance Share on Authors: Jaideep Srivastava Computer Science Division, University of California Berkeley and Computer Science Research, Lawrence Berkeley Laboratories, University of California, Berkeley, CA Computer Science Division, University of California Berkeley and Computer Science Research, Lawrence Berkeley Laboratories, University of California, Berkeley, CAView Profile , Doron Rotem Computer Science Research, Lawrence Berkeley Laboratories, University of California, Berkeley, CA Computer Science Research, Lawrence Berkeley Laboratories, University of California, Berkeley, CAView Profile Authors Info & Claims PODS '88: Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsMarch 1988 Pages 126–134https://doi.org/10.1145/308386.308425Published:01 March 1988 26citation292DownloadsMetricsTotal Citations26Total Downloads292Last 12 Months8Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The problem of multidimensional file partitioning (MDFP) arises in large databases that are subject to frequent range queries on one or more attributes. In an MDFP scheme, the search attribute space is partitioned into cells, which are mapped to physical disk locations. This mapping preserves the order of the search attribute values so that range queries can be answered most efficiently, while maintaining good performance for other types of queries. Recently, MDFP schemes have been suggested to include both dynamic and static file organizations. Optimal and heuristic MDFP algorithms are developed for the static case. The results of extensive computational experiments show that the proposed heuristics perform better than known static ones. It is also shown that incorporating a static algorithm into a dynamic MDFP such as a grid file at conversion and/or periodical reorganization points significantly improves the resulting storage utilization of the data file and decreases the size of the directory file.>

In this paper, we propose a partitioning scheme of files in a temporal database system, and develop algorithms to minimize the overflow associated with that scheme. The proposed partitioning is suitable for range queries and aggregation operations along the time dimension. Simulation results show that the partitioning algorithms proposed in this paper result in better performance than in the case of a grid-type partitioning.

fixed k

Abstract An algorithm for selecting the kth smallest element of a distributed file using shout‐echo communication primitives is presented. It is shown that, for large values of k (e. g., the median), the proposed algorithm improves the existing upperbound.

The problem of sorting a file distributed over a number of sites of a communication network is examined. Two versions of this problem are investigated; distributed solution algorithms are presented; and their communication complexity analyzed both in the worst and in the average case. The worst case bounds are shown to be sharp, with respect to order of magnitude, for large files.

Tills paper establishes several lower bounds of the form f~(nlogn) for the number of messages needed to find the maximum label in a circular configuration of n labeled processes with no central controller.

The problem of determining in a distributed fashion the centers and the medians of a network is considered.Lower bounds on the time needed to solve these problems are proved.Algorithms that achieve those bounds for tree networks are presented; the number of exchanged messages is linear in the number of nodes.These techniques are extended to work on general networks in O(n) time units exchanging O(n.e) messages, where n is the number of nodes and e the number of edges in the network.In addition, a comparison with a simple heuristic approach is included.

This paper deals with the problem of finding the maximum of a distributed set of distinct integers. The problem is to be solved by a completely distributed asynchronous algorithm.

Abstract A new class of intersection graphs called circular permutation graphs is introduced and characterized. A circular permutation diagram for a permutation P (1),…, P ( n ) consists of two circles C 1 and C 2 ; the numbers 1′, 2′,…,n′ and P (1),…, P ( n ) on C 1 and C 2 , respectively; and a set of n chords 1, 2,…, n connecting i to i ′ such that two chords intersect each other at most once. A graph G represents a circular permutation diagram if there is a labeling of V ( G ) with {1,…, n} such that i is adjacement to j iff i and j intersect. Graphs which represent at least one permutation diagram are called circular permutation graphs. Circular permutation graphs generalize permutation graphs [2], [8] and are embedded in the set of comparability graphs [4]. The characterization leads to a recognition algorithm which requires O (δ|E|) steps where δ is the maximum degree of a vertex.

A new algorithm to generate all topological sorting arrangements is presented. It is compared with other such algorithms and is found to be more efficient.

Some experiences with the Johnson-Trotter permutation generation algorithm are reported. A version which generates strings containing permutations as subsequences and has the offset maintenance removed is proposed. This version is faster than any other known algorithm and has indexing properties which make it of practical use.

Abstract A circle diagram consists of a circle C and a set of n chords. This diagram defines a graph with n vertices where each vertex corresponds to a chord, and two vertices are adjacent if their corresponding chords intersect in C. A graph G is called a circle graph if it is defined by some circle diagram. An algorithm which requires O(n2) steps to generate one maximum clique is presented. The algorithm can also be used to generate all maximum cliques where the number of steps need to generate each additional maximum clique is linear in its size. This compares favourably with Gavril's algorithm [4] which works in O(n3) steps.

An efficient algorithm for generating and indexing all shapes of n-noded binary trees is described The algorithm is based on a correspondence between binary trees and the class of stack-sortable permutations.together with a representation of such permutatmns as ballot sequences Justification for the related procedures is given, and their efficiency estabhshed by comparison to other approaches