OpenRaiser/Intern-Atlas huggingface dataset:
Heart Disease Prediction System using Associative Classification and Genetic Algorithm
Venue: arXiv cs.AI 2013
Year: 2013

Associative classification is a recent and rewarding technique which integrates association rule mining and classification to a model for prediction and achieves maximum accuracy. Associative classifiers are especially fit to applications where maximum accuracy is desired to a model for prediction. There are many domains such as medical where the maximum accuracy of the model is desired. Heart disease is a single largest cause of death in developed countries and one of the main contributors to disease burden in developing countries. Mortality data from the registrar general of India shows that heart disease are a major cause of death in India, and in Andhra Pradesh coronary heart disease cause about 30%of deaths in rural areas. Hence there is a need to develop a decision support system for predicting heart disease of a patient. In this paper we propose efficient associative classification algorithm using genetic approach for heart disease prediction. The main motivation for using genetic algorithm in the discovery of high level prediction rules is that the discovered rules are highly comprehensible, having high predictive accuracy and of high interestingness values. Experimental Results show that most of the classifier rules help in the best prediction of heart disease which even helps doctors in their diagnosis decisions.
A Faster Algorithm for Computing Motorcycle Graphs
Venue: arXiv cs.CG 2013
Year: 2013

We present a new algorithm for computing motorcycle graphs that runs in O(n^(4/3+e)) time for any e>0, improving on all previously known algorithms. The main application of this result is to computing the straight skeleton of a polygon. It allows us to compute the straight skeleton of a non-degenerate polygon with h holes in O(n.sqrt(h+1)log^2(n)+n^(4/3+e)) expected time. If all input coordinates are O(log n)-bit rational numbers, we can compute the straight skeleton of a (possibly degenerate) polygon with h holes in O(n.sqrt(h+1)log^3(n)) expected time. In particular, it means that we can compute the straight skeleton of a simple polygon in O(n.log^3(n)) expected time if all input coordinates are O(\log n)-bit rationals, while all previously known algorithms have worst-case running time larger than n^(3/2).
Spatio-Temporal Covariance Descriptors for Action and Gesture Recognition
Venue: arXiv cs.CV 2013
Year: 2013

We propose a new action and gesture recognition method based on spatio-temporal covariance descriptors and a weighted Riemannian locality preserving projection approach that takes into account the curved space formed by the descriptors. The weighted projection is then exploited during boosting to create a final multiclass classification algorithm that employs the most useful spatio-temporal regions. We also show how the descriptors can be computed quickly through the use of integral video representations. Experiments on the UCF sport, CK+ facial expression and Cambridge hand gesture datasets indicate superior performance of the proposed method compared to several recent state-of-the-art techniques. The proposed method is robust and does not require additional processing of the videos, such as foreground detection, interest-point detection or tracking.
ZKCM: a C++ library for multiprecision matrix computation with applications in quantum information
Venue: arXiv cs.MS 2013
Year: 2013

ZKCM is a C++ library developed for the purpose of multiprecision matrix computation, on the basis of the GNU MP and MPFR libraries. It provides an easy-to-use syntax and convenient functions for matrix manipulations including those often used in numerical simulations in quantum physics. Its extension library, ZKCM_QC, is developed for simulating quantum computing using the time-dependent matrix-product-state simulation method. This paper gives an introduction about the libraries with practical sample programs.
Optimized-Cost Repair in Multi-hop Distributed Storage Systems with Network Coding
Venue: arXiv cs.IT 2013
Year: 2013

In distributed storage systems reliability is achieved through redundancy stored at different nodes in the network. Then a data collector can reconstruct source information even though some nodes fail. To maintain reliability, an autonomous and efficient protocol should be used to repair the failed node. The repair process causes traffic and consequently transmission cost in the network. Recent results found the optimal trafficstorage tradeoff, and proposed regenerating codes to achieve the optimality. We aim at minimizing the transmission cost in the repair process. We consider the network topology in the repair, and accordingly modify information flow graphs. Then we analyze the cut requirement and based on the results, we formulate the minimum-cost as a linear programming problem for linear costs. We show that the solution of the linear problem establishes a fundamental lower bound of the repair-cost. We also show that this bound is achievable for minimum storage regenerating, which uses the optimal-cost minimum-storage regenerating (OCMSR) code. We propose surviving node cooperation which can efficiently reduce the repair cost. Further, the field size for the construction of OCMSR codes is discussed. We show the gain of optimal-cost repair in tandem, star, grid and fully connected networks.
Polylogarithmic Cuts in Models of V^0
Venue: arXiv cs.LO 2013
Year: 2013

We study initial cuts of models of weak two-sorted Bounded Arithmetics with respect to the strength of their theories and show that these theories are stronger than the original one. More explicitly we will see that polylogarithmic cuts of models of $\mathbf{V}^0$ are models of $\mathbf{VNC}^1$ by formalizing a proof of Nepomnjascij's Theorem in such cuts. This is a strengthening of a result by Paris and Wilkie. We can then exploit our result in Proof Complexity to observe that Frege proof systems can be sub exponentially simulated by bounded depth Frege proof systems. This result has recently been obtained by Filmus, Pitassi and Santhanam in a direct proof. As an interesting observation we also obtain an average case separation of Resolution from AC0-Frege by applying a recent result with Tzameret.
Agent-based environment for knowledge integration
Venue: arXiv cs.MA 2013
Year: 2013

Representing knowledge with the use of ontology description languages offers several advantages arising from knowledge reusability, possibilities of carrying out reasoning processes and the use of existing concepts of knowledge integration. In this work we are going to present an environment for the integration of knowledge expressed in such a way. Guaranteeing knowledge integration is an important element during the development of the Semantic Web. Thanks to this, it is possible to obtain access to services which offer knowledge contained in various distributed databases associated with semantically described web portals. We will present the advantages of the multi-agent approach while solving this problem. Then, we will describe an example of its application in systems supporting company management knowledge in the process of constructing supply-chains.
About the survey of propagandistic messages in contemporary social media
Venue: arXiv cs.SI 2013
Year: 2013

This paper presents the research results that have identified a set of characteristic parameters of propagandistic messages. Later these parameters can be used in the algorithm creating special user-oriented propagandistic messages to improve distribution and assimilation of information by users.
Limited benefit of cooperation in distributed relative localization
Venue: arXiv cs.SY 2013
Year: 2013

Important applications in robotic and sensor networks require distributed algorithms to solve the so-called relative localization problem: a node-indexed vector has to be reconstructed from measurements of differences between neighbor nodes. In a recent note, we have studied the estimation error of a popular gradient descent algorithm showing that the mean square error has a minimum at a finite time, after which the performance worsens. This paper proposes a suitable modification of this algorithm incorporating more realistic "a priori" information on the position. The new algorithm presents a performance monotonically decreasing to the optimal one. Furthermore, we show that the optimal performance is approximated, up to a 1 + \eps factor, within a time which is independent of the graph and of the number of nodes. This convergence time is very much related to the minimum exhibited by the previous algorithm and both lead to the following conclusion: in the presence of noisy data, cooperation is only useful till a certain limit.
Constructing Limited Scale-Free Topologies Over Peer-to-Peer Networks
Venue: arXiv cs.NI 2013
Year: 2013

Overlay network topology together with peer/data organization and search algorithm are the crucial components of unstructured peer-to-peer (P2P) networks as they directly affect the efficiency of search on such networks. Scale-free (powerlaw) overlay network topologies are among structures that offer high performance for these networks. A key problem for these topologies is the existence of hubs, nodes with high connectivity. Yet, the peers in a typical unstructured P2P network may not be willing or able to cope with such high connectivity and its associated load. Therefore, some hard cutoffs are often imposed on the number of edges that each peer can have, restricting feasible overlays to limited or truncated scale-free networks. In this paper, we analyze the growth of such limited scale-free networks and propose two different algorithms for constructing perfect scale-free overlay network topologies at each instance of such growth. Our algorithms allow the user to define the desired scalefree exponent (gamma). They also induce low communication overhead when network grows from one size to another. Using extensive simulations, we demonstrate that these algorithms indeed generate perfect scale free networks (at each step of network growth) that provide better search efficiency in various search algorithms than the networks generated by the existing solutions.
Message Passing Algorithm for Distributed Downlink Regularized Zero-forcing Beamforming with Cooperative Base Stations
Venue: arXiv cs.IT 2013
Year: 2013

Base station (BS) cooperation can turn unwanted interference to useful signal energy for enhancing system performance. In the cooperative downlink, zero-forcing beamforming (ZFBF) with a simple scheduler is well known to obtain nearly the performance of the capacity-achieving dirty-paper coding. However, the centralized ZFBF approach is prohibitively complex as the network size grows. In this paper, we devise message passing algorithms for realizing the regularized ZFBF (RZFBF) in a distributed manner using belief propagation. In the proposed methods, the overall computational cost is decomposed into many smaller computation tasks carried out by groups of neighboring BSs and communications is only required between neighboring BSs. More importantly, some exchanged messages can be computed based on channel statistics rather than instantaneous channel state information, leading to significant reduction in computational complexity. Simulation results demonstrate that the proposed algorithms converge quickly to the exact RZFBF and much faster compared to conventional methods.
Sketching Sparse Matrices
Venue: arXiv cs.IT 2013
Year: 2013

This paper considers the problem of recovering an unknown sparse p\times p matrix X from an m\times m matrix Y=AXB^T, where A and B are known m \times p matrices with m << p. The main result shows that there exist constructions of the "sketching" matrices A and B so that even if X has O(p) non-zeros, it can be recovered exactly and efficiently using a convex program as long as these non-zeros are not concentrated in any single row/column of X. Furthermore, it suffices for the size of Y (the sketch dimension) to scale as m = O(\sqrt{# nonzeros in X} \times log p). The results also show that the recovery is robust and stable in the sense that if X is equal to a sparse matrix plus a perturbation, then the convex program we propose produces an approximation with accuracy proportional to the size of the perturbation. Unlike traditional results on sparse recovery, where the sensing matrix produces independent measurements, our sensing operator is highly constrained (it assumes a tensor product structure). Therefore, proving recovery guarantees require non-standard techniques. Indeed our approach relies on a novel result concerning tensor products of bipartite graphs, which may be of independent interest. This problem is motivated by the following application, among others. Consider a p\times n data matrix D, consisting of n observations of p variables. Assume that the correlation matrix X:=DD^{T} is (approximately) sparse in the sense that each of the p variables is significantly correlated with only a few others. Our results show that these significant correlations can be detected even if we have access to only a sketch of the data S=AD with A \in R^{m\times p}.
Partial Star Products: A Local Covering Approach for the Recognition of Approximate Cartesian Product Graphs
Venue: arXiv cs.DM 2013
Year: 2013

This paper is concerned with the recognition of approximate graph products with respect to the Cartesian product. Most graphs are prime, although they can have a rich product-like structure. The proposed algorithms are based on a local approach that covers a graph by small subgraphs, so-called partial star products, and then utilizes this information to derive the global factors and an embedding of the graph under investigation into Cartesian product graphs.
Exponential-Condition-Based Barrier Certificate Generation for Safety Verification of Hybrid Systems
Venue: arXiv cs.SE 2013
Year: 2013

A barrier certificate is an inductive invariant function which can be used for the safety verification of a hybrid system. Safety verification based on barrier certificate has the benefit of avoiding explicit computation of the exact reachable set which is usually intractable for nonlinear hybrid systems. In this paper, we propose a new barrier certificate condition, called Exponential Condition, for the safety verification of semi-algebraic hybrid systems. The most important benefit of Exponential Condition is that it has a lower conservativeness than the existing convex condition and meanwhile it possesses the property of convexity. On the one hand, a less conservative barrier certificate forms a tighter over-approximation for the reachable set and hence is able to verify critical safety properties. On the other hand, the property of convexity guarantees its solvability by semidefinite programming method. Some examples are presented to illustrate the effectiveness and practicality of our method.
Index Coding Capacity: How far can one go with only Shannon Inequalities?
Venue: arXiv cs.IT 2013
Year: 2013

An interference alignment perspective is used to identify the simplest instances (minimum possible number of edges in the alignment graph, no more than 2 interfering messages at any destination) of index coding problems where non-Shannon information inequalities are necessary for capacity characterization. In particular, this includes the first known example of a multiple unicast (one destination per message) index coding problem where non-Shannon information inequalities are shown to be necessary. The simplest multiple unicast example has 7 edges in the alignment graph and 11 messages. The simplest multiple groupcast (multiple destinations per message) example has 6 edges in the alignment graph, 6 messages, and 10 receivers. For both the simplest multiple unicast and multiple groupcast instances, the best outer bound based on only Shannon inequalities is $\frac{2}{5}$, which is tightened to $\frac{11}{28}$ by the use of the Zhang-Yeung non-Shannon type information inequality, and the linear capacity is shown to be $\frac{5}{13}$ using the Ingleton inequality. Conversely, identifying the minimal challenging aspects of the index coding problem allows an expansion of the class of solved index coding problems up to (but not including) these instances.
Enhanced Security for Cloud Storage using File Encryption
Venue: arXiv cs.CR 2013
Year: 2013

Cloud computing is a term coined to a network that offers incredible processing power, a wide array of storage space and unbelievable speed of computation. Social media channels, corporate structures and individual consumers are all switching to the magnificent world of cloud computing. The flip side to this coin is that with cloud storage emerges the security issues of confidentiality, data integrity and data availability. Since the cloud is a mere collection of tangible super computers spread across the world, authentication and authorization for data access is more than a necessity. Our work attempts to overcome these security threats. The proposed methodology suggests the encryption of the files to be uploaded on the cloud. The integrity and confidentiality of the data uploaded by the user is ensured doubly by not only encrypting it but also providing access to the data only on successful authentication.
Discrete Optimization of Statistical Sample Sizes in Simulation by Using the Hierarchical Bootstrap Method
Venue: arXiv cs.AI 2013
Year: 2013

The Bootstrap method application in simulation supposes that value of random variables are not generated during the simulation process but extracted from available sample populations. In the case of Hierarchical Bootstrap the function of interest is calculated recurrently using the calculation tree. In the present paper we consider the optimization of sample sizes in each vertex of the calculation tree. The dynamic programming method is used for this aim. Proposed method allows to decrease a variance of system characteristic estimators.
Parallelization in Scientific Workflow Management Systems
Venue: arXiv cs.DC 2013
Year: 2013

Over the last two decades, scientific workflow management systems (SWfMS) have emerged as a means to facilitate the design, execution, and monitoring of reusable scientific data processing pipelines. At the same time, the amounts of data generated in various areas of science outpaced enhancements in computational power and storage capabilities. This is especially true for the life sciences, where new technologies increased the sequencing throughput from kilobytes to terabytes per day. This trend requires current SWfMS to adapt: Native support for parallel workflow execution must be provided to increase performance; dynamically scalable "pay-per-use" compute infrastructures have to be integrated to diminish hardware costs; adaptive scheduling of workflows in distributed compute environments is required to optimize resource utilization. In this survey we give an overview of parallelization techniques for SWfMS, both in theory and in their realization in concrete systems. We find that current systems leave considerable room for improvement and we propose key advancements to the landscape of SWfMS.
Design for a Darwinian Brain: Part 1. Philosophy and Neuroscience
Venue: arXiv cs.AI 2013
Year: 2013

Physical symbol systems are needed for open-ended cognition. A good way to understand physical symbol systems is by comparison of thought to chemistry. Both have systematicity, productivity and compositionality. The state of the art in cognitive architectures for open-ended cognition is critically assessed. I conclude that a cognitive architecture that evolves symbol structures in the brain is a promising candidate to explain open-ended cognition. Part 2 of the paper presents such a cognitive architecture.
Design for a Darwinian Brain: Part 2. Cognitive Architecture
Venue: arXiv cs.AI 2013
Year: 2013

The accumulation of adaptations in an open-ended manner during lifetime learning is a holy grail in reinforcement learning, intrinsic motivation, artificial curiosity, and developmental robotics. We present a specification for a cognitive architecture that is capable of specifying an unlimited range of behaviors. We then give examples of how it can stochastically explore an interesting space of adjacent possible behaviors. There are two main novelties; the first is a proper definition of the fitness of self-generated games such that interesting games are expected to evolve. The second is a modular and evolvable behavior language that has systematicity, productivity, and compositionality, i.e. it is a physical symbol system. A part of the architecture has already been implemented on a humanoid robot.
Regularly random duality
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we look at a class of random optimization problems. We discuss ways that can help determine typical behavior of their solutions. When the dimensions of the optimization problems are large such an information often can be obtained without actually solving the original problems. Moreover, we also discover that fairly often one can actually determine many quantities of interest (such as, for example, the typical optimal values of the objective functions) completely analytically. We present a few general ideas and emphasize that the range of applications is enormous.
Queuing Methodology Based Power Efficient Routing Protocol for Reliable Data Communications in Manets
Venue: arXiv cs.DC 2013
Year: 2013

A mobile ad hoc network (MANET) is a wireless network that uses multi-hop peer-to- peer routing instead of static network infrastructure to provide network connectivity. MANETs have applications in rapidly deployed and dynamic military and civilian systems. The network topology in a MANET usually changes with time. Therefore, there are new challenges for routing protocols in MANETs since traditional routing protocols may not be suitable for MANETs. In recent years, a variety of new routing protocols targeted specifically at this environment have been developed, but little performance information on each protocol and no realistic performance comparison between them is available. This paper presents the results of a detailed packet-level simulation comparing three multi-hop wireless ad hoc network routing protocols that cover a range of design choices: DSR, NFPQR, and clustered NFPQR. By applying queuing methodology to the introduced routing protocol the reliability and throughput of the network is increased.
A Modified LSB Technique of Digital Watermarking in Spatial Domain
Venue: arXiv cs.MM 2013
Year: 2013

Digital watermarking is a technique of embedding pieces of information into digital data such as text, audio, video, and still images that can be detected or extracted later to show authentication about the data. Watermark is hidden information in the image(s) and is so designed that it does not degrade/distort the quality of the image and still keeps the information. Digital watermarking is basically to protect ownership rights and to control of making illicit copies of digital data. In this paper, we have discussed various watermarking techniques and properties and have proposed a modified LSB technique. We have implemented the proposed technique by following: 2-bits of 8-bit gray image is replaced by luminance part, next 2-bits by red component, next 2-bits by green component and next 2-bits by blue component of 32-bit image using secret key. The advantage is that watermarking capacity has been increased and unaffected by various attacks e.g. zero out LSB bits, cropping etc. Watermark image is imperceptible in resultant image. We have tested this technique on several images and found that it is quite satisfactory. This technique is secured as unauthorized user can not extract the watermarked contents easily from the original image and works well in adverse situations. We have implemented this technique on platform java 1.5.0.