202158
An adaptive packed-memory array
The <i>packed-memory array (PMA)</i> is a data structure that maintains a dynamic set of <i>N</i> elements in sorted order in a Θ<i>(N)</i>-sized array. The idea is to intersperse Θ<i>(N)</i> empty spaces or <i>gaps</i> among the elements so that only a small number of elements need to be shifted around on an insert or delete. Because the elements are stored physically in sorted order in memory or on disk, the PMA can be used to support extremely efficient range queries. Specifically, the cost to scan <i>L</i> consecutive elements is <i>O(1+L/B)</i> memory transfers.This paper gives the first <i>adaptive packed-memory array (APMA)</i>, which automatically adjusts to the input pattern. Like the original PMA, any pattern of updates costs only <i>O</i>(log<sup>2</sup> <i>N</i>) amortized element moves and <i>O</i>(1+(log<sup>2</sup> <i>N)/B)</i> amortized memory transfers per update. However, the APMA performs even better on many common input distributions achieving only <i>O</i>(log<i>N</i>) amortized element moves and <i>O</i>(1+(log<i>N)/B)</i> amortized memory transfers. The paper analyzes <i>sequential</i> inserts, where the insertions are to the front of the APMA, <i>hammer</i> inserts, where the insertions "hammer" on one part of the APMA, <i>random</i> inserts, where the insertions are after random elements in the APMA, and <i>bulk</i> inserts, where for constant α∈[0,1], <i>N</i><sup>α</sup> elements are inserted after random elements in the APMA. The paper then gives simulation results that are consistent with the asymptotic bounds. For sequential insertions of roughly 1.4 million elements, the APMA has four times fewer element moves per insertion than the traditional PMA and running times that are more than seven times faster.
9136187
Improved bounds on sorting with length-weighted reversals
We study the problem of sorting integer sequences and permutations by length-weighted reversals. We consider a wide class of cost functions, namely f(l) = lα for all α ≥ 0, where l is the length of the reversed subsequence. We present tight or nearly tight upper and lower bounds on the worst-case cost of sorting by reversals. Then we develop algorithms to approximate the optimal cost to sort a given input. Furthermore, we give polynomial-time algorithms to determine the optimal reversal sequence for a restricted but interesting class of sequences and cost functions. Our results have direct application in computational biology to the field of comparative genomics.
872013
Integrative Array Analyzer: a software package for analysis of cross-platform and cross-species microarray data
The rapid accumulation of microarray data translates into an urgent need for tools to perform integrative microarray analysis. Integrative Array Analyzer is a comprehensive analysis and visualization software toolkit, which aims to facilitate the reuse of the large amount of cross-platform and cross-species microarray data. It is composed of the data preprocess module, the co-expression analysis module, the differential expression analysis module, the functional and transcriptional annotation module and the graph visualization module.
12997444
Towards realizing a formal RBAC model in real systems
There still exists an open question on how formal models can be fully realized in the system development phase. The Model Driven Development (MDD) approach has been recently introduced to deal with such a critical issue for building high assurance software systems.
 There still exists an open question on how formal models can be fully realized in the system development phase. The Model Driven Development (MDD) approach has been recently introduced to deal with such a critical issue for building high assurance software systems.
 The MDD approach focuses on the transformation of high-level design models to system implementation modules. However, this emerging development approach lacks an adequate procedure to address security issues derived from formal security models. In this paper, we propose an empirical framework to integrate security model representation, security policy specification, and systematic validation of security model and policy, which would be eventually used for accommodating security concerns during the system development. We also describe how our framework can minimize the gap between security models and the development of secure systems. In addition, we overview a proof-of-concept prototype of our tool that facilitates existing software engineering mechanisms to achieve the above-mentioned features of our framework.
39571798
Rough Set Based Image Texture Recognition Algorithm
Rough set theory is emerging as a new tool for dealing with fuzzy and uncertain data. In recent years, it has been successfully applied in such fields as machine learning, data mining, knowledge acquiring, etc. In this paper, rough set theory is applied to image texture recognition. Based on rough set and generalized approximate space, we develop a rough set based image texture recognition algorithm. We compare it with some other algorithms and the results show that our algorithm is effective and efficient.
14469938
Verification of Reduced Convergence Rates
In this short article, we recalculate the numerical example in Křížek and Neittaanmäki (1987) for the Poisson solution u=xσ(1−x)sinπy in the unit square S as . By the finite difference method, an error analysis for such a problem is given from our previous study by where h is the meshspacing of the uniform square grids used, and C1 and C2 are two positive constants. Let ε=u−uh, where uh is the finite difference solution, and is the discrete H1 norm. Several techniques are employed to confirm the reduced rate of convergence, and to give the constants, C1=0.09034 and C2=0.002275 for a stripe domain. The better performance for arises from the fact that the constant C1 is much large than C2, and the h in computation is not small enough.