A family of codes with a natural 2-D structure is presented, inspired by an application of redundant arrays of independent disks (RAID) type of architectures whose units are solid-state drives (SSDs). Arrays of SSDs behave differently from arrays of hard disk drives, since hard errors in sectors are common and traditional RAID approaches (like RAID 5 or RAID 6) may be either insufficient or excessive. An efficient solution to this problem is given by the new codes presented, called partial maximum distance separable (PMDS) codes.

High-end enterprise storage has traditionally consisted of monolithic systems with customized hardware, multiple redundant components and paths, and no single point of failure. Distributed storage systems realized through networked storage nodes offer several advantages over monolithic systems such as lower cost and increased scalability. In order to achieve reliability goals associated with enterprise-class storage systems, redundancy will have to be distributed across the collection of nodes to tolerate both node and drive failures. In this paper, we present alternatives for distributing this redundancy, and models to determine the reliability of such systems. We specify a reliability target and determine the configurations that meet this target. Further, we perform sensitivity analyses, where selected parameters are varied to observe their effect on reliability.

Despite the reliability of modern disks, recent studies have made it clear that a new class of faults, UndetectedDisk Errors (UDEs) also known as silent data corruption events, become a real challenge as storage capacity scales. While RAID systems have proven effective in protecting data from traditional disk failures, silent data corruption events remain a significant problem unaddressed by RAID. We present a fault model for UDEs, and a hybrid framework for simulating UDEs in large-scale systems. The framework combines a multi-resolution discrete event simulator with numerical solvers. Our implementation enables us to model arbitrary storage systems and workloads and estimate the rate of undetected data corruptions. We present results for several systems and workloads, from gigascale to petascale. These results indicate that corruption from UDEs is a significant problem in the absence of protection schemes and that such schemes dramatically decrease the rate of undetected data corruption.

We present a new family of XOR-based erasure codes primarily targeted for use in disk arrays. These codes have a unique data/parity layout, with both horizontal and vertical parity arrangements giving rise to the name HoVer codes. We give constructions that tolerate up to four disk failures. Though the codes are only approximately maximum distance separable (MDS), they have performance advantages over other codes at many common array sizes. In addition, they have fewer parameter constraints than many other codes which enable greater choices and flexibility in efficiency and performance trade-offs

High-end enterprise storage has traditionally consisted of monolithic systems with customized hardware, multiple redundant components and paths, and no single point of failure. Distributed storage systems realized through networked storage nodes offer several advantages over monolithic systems such as lower cost and increased scalability. In order to achieve reliability goals associated with enterprise-class storage systems, redundancy has to be distributed across the collection of nodes to tolerate both node and drive failures. In this paper, we present alternatives for distributing this redundancy, and models to determine the reliability of such systems. We specify a reliability target and determine the configurations that meet this target. Further, we perform sensitivity analyses where selected parameters are varied to observe their effect on reliability

Presents a new covariant basis, dubbed the quasi-orthogonal Q-spline basis, for the space of n-degree periodic uniform splines with k knots. This basis is obtained analogously to the B-spline basis by scaling and periodically translating a single spline function of bounded support. The construction hinges on an important theorem involving the asymptotic behavior (in the dimension) of the inverse of banded Toeplitz matrices. The authors show that the Gram matrix for this basis is nearly diagonal, hence, the name "quasi-orthogonal". The new basis is applied to the problem of approximating closed digital curves in 2D images by least-squares fitting. Since the new spline basis is almost orthogonal, the least-squares solution can be approximated by decimating a convolution between a resolution-dependent kernel and the given data. The approximating curve is expressed as a linear combination of the new spline functions and new "control points". Another convolution maps these control points to the classical B-spline control points. A generalization of the result has relevance to the solution of regularized fitting problems.

In image retrieval based on color, the weighted distance between color histograms of two images, represented as a quadratic form, may be defined as a match measure. However, this distance measure is computationally expensive and it operates on high dimensional features (O(N)). We propose the use of low-dimensional, simple to compute distance measures between the color distributions, and show that these are lower bounds on the histogram distance measure. Results on color histogram matching in large image databases show that prefiltering with the simpler distance measures leads to significantly less time complexity because the quadratic histogram distance is now computed on a smaller set of images. The low-dimensional distance measure can also be used for indexing into the database.>

The paper presents a new approach to least-squares spline fitting of curves. A new approximately orthogonal basis, the Q-spline basis, for n-degree uniform spline space is developed. Using the Q-spline basis, it is shown that least squares spline fitting can be approximated via a single fixed sized inner product for each control point. Another convolution maps these Q-spline control points to the classical B-spline control points. Tight error bounds on the approximation induced errors are derived. Finally a procedure for discrete least squares spline fitting via convolution is presented along with several examples. A generalization of the result has relevance to the solution of regularized fitting problems.>

On-line collections of images are growing larger and more common, and tools are needed to efficiently manage, organize, and navigate through them. The authors have developed a prototype system called QBIC which allows complex multi-object and multi-feature queries of large image databases. The queries are based on image content-the colors, textures, shapes, and positions of images and the objects/regions they contain. The system computes numeric features to represent the image properties and uses similarity measures based on these features for image retrieval. The focus of the paper is its user interface which allows a user to graphically pose and refine queries based on multiple visual properties of images and their objects.>

In image retrieval based on color, the weighted distance between color histograms of two images, represented as a quadratic form, may be defined as a match measure. However, this distance measure is computationally expensive (naively O(N/sup 2/) and at best O(N) in the number N of histogram bins) and it operates on high dimensional features (O(N)). We propose the use of low-dimensional, simple to compute distance measures between the color distributions, and show that these are lower bounds on the histogram distance measure. Results on color histogram matching in large image databases show that pre-filtering with the simpler distance measures leads to significantly less time complexity because the quadratic histogram distance is now computed on a smaller set of images. The low-dimensional distance measure can also be used for indexing into the database.>

We describe how the QBIC (Query By Image Content) system handles "multi-*" queries-queries on large image collections involving multifeatures of each image as a whole and of multiple objects within each image. The queries are based on properties of image content-such as colors, textures, shapes, and edges. The system computes a set of features to describe the above properties, uses distance-like measures on the features to provide similarity based retrieval, and has a graphical interface that enable users pose queries visually. In this paper, we present QBIC indexing algorithms that allow these "multi-*" queries to run efficiently.

This paper considers the problems of triangularizing and diagonalizing matrices over rings, with particular emphasis on the integral case. It begins with a description of fast algorithms for the computation of Hermite and Smith normal forms of integer matrices. Then it shows how to apply fast matrix multiplication techniques to the problem of triangularizing a matrix over a ring using elementary column operations. These general results lead to an algorithm for triangularizing integer matrices that has a faster running time than the known Hermite normal form algorithms. The triangular matrix that is computed has small entries like the Hermite normal form, and will suffice for many applications.