OpenRaiser/Intern-Atlas huggingface dataset:
Automating Fault Tolerance in High-Performance Computational Biological Jobs Using Multi-Agent Approaches
Venue: arXiv cs.DC 2014
Year: 2014

Background: Large-scale biological jobs on high-performance computing systems require manual intervention if one or more computing cores on which they execute fail. This places not only a cost on the maintenance of the job, but also a cost on the time taken for reinstating the job and the risk of losing data and execution accomplished by the job before it failed. Approaches which can proactively detect computing core failures and take action to relocate the computing core's job onto reliable cores can make a significant step towards automating fault tolerance. Method: This paper describes an experimental investigation into the use of multi-agent approaches for fault tolerance. Two approaches are studied, the first at the job level and the second at the core level. The approaches are investigated for single core failure scenarios that can occur in the execution of parallel reduction algorithms on computer clusters. A third approach is proposed that incorporates multi-agent technology both at the job and core level. Experiments are pursued in the context of genome searching, a popular computational biology application. Result: The key conclusion is that the approaches proposed are feasible for automating fault tolerance in high-performance computing systems with minimal human intervention. In a typical experiment in which the fault tolerance is studied, centralised and decentralised checkpointing approaches on an average add 90% to the actual time for executing the job. On the other hand, in the same experiment the multi-agent approaches add only 10% to the overall execution time.
Performance Analysis of Multi-Antenna Relay Networks over Nakagami-m Fading Channel
Venue: arXiv cs.IT 2014
Year: 2014

In this chapter, the authors present the performance of multi-antenna selective combining decode-and-forward (SC-DF) relay networks over independent and identically distributed (i.i.d) Nakagami-m fading channels. The outage probability, moment generation function, symbol error probability and average channel capacity are derived in closed-form using the Signal-to-Noise-Ratio (SNR) statistical characteristics. After that, the authors formulate the outage probability problem, optimize it with an approximated problem, and then solve it analytically. Finally, for comparison with analytical formulas, the authors perform some Monte-Carlo simulations.
Evaluating Dynamic Linking through the Query Process using the Licas Test Platform
Venue: arXiv cs.DC 2014
Year: 2014

A novel linking mechanism has been described previously [4] that can be used to autonomously link sources that provide related answers to queries executed over an information network. The test query platform has now been re-written resulting in essentially a new test platform using the same basic query mechanism, but with a slightly different algorithm. This paper describes recent test results on the same query test process that supports the original findings and also shows the effectiveness of the linking mechanism in a new set of test scenarios.
Dynamic Move Chains -- a Forward Pruning Approach to Tree Search in Computer Chess
Venue: arXiv cs.AI 2014
Year: 2014

This paper proposes a new mechanism for pruning a search game-tree in computer chess. The algorithm stores and then reuses chains or sequences of moves, built up from previous searches. These move sequences have a built-in forward-pruning mechanism that can radically reduce the search space. A typical search process might retrieve a move from a Transposition Table, where the decision of what move to retrieve would be based on the position itself. This algorithm stores move sequences based on what previous sequences were better, or caused cutoffs. This is therefore position independent and so it could also be useful in games with imperfect information or uncertainty, where the whole situation is not known at any one time. Over a small set of tests, the algorithm was shown to clearly out-perform Transposition Tables, both in terms of search reduction and game-play results.
Uncertainty in Crowd Data Sourcing under Structural Constraints
Venue: arXiv cs.DB 2014
Year: 2014

Applications extracting data from crowdsourcing platforms must deal with the uncertainty of crowd answers in two different ways: first, by deriving estimates of the correct value from the answers; second, by choosing crowd questions whose answers are expected to minimize this uncertainty relative to the overall data collection goal. Such problems are already challenging when we assume that questions are unrelated and answers are independent, but they are even more complicated when we assume that the unknown values follow hard structural constraints (such as monotonicity). In this vision paper, we examine how to formally address this issue with an approach inspired by [Amsterdamer et al., 2013]. We describe a generalized setting where we model constraints as linear inequalities, and use them to guide the choice of crowd questions and the processing of answers. We present the main challenges arising in this setting, and propose directions to solve them.
Most Recent Match Queries in On-Line Suffix Trees (with appendix)
Venue: arXiv cs.DS 2014
Year: 2014

A suffix tree is able to efficiently locate a pattern in an indexed string, but not in general the most recent copy of the pattern in an online stream, which is desirable in some applications. We study the most general version of the problem of locating a most recent match: supporting queries for arbitrary patterns, at each step of processing an online stream. We present augmentations to Ukkonen's suffix tree construction algorithm for optimal-time queries, maintaining indexing time within a logarithmic factor in the size of the indexed string. We show that the algorithm is applicable to sliding-window indexing, and sketch a possible optimization for use in the special case of Lempel-Ziv compression.
A Potential Game Approach for Information-Maximizing Cooperative Planning of Sensor Networks
Venue: arXiv cs.SY 2014
Year: 2014

This paper presents a potential game approach for distributed cooperative selection of informative sensors, when the goal is to maximize the mutual information between the measurement variables and the quantities of interest. It is proved that a local utility function defined by the conditional mutual information of an agent conditioned on the other agents' sensing decisions leads to a potential game with the global potential being the original mutual information of the cooperative planning problem. The joint strategy fictitious play method is then applied to obtain a distributed solution that provably converges to a pure strategy Nash equilibrium. Two numerical examples on simplified weather forecasting and range-only target tracking verify convergence and performance characteristics of the proposed game-theoretic approach.
Locally-Optimized Reweighted Belief Propagation for Decoding LDPC Codes with Finite-Length
Venue: arXiv cs.IT 2014
Year: 2014

In practice, LDPC codes are decoded using message passing methods. These methods offer good performance but tend to converge slowly and sometimes fail to converge and to decode the desired codewords correctly. Recently, tree-reweighted message passing methods have been modified to improve the convergence speed at little or no additional complexity cost. This paper extends this line of work and proposes a new class of locally optimized reweighting strategies, which are suitable for both regular and irregular LDPC codes. The proposed decoding algorithm first splits the factor graph into subgraphs and subsequently performs a local optimization of reweighting parameters. Simulations show that the proposed decoding algorithm significantly outperforms the standard message passing and existing reweighting techniques.
On the connection between compression learning and scenario based optimization
Venue: arXiv cs.SY 2014
Year: 2014

We investigate the connections between compression learning and scenario based optimization. We first show how to strengthen, or relax the consistency assumption at the basis of compression learning and study the learning and generalization properties of the algorithm involved. We then consider different constrained optimization problems affected by uncertainty represented by means of scenarios. We show that the issue of providing guarantees on the probability of constraint violation reduces to a learning problem for an appropriately chosen algorithm that enjoys compression learning properties. The compression learning perspective provides a unifying framework for scenario based optimization and allows us to revisit the scenario approach and the probabilistically robust design, a recently developed technique based on a mixture of randomized and robust optimization, and to extend the guarantees on the probability of constraint violation to cascading optimization problems.
K-Tangent Spaces on Riemannian Manifolds for Improved Pedestrian Detection
Venue: arXiv cs.CV 2014
Year: 2014

For covariance-based image descriptors, taking into account the curvature of the corresponding feature space has been shown to improve discrimination performance. This is often done through representing the descriptors as points on Riemannian manifolds, with the discrimination accomplished on a tangent space. However, such treatment is restrictive as distances between arbitrary points on the tangent space do not represent true geodesic distances, and hence do not represent the manifold structure accurately. In this paper we propose a general discriminative model based on the combination of several tangent spaces, in order to preserve more details of the structure. The model can be used as a weak learner in a boosting-based pedestrian detection framework. Experiments on the challenging INRIA and DaimlerChrysler datasets show that the proposed model leads to considerably higher performance than methods based on histograms of oriented gradients as well as previous Riemannian-based techniques.
Automated Fixing of Programs with Contracts
Venue: arXiv cs.SE 2014
Year: 2014

This paper describes AutoFix, an automatic debugging technique that can fix faults in general-purpose software. To provide high-quality fix suggestions and to enable automation of the whole debugging process, AutoFix relies on the presence of simple specification elements in the form of contracts (such as pre- and postconditions). Using contracts enhances the precision of dynamic analysis techniques for fault detection and localization, and for validating fixes. The only required user input to the AutoFix supporting tool is then a faulty program annotated with contracts; the tool produces a collection of validated fixes for the fault ranked according to an estimate of their suitability. In an extensive experimental evaluation, we applied AutoFix to over 200 faults in four code bases of different maturity and quality (of implementation and of contracts). AutoFix successfully fixed 42% of the faults, producing, in the majority of cases, corrections of quality comparable to those competent programmers would write; the used computational resources were modest, with an average time per fix below 20 minutes on commodity hardware. These figures compare favorably to the state of the art in automated program fixing, and demonstrate that the AutoFix approach is successfully applicable to reduce the debugging burden in real-world scenarios.
Estudio exploratorio sobre las competencias informacionales de los estudiantes de la Universidad de La Habana
Venue: arXiv cs.CY 2014
Year: 2014

The present article shows the results of a survey aimed at identifying the informational abilities of Havana University students. Several methods such as the survey, expert's interviews and content and document analysis are used. The questionnaire has been structured base on three basic variables: information search, information analysis and release and self evaluation elements. The identification of these abilities was a key element for guiding libraries in the development of actions focused on their communities.
An n\log n Lower Bound for Fourier Transform Computation in the Well Conditioned Model
Venue: arXiv cs.CC 2014
Year: 2014

Obtaining a non-trivial (super-linear) lower bound for computation of the Fourier transform in the linear circuit model has been a long standing open problem for over 40 years. An early result by Morgenstern from 1973, provides an $Ω(n \log n)$ lower bound for the unnormalized Fourier transform when the constants used in the computation are bounded. The proof uses a potential function related to a determinant. The result does not explain why the normalized Fourier transform (of unit determinant) should be difficult to compute in the same model. Hence, the result is not scale insensitive. More recently, Ailon (2013) showed that if only unitary 2-by-2 gates are used, and additionally no extra memory is allowed, then the normalized Fourier transform requires $Ω(n\log n)$ steps. This rather limited result is also sensitive to scaling, but highlights the complexity inherent in the Fourier transform arising from introducing entropy, unlike, say, the identity matrix (which is as complex as the Fourier transform using Morgenstern's arguments, under proper scaling). In this work we extend the arguments of Ailon (2013). In the first extension, which is also the main contribution, we provide a lower bound for computing any scaling of the Fourier transform. Our restriction is that, the composition of all gates up to any point must be a well conditioned linear transformation. The lower bound is $Ω(R^{-1}n\log n)$, where $R$ is the uniform condition number. Second, we assume extra space is allowed, as long as it contains information of bounded norm at the end of the computation. The main technical contribution is an extension of matrix entropy used in Ailon (2013) for unitary matrices to a potential function computable for any matrix, using Shannon entropy on "quasi-probabilities".
Authorship detection of SMS messages using unigrams
Venue: arXiv cs.CL 2014
Year: 2014

SMS messaging is a popular media of communication. Because of its popularity and privacy, it could be used for many illegal purposes. Additionally, since they are part of the day to day life, SMSes can be used as evidence for many legal disputes. Since a cellular phone might be accessible to people close to the owner, it is important to establish the fact that the sender of the message is indeed the owner of the phone. For this purpose, the straight forward solutions seem to be the use of popular stylometric methods. However, in comparison with the data used for stylometry in the literature, SMSes have unusual characteristics making it hard or impossible to apply these methods in a conventional way. Our target is to come up with a method of authorship detection of SMS messages that could still give a usable accuracy. We argue that, considering the methods of author attribution, the best method that could be applied to SMS messages is an n-gram method. To prove our point, we checked two different methods of distribution comparison with varying number of training and testing data. We specifically try to compare how well our algorithms work under less amount of testing data and large number of candidate authors (which we believe to be the real world scenario) against controlled tests with less number of authors and selected SMSes with large number of words. To counter the lack of information in an SMS message, we propose the method of stacking together few SMSes.
Software implementation level countermeasures against the cache timing attack on advanced encryption standard
Venue: arXiv cs.CR 2014
Year: 2014

Advanced Encryption Standard (AES) is a symmetric key encryption algorithm which is extensively used in secure electronic data transmission. When introduced, although it was tested and declared as secure, in 2005, a researcher named Bernstein claimed that it is vulnerable to side channel attacks. The cache-based timing attack is the type of side channel attack demonstrated by Bernstein, which uses the timing variation in cache hits and misses. This kind of attacks can be prevented by masking the actual timing information from the attacker. Such masking can be performed by altering the original AES software implementation while preserving its semantics. This paper presents possible software implementation level countermeasures against Bernstein's cache timing attack. Two simple software based countermeasures based on the concept of "constant-encryption-time" were demonstrated against the remote cache timing attack with positive outcomes, in which we establish a secured environment for the AES encryption.
An Extensive Repot on the Efficiency of AIS-INMACA (A Novel Integrated MACA based Clonal Classifier for Protein Coding and Promoter Region Prediction)
Venue: arXiv cs.CE 2014
Year: 2014

This paper exclusively reports the efficiency of AIS-INMACA. AIS-INMACA has created good impact on solving major problems in bioinformatics like protein region identification and promoter region prediction with less time (Pokkuluri Kiran Sree, 2014). This AIS-INMACA is now came with several variations (Pokkuluri Kiran Sree, 2014) towards projecting it as a tool in bioinformatics for solving many problems in bioinformatics. So this paper will be very much useful for so many researchers who are working in the domain of bioinformatics with cellular automata.
Real-Time Classification of Twitter Trends
Venue: arXiv cs.IR 2014
Year: 2014

Social media users give rise to social trends as they share about common interests, which can be triggered by different reasons. In this work, we explore the types of triggers that spark trends on Twitter, introducing a typology with following four types: 'news', 'ongoing events', 'memes', and 'commemoratives'. While previous research has analyzed trending topics in a long term, we look at the earliest tweets that produce a trend, with the aim of categorizing trends early on. This would allow to provide a filtered subset of trends to end users. We analyze and experiment with a set of straightforward language-independent features based on the social spread of trends to categorize them into the introduced typology. Our method provides an efficient way to accurately categorize trending topics without need of external data, enabling news organizations to discover breaking news in real-time, or to quickly identify viral memes that might enrich marketing decisions, among others. The analysis of social features also reveals patterns associated with each type of trend, such as tweets about ongoing events being shorter as many were likely sent from mobile devices, or memes having more retweets originating from a few trend-setters.
Adaptive Model for Computer-Assisted Assessment in Programming Skills
Venue: arXiv cs.CY 2014
Year: 2014

In this work, we show a methodology aimed to improve the quality of the assessment process for subjects related to basic programming. The method takes into account the relevance of the items and the students answers to follow different paths to improve the accuracy of the assessment process. We have developed numerical simulations and experiments with real students that demonstrate the advantages of this model when compared with traditional evaluation tools. This method improves the objectiveness and takes into account the relevance of the subject contents. We also demonstrate that the architecture of the algorithm is fully compatible with traditional multiple choice test formalisms. Our results can be directly used in computer-assisted tests for different subjects and disciplines, as well as used by the students as a self-evaluation tool with the objective of correcting their deficiencies in the learning process.
Optimal constructions for ID-based one-way-function key predistribution schemes realizing specified communication graphs
Venue: arXiv cs.CR 2014
Year: 2014

We study a method for key predistribution in a network of $n$ users where pairwise keys are computed by hashing users' IDs along with secret information that has been (pre)distributed to the network users by a trusted entity. A communication graph $G$ can be specified to indicate which pairs of users should be able to compute keys. We determine necessary and sufficient conditions for schemes of this type to be secure. We also consider the problem of minimizing the storage requirements of such a scheme; we are interested in the total storage as well as the maximum storage required by any user. Minimizing the total storage is NP-hard, whereas minimizing the maximum storage required by a user can be computed in polynomial time.
A Tale of Two Data-Intensive Paradigms: Applications, Abstractions, and Architectures
Venue: arXiv cs.DC 2014
Year: 2014

Scientific problems that depend on processing large amounts of data require overcoming challenges in multiple areas: managing large-scale data distribution, co-placement and scheduling of data with compute resources, and storing and transferring large volumes of data. We analyze the ecosystems of the two prominent paradigms for data-intensive applications, hereafter referred to as the high-performance computing and the Apache-Hadoop paradigm. We propose a basis, common terminology and functional factors upon which to analyze the two approaches of both paradigms. We discuss the concept of "Big Data Ogres" and their facets as means of understanding and characterizing the most common application workloads found across the two paradigms. We then discuss the salient features of the two paradigms, and compare and contrast the two approaches. Specifically, we examine common implementation/approaches of these paradigms, shed light upon the reasons for their current "architecture" and discuss some typical workloads that utilize them. In spite of the significant software distinctions, we believe there is architectural similarity. We discuss the potential integration of different implementations, across the different levels and components. Our comparison progresses from a fully qualitative examination of the two paradigms, to a semi-quantitative methodology. We use a simple and broadly used Ogre (K-means clustering), characterize its performance on a range of representative platforms, covering several implementations from both paradigms. Our experiments provide an insight into the relative strengths of the two paradigms. We propose that the set of Ogres will serve as a benchmark to evaluate the two paradigms along different dimensions.
On Effects of Imperfect Channel State Information on Null Space Based Cognitive MIMO Communication
Venue: arXiv cs.IT 2014
Year: 2014

In cognitive radio networks, when secondary users transmit in the null space of their interference channel with primary user, they can avoid interference. However, performance of this scheme depends on knowledge of channel state information for secondary user to perform inverse waterfilling. We evaluate the effects of imperfect channel estimation on error rates and performance degradation of primary user and elucidate the tradeoffs, such as amount of interference and guard distance. Results show that, based on the amount of perturbation in channel matrices, performance of null space based technique can degrade to that of open loop MIMO. Outcomes presented in this paper also apply to null space based MIMO radar waveform design to avoid interference with commercial communication systems, operating in same or adjacent bands.