We address the problem of cache replacement policies for Storage Resource Managers (SRMs) that are used in Data Grids. An SRM has a disk storage of bounded capacity that retains some N objects. A replacement policy is applied to determine which object in the cache needs to be evicted when space is needed. We define a utility function for ranking the candidate objects for eviction and then describe an efficient algorithm for computing the replacement policy based on this function. This computation takes time O (log N). We compare our policy with traditional replacement policies such as Least Frequently Used (LFU), Least Recently Used (LRU), LRU-K, Greedy Dual Size (GDS), etc., using simulations of both synthetic and real workloads of file accesses to tertiary storage. Our simulations of replacement policies account for delays in cache space reservation, data transfer and processing. The results obtained show that our proposed method is the most cost effective cache replacement policy for Storage Resource Managers (SRM).

In this paper we describe our experiences with the design, the deployment, and the initial operation of a distributed system for the remote monitoring and operation of multiple heterogeneous commercial buildings across the Internet from a single control center. Such systems can significantly reduce building energy usage. Our system is distinguished by its ability to interface to multiple heterogeneous legacy building Energy Management Control Systems (EMCSs), its use of the Common Object Request Broker Architecture (CORBA) standard communication protocols for the former task, development of a standardized naming system for monitoring points in buildings, the use of a relational DBMS to store and process time series data, automatic time and unit conversion, and a scripted time series visualization system. We describe our design choices and our experiences in development and operation. We note requirements for future distributed systems software for interoperability of heterogeneous re...

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

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.

fixed k

With the availability of very large, relatively inexpensive main memories, it is becoming possible keep large databases resident in main memory In this paper we consider the changes necessary to permit a relational database system to take advantage of large amounts of main memory We evaluate AVL vs B+-tree access methods for main memory databases, hash-based query processing strategies vs sort-merge, and study recovery issues when most or all of the database fits in main memory As expected, B+-trees are the preferred storage mechanism unless more than 80--90% of the database fits in main memory A somewhat surprising result is that hash based query processing strategies are advantageous for large memory situations

The STOCHOPT automatic file migration policy (proposed by A.J. Smith) minimizes the expected retention and recall costs of an abitrarily sized file. We consider the application of the STOCHOPT policy to a file system in which the file inter-reference time (IRT) distributions are characterized by strictly monotonically decreasing hazard rates (SDHR) (also known as decreasing failure rates, DFR). We show that in this case the STOCHOPT policy can be simply stated in terms of a scaled hazard rate, i.e., the hazard rate divided by the file size. Such decreasing failure rate distributions have been used by Smith to model empirically observed file inter-reference times.