6232755
Algorithms for minimum covering by cliques and maximum clique in claw-free perfect graphs
An algorithm is given for determining a minimum cardinality clique cover ongraphs that do not contain claws, odd holes or odd anti-holes. These graphs are also shown to be perfect so that we obtain a new proof of the strong perfect graph theorem for claw-free graphs. A by-product of our analysis is an algorithm for determining a maximum cardinality clique on claw-free perfect graphs.
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.
87458683
A Knowledge-Based Approach to Protein Local Structure Prediction
Local structure prediction can facilitate ab initio structure prediction, protein threading, and remote homology detection. However, previous approaches to local structure prediction suffer from poor accuracy. In this paper, we propose a knowledge-based prediction method that assigns a measure called the local match rate to each position of an amino acid sequence to estimate the confidence of our approach. To remedy prediction results with low local match rates, we use a neural network prediction method. Then, we have a hybrid prediction method, HYPLOSP (HYbrid method to Protein LOcal Structure Prediction) that combines our knowledge-based method with a neural network method. We test the method on two different structural alphabets and evaluate it by QN, which is similar to Q3 in secondary structure prediction. The experimental results show that our method yields a significant improvement over previous studies.
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.
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.
15536153
Applying Cilk in Provably Efficient Task Scheduling
We consider the application of Cilk, a C-based runtime system for multithreaded parallel programming, in scheduling static task graphs. We assume no pre-emption of task execution and no prior knowledge of the task execution times. Given a task graph G, the output of the scheduling algorithm is a Cilk program which, when executed, will initiate the tasks in a manner consistent with the precedence requirement of G. We rst report a restriction arising from the computational model of Cilk in task scheduling, in the sense that optimal scheduling may not be achievable with Cilk for certain task graphs. Luckily the restriction does not fundamentally hinder the practical application of the Cilk tool, as we next show that it is possible to quickly produce a reasonably good quality schedule in the sense of expected execution time. Given a task graph, our algorithm partitions the task nodes into subsets called bundles. Each bundle is mapped into a Cilk procedure. The output program then consists of a series of such Cilk procedures. By using Tarjan's disjoint-set algorithm for handling the bundles, we demonstrate that the parallel schedule can be derived in O(n + e) time for all practical purposes, whereand e denote the number of nodes and edges in the task graph. We further show that, with P processors, the expected completion time for the scheduled tasks achieves a near-optimum of T P T 1 = P + 1:5T 1 , where T 1 denotes the work, i.e., the sequential execution time of all tasks, and T 1 denotes the critical path, i.e., the total execution time of all tasks lying on the longest dependency path. Our work represents a serious attempt to use Cilk to handle complicated types of concurrency.
32109322
RIBRA-An Error-Tolerant Algorithm for the NMR Backbone Assignment Problem
We develop an iterative relaxation algorithm, called RIBRA, for NMR protein backbone assignment. RIBRA applies nearest neighbor and weighted maximum independent set algorithms to solve the problem. To deal with noisy NMR spectral data, RIBRA is executed in an iterative fashion based on the quality of spectral peaks. We first produce spin system pairs using the spectral data without missing peaks, then the data group with one missing peak, and finally, the data group with two missing peaks. We test RIBRA on two real NMR datasets: hb-SBD and hbLBD, and perfect BMRB data (with 902 proteins) and four synthetic BMRB data which simulate four kinds of errors. The accuracy of RIBRA on hbSBD and hbLBD are 91.4% and 83.6%, respectively. The average accuracy of RIBRA on perfect BMRB datasets is 98.28%, and 98.28%, 95.61%, 98.16% and 96.28% on four kinds of synthetic datasets, respectively.