308038
Projecting the performance of decision support workloads on systems with smart storage (SmartSTOR)
Recent developments in both hardware and software have made it worthwhile to consider embedding intelligence in storage to handle general-purpose processing that can be off-loaded from the hosts. In particular, low-cost processing power is now widely available and software can be made robust, secure and mobile. In this paper, we propose a general smart storage (SmartSTOR) architecture in which a processing unit that is coupled to one or more disks can be used to perform such off-loaded processing. A major part of the paper is devoted to understanding the performance potential of the SmartSTOR architecture for decision support workloads. Our analysis suggests that there is a definite performance advantage in using fewer but more powerful processors, a result that bolsters the case for sharing a powerful processor among multiple disks. As for software architecture, we find that the off-loading of database operations that involve only a single relation is not very promising. In order to achieve significant speed-up, we have to consider the off-loading of multiple-relation operations. In general, if embedding intelligence in storage is an inevitable architectural trend, we have to focus on developing parallel software systems that can effectively take advantage of the large number of processing units that will be in the system.
7063986
Fossilized index: the linchpin of trustworthy non-alterable electronic records
As critical records are increasingly stored in electronic form, which tends to make for easy destruction and clandestine modification, it is imperative that they be properly managed to preserve their trustworthiness, i.e., their ability to provide irrefutable proof and accurate details of events that have occurred. The need for proper record keeping is further underscored by the recent corporate misconduct and ensuing attempts to destroy incriminating records. Currently, the industry practice and regulatory requirements (e.g., SEC Rule 17a-4) rely on storing records in WORM storage to immutably preserve the records. In this paper, we contend that simply storing records in WORM storage is increasingly inadequate to ensure that they are trustworthy. Specifically, with the large volume of records that are typical today, meeting the ever more stringent query response time requires the use of direct access mechanisms such as indexes. Relying on indexes for accessing records could, however, provide a means for effectively altering or deleting records, even those stored in WORM storage.In this paper, we establish the key requirements for a fossilized index that protects the records from such logical modification. We also analyze current indexing methods to determine how they fall short of these requirements. Based on our insights, we propose the Generalized Hash Tree (GHT). Using both theoretical analysis and simulations with real system data, we demonstrate that the GHT can satisfy the requirements of a fossilized index with performance and cost that are comparable to regular indexing techniques such as the B-tree. We further note that as records are indexed on multiple fields to facilitate search and retrieval, the records can be reconstructed from the corresponding index entries even after the records expire and are disposed of, Therefore, we also present a novel method to eliminate this disclosure risk by allowing an index entry to be effectively disposed of when its record expires.
6036700
Functional Implementation Techniques for CPU Cache Memories
As the performance gap between processors and main memory continues to widen, increasingly aggressive implementations of cache memories are needed to bridge the gap. In this paper, we consider some of the issues that are involved in the implementation of highly optimized cache memories and survey the techniques that can be used to help achieve the increasingly stringent design targets and constraints of modern processors. In particular, we consider techniques that enable the cache to be accessed quickly and still achieve a good hit ratio. We also consider issues such as area cost and bandwidth requirements. Trace-driven simulations of a TPC-C-like workload and selected applications from the SPEC95 benchmark suite are used in the paper to compare the performance of some of the techniques.
2578042
Trustworthy keyword search for regulatory-compliant records retention
Recent litigation and intense regulatory focus on secure retention of electronic records have spurred a rush to introduce Write-Once-Read-Many (WORM) storage devices for retaining business records such as electronic mail. However, simply storing records in WORM storage is insuffcient to ensure that the records are trustworthy, i.e., able to provide irrefutable proof and accurate details of past events. Specifically, some form of index is needed for timely access to the records, but unless the index is maintained securely, the records can in effect be hidden or altered, even if stored in WORM storage. In this paper, we systematically analyze the requirements for establishing a trustworthy inverted index to enable keyword-based search queries. We propose a novel scheme for effcient creation of such an index and demonstrate, through extensive simulations and experiments with an enterprise keyword search engine, that the scheme can achieve online update speeds while maintaining good query performance. In addition, we present a secure index structure for multi-keyword queries that supports insert, lookup and range queries in time logarithmic in the number of documents.
931369
Improving cache performance with balanced tag and data paths
There are two concurrent paths in a typical cache access --- one through the data array and the other through the tag array. The path through the data array drives the selected set out of the array. The path through the tag array determines cache hit/miss and, for set-associative caches, selects the appropriate line from within the selected set. In both direct-mapped and set-associative caches, the path through the tag array is significantly longer than that through the data array. In this paper, we propose a path balancing technique help match the delays of the tag and data paths. The basic idea behind this technique is to employ a separate subset of the tag array to decouple the one-to-one relationship between address tags and cache lines so as to achieve a design that provides higher performance. Performance evaluation using both TPC-C and SPEC92 benchmarks shows that this path balancing technique offers impressive improvements in overall system performance over conventional cache designs. For TPC-C, improvements in the range of 6% to 28% are possible.
11584462
The automatic improvement of locality in storage systems
Disk I/O is increasingly the performance bottleneck in computer systems despite rapidly increasing disk data transfer rates. In this article, we propose Automatic Locality-Improving Storage (ALIS), an introspective storage system that automatically reorganizes selected disk blocks based on the dynamic reference stream to increase effective storage performance. ALIS is based on the observations that sequential data fetch is far more efficient than random access, that improving seek distances produces only marginal performance improvements, and that the increasingly powerful processors and large memories in storage systems have ample capacity to reorganize the data layout and redirect the accesses so as to take advantage of rapid sequential data transfer. Using trace-driven simulation with a large set of real workloads, we demonstrate that ALIS considerably outperforms prior techniques, improving the average read performance by up to 50% for server workloads and by about 15% for personal computer workloads. We also show that the performance improvement persists as disk technology evolves. Since disk performance in practice is increasing by only about 8% per year, the benefit of ALIS may correspond to as much as several years of technological progress.
5208095
Decomposition of perfect graphs
Abstract We describe composition and decomposition schemes for perfect graphs, which generalize all recent results in this area, e.g., the amalgam and the 2-amalgam split. Our approach is based on the consideration of induced cycles and their complements in perfect graphs (as opposed to the consideration of cycles for defining biconnected or 3-connected graphs). Our notion of 1-inseparable graphs is “parallel” to that of biconnected graphs in that different edges in different inseparable components of a graph are not contained in any induced cycle or any complement of an induced cycle. Furthermore, in a special case which generalizes the join operation, this definition is self-complementary in a natural fashion. Our 2-composition operation, which only creates even induced cycles in the composed graphs, is based on two perfection-preserving vertex merge operations on perfect graphs. As a by-product, some new properties of minimally imperfect graphs are presented.
17795095
A Simple Test for the Consecutive Ones Property
A (0,1)-matrix satisfies the consecutive ones property if there exists a column permutation such that the one's in each row of the resulting matrix are consecutive. Booth and Lueker [1976] designed a linear time testing algorithm for this property based on a data structure called “PQ-trees”. This procedure is very complicated and the linear time amortized analysis is also rather involved. We develop an off-line testing algorithm for the consecutive ones property without using PQ-trees. Our approach is based on a decomposition technique which separates the rows into “prime” subsets which admit unique column orderings that realize the consecutive ones property. The success of this approach is based on finding a good “row ordering” to be tested iteratively.
269822
Visual Cue Cluster Construction via Information Bottleneck Principle and Kernel Density Estimation
Recent research in video analysis has shown a promising direction, in which mid-level features (e.g., people, anchor, indoor) are abstracted from low-level features (e.g., color, texture, motion, etc.) and used for discriminative classification of semantic labels. However, in most systems, such mid-level features are selected manually. In this paper, we propose an information-theoretic framework, visual cue cluster construction (VC3), to automatically discover adequate mid-level features. The problem is posed as mutual information maximization, through which optimal cue clusters are discovered to preserve the highest information about the semantic labels. We extend the Information Bottleneck framework to high-dimensional continuous features and further propose a projection method to map each video into probabilistic memberships over all the cue clusters. The biggest advantage of the proposed approach is to remove the dependence on the manual process in choosing the mid-level features and the huge labor cost involved in annotating the training corpus for training the detector of each mid-level feature. The proposed VC3 framework is general and effective, leading to exciting potential in solving other problems of semantic video analysis. When tested in news video story segmentation, the proposed approach achieves promising performance gain over representations derived from conventional clustering techniques and even the mid-level features selected manually.
1251407
Reference metadata extraction using a hierarchical knowledge representation framework
The integration of bibliographical information on scholarly publications available on the Internet is an important task in the academic community. Accurate reference metadata extraction from such publications is essential for the integration of metadata from heterogeneous reference sources. In this paper, we propose a hierarchical template-based reference metadata extraction method for scholarly publications. We adopt a hierarchical knowledge representation framework called INFOMAP, which automatically extracts metadata. The experimental results show that, by using INFOMAP, we can extract author, title, journal, volume, number (issue), year, and page information from different kinds of reference styles with a high degree of precision. The overall average accuracy is 92.39% for the six major reference styles compared in this study.
5724385
An iterative relaxation technique for the NMR backbone assignment problem
NMR spectroscopy is one of the popular experiments to determine protein structures. An important stage of protein structure determination by using NMR is protein backbone resonance assignment (or backbone assignment for short). Due to the messiness and disorder of NMR spectral data, backbone assignment is usually a tedious and time-consuming manual work. This raises a great interest in developing an efficient and automatic method to perform backbone assignment. An iterative algorithm is proposed that is equipped with two operations: grouping and linking. Grouping is responsible for peak picking and part of connectivity determination. Ideally, those peaks with the same H/sup N/ and N chemical shifts can be grouped together; peaks belonging to the same group can be used to determine the order of two consecutive spin systems. However, in real situation, grouping is a difficult task due to false positives and false negatives. We sometimes add hypothetic peaks to tackle false negatives and use linking operation to remove false positives. Linking is responsible for part of connectivity determination and backbone assignment. Given a protein sequence and partial connectivity information, we try to link connected spin systems as much as possible. False positive spin systems may create conflicts in the linking stage. To find a good assignment on a noisy dataset, the backbone assignment problem is modeled as a maximum independent set problem. Although the problem is NP-complete, there are heuristic methods that obtain pretty good results.