OpenRaiser/Intern-Atlas huggingface dataset:
Simplifying Complex Software Assembly: The Component Retrieval Language and Implementation
Venue: arXiv cs.PL 2010
Year: 2010

Assembling simulation software along with the associated tools and utilities is a challenging endeavor, particularly when the components are distributed across multiple source code versioning systems. It is problematic for researchers compiling and running the software across many different supercomputers, as well as for novices in a field who are often presented with a bewildering list of software to collect and install. In this paper, we describe a language (CRL) for specifying software components with the details needed to obtain them from source code repositories. The language supports public and private access. We describe a tool called GetComponents which implements CRL and can be used to assemble software. We demonstrate the tool for application scenarios with the Cactus Framework on the NSF TeraGrid resources. The tool itself is distributed with an open source license and freely available from our web page.
Sensing Matrix Optimization for Block-Sparse Decoding
Venue: arXiv cs.IT 2010
Year: 2010

Recent work has demonstrated that using a carefully designed sensing matrix rather than a random one, can improve the performance of compressed sensing. In particular, a well-designed sensing matrix can reduce the coherence between the atoms of the equivalent dictionary, and as a consequence, reduce the reconstruction error. In some applications, the signals of interest can be well approximated by a union of a small number of subspaces (e.g., face recognition and motion segmentation). This implies the existence of a dictionary which leads to block-sparse representations. In this work, we propose a framework for sensing matrix design that improves the ability of block-sparse approximation techniques to reconstruct and classify signals. This method is based on minimizing a weighted sum of the inter-block coherence and the sub-block coherence of the equivalent dictionary. Our experiments show that the proposed algorithm significantly improves signal recovery and classification ability of the Block-OMP algorithm compared to sensing matrix optimization methods that do not employ block structure.
Protocols for Bio-Inspired Resource Discovery and Erasure Coded Replication in P2P Networks
Venue: arXiv cs.NI 2010
Year: 2010

Efficient resource discovery and availability improvement are very important issues in unstructured P2P networks. In this paper, a bio-inspired resource discovery scheme inspired by the principle of elephants migration is proposed. A replication scheme based on Q-learning and erasure codes is also introduced. Simulation results show that the proposed schemes significantly increases query success rate and availability, and reduces the network traffic as the resources are effectively distributed to well-performing nodes.
Power optimized programmable embedded controller
Venue: arXiv cs.AR 2010
Year: 2010

Now a days, power has become a primary consideration in hardware design, and is critical in computer systems especially for portable devices with high performance and more functionality. Clock-gating is the most common technique used for reducing processor's power. In this work clock gating technique is applied to optimize the power of fully programmable Embedded Controller (PEC) employing RISC architecture. The CPU designed supports i) smart instruction set, ii) I/O port, UART iii) on-chip clocking to provide a range of frequencies , iv) RISC as well as controller concepts. The whole design is captured using VHDL and is implemented on FPGA chip using Xilinx .The architecture and clock gating technique together is found to reduce the power consumption by 33.33% of total power consumed by this chip.
Feedback stabilisation of switched systems via iterative approximate eigenvector assignment
Venue: arXiv cs.SY 2010
Year: 2010

This paper presents and implements an iterative feedback design algorithm for stabilisation of discrete-time switched systems under arbitrary switching regimes. The algorithm seeks state feedback gains so that the closed-loop switching system admits a common quadratic Lyapunov function (CQLF) and hence is uniformly globally exponentially stable. Although the feedback design problem considered can be solved directly via linear matrix inequalities (LMIs), direct application of LMIs for feedback design does not provide information on closed-loop system structure. In contrast, the feedback matrices computed by the proposed algorithm assign closed-loop structure approximating that required to satisfy Lie-algebraic conditions that guarantee existence of a CQLF. The main contribution of the paper is to provide, for single-input systems, a numerical implementation of the algorithm based on iterative approximate common eigenvector assignment, and to establish cases where such algorithm is guaranteed to succeed. We include pseudocode and a few numerical examples to illustrate advantages and limitations of the proposed technique.
Multi-Agent Only-Knowing Revisited
Venue: arXiv cs.AI 2010
Year: 2010

Levesque introduced the notion of only-knowing to precisely capture the beliefs of a knowledge base. He also showed how only-knowing can be used to formalize non-monotonic behavior within a monotonic logic. Despite its appeal, all attempts to extend only-knowing to the many agent case have undesirable properties. A belief model by Halpern and Lakemeyer, for instance, appeals to proof-theoretic constructs in the semantics and needs to axiomatize validity as part of the logic. It is also not clear how to generalize their ideas to a first-order case. In this paper, we propose a new account of multi-agent only-knowing which, for the first time, has a natural possible-world semantics for a quantified language with equality. We then provide, for the propositional fragment, a sound and complete axiomatization that faithfully lifts Levesque's proof theory to the many agent case. We also discuss comparisons to the earlier approach by Halpern and Lakemeyer.
Multiplex Structures: Patterns of Complexity in Real-World Networks
Venue: arXiv cs.SI 2010
Year: 2010

Complex network theory aims to model and analyze complex systems that consist of multiple and interdependent components. Among all studies on complex networks, topological structure analysis is of the most fundamental importance, as it represents a natural route to understand the dynamics, as well as to synthesize or optimize the functions, of networks. A broad spectrum of network structural patterns have been respectively reported in the past decade, such as communities, multipartites, hubs, authorities, outliers, bow ties, and others. Here, we show that most individual real-world networks demonstrate multiplex structures. That is, a multitude of known or even unknown (hidden) patterns can simultaneously situate in the same network, and moreover they may be overlapped and nested with each other to collaboratively form a heterogeneous, nested or hierarchical organization, in which different connective phenomena can be observed at different granular levels. In addition, we show that the multiplex structures hidden in exploratory networks can be well defined as well as effectively recognized within an unified framework consisting of a set of proposed concepts, models, and algorithms. Our findings provide a strong evidence that most real-world complex systems are driven by a combination of heterogeneous mechanisms that may collaboratively shape their ubiquitous multiplex structures as we observe currently. This work also contributes a mathematical tool for analyzing different sources of networks from a new perspective of unveiling multiplex structures, which will be beneficial to multiple disciplines including sociology, economics and computer science.
Simplifying Negative Goals Using Typed Existence Properties
Venue: arXiv cs.PL 2010
Year: 2010

A method for extracting positive information from negative goals is proposed. It makes use of typed existence properties between arguments of a predicate to rewrite negative goals in a logic program. A typed existence property is a generalization of functional dependencies in that an input value maps to a fixed number of output values. Types are used to specify the domains of the input and output values. An implementation of the simplification method is presented and its complexity is analyzed. A key algorithm of the implementation checks if an atom in a negative goal can be extracted using a given typed existence property. A digraph links an atom to the quantified variables occurring in the atom and is used to quickly retrieve atoms in the negative goal that may become extractable after some other atom is extracted.
MiBoard: Metacognitive Training Through Gaming in iSTART
Venue: arXiv cs.GT 2010
Year: 2010

MiBoard (Multiplayer Interactive Board Game) is an online, turn-based board game, which is a supplement of the iSTART (Interactive Strategy Training for Active Reading and Thinking) application. MiBoard is developed to test the hypothesis that integrating game characteristics (point rewards, game-like interaction, and peer feedback) into the iSTART trainer will significantly improve its effectiveness on students' learning. It was shown by M. Rowe that a physical board game did in fact enhance students' performance. MiBoard is a computer-based version of Rowe's board game that eliminates constraints on locality while retaining the crucial practice components that were the game's objective. MiBoard gives incentives for participation and provides a more enjoyable and social practice environment compared to the online individual practice component of the original trainer.
SNAP: SNowbAll multi-tree Pushing for Peer-to-Peer Media Streaming
Venue: arXiv cs.NI 2010
Year: 2010

Given the respective advantages of the two complimentary techniques for peer-to-peer media streaming (namely tree-based push and mesh-based pull), there is a strong trend of combining them into a hybrid streaming system. Backed by recently proposed mechanisms to identify stable peers, such a hybrid system usually consists of backbone trees formed by the stable peers and other overlay structures in the second tier to accommodate the remaining peers. In this paper, we embrace the hybrid push-pull structure for peer-to-peer media streaming. Our protocol is dominated by a multi-tree push mechanism to minimize the delay in the backbone and is complemented by other overlay structures to cope with peer dynamics. What mainly distinguishes our multi-tree pushing from the conventional ones is an unbalanced tree design guided by the so called snow-ball streaming, which has a provable minimum delay and can be smoothly "melded" with virtually any other existing overlay structures lying in the second tier. We design algorithms to construct and maintain our SNowbAll multi-tree Pushing (SNAP) overlay, and we also illustrate how to smoothly weld the SNAP backbone with the second tier. Finally, we perform simulations in ns-2; the results indicate that our approach outperforms a recently proposed hybrid streaming system.
Mapping Cloud Computing onto Useful e-Governance
Venue: arXiv cs.DC 2010
Year: 2010

Most of the services viewed in context to grid and cloud computing are mostly confined to services that are available for intellectual purposes. The grid or cloud computing are large scale distributed systems. The essence of large scale distribution can only be realized if the services are rendered to common man. The only organization which has exposure to almost every single resident is the respective governments in every country. As the size of population increases so the need for a larger purview arises. The problem of having a large purview can be solved by means of large scale grid for online services. The government services can be rendered through fully customized Service-oriented Clouds. In this paper we are presenting tight similarities between generic government functioning and the service oriented grid/cloud approach. Also, we will discuss the major issues in establishing services oriented grids for governmental organization.
Deterministic Online Call Control in Cellular Networks and Triangle-Free Cellular Networks
Venue: arXiv cs.DS 2010
Year: 2010

Wireless Communication Networks based on Frequency Division Multiplexing (FDM in short) plays an important role in the field of communications, in which each request can be satisfied by assigning a frequency. To avoid interference, each assigned frequency must be different to the neighboring assigned frequencies. Since frequency is a scarce resource, the main problem in wireless networks is how to fully utilize the given bandwidth of frequencies. In this paper, we consider the online call control problem. Given a fixed bandwidth of frequencies and a sequence of communication requests arrive over time, each request must be either satisfied immediately after its arrival by assigning an available frequency, or rejected. The objective of call control problem is to maximize the number of accepted requests. We study the asymptotic performance of this problem, i.e., the number of requests in the sequence and the bandwidth of frequencies are very large. In this paper, we give a 7/3-competitive algorithm for call control problem in cellular network, improving the previous 2.5-competitive result. Moreover, we investigate the triangle-free cellular network, propose a 9/4-competitive algorithm and prove that the lower bound of competitive ratio is at least 5/3.
Adaptation of the neural network-based IDS to new attacks detection
Venue: arXiv cs.CR 2010
Year: 2010

In this paper we report our experiment concerning new attacks detection by a neural network-based Intrusion Detection System. What is crucial for this topic is the adaptation of the neural network that is already in use to correct classification of a new "normal traffic" and of an attack representation not presented during the network training process. When it comes to the new attack it should also be easy to obtain vectors to test and to retrain the neural classifier. We describe the proposal of an algorithm and a distributed IDS architecture that could achieve the goals mentioned above.
On the Design and Analysis of Quaternary Serial and Parallel Adders
Venue: arXiv cs.AR 2010
Year: 2010

Optimization techniques for decreasing the time and area of adder circuits have been extensively studied for years mostly in binary logic system. In this paper, we provide the necessary equations required to design a full adder in quaternary logic system. We develop the equations for single-stage parallel adder which works as a carry look-ahead adder. We also provide the design of a logarithmic stage parallel adder which can compute the carries within log2(n) time delay for n qudits. At last, we compare the designs and finally propose a hybrid adder which combines the advantages of serial and parallel adder.
Teaching Spreadsheets: Curriculum Design Principles
Venue: arXiv cs.SE 2010
Year: 2010

EuSpRIG concerns direct researchers to revisit spreadsheet education, taking into account error auditing tools, checklists, and good practices. This paper aims at elaborating principles to design a spreadsheet curriculum. It mainly focuses on two important issues. Firstly, it is necessary to establish the spreadsheet invariants to be taught, especially those concerning errors and good practices. Secondly, it is important to take into account the learners' ICT experience, and to encourage them to attitudes that foster self-learning. We suggest key principles for spreadsheet teaching, and we illustrate them with teaching guidelines.
Estimation of Infants' Cry Fundamental Frequency using a Modified SIFT algorithm
Venue: arXiv cs.SD 2010
Year: 2010

This paper addresses the problem of infants' cry fundamental frequency estimation. The fundamental frequency is estimated using a modified simple inverse filtering tracking (SIFT) algorithm. The performance of the modified SIFT is studied using a real database of infants' cry. It is shown that the algorithm is capable of overcoming the problem of under-estimation and over-estimation of the cry fundamental frequency, with an estimation accuracy of 6.15% and 3.75%, for hyperphonated and phonated cry segments, respectively. Some typical examples of the fundamental frequency contour in typical cases of pathological and healthy cry signals are presented and discussed.
Tree Languages Defined in First-Order Logic with One Quantifier Alternation
Venue: arXiv cs.FL 2010
Year: 2010

We study tree languages that can be defined in Δ_2 . These are tree languages definable by a first-order formula whose quantifier prefix is forall exists, and simultaneously by a first-order formula whose quantifier prefix is . For the quantifier free part we consider two signatures, either the descendant relation alone or together with the lexicographical order relation on nodes. We provide an effective characterization of tree and forest languages definable in Δ_2 . This characterization is in terms of algebraic equations. Over words, the class of word languages definable in Δ_2 forms a robust class, which was given an effective algebraic characterization by Pin and Weil.
Invariant Spectral Hashing of Image Saliency Graph
Venue: arXiv cs.CV 2010
Year: 2010

Image hashing is the process of associating a short vector of bits to an image. The resulting summaries are useful in many applications including image indexing, image authentication and pattern recognition. These hashes need to be invariant under transformations of the image that result in similar visual content, but should drastically differ for conceptually distinct contents. This paper proposes an image hashing method that is invariant under rotation, scaling and translation of the image. The gist of our approach relies on the geometric characterization of salient point distribution in the image. This is achieved by the definition of a "saliency graph" connecting these points jointly with an image intensity function on the graph nodes. An invariant hash is then obtained by considering the spectrum of this function in the eigenvector basis of the Laplacian graph, that is, its graph Fourier transform. Interestingly, this spectrum is invariant under any relabeling of the graph nodes. The graph reveals geometric information of the image, making the hash robust to image transformation, yet distinct for different visual content. The efficiency of the proposed method is assessed on a set of MRI 2-D slices and on a database of faces.
Analyzing Weighted $\ell_1$ Minimization for Sparse Recovery with Nonuniform Sparse Models\footnote{The results of this paper were presented in part at the International Symposium on Information Theory, ISIT 2009}
Venue: arXiv cs.IT 2010
Year: 2010

In this paper we introduce a nonuniform sparsity model and analyze the performance of an optimized weighted $\ell_1$ minimization over that sparsity model. In particular, we focus on a model where the entries of the unknown vector fall into two sets, with entries of each set having a specific probability of being nonzero. We propose a weighted $\ell_1$ minimization recovery algorithm and analyze its performance using a Grassmann angle approach. We compute explicitly the relationship between the system parameters-the weights, the number of measurements, the size of the two sets, the probabilities of being nonzero- so that when i.i.d. random Gaussian measurement matrices are used, the weighted $\ell_1$ minimization recovers a randomly selected signal drawn from the considered sparsity model with overwhelming probability as the problem dimension increases. This allows us to compute the optimal weights. We demonstrate through rigorous analysis and simulations that for the case when the support of the signal can be divided into two different subclasses with unequal sparsity fractions, the optimal weighted $\ell_1$ minimization outperforms the regular $\ell_1$ minimization substantially. We also generalize the results to an arbitrary number of classes.
Is A Quantum Stabilizer Code Degenerate or Nondegenerate for Pauli Channel?
Venue: arXiv cs.CR 2010
Year: 2010

Mapping an error syndrome to the error operator is the core of quantum decoding network and is also the key step of recovery. The definitions of the bit-flip error syndrome matrix and the phase-flip error syndrome matrix were presented, and then the error syndromes of quantum errors were expressed in terms of the columns of the bit-flip error syndrome matrix and the phase-flip error syndrome matrix. It also showed that the error syndrome matrices of a stabilizer code are determined by its check matrix, which is similar to the classical case. So, the error-detection and recovery techniques of classical linear codes can be applied to quantum stabilizer codes after some modifications. Some necessary and/or sufficient conditions for the stabilizer code over GF(2) is degenerate or nondegenerate for Pauli channel based on the relationship between the error syndrome matrices and the check matrix was presented. A new way to find the minimum distance of the quantum stabilizer codes based on their check matrices was presented, and followed from which we proved that the performance of degenerate quantum code outperform (at least have the same performance) nondegenerate quantum code for Pauli channel.
Deep Self-Taught Learning for Handwritten Character Recognition
Venue: arXiv cs.LG 2010
Year: 2010

Recent theoretical and empirical work in statistical machine learning has demonstrated the importance of learning algorithms for deep architectures, i.e., function classes obtained by composing multiple non-linear transformations. Self-taught learning (exploiting unlabeled examples or examples from other distributions) has already been applied to deep learners, but mostly to show the advantage of unlabeled examples. Here we explore the advantage brought by {\em out-of-distribution examples}. For this purpose we developed a powerful generator of stochastic variations and noise processes for character images, including not only affine transformations but also slant, local elastic deformations, changes in thickness, background images, grey level changes, contrast, occlusion, and various types of noise. The out-of-distribution examples are obtained from these highly distorted images or by including examples of object classes different from those in the target test set. We show that {\em deep learners benefit more from out-of-distribution examples than a corresponding shallow learner}, at least in the area of handwritten character recognition. In fact, we show that they beat previously published results and reach human-level performance on both handwritten digit classification and 62-class handwritten character recognition.
3-SAT Polynomial Solution of Knowledge Recognition Algorithm
Venue: arXiv cs.CC 2010
Year: 2010

This paper introduces a knowledge recognition algorithm (KRA) for solving the 3SAT problem in polynomial time. KRA learns member-class relations and retrieves information through deductive and reductive iterative reasoning. It applies the principle of Chinese COVA* (equivalent to a set of eight 3-variable conjunctive clauses) and eliminates the "OR" operation to solve 3-SAT problem. That is, KRA does not search the assignment directly. It recognizes the complements as rejections at each level of the set through iterative set relation recognition. KRA recognizes which conjunctive 3-variable-clause is not satisfiable. If all the eight clauses of any set of 3-variable clauses are rejected, then there is not an assignment for the formula. If there is at least one clause in each set that remains, then there is at least one assignment that is the union of clauses of each set. If there is more than one clause in each set that remains, then there are multiple assignments that are the unions of the clauses of each set respectively.