OpenRaiser/Intern-Atlas huggingface dataset:
Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions
Venue: arXiv cs.SI 2015
Year: 2015

The Adaptive Seeding problem is an algorithmic challenge motivated by influence maximization in social networks: One seeks to select among certain accessible nodes in a network, and then select, adaptively, among neighbors of those nodes as they become accessible in order to maximize a global objective function. More generally, adaptive seeding is a stochastic optimization framework where the choices in the first stage affect the realizations in the second stage, over which we aim to optimize. Our main result is a $(1-1/e)^2$-approximation for the adaptive seeding problem for any monotone submodular function. While adaptive policies are often approximated via non-adaptive policies, our algorithm is based on a novel method we call \emph{locally-adaptive} policies. These policies combine a non-adaptive global structure, with local adaptive optimizations. This method enables the $(1-1/e)^2$-approximation for general monotone submodular functions and circumvents some of the impossibilities associated with non-adaptive policies. We also introduce a fundamental problem in submodular optimization that may be of independent interest: given a ground set of elements where every element appears with some small probability, find a set of expected size at most $k$ that has the highest expected value over the realization of the elements. We show a surprising result: there are classes of monotone submodular functions (including coverage) that can be approximated almost optimally as the probability vanishes. For general monotone submodular functions we show via a reduction from \textsc{Planted-Clique} that approximations for this problem are not likely to be obtainable. This optimization problem is an important tool for adaptive seeding via non-adaptive policies, and its hardness motivates the introduction of \emph{locally-adaptive} policies we use in the main result.
Request Prediction in Cloud with a Cyclic Window Learning Algorithm
Venue: arXiv cs.DC 2015
Year: 2015

Automatic resource scaling is one advantage of Cloud systems. Cloud systems are able to scale the number of physical machines depending on user requests. Therefore, accurate request prediction brings a great improvement in Cloud systems' performance. If we can make accurate requests prediction, the appropriate number of physical machines that can accommodate predicted amount of requests can be activated and Cloud systems will save more energy by preventing excessive activation of physical machines. Also, Cloud systems can implement advanced load distribution with accurate requests prediction. We propose an algorithm that predicts a probability distribution parameters of requests for each time interval. Maximum Likelihood Estimation (MLE) and Local Linear Regression (LLR) are used to implement this algorithm. An evaluation of the proposed algorithm is performed with the Google cluster-trace data. The prediction is implemented about the number of task arrivals, CPU requests, and memory requests. Then the accuracy of prediction is measured with Mean Absolute Percentage Error (MAPE).
Decentralized Joint-Sparse Signal Recovery: A Sparse Bayesian Learning Approach
Venue: arXiv cs.LG 2015
Year: 2015

This work proposes a decentralized, iterative, Bayesian algorithm called CB-DSBL for in-network estimation of multiple jointly sparse vectors by a network of nodes, using noisy and underdetermined linear measurements. The proposed algorithm exploits the network wide joint sparsity of the un- known sparse vectors to recover them from significantly fewer number of local measurements compared to standalone sparse signal recovery schemes. To reduce the amount of inter-node communication and the associated overheads, the nodes exchange messages with only a small subset of their single hop neighbors. Under this communication scheme, we separately analyze the convergence of the underlying Alternating Directions Method of Multipliers (ADMM) iterations used in our proposed algorithm and establish its linear convergence rate. The findings from the convergence analysis of decentralized ADMM are used to accelerate the convergence of the proposed CB-DSBL algorithm. Using Monte Carlo simulations, we demonstrate the superior signal reconstruction as well as support recovery performance of our proposed algorithm compared to existing decentralized algorithms: DRL-1, DCOMP and DCSP.
SAT-based Explicit LTL Reasoning
Venue: arXiv cs.LO 2015
Year: 2015

We present here a new explicit reasoning framework for linear temporal logic (LTL), which is built on top of propositional satisfiability (SAT) solving. As a proof-of-concept of this framework, we describe a new LTL satisfiability tool, Aalta\_v2.0, which is built on top of the MiniSAT SAT solver. We test the effectiveness of this approach by demonnstrating that Aalta\_v2.0 significantly outperforms all existing LTL satisfiability solvers. Furthermore, we show that the framework can be extended from propositional LTL to assertional LTL (where we allow theory atoms), by replacing MiniSAT with the Z3 SMT solver, and demonstrating that this can yield an exponential improvement in performance.
An algorithm for fast computation of the multiresolution discrete Fourier transform
Venue: arXiv cs.DS 2015
Year: 2015

The article presents a computationally effective algorithm for calculating the multiresolution discrete Fourier transform (MrDFT). The algorithm is based on the idea of reducing the computational complexity which was introduced by Wen and Sandler [10] and utilizes the vectorization of calculating process at each stage of the considered transformation. This allows for the use of a computational process parallelization and results in a reduction of computation time. In the description of the computational procedure, which describes the algorithm, we use the matrix notation. This notation enables to represent adequately the space-time structures of the implemented computational process and directly map these structures into the constructions of a high-level programming language or into a hardware realization space.
On the Time and Space Complexity of ABA Prevention and Detection
Venue: arXiv cs.DC 2015
Year: 2015

We investigate the time and space complexity of detecting and preventing ABAs in shared memory algorithms for systems with n processes and bounded base objects. To that end, we define ABA-detecting registers, which are similar to normal read/write registers, except that they allow a process q to detect with a read operation, whether some process wrote the register since q's last read. ABA-detecting registers can be implemented trivially from a single unbounded register, but we show that they have a high complexity if base objects are bounded: An obstruction-free implementation of an ABA-detecting single bit register cannot be implemented from fewer than n-1 bounded registers. Moreover, bounded CAS objects (or more generally, conditional read-modify-write primitives) offer little help to implement ABA-detecting single bit registers: We prove a linear time-space tradeoff for such implementations. We show that the same time-space tradeoff holds for implementations of single bit LL/SC primitives from bounded writable CAS objects. This proves that the implementations of LL/SC/VL by Anderson and Moir (1995) as well as Jayanti and Petrovic (2003) are optimal. We complement our lower bounds with tight upper bounds: We give an implementation of ABA-detecting registers from n+1 bounded registers, which has step complexity O(1). We also show that (bounded) LL/SC/VL can be implemented from a single bounded CAS object and with O(n) step complexity. Both upper bounds are asymptotically optimal with respect to their time-space product. These results give formal evidence that the ABA problem is inherently difficult, that even writable CAS objects do not provide significant benefits over registers for dealing with the ABA problem itself, and that there is no hope of finding a more efficient implementation of LL/SC/VL from bounded CAS objects and registers than the ones mentioned.
Some properties of skew codes over finite fields
Venue: arXiv cs.IT 2015
Year: 2015

After recalling the definition of codes as modules over skew polynomial rings, whose multiplication is defined by using an automorphism and a derivation, and some basic facts about them, in the first part of this paper we study some of their main algebraic and geometric properties. Finally, for module skew codes constructed only with an automorphism, we give some BCH type lower bounds for their minimum distance.
Lazy Explanation-Based Approximation for Probabilistic Logic Programming
Venue: arXiv cs.AI 2015
Year: 2015

We introduce a lazy approach to the explanation-based approximation of probabilistic logic programs. It uses only the most significant part of the program when searching for explanations. The result is a fast and anytime approximate inference algorithm which returns hard lower and upper bounds on the exact probability. We experimentally show that this method outperforms state-of-the-art approximate inference.
POSTER: Self-Healing Mechanisms for Software-Defined Networks
Venue: arXiv cs.NI 2015
Year: 2015

Operators perceive programmable networks brought by Software Defined Networks (SDN) as cornerstone to decrease the time to deploy new services, to augment the flexibility and to adapt network resources to customer needs at runtime. However, despite the vulnerabilities identified due that the intelligence is centralized on SDN, its research is more centered on forwarding traffic and reconfiguration issues, not considering to a great extent the fault management aspects of the control plane. This paper provides SDN with fault management capabilities by using autonomic principles like self-healing mechanisms. We propose a generic self-healing approach that relies on a Bayesian Networks for the diagnosis block and we applied this algorithm to a centralized SDN infrastructure to prove its functioning in the presence of faults.
Networks of digital humanities scholars: The informational and social uses and gratifications of Twitter
Venue: arXiv cs.CY 2015
Year: 2015

Big data research is currently split on whether and to what extent Twitter can be characterised as an informational or social network. We contribute to this line of inquiry through an investigation of digital humanities scholars' uses and gratifications of Twitter. We conducted a thematic analysis of 25 semistructured interview transcripts to learn about these scholars' professional use of Twitter. Our findings show that Twitter is considered a critical tool for informal communication within DH invisible colleges, functioning at varying levels as both an informational network (learning to 'Twitter' and maintaining awareness) and a social network (imagining audiences and engaging other digital humanists). We find that Twitter follow relationships reflect common academic interests and are closely tied to scholars' preexisting social ties and conference or event co-attendance. The concept of the invisible college continues to be relevant but requires revisiting. The invisible college formed on Twitter is messy, consisting of overlapping social contexts (professional, personal, and public), scholars with different habits of engagement, and both formal and informal ties. Our research illustrates the value of using multiple methods to explore the complex questions arising from big data studies and points toward future research that could implement big data techniques on a small scale, focusing on sub-topics or emerging fields, to expose the nature of scholars' invisible colleges made visible on Twitter.
Forecasting the cost of processing multi-join queries via hashing for main-memory databases (Extended version)
Venue: arXiv cs.DB 2015
Year: 2015

Database management systems (DBMSs) carefully optimize complex multi-join queries to avoid expensive disk I/O. As servers today feature tens or hundreds of gigabytes of RAM, a significant fraction of many analytic databases becomes memory-resident. Even after careful tuning for an in-memory environment, a linear disk I/O model such as the one implemented in PostgreSQL may make query response time predictions that are up to 2X slower than the optimal multi-join query plan over memory-resident data. This paper introduces a memory I/O cost model to identify good evaluation strategies for complex query plans with multiple hash-based equi-joins over memory-resident data. The proposed cost model is carefully validated for accuracy using three different systems, including an Amazon EC2 instance, to control for hardware-specific differences. Prior work in parallel query evaluation has advocated right-deep and bushy trees for multi-join queries due to their greater parallelization and pipelining potential. A surprising finding is that the conventional wisdom from shared-nothing disk-based systems does not directly apply to the modern shared-everything memory hierarchy. As corroborated by our model, the performance gap between the optimal left-deep and right-deep query plan can grow to about 10X as the number of joins in the query increases.
Ontology Matching with Knowledge Rules
Venue: arXiv cs.AI 2015
Year: 2015

Ontology matching is the process of automatically determining the semantic equivalences between the concepts of two ontologies. Most ontology matching algorithms are based on two types of strategies: terminology-based strategies, which align concepts based on their names or descriptions, and structure-based strategies, which exploit concept hierarchies to find the alignment. In many domains, there is additional information about the relationships of concepts represented in various ways, such as Bayesian networks, decision trees, and association rules. We propose to use the similarities between these relationships to find more accurate alignments. We accomplish this by defining soft constraints that prefer alignments where corresponding concepts have the same local relationships encoded as knowledge rules. We use a probabilistic framework to integrate this new knowledge-based strategy with standard terminology-based and structure-based strategies. Furthermore, our method is particularly effective in identifying correspondences between complex concepts. Our method achieves substantially better F-score than the previous state-of-the-art on three ontology matching domains.
Enhancing the Security of Protocols against Actor Key Compromise Problems
Venue: arXiv cs.CR 2015
Year: 2015

Security of complex systems is an important issue in software engineering. For complex computer systems involving many actors, security protocols are often used for the communication of sensitive data. Actor key compromise (AKC) denotes a situation where the long-term secret key of an actor may be known to an adversary for some reasons. Many protocols are not secure enough for ensuring security in such a situation. In this paper, we further study this problem by looking at potential types of attacks, defining their formal properties and providing solutions to enhance the level of security. As case studies, we analyze the vulnerabilities (with respect to potential AKC attacks) of practical protocols, including PKMv2RSA and Kerberos, and provide solutions to enhance the level of security of such protocols.
A Probabilistic Approach to Knowledge Translation
Venue: arXiv cs.AI 2015
Year: 2015

In this paper, we focus on a novel knowledge reuse scenario where the knowledge in the source schema needs to be translated to a semantically heterogeneous target schema. We refer to this task as "knowledge translation" (KT). Unlike data translation and transfer learning, KT does not require any data from the source or target schema. We adopt a probabilistic approach to KT by representing the knowledge in the source schema, the mapping between the source and target schemas, and the resulting knowledge in the target schema all as probability distributions, specially using Markov random fields and Markov logic networks. Given the source knowledge and mappings, we use standard learning and inference algorithms for probabilistic graphical models to find an explicit probability distribution in the target schema that minimizes the Kullback-Leibler divergence from the implicit distribution. This gives us a compact probabilistic model that represents knowledge from the source schema as well as possible, respecting the uncertainty in both the source knowledge and the mapping. In experiments on both propositional and relational domains, we find that the knowledge obtained by KT is comparable to other approaches that require data, demonstrating that knowledge can be reused without data.
The Coloring Game on Planar Graphs with Large Girth, by a result on Sparse Cactuses
Venue: arXiv cs.DM 2015
Year: 2015

We denote by $χ$ g (G) the game chromatic number of a graph G, which is the smallest number of colors Alice needs to win the coloring game on G. We know from Montassier et al. [M. Montassier, P. Ossona de Mendez, A. Raspaud and X. Zhu, Decomposing a graph into forests, J. Graph Theory Ser. B, 102(1):38-52, 2012] and, independantly, from Wang and Zhang, [Y. Wang and Q. Zhang. Decomposing a planar graph with girth at least 8 into a forest and a matching, Discrete Maths, 311:844-849, 2011] that planar graphs with girth at least 8 have game chromatic number at most 5. One can ask if this bound of 5 can be improved for a sufficiently large girth. In this paper, we prove that it cannot. More than that, we prove that there are cactuses CT (i.e. graphs whose edges only belong to at most one cycle each) having $χ$ g (CT) = 5 despite having arbitrary large girth, and even arbitrary large distance between its cycles.
Use of the Triangular Fuzzy Numbers for Student Assessment
Venue: arXiv cs.AI 2015
Year: 2015

In an earlier work we have used the Triangular Fuzzy Numbers (TFNs)as an assessment tool of student skills.This approach led to an approximate linguistic characterization of the students' overall performance, but it was not proved to be sufficient in all cases for comparing the performance of two different student groups, since tywo TFNs are not always comparable. In the present paper we complete the above fuzzy assessment approach by presenting a defuzzification method of TFNS based on the Center of Gravity (COG) technique, which enables the required comparison. In addition we extend our results by using the Trapezoidal Fuzzy Numbers (TpFNs) too, which are a generalization of the TFNs, for student assessment and we present suitable examples illustrating our new results in practice.
Self-Modeling Based Diagnosis of Software-Defined Networks
Venue: arXiv cs.NI 2015
Year: 2015

Networks built using SDN (Software-Defined Networks) and NFV (Network Functions Virtualization) approaches are expected to face several challenges such as scalability, robustness and resiliency. In this paper, we propose a self-modeling based diagnosis to enable resilient networks in the context of SDN and NFV. We focus on solving two major problems: On the one hand, we lack today of a model or template that describes the managed elements in the context of SDN and NFV. On the other hand, the highly dynamic networks enabled by the softwarisation require the generation at runtime of a diagnosis model from which the root causes can be identified. In this paper, we propose finer granular templates that do not only model network nodes but also their sub-components for a more detailed diagnosis suitable in the SDN and NFV context. In addition, we specify and validate a self-modeling based diagnosis using Bayesian Networks. This approach differs from the state of the art in the discovery of network and service dependencies at run-time and the building of the diagnosis model of any SDN infrastructure using our templates.
Strategy Synthesis in Adversarial Patrolling Games
Venue: arXiv cs.GT 2015
Year: 2015

Patrolling is one of the central problems in operational security. Formally, a patrolling problem is specified by a set $U$ of nodes (admissible defender's positions), a set $T \subseteq U$ of vulnerable targets, an admissible defender's moves over $U$, and a function which to every target assigns the time needed to complete an intrusion at it. The goal is to design an optimal strategy for a defender who is moving from node to node and aims at detecting possible intrusions at the targets. The goal of the attacker is to maximize the probability of a successful attack. We assume that the attacker is adversarial, i.e., he knows the strategy of the defender and can observe her moves. We prove that the defender has an optimal strategy for every patrolling problem. Further, we show that for every $\varepsilon$ > 0, there exists a finite-memory $\varepsilon$-optimal strategy for the defender constructible in exponential time, and we observe that such a strategy cannot be computed in polynomial time unless P=NP. Then we focus ourselves to unrestricted defender's moves. Here, a patrolling problem is fully determined by its signature, the number of targets of each attack length. We bound the maximal probability of successfully defended attacks. Then, we introduce a decomposition method which allows to split a given patrolling problem $G$ into smaller subproblems and construct a defender's strategy for $G$ by "composing" the strategies constructed for these subproblems. Finally, for patrolling problems with $T = U$ and a well-formed signature, we give an exact classification of all sufficiently connected environments where the defender can achieve the same value as in the fully connected uniform environment. This result is useful for designing "good" environments where the defender can act optimally.
A Cross-Layer Security Analysis for Process-Aware Information Systems
Venue: arXiv cs.CR 2015
Year: 2015

Information security in Process-aware Information System (PAIS) relies on many factors, including security of business process and the underlying system and technologies. Moreover, humans can be the weakest link that creates pathway to vulnerabilities, or the worst enemy that compromises a well-defended system. Since a system is as secure as its weakest link, information security can only be achieved in PAIS if all factors are secure. In this paper, we address two research questions: how to conduct a cross-layer security analysis that couple security concerns at business process layer as well as at the technical layer; and how to include human factor into the security analysis for the identification of human-oriented vulnerabilities and threats. We propose a methodology that supports the tracking of security interdependencies between functional, technical, and human aspects which contribute to establish a holistic approach to information security in PAIS. We demonstrate the applicability with a scenario from the payment card industry.
Supervised Hierarchical Classification for Student Answer Scoring
Venue: arXiv cs.CL 2015
Year: 2015

This paper describes a hierarchical system that predicts one label at a time for automated student response analysis. For the task, we build a classification binary tree that delays more easily confused labels to later stages using hierarchical processes. In particular, the paper describes how the hierarchical classifier has been built and how the classification task has been broken down into binary subtasks. It finally discusses the motivations and fundamentals of such an approach.
JSKETCH: Sketching for Java
Venue: arXiv cs.PL 2015
Year: 2015

Sketch-based synthesis, epitomized by the SKETCH tool, lets developers synthesize software starting from a partial program, also called a sketch or template. This paper presents JSKETCH, a tool that brings sketch-based synthesis to Java. JSKETCH's input is a partial Java program that may include holes, which are unknown constants, expression generators, which range over sets of expressions, and class generators, which are partial classes. JSKETCH then translates the synthesis problem into a SKETCH problem; this translation is complex because SKETCH is not object-oriented. Finally, JSKETCH synthesizes an executable Java program by interpreting the output of SKETCH.