OpenRaiser/Intern-Atlas huggingface dataset:
A Description Driven Approach for Flexible Metadata Tracking
Venue: arXiv cs.SE 2014
Year: 2014

Evolving user requirements presents a considerable software engineering challenge, all the more so in an environment where data will be stored for a very long time, and must remain usable as the system specification evolves around it. Capturing the description of the system addresses this issue since a description-driven approach enables new versions of data structures and processes to be created alongside the old, thereby providing a history of changes to the underlying data models and enabling the capture of provenance data. This description-driven approach is advocated in this paper in which a system called CRISTAL is presented. CRISTAL is based on description-driven principles; it can use previous versions of stored descriptions to define various versions of data which can be stored in various forms. To demonstrate the efficacy of this approach the history of the project at CERN is presented where CRISTAL was used to track data and process definitions and their associated provenance data in the construction of the CMS ECAL detector, how it was applied to handle analysis tracking and data index provenance in the neuGRID and N4U projects, and how it will be matured further in the CRISTAL-ISE project. We believe that the CRISTAL approach could be invaluable in handling the evolution, indexing and tracking of large datasets, and are keen to apply it further in this direction.
Exact Analysis of TTL Cache Networks: The Case of Caching Policies driven by Stopping Times
Venue: arXiv cs.PF 2014
Year: 2014

TTL caching models have recently regained significant research interest, largely due to their ability to fit popular caching policies such as LRU. This paper advances the state-of-the-art analysis of TTL-based cache networks by developing two exact methods with orthogonal generality and computational complexity. The first method generalizes existing results for line networks under renewal requests to the broad class of caching policies whereby evictions are driven by stopping times. The obtained results are further generalized, using the second method, to feedforward networks with Markov arrival processes (MAP) requests. MAPs are particularly suitable for non-line networks because they are closed not only under superposition and splitting, as known, but also under input-output caching operations as proven herein for phase-type TTL distributions. The crucial benefit of the two closure properties is that they jointly enable the first exact analysis of feedforward networks of TTL caches in great generality.
Abiot: A Low cost agile sonic pest control tricopter
Venue: arXiv cs.RO 2014
Year: 2014

In this paper we introduce the concept of an agile electronic pest control intelligent device for commercial usage and we have evaluated its performance in comparison with other existing similar technologies. The frequency and intensities are changed with respect to the target pest however human behavior has been found to be inert with their exposure. The unit has been tested in lab conditions as well as field testing done have given encouraging results. The device can be a standalone unit and hence work for small scale viz. kitchen garden on the other hand multiple devices acting in coordination with each other give the desired output on a larger scale.
Regular path queries on graphs with data: A rigid approach
Venue: arXiv cs.LO 2014
Year: 2014

Regular path queries (RPQ) is a classical navigational query formalism for graph databases to specify constraints on labeled paths. Recently, RPQs have been extended by Libkin and Vrgo$\rm \check{c}$ to incorporate data value comparisons among different nodes on paths, called regular path queries with data (RDPQ). It has been shown that the evaluation problem of RDPQs is PSPACE-complete and NLOGSPACE-complete in data complexity. On the other hand, the containment problem of RDPQs is in general undecidable. In this paper, we propose a novel approach to extend regular path queries with data value comparisons, called rigid regular path queries with data (RRDPQ). The main ingredient of this approach is an automata model called nondeterministic rigid register automata (NRRA), in which the data value comparisons are \emph{rigid}, in the sense that if the data value in the current position $x$ is compared to a data value in some other position $y$, then by only using the labels (but not data values), the position $y$ can be uniquely determined from $x$. We show that NRRAs are robust in the sense that nondeterministic, deterministic and two-way variant of NRRAs, as well as an extension of regular expressions, are all of the same expressivity. We then argue that the expressive power of RDPQs are reasonable by demonstrating that for every graph database, there is a localized transformation of the graph database so that every RDPQ in the original graph database can be turned into an equivalent RRDPQ over the transformed one. Finally, we investigate the computational properties of RRDPQs and conjunctive RRDPQs (CRRDPQ). In particular, we show that the containment of CRRDPQs (and RRDPQs) can be decided in 2EXPSPACE.
Approximating the Cubicity of Trees
Venue: arXiv cs.DM 2014
Year: 2014

Cubicity of a graph $G$ is the smallest dimension $d$, for which $G$ is a unit disc graph in ${\mathbb{R}}^d$, under the $l^\infty$ metric, i.e. $G$ can be represented as an intersection graph of $d$-dimensional (axis-parallel) unit hypercubes. We call such an intersection representation a $d$-dimensional cube representation of $G$. Computing cubicity is known to be inapproximable in polynomial time, within an $O(n^{1-ε})$ factor for any $ε>0$, unless NP=ZPP. In this paper, we present a randomized algorithm that runs in polynomial time and computes cube representations of trees, of dimension within a constant factor of the optimum. It is also shown that the cubicity of trees can be approximated within a constant factor in deterministic polynomial time, if the cube representation is not required to be computed. As far as we know, this is the first constant factor approximation algorithm for computing the cubicity of trees. It is not yet clear whether computing the cubicity of trees is NP-hard or not.
A proof-theoretic view on scheduling in concurrency
Venue: arXiv cs.LO 2014
Year: 2014

This paper elaborates on a new approach of the question of the proof-theoretic study of concurrent interaction called "proofs as schedules". Observing that proof theory is well suited to the description of confluent systems while concurrency has non-determinism as a fundamental feature, we develop a correspondence where proofs provide what is needed to make concurrent systems confluent, namely scheduling. In our logical system, processes and schedulers appear explicitly as proofs in different fragments of the proof language and cut elimination between them does correspond to execution of a concurrent system. This separation of roles suggests new insights for the denotational semantics of processes and new methods for the translation of pi-calculi into prefix-less formalisms (like solos) as the operational counterpart of translations between proof systems.
Authentication Mechanism for Resistance to Password Stealing and Reuse Attack
Venue: arXiv cs.CR 2014
Year: 2014

Considering computer systems, security is the major concern with usability. Security policies need to be developed to protect information from unauthorized access. Passwords and secrete codes used between users and information systems for secure user authentication with the system. Playing a vital role in security, easily guessed passwords are links to vulnerability. They allow invader to put system resources significantly closer to access them, other accounts on nearby machines and possibly even administrative privileges with different threats and vulnerabilities (e.g., phishing, key logging and malwares). The purpose of this system is to introduce the concept and methodology which helps organization and users to implement stronger password policies. This paper studies a password stealing and reuse issues of password based authentication systems. Techniques and concepts of authentication are discussed which gives rise to a novel approach of two-factor authentication. Avoiding password reuse is a crucial issue in information systems which can at some extent contribute to password stealing issue also. In the proposed system, each participating website possesses a user's unique phone number, telecommunication services in registration and recovery phases and a long-term password used to generate one-time password for each login session on all websites.
Considerations about multistep community detection
Venue: arXiv cs.SI 2014
Year: 2014

The problem and implications of community detection in networks have raised a huge attention, for its important applications in both natural and social sciences. A number of algorithms has been developed to solve this problem, addressing either speed optimization or the quality of the partitions calculated. In this paper we propose a multi-step procedure bridging the fastest, but less accurate algorithms (coarse clustering), with the slowest, most effective ones (refinement). By adopting heuristic ranking of the nodes, and classifying a fraction of them as `critical', a refinement step can be restricted to this subset of the network, thus saving computational time. Preliminary numerical results are discussed, showing improvement of the final partition.
Tensor computations in computer algebra systems
Venue: arXiv cs.SC 2014
Year: 2014

This paper considers three types of tensor computations. On their basis, we attempt to formulate criteria that must be satisfied by a computer algebra system dealing with tensors. We briefly overview the current state of tensor computations in different computer algebra systems. The tensor computations are illustrated with appropriate examples implemented in specific systems: Cadabra and Maxima.
Analysis of Multibeam SONAR Data using Dissimilarity Representations
Venue: arXiv cs.CE 2014
Year: 2014

This paper considers the problem of low-dimensional visualisation of very high dimensional information sources for the purpose of situation awareness in the maritime environment. In response to the requirement for human decision support aids to reduce information overload (and specifically, data amenable to inter-point relative similarity measures) appropriate to the below-water maritime domain, we are investigating a preliminary prototype topographic visualisation model. The focus of the current paper is on the mathematical problem of exploiting a relative dissimilarity representation of signals in a visual informatics mapping model, driven by real-world sonar systems. An independent source model is used to analyse the sonar beams from which a simple probabilistic input model to represent uncertainty is mapped to a latent visualisation space where data uncertainty can be accommodated. The use of euclidean and non-euclidean measures are used and the motivation for future use of non-euclidean measures is made. Concepts are illustrated using a simulated 64 beam weak SNR dataset with realistic sonar targets.
Computing discrete logarithms in subfields of residue class rings
Venue: arXiv cs.CC 2014
Year: 2014

Recent breakthrough methods \cite{gggz,joux,bgjt} on computing discrete logarithms in small characteristic finite fields share an interesting feature in common with the earlier medium prime function field sieve method \cite{jl}. To solve discrete logarithms in a finite extension of a finite field $\F$, a polynomial $h(x) \in \F[x]$ of a special form is constructed with an irreducible factor $g(x) \in \F[x]$ of the desired degree. The special form of $h(x)$ is then exploited in generating multiplicative relations that hold in the residue class ring $\F[x]/h(x)\F[x]$ hence also in the target residue class field $\F[x]/g(x)\F[x]$. An interesting question in this context and addressed in this paper is: when and how does a set of relations on the residue class ring determine the discrete logarithms in the finite fields contained in it? We give necessary and sufficient conditions for a set of relations on the residue class ring to determine discrete logarithms in the finite fields contained in it. We also present efficient algorithms to derive discrete logarithms from the relations when the conditions are met. The derived necessary conditions allow us to clearly identify structural obstructions intrinsic to the special polynomial $h(x)$ in each of the aforementioned methods, and propose modifications to the selection of $h(x)$ so as to avoid obstructions.
On Linear Codes over $\mathbb{Z}_4+v\mathbb{Z}_4$
Venue: arXiv cs.IT 2014
Year: 2014

Linear codes are considered over the ring $\mathbb{Z}_4+v\mathbb{Z}_4$, where $v^2=v$. Gray weight, Gray maps for linear codes are defined and MacWilliams identity for the Gray weight enumerator is given. Self-dual codes, construction of Euclidean isodual codes, unimodular complex lattices, MDS codes and MGDS codes over $\mathbb{Z}_4+v\mathbb{Z}_4$ are studied. Cyclic codes and quadratic residue codes are also considered. Finally, some examples for illustrating the main work are given.
Analyzing Cascading Failures in Smart Grids under Random and Targeted Attacks
Venue: arXiv cs.SI 2014
Year: 2014

We model smart grids as complex interdependent networks, and study targeted attacks on smart grids for the first time. A smart grid consists of two networks: the power network and the communication network, interconnected by edges. Occurrence of failures (attacks) in one network triggers failures in the other network, and propagates in cascades across the networks. Such cascading failures can result in disintegration of either (or both) of the networks. Earlier works considered only random failures. In practical situations, an attacker is more likely to compromise nodes selectively. We study cascading failures in smart grids, where an attacker selectively compromises the nodes with probabilities proportional to their degrees; high degree nodes are compromised with higher probability. We mathematically analyze the sizes of the giant components of the networks under targeted attacks, and compare the results with the corresponding sizes under random attacks. We show that networks disintegrate faster for targeted attacks compared to random attacks. A targeted attack on a small fraction of high degree nodes disintegrates one or both of the networks, whereas both the networks contain giant components for random attack on the same fraction of nodes.
It's distributions all the way down!: Second order changes in statistical distributions also occur
Venue: arXiv cs.CL 2014
Year: 2014

The textual, big-data literature misses Bentley, OBrien, & Brocks (Bentley et als) message on distributions; it largely examines the first-order effects of how a single, signature distribution can predict population behaviour, neglecting second-order effects involving distributional shifts, either between signature distributions or within a given signature distribution. Indeed, Bentley et al. themselves under-emphasise the potential richness of the latter, within-distribution effects.
Marginalizing Corrupted Features
Venue: arXiv cs.LG 2014
Year: 2014

The goal of machine learning is to develop predictors that generalize well to test data. Ideally, this is achieved by training on an almost infinitely large training data set that captures all variations in the data distribution. In practical learning settings, however, we do not have infinite data and our predictors may overfit. Overfitting may be combatted, for example, by adding a regularizer to the training objective or by defining a prior over the model parameters and performing Bayesian inference. In this paper, we propose a third, alternative approach to combat overfitting: we extend the training set with infinitely many artificial training examples that are obtained by corrupting the original training data. We show that this approach is practical and efficient for a range of predictors and corruption models. Our approach, called marginalized corrupted features (MCF), trains robust predictors by minimizing the expected value of the loss function under the corruption model. We show empirically on a variety of data sets that MCF classifiers can be trained efficiently, may generalize substantially better to test data, and are also more robust to feature deletion at test time.
Data-driven HRF estimation for encoding and decoding models
Venue: arXiv cs.CE 2014
Year: 2014

Despite the common usage of a canonical, data-independent, hemodynamic response function (HRF), it is known that the shape of the HRF varies across brain regions and subjects. This suggests that a data-driven estimation of this function could lead to more statistical power when modeling BOLD fMRI data. However, unconstrained estimation of the HRF can yield highly unstable results when the number of free parameters is large. We develop a method for the joint estimation of activation and HRF using a rank constraint causing the estimated HRF to be equal across events/conditions, yet permitting it to be different across voxels. Model estimation leads to an optimization problem that we propose to solve with an efficient quasi-Newton method exploiting fast gradient computations. This model, called GLM with Rank-1 constraint (R1-GLM), can be extended to the setting of GLM with separate designs which has been shown to improve decoding accuracy in brain activity decoding experiments. We compare 10 different HRF modeling methods in terms of encoding and decoding score in two different datasets. Our results show that the R1-GLM model significantly outperforms competing methods in both encoding and decoding settings, positioning it as an attractive method both from the points of view of accuracy and computational efficiency.
Neural Network Approach to Railway Stand Lateral Skew Control
Venue: arXiv cs.SY 2014
Year: 2014

The paper presents a study of an adaptive approach to lateral skew control for an experimental railway stand. The preliminary experiments with the real experimental railway stand and simulations with its 3-D mechanical model, indicates difficulties of model-based control of the device. Thus, use of neural networks for identification and control of lateral skew shall be investigated. This paper focuses on real-data based modeling of the railway stand by various neural network models, i.e; linear neural unit and quadratic neural unit architectures. Furthermore, training methods of these neural architectures as such, real-time-recurrent-learning and a variation of back-propagation-through-time are examined, accompanied by a discussion of the produced experimental results.
Identifying Users with Opposing Opinions in Twitter Debates
Venue: arXiv cs.SI 2014
Year: 2014

In recent times, social media sites such as Twitter have been extensively used for debating politics and public policies. These debates span millions of tweets and numerous topics of public importance. Thus, it is imperative that this vast trove of data is tapped in order to gain insights into public opinion especially on hotly contested issues such as abortion, gun reforms etc. Thus, in our work, we aim to gauge users' stance on such topics in Twitter. We propose ReLP, a semi-supervised framework using a retweet-based label propagation algorithm coupled with a supervised classifier to identify users with differing opinions. In particular, our framework is designed such that it can be easily adopted to different domains with little human supervision while still producing excellent accuracy
Two-Hop Routing with Traffic-Differentiation for QoS Guarantee in Wireless Sensor Networks
Venue: arXiv cs.NI 2014
Year: 2014

This paper proposes a Traffic-Differentiated Two-Hop Routing protocol for Quality of Service (QoS) in Wireless Sensor Networks (WSNs). It targets WSN applications having different types of data traffic with several priorities. The protocol achieves to increase Packet Reception Ratio (PRR) and reduce end-to-end delay while considering multi-queue priority policy, two-hop neighborhood information, link reliability and power efficiency. The protocol is modular and utilizes effective methods for estimating the link metrics. Numerical results show that the proposed protocol is a feasible solution to addresses QoS service differenti- ation for traffic with different priorities.
Large-Scale Molecular Dynamics Simulations for Highly Parallel Infrastructures
Venue: arXiv cs.DC 2014
Year: 2014

Computational chemistry allows researchers to experiment in sillico: by running a computer simulations of a biological or chemical processes of interest. Molecular dynamics with molecular mechanics model of interactions simulates N-body problem of atoms$-$it computes movements of atoms according to Newtonian physics and empirical descriptions of atomic electrostatic interactions. These simulations require high performance computing resources, as evaluations within each step are computationally demanding and billions of steps are needed to reach interesting timescales. Current methods decompose the spatial domain of the problem and calculate on parallel/distributed infrastructures. Even the methods with the highest strong scaling hit the limit at half a million cores: they are not able to cut the time to result if provided with more processors. At the dawn of exascale computing with massively parallel computational resources, we want to increase the level of parallelism by incorporating parallel-in-time computation to molecular dynamics simulations. Calculation of results in several successive time points simultaneously without a priori knowledge has been examined with no major success. We will study and implement a novel combinations of methods that according to our theoretical analyses should achieve promising speed-up compared to sequential-in-time calculation.
A Simple Character String Proof of the "True but Unprovable" Version of Gödel's First Incompleteness Theorem
Venue: arXiv cs.LO 2014
Year: 2014

A rather easy yet rigorous proof of a version of Gödel's first incompleteness theorem is presented. The version is "each recursively enumerable theory of natural numbers with 0, 1, +, *, =, logical and, logical not, and the universal quantifier either proves a false sentence or fails to prove a true sentence". The proof proceeds by first showing a similar result on theories of finite character strings, and then transporting it to natural numbers, by using them to model strings and their concatenation. Proof systems are expressed via Turing machines that halt if and only if their input string is a theorem. This approach makes it possible to present all but one parts of the proof rather briefly with simple and straightforward constructions. The details require some care, but do not require significant background knowledge. The missing part is the widely known fact that Turing machines can perform complicated computational tasks.
On nonpermutational transformation semigroups with an application to syntactic complexity
Venue: arXiv cs.FL 2014
Year: 2014

We give an upper bound of $n((n-1)!-(n-3)!)$ for the possible largest size of a subsemigroup of the full transformational semigroup over $n$ elements consisting only of nonpermutational transformations. As an application we gain the same upper bound for the syntactic complexity of (generalized) definite languages as well.