OpenRaiser/Intern-Atlas huggingface dataset:
Effect of Different Distance Measures on the Performance of K-Means Algorithm: An Experimental Study in Matlab
Venue: arXiv cs.LG 2014
Year: 2014

K-means algorithm is a very popular clustering algorithm which is famous for its simplicity. Distance measure plays a very important rule on the performance of this algorithm. We have different distance measure techniques available. But choosing a proper technique for distance calculation is totally dependent on the type of the data that we are going to cluster. In this paper an experimental study is done in Matlab to cluster the iris and wine data sets with different distance measures and thereby observing the variation of the performances shown.
Automatic Generation of Security Argument Graphs
Venue: arXiv cs.CR 2014
Year: 2014

Graph-based assessment formalisms have proven to be useful in the safety, dependability, and security communities to help stakeholders manage risk and maintain appropriate documentation throughout the system lifecycle. In this paper, we propose a set of methods to automatically construct security argument graphs, a graphical formalism that integrates various security-related information to argue about the security level of a system. Our approach is to generate the graph in a progressive manner by exploiting logical relationships among pieces of diverse input information. Using those emergent argument patterns as a starting point, we define a set of extension templates that can be applied iteratively to grow a security argument graph. Using a scenario from the electric power sector, we demonstrate the graph generation process and highlight its application for system security evaluation in our prototype software tool, CyberSAGE.
On total communication complexity of collapsing protocols for pointer jumping problem
Venue: arXiv cs.CC 2014
Year: 2014

This paper focuses on bounding the total communication complexity of collapsing protocols for multiparty pointer jumping problem ($MPJ_k^n$). Brody and Chakrabati in \cite{bc08} proved that in such setting one of the players must communicate at least $n - 0.5\log{n}$ bits. Liang in \cite{liang} has shown protocol matching this lower bound on maximum complexity. His protocol, however, was behaving worse than the trivial one in terms of total complexity (number of bits sent by all players). He conjectured that achieving total complexity better then the trivial one is impossible. In this paper we prove this conjecture. Namely, we show that for a collapsing protocol for $MPJ_k^n$, the total communication complexity is at least $n-2$ which closes the gap between lower and upper bound for total complexity of $MPJ_k^n$ in collapsing setting.
Formal Verification of Control Systems Properties with Theorem Proving
Venue: arXiv cs.SY 2014
Year: 2014

This paper presents the deductive formal verification of high-level properties of control systems with theorem proving, using the Why3 tool. Properties that can be verified with this approach include stability, feedback gain, and robustness, among others. For the systems, modelled in Simulink, we propose three main steps to achieve the verification: specifying the properties of interest over the signals within the model using Simulink blocks, an automatic translation of the model into Why3, and the automatic verification of the properties with theorem provers in Why3. We present a methodology to specify the properties in the model and a library of relevant assertion blocks (logic expressions), currently in development. The functionality of the blocks in the Simulink models are automatically translated to Why3 as theories and verification goals by our tool implemented in MATLAB. A library of theories in Why3 corresponding to each supported block has been developed to facilitate the process of translation. The goals are automatically verified in Why3 with relevant theorem provers. A simple first-order discrete system is used to exemplify the specification of the Simulink model, the translation process from Simulink to the Why3 formal logic language, and the verification of Lyapunov stability.
Diffusion-Aware Sampling and Estimation in Information Diffusion Networks
Venue: arXiv cs.SI 2014
Year: 2014

Partially-observed data collected by sampling methods is often being studied to obtain the characteristics of information diffusion networks. However, these methods usually do not consider the behavior of diffusion process. In this paper, we propose a novel two-step (sampling/estimation) measurement framework by utilizing the diffusion process characteristics. To this end, we propose a link-tracing based sampling design which uses the infection times as local information without any knowledge about the latent structure of diffusion network. To correct the bias of sampled data, we introduce three estimators for different categories; link-based, node-based, and cascade-based. To the best of our knowledge, this is the first attempt to introduce a complete measurement framework for diffusion networks. We also show that the estimator plays an important role in correcting the bias of sampling from diffusion networks. Our comprehensive empirical analysis over large synthetic and real datasets demonstrates that in average, the proposed framework outperforms the common BFS and RW sampling methods in terms of link-based characteristics by about 37% and 35%, respectively.
Learning to Act Greedily: Polymatroid Semi-Bandits
Venue: arXiv cs.LG 2014
Year: 2014

Many important optimization problems, such as the minimum spanning tree and minimum-cost flow, can be solved optimally by a greedy method. In this work, we study a learning variant of these problems, where the model of the problem is unknown and has to be learned by interacting repeatedly with the environment in the bandit setting. We formalize our learning problem quite generally, as learning how to maximize an unknown modular function on a known polymatroid. We propose a computationally efficient algorithm for solving our problem and bound its expected cumulative regret. Our gap-dependent upper bound is tight up to a constant and our gap-free upper bound is tight up to polylogarithmic factors. Finally, we evaluate our method on three problems and demonstrate that it is practical.
Software Package with Exercises for Therapy of Children with Dyslalia
Venue: arXiv cs.CY 2014
Year: 2014

In this paper we present a consistent set of exercises for children with dyslalia (dyslalia is a speech disorder that affect pronunciation of one ore many sounds). The achievement has gone from "Therapeutic Guide" made available by the team of researchers led by Professor Mrs. Iolanda TOBOLCEA from the "Alexandru Ioan Cuza" University of Iasi. The specifications of the "Therapeutic Guide" have been fully complied with, such exercises being adapted both age and level of children. To achieve these exercises were recorded, processed and used more than 10000 voice production. They also have been made over the 2000 corresponding recorded nouns. These exercises are being tested by Interschool Regional Logopaedic Center of Suceava - Romania.
ROMEO: ReputatiOn Model Enhancing OpenID Simulator
Venue: arXiv cs.CR 2014
Year: 2014

OpenID is a standard decentralized initiative aimed at allowing Internet users to use the same personal account to access different services. Since it does not rely on any central authority, it is hard for such users or other entities to validate the trust level of each entity deployed in the system. Some research has been conducted to handle this issue, defining a reputation framework to determine the trust level of a relying party based on past experiences. However, this framework has been proposed in a theoretical way and some deeper analysis and validation is still missing. Our main contribution in this paper consist of a simulation environment able to validate the feasibility of the reputation framework and analyze its behaviour within different scenarios.
Analysis Of Possible Attack On AODV Protocol In MANET
Venue: arXiv cs.NI 2014
Year: 2014

Mobile Ad Hoc Networks (MANETs) consist of wireless mobile nodes which coordinate with each other to form temporary network without its pre-existing infrastructure. AODV is popular Ad-hoc distance vector routing reactive protocol which is used to find correct & shortest route to destination. Due to openness, dynamic, infrastructure-less nature, MANET are vulnerable to various attacks. One of these possible attacks is a Black Hole Attack in which a mobile node falsely replies to the source node that it is having a shortest path to the destination without checking its routing table. Therefore source node send all of its data to the black hole node and it deprives all the traffic of the source node. In this paper, We are proposing a technique to detect and prevent the multiple black hole nodes from MANET so that source to destination communication can be made easily. We also analysed the performance of the network in terms of number of packets sent, received, throughput, energy of network before attack and after detection & prevention of Attack. From these analysis, we can conclude that performance decreased due to attack can be improved after detection & prevention black hole attack in MANET.
Knowledge Maps and Information Retrieval (KMIR)
Venue: arXiv cs.IR 2014
Year: 2014

Information systems usually show as a particular point of failure the vagueness between user search terms and the knowledge orders of the information space in question. Some kind of guided searching therefore becomes more and more important in order to precisely discover information without knowing the right search terms. Knowledge maps of digital library collections are promising navigation tools through knowledge spaces but still far away from being applicable for searching digital libraries. However, there is no continuous knowledge exchange between the "map makers" on the one hand and the Information Retrieval (IR) specialists on the other hand. Thus, there is also a lack of models that properly combine insights of the two strands. The proposed workshop aims at bringing together these two communities: experts in IR reflecting on visual enhanced search interfaces and experts in knowledge mapping reflecting on visualizations of the content of a collection that might also present a context for a search term in a visual manner. The intention of the workshop is to raise awareness of the potential of interactive knowledge maps for information seeking purposes and to create a common ground for experiments aiming at the incorporation of knowledge maps into IR models at the level of the user interface.
Chordal Editing is Fixed-Parameter Tractable
Venue: arXiv cs.DS 2014
Year: 2014

Graph modification problems are typically asked as follows: is there a small set of operations that transforms a given graph to have a certain property. The most commonly considered operations include vertex deletion, edge deletion, and edge addition; for the same property, one can define significantly different versions by allowing different operations. We study a very general graph modification problem which allows all three types of operations: given a graph $G$ and integers $k_1$, $k_2$, and $k_3$, the \textsc{chordal editing} problem asks whether $G$ can be transformed into a chordal graph by at most $k_1$ vertex deletions, $k_2$ edge deletions, and $k_3$ edge additions. Clearly, this problem generalizes both \textsc{chordal vertex/edge deletion} and \textsc{chordal completion} (also known as \textsc{minimum fill-in}). Our main result is an algorithm for \textsc{chordal editing} in time $2^{O(k\log k)}\cdot n^{O(1)}$, where $k:=k_1+k_2+k_3$ and $n$ is the number of vertices of $G$. Therefore, the problem is fixed-parameter tractable parameterized by the total number of allowed operations. Our algorithm is both more efficient and conceptually simpler than the previously known algorithm for the special case \textsc{chordal deletion}.
Empirical mode decomposition and normalshrink tresholding for speech denoising
Venue: arXiv cs.IT 2014
Year: 2014

In this paper a signal denoising scheme based on Empirical mode decomposition (EMD) is presented. The denoising method is a fully data driven approach. Noisy signal is decomposed adaptively into intrinsic oscillatory components called Intrinsic mode functions (IMFs) using a decomposition algorithm called sifting process. The basic principle of the method is to decompose a speech signal into segments each frame is categorised as either signal-dominant or noise-dominant then reconstruct the signal with IMFs signal dominant frame previously filtered or thresholded. It is shown, on the basis of intensive simulations that EMD improves the signal to noise ratio and address the problem of signal degradation. The denoising method is applied to real signal with different noise levels and the results compared to Winner and universal threshold of DONOHO and JOHNSTONE [11] with soft and hard tresholding. The effect of level noise value on the performances of the proposed denoising is analysed. The study is limited to signals corrupted by additive white Gaussian random noise.
The Shortlist Method for Fast Computation of the Earth Mover's Distance and Finding Optimal Solutions to Transportation Problems
Venue: arXiv cs.CV 2014
Year: 2014

Finding solutions to the classical transportation problem is of great importance, since this optimization problem arises in many engineering and computer science applications. Especially the Earth Mover's Distance is used in a plethora of applications ranging from content-based image retrieval, shape matching, fingerprint recognition, object tracking and phishing web page detection to computing color differences in linguistics and biology. Our starting point is the well-known revised simplex algorithm, which iteratively improves a feasible solution to optimality. The Shortlist Method that we propose substantially reduces the number of candidates inspected for improving the solution, while at the same time balancing the number of pivots required. Tests on simulated benchmarks demonstrate a considerable reduction in computation time for the new method as compared to the usual revised simplex algorithm implemented with state-of-the-art initialization and pivot strategies. As a consequence, the Shortlist Method facilitates the computation of large scale transportation problems in viable time. In addition we describe a novel method for finding an initial feasible solution which we coin Modified Russell's Method.
Bisimulation Equivalence of First-Order Grammars
Venue: arXiv cs.LO 2014
Year: 2014

A decidability proof for bisimulation equivalence of first-order grammars (finite sets of labelled rules for rewriting roots of first-order terms) is presented. The equivalence generalizes the DPDA (deterministic pushdown automata) equivalence, and the result corresponds to the result achieved by Senizergues (1998, 2005) in the framework of equational graphs, or of PDA with restricted epsilon-steps. The framework of classical first-order terms seems particularly useful for providing a proof that should be understandable for a wider audience. We also discuss an extension to branching bisimilarity, announced by Fu and Yin (2014).
Biclique coverings, rectifier networks and the cost of $\varepsilon$-removal
Venue: arXiv cs.FL 2014
Year: 2014

We relate two complexity notions of bipartite graphs: the minimal weight biclique covering number $\mathrm{Cov}(G)$ and the minimal rectifier network size $\mathrm{Rect}(G)$ of a bipartite graph $G$. We show that there exist graphs with $\mathrm{Cov}(G)\geq \mathrm{Rect}(G)^{3/2-ε}$. As a corollary, we establish that there exist nondeterministic finite automata (NFAs) with $\varepsilon$-transitions, having $n$ transitions total such that the smallest equivalent $\varepsilon$-free NFA has $Ω(n^{3/2-ε})$ transitions. We also formulate a version of previous bounds for the weighted set cover problem and discuss its connections to giving upper bounds for the possible blow-up.
EACOF: A Framework for Providing Energy Transparency to enable Energy-Aware Software Development
Venue: arXiv cs.SE 2014
Year: 2014

Making energy consumption data accessible to software developers is an essential step towards energy efficient software engineering. The presence of various different, bespoke and incompatible, methods of instrumentation to obtain energy readings is currently limiting the widespread use of energy data in software development. This paper presents EACOF, a modular Energy-Aware Computing Framework that provides a layer of abstraction between sources of energy data and the applications that exploit them. EACOF replaces platform specific instrumentation through two APIs - one accepts input to the framework while the other provides access to application software. This allows developers to profile their code for energy consumption in an easy and portable manner using simple API calls. We outline the design of our framework and provide details of the API functionality. In a use case, where we investigate the impact of data bit width on the energy consumption of various sorting algorithms, we demonstrate that the data obtained using EACOF provides interesting, sometimes counter-intuitive, insights. All the code is available online under an open source license. http://github.com/eacof
Deterministic Rateless Codes for BSC
Venue: arXiv cs.IT 2014
Year: 2014

A rateless code encodes a finite length information word into an infinitely long codeword such that longer prefixes of the codeword can tolerate a larger fraction of errors. A rateless code achieves capacity for a family of channels if, for every channel in the family, reliable communication is obtained by a prefix of the code whose rate is arbitrarily close to the channel's capacity. As a result, a universal encoder can communicate over all channels in the family while simultaneously achieving optimal communication overhead. In this paper, we construct the first \emph{deterministic} rateless code for the binary symmetric channel. Our code can be encoded and decoded in $O(β)$ time per bit and in almost logarithmic parallel time of $O(β\log n)$, where $β$ is any (arbitrarily slow) super-constant function. Furthermore, the error probability of our code is almost exponentially small $\exp(-Ω(n/β))$. Previous rateless codes are probabilistic (i.e., based on code ensembles), require polynomial time per bit for decoding, and have inferior asymptotic error probabilities. Our main technical contribution is a constructive proof for the existence of an infinite generating matrix that each of its prefixes induce a weight distribution that approximates the expected weight distribution of a random linear code.
Parallelism Via Concurrency at Multiple Levels
Venue: arXiv cs.PF 2014
Year: 2014

In this paper we examine the key elements determining the best performance of computing by increasing the frequency of a single chip and to get the minimum latency during execution of the programs to achieve best possible output. It is not enough to provide concurrent improvements in the hardware as Software also have to introduce concurrency in order to exploit the parallelism. The software parallelism is defined by the control and data dependency of programs whereas Hardware refers to the type of parallelism defined by the machine architecture and hardware multiplicity.
Efficient Soft-Input Soft-Output Detection of Dual-Layer MIMO Systems
Venue: arXiv cs.IT 2014
Year: 2014

A dual-layer multiple-input multiple-output (MIMO) system with multi-level modulation is considered. A computationally efficient soft-input soft-output receiver based on the exact max-log maximum a posteriori (max-log-MAP) principle is presented in the context of iterative detection and decoding. We show that the computational complexity of our exact max-log-MAP solution grows linearly with the constellation size and is, furthermore, less than that of the best known methods of Turbo-LORD that only provide approximate solutions. Using decoder feedback to change the decision thresholds of the constellation symbols, we show that the exhaustive search operation boils down to a simple slicing operation. For various simulation parameters, we verify that our solution performs identically to the brute-force exhaustive search max-log MAP solution.
A quadratic lower bound for the convergence rate in the one-dimensional Hegselmann-Krause bounded confidence dynamics
Venue: arXiv cs.SY 2014
Year: 2014

Let f_{k}(n) be the maximum number of time steps taken to reach equilibrium by a system of n agents obeying the k-dimensional Hegselmann-Krause bounded confidence dynamics. Previously, it was known that Ω(n) = f_{1}(n) = O(n^3). Here we show that f_{1}(n) = Ω(n^2), which matches the best-known lower bound in all dimensions k >= 2.
A Cooperative Emergency Navigation Framework using Mobile Cloud Computing
Venue: arXiv cs.NI 2014
Year: 2014

The use of wireless sensor networks (WSNs) for emergency navigation systems suffer disadvantages such as limited computing capacity, restricted battery power and high likelihood of malfunction due to the harsh physical environment. By making use of the powerful sensing ability of smart phones, this paper presents a cloud-enabled emergency navigation framework to guide evacuees in a coordinated manner and improve the reliability and resilience in both communication and localization. By using social potential fields (SPF), evacuees form clusters during an evacuation process and are directed to egresses with the aid of a Cognitive Packet Networks (CPN) based algorithm. Rather than just rely on the conventional telecommunications infrastructures, we suggest an Ad hoc Cognitive Packet Network (AHCPN) based protocol to prolong the life time of smart phones, that adaptively searches optimal communication routes between portable devices and the egress node that provides access to a cloud server with respect to the remaining battery power of smart phones and the time latency.
Query Answering over Contextualized RDF/OWL Knowledge with Forall-Existential Bridge Rules: Attaining Decidability using Acyclicity (full version)
Venue: arXiv cs.LO 2014
Year: 2014

The recent outburst of context-dependent knowledge on the Semantic Web (SW) has led to the realization of the importance of the quads in the SW community. Quads, which extend a standard RDF triple, by adding a new parameter of the `context' of an RDF triple, thus informs a reasoner to distinguish between the knowledge in various contexts. Although this distinction separates the triples in an RDF graph into various contexts, and allows the reasoning to be decoupled across various contexts, bridge rules need to be provided for inter-operating the knowledge across these contexts. We call a set of quads together with the bridge rules, a quad-system. In this paper, we discuss the problem of query answering over quad-systems with expressive forall-existential bridge rules. It turns out the query answering over quad-systems is undecidable, in general. We derive a decidable class of quad-systems, namely context-acyclic quad-systems, for which query answering can be done using forward chaining. Tight bounds for data and combined complexity of query entailment has been established for the derived class.