OpenRaiser/Intern-Atlas huggingface dataset:
Towards a Networks-of-Networks Framework for Cyber Security
Venue: arXiv cs.CR 2013
Year: 2013

Networks-of-networks (NoN) is a graph-theoretic model of interdependent networks that have distinct dynamics at each network (layer). By adding special edges to represent relationships between nodes in different layers, NoN provides a unified mechanism to study interdependent systems intertwined in a complex relationship. While NoN based models have been proposed for cyber-physical systems, in this position paper we build towards a three-layered NoN model for an enterprise cyber system. Each layer captures a different facet of a cyber system. We present in-depth discussion for four major graph- theoretic applications to demonstrate how the three-layered NoN model can be leveraged for continuous system monitoring and mission assurance.
Approximating Semi-Matchings in Streaming and in Two-Party Communication
Venue: arXiv cs.DS 2013
Year: 2013

We study the communication complexity and streaming complexity of approximating unweighted semi-matchings. A semi-matching in a bipartite graph G = (A, B, E), with n = |A|, is a subset of edges S that matches all A vertices to B vertices with the goal usually being to do this as fairly as possible. While the term 'semi-matching' was coined in 2003 by Harvey et al. [WADS 2003], the problem had already previously been studied in the scheduling literature under different names. We present a deterministic one-pass streaming algorithm that for any 0 <= ε<= 1 uses space O(n^{1+ε}) and computes an O(n^{(1-ε)/2})-approximation to the semi-matching problem. Furthermore, with O(log n) passes it is possible to compute an O(log n)-approximation with space O(n). In the one-way two-party communication setting, we show that for every ε> 0, deterministic communication protocols for computing an O(n^{1/((1+ε)c + 1)})-approximation require a message of size more than cn bits. We present two deterministic protocols communicating n and 2n edges that compute an O(sqrt(n)) and an O(n^{1/3})-approximation respectively. Finally, we improve on results of Harvey et al. [Journal of Algorithms 2006] and prove new links between semi-matchings and matchings. While it was known that an optimal semi-matching contains a maximum matching, we show that there is a hierarchical decomposition of an optimal semi-matching into maximum matchings. A similar result holds for semi-matchings that do not admit length-two degree-minimizing paths.
A bibliometric index based on the complete list of cited publications
Venue: arXiv cs.DL 2013
Year: 2013

We propose a new index, the $j$-index, which is defined for an author as the sum of the square roots of the numbers of citations to each of the author's publications. The idea behind the $j$-index it to remedy a drawback of the $h$-index $-$ that the $h$-index does not take into account the full citation record of a researcher. The square root function is motivated by our desire to avoid the possible bias that may occur with a simple sum when an author has several very highly cited papers. We compare the $j$-index to the $h$-index, the $g$-index and the total citation count for three subject areas using several association measures. Our results indicate that that the association between the $j$-index and the other indices varies according to the subject area. One explanation of this variation may be due to the proportion of citations to publications of the researcher that are in the $h$-core. The $j$-index is {\em not} an $h$-index variant, and as such is intended to complement rather than necessarily replace the $h$-index and other bibliometric indicators, thus providing a more complete picture of a researcher's achievements.
Enhanced CBF Packet Filtering Method to Detect DDoS Attack in Cloud Computing Environment
Venue: arXiv cs.CR 2013
Year: 2013

Tremendous and extraordinary growths in the field of internet, intranet, extranet and its users have developed an innovative era of great global competition and contention. Denial of service attack by multiple nodes is accomplished of disturbing the services of rival servers. The attack can be for multiple reasons. So it is a major threat for cloud environment. Due to low effectiveness and large storage conventional defending approaches cannot be easily applied in cloud security. The effects of various attacks can decrease the influence of a cloud. So, in view of this challenge task, this paper aims at enhancing a proposed method for cloud security. We propose a modification to the confidence Based Filtering method (CBF) which is investigated for cloud computing environment based on correlation pattern to mitigate DDoS attacks on Cloud. The modification introduces nominal additional bandwidth and tries to increase the processing speed of the victim initiated server.
A Convex Approach for Image Hallucination
Venue: arXiv cs.CV 2013
Year: 2013

In this paper we propose a global convex approach for image hallucination. Altering the idea of classical multi image super resolution (SU) systems to single image SU, we incorporate aligned images to hallucinate the output. Our work is based on the paper of Tappen et al. where they use a non-convex model for image hallucination. In comparison we formulate a convex primal optimization problem and derive a fast converging primal-dual algorithm with a global optimal solution. We use a database with face images to incorporate high-frequency details to the high-resolution output. We show that we can achieve state-of-the-art results by using a convex approach.
Irreflexive and Hierarchical Relations as Translations
Venue: arXiv cs.LG 2013
Year: 2013

We consider the problem of embedding entities and relations of knowledge bases in low-dimensional vector spaces. Unlike most existing approaches, which are primarily efficient for modeling equivalence relations, our approach is designed to explicitly model irreflexive relations, such as hierarchies, by interpreting them as translations operating on the low-dimensional embeddings of the entities. Preliminary experiments show that, despite its simplicity and a smaller number of parameters than previous approaches, our approach achieves state-of-the-art performance according to standard evaluation protocols on data from WordNet and Freebase.
Traitement approximatif des requêtes flexibles avec groupement d'attributs et jointure
Venue: arXiv cs.DB 2013
Year: 2013

This paper addresses the problem of approximate processing for flexible queries in the form SELECT-FROM-WHERE-GROUP BY with join condition. It offers a flexible framework for online aggregation while promoting response time at the expense of result accuracy.
TimeML-strict: clarifying temporal annotation
Venue: arXiv cs.CL 2013
Year: 2013

TimeML is an XML-based schema for annotating temporal information over discourse. The standard has been used to annotate a variety of resources and is followed by a number of tools, the creation of which constitute hundreds of thousands of man-hours of research work. However, the current state of resources is such that many are not valid, or do not produce valid output, or contain ambiguous or custom additions and removals. Difficulties arising from these variances were highlighted in the TempEval-3 exercise, which included its own extra stipulations over conventional TimeML as a response. To unify the state of current resources, and to make progress toward easy adoption of its current incarnation ISO-TimeML, this paper introduces TimeML-strict: a valid, unambiguous, and easy-to-process subset of TimeML. We also introduce three resources -- a schema for TimeML-strict; a validator tool for TimeML-strict, so that one may ensure documents are in the correct form; and a repair tool that corrects common invalidating errors and adds disambiguating markup in order to convert documents from the laxer TimeML standard to TimeML-strict.
Self Configurable Re-link Establishment using Continuous Neighbor Discovery in Asynchronous Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

A Sensor network generally has a large number of sensor nodes that are deployed at some audited site. In most sensor networks the nodes are static. Nevertheless, node connectivity is subject to changes because of disruptions in wireless communication, transmission power changes, or loss of synchronization between neighbouring nodes, so there is a need to maintain synchronization between the neighbouring nodes in order to have efficient communication. Hence even after a sensor is aware of its immediate neighbours, it must continuously maintain its view a process we call continuous neighbour discovery. In this proposed work we are maintaining synchronization between neighbouring nodes so that the sensor network will be always active.
Coverage and adoption of altmetrics sources in the bibliometric community
Venue: arXiv cs.DL 2013
Year: 2013

Altmetrics, indices based on social media platforms and tools, have recently emerged as alternative means of measuring scholarly impact. Such indices assume that scholars in fact populate online social environments, and interact with scholarly products there. We tested this assumption by examining the use and coverage of social media environments amongst a sample of bibliometricians. As expected, coverage varied: 82% of articles published by sampled bibliometricians were included in Mendeley libraries, while only 28% were included in CiteULike. Mendeley bookmarking was moderately correlated (.45) with Scopus citation. Over half of respondents asserted that social media tools were affecting their professional lives, although uptake of online tools varied widely. 68% of those surveyed had LinkedIn accounts, while Academia.edu, Mendeley, and ResearchGate each claimed a fifth of respondents. Nearly half of those responding had Twitter accounts, which they used both personally and professionally. Surveyed bibliometricians had mixed opinions on altmetrics' potential; 72% valued download counts, while a third saw potential in tracking articles' influence in blogs, Wikipedia, reference managers, and social media. Altogether, these findings suggest that some online tools are seeing substantial use by bibliometricians, and that they present a potentially valuable source of impact data.
Adaptive Software Radio Steganography
Venue: arXiv cs.MM 2013
Year: 2013

This paper presents an adaptable steganography (information hiding) method for digital radio communication. Many radio steganography methods exist, but most are defined at higher levels of the protocol stack and are thus protocol dependent. In contrast, this method is defined at the physical layer, which makes it widely applicable regardless of the protocols used at higher layers. This approach is also adaptive; the covertness of the hidden channel is simple to control via a single continuous parameter either manually or automatically. Several variations are introduced, each with performance evaluated by simulation. Results show this to be a feasible method with a reasonable trade-off between performance and covertness.
NP-Hardness of Speed Scaling with a Sleep State
Venue: arXiv cs.DS 2013
Year: 2013

A modern processor can dynamically set it's speed while it's active, and can make a transition to sleep state when required. When the processor is operating at a speed $s$, the energy consumed per unit time is given by a convex power function $P(s)$ having the property that $P(0) > 0$ and $P"(s) > 0$ for all values of $s$. Moreover, $C > 0$ units of energy is required to make a transition from the sleep state to the active state. The jobs are specified by their arrival time, deadline and the processing volume. We consider a scheduling problem, called speed scaling with sleep state, where each job has to be scheduled within their arrival time and deadline, and the goal is to minimize the total energy consumption required to process these jobs. Albers et. al. proved the NP-hardness of this problem by reducing an instance of an NP-hard partition problem to an instance of this scheduling problem. The instance of this scheduling problem consists of the arrival time, the deadline and the processing volume for each of the jobs, in addition to $P$ and $C$. Since $P$ and $C$ depend on the instance of the partition problem, this proof of the NP-hardness of the speed scaling with sleep state problem doesn't remain valid when $P$ and $C$ are fixed. In this paper, we prove that the speed scaling with sleep state problem remains NP-hard for any fixed positive number $C$ and convex $P$ satisfying $P(0) > 0$ and $P"(s) > 0$ for all values of $s$.
A Static Analysis Framework for Livelock Freedom in CSP
Venue: arXiv cs.LO 2013
Year: 2013

In a process algebra with hiding and recursion it is possible to create processes which compute internally without ever communicating with their environment. Such processes are said to diverge or livelock. In this paper we show how it is possible to conservatively classify processes as livelock-free through a static analysis of their syntax. In particular, we present a collection of rules, based on the inductive structure of terms, which guarantee livelock-freedom of the denoted process. This gives rise to an algorithm which conservatively flags processes that can potentially livelock. We illustrate our approach by applying both BDD-based and SAT-based implementations of our algorithm to a range of benchmarks, and show that our technique in general substantially outperforms the model checker FDR whilst exhibiting a low rate of inconclusive results.
Deterministic Initialization of the K-Means Algorithm Using Hierarchical Clustering
Venue: arXiv cs.LG 2013
Year: 2013

K-means is undoubtedly the most widely used partitional clustering algorithm. Unfortunately, due to its gradient descent nature, this algorithm is highly sensitive to the initial placement of the cluster centers. Numerous initialization methods have been proposed to address this problem. Many of these methods, however, have superlinear complexity in the number of data points, making them impractical for large data sets. On the other hand, linear methods are often random and/or order-sensitive, which renders their results unrepeatable. Recently, Su and Dy proposed two highly successful hierarchical initialization methods named Var-Part and PCA-Part that are not only linear, but also deterministic (non-random) and order-invariant. In this paper, we propose a discriminant analysis based approach that addresses a common deficiency of these two methods. Experiments on a large and diverse collection of data sets from the UCI Machine Learning Repository demonstrate that Var-Part and PCA-Part are highly competitive with one of the best random initialization methods to date, i.e., k-means++, and that the proposed approach significantly improves the performance of both hierarchical methods.
Design of Non-Binary Quasi-Cyclic LDPC Codes by ACE Optimization
Venue: arXiv cs.IT 2013
Year: 2013

An algorithm for constructing Tanner graphs of non-binary irregular quasi-cyclic LDPC codes is introduced. It employs a new method for selection of edge labels allowing control over the code's non-binary ACE spectrum and resulting in low error-floor. The efficiency of the algorithm is demonstrated by generating good codes of short to moderate length over small fields, outperforming codes generated by the known methods.
Measuring Cultural Relativity of Emotional Valence and Arousal using Semantic Clustering and Twitter
Venue: arXiv cs.CL 2013
Year: 2013

Researchers since at least Darwin have debated whether and to what extent emotions are universal or culture-dependent. However, previous studies have primarily focused on facial expressions and on a limited set of emotions. Given that emotions have a substantial impact on human lives, evidence for cultural emotional relativity might be derived by applying distributional semantics techniques to a text corpus of self-reported behaviour. Here, we explore this idea by measuring the valence and arousal of the twelve most popular emotion keywords expressed on the micro-blogging site Twitter. We do this in three geographical regions: Europe, Asia and North America. We demonstrate that in our sample, the valence and arousal levels of the same emotion keywords differ significantly with respect to these geographical regions --- Europeans are, or at least present themselves as more positive and aroused, North Americans are more negative and Asians appear to be more positive but less aroused when compared to global valence and arousal levels of the same emotion keywords. Our work is the first in kind to programatically map large text corpora to a dimensional model of affect.
Quantum Circuits for GCD Computation with $O(n \log n)$ Depth and O(n) Ancillae
Venue: arXiv cs.ET 2013
Year: 2013

GCD computations and variants of the Euclidean algorithm enjoy broad uses in both classical and quantum algorithms. In this paper, we propose quantum circuits for GCD computation with $O(n \log n)$ depth with O(n) ancillae. Prior circuit construction needs $O(n^2)$ running time with O(n) ancillae. The proposed construction is based on the binary GCD algorithm and it benefits from log-depth circuits for 1-bit shift, comparison/subtraction, and managing ancillae. The worst-case gate count remains $O(n^2)$, as in traditional circuits.
Approximating {0,1,2}-Survivable Networks with Minimum Number of Steiner Points
Venue: arXiv cs.DS 2013
Year: 2013

We consider low connectivity variants of the Survivable Network with Minimum Number of Steiner Points (SN-MSP) problem: given a finite set $R$ of terminals in a metric space (M,d), a subset $B \subseteq R$ of "unstable" terminals, and connectivity requirements {r_{uv}: u,v \in R}, find a minimum size set $S \subseteq M$ of additional points such that the unit-disc graph of $R \cup S$ contains $r_{uv}$ pairwise internally edge-disjoint and $(B \cup S)$-disjoint $uv$-paths for all $u,v \in R$. The case when $r_{uv}=1$ for all $u,v \in R$ is the {\sf Steiner Tree with Minimum Number of Steiner Points} (ST-MSP) problem, and the case $r_{uv} \in \{0,1\}$ is the {\sf Steiner Forest with Minimum Number of Steiner Points} (SF-MSP) problem. Let $Δ$ be the maximum number of points in a unit ball such that the distance between any two of them is larger than 1. It is known that $Δ=5$ in $\mathbb{R}^2$ The previous known approximation ratio for {\sf ST-MSP} was $\lfloor (Δ+1)/2 \rfloor+1+ε$ in an arbitrary normed space \cite{NY}, and $2.5+ε$ in the Euclidean space $\mathbb{R}^2$ \cite{cheng2008relay}. Our approximation ratio for ST-MSP is $1+\ln(Δ-1)+ε$ in an arbitrary normed space, which in $\mathbb{R}^2$ reduces to $1+\ln 4+ε< 2.3863 +ε$. For SN-MSP with $r_{uv} \in \{0,1,2\}$, we give a simple $Δ$-approximation algorithm. In particular, for SF-MSP, this improves the previous ratio $2Δ$.
Cylindrical Algebraic Decompositions for Boolean Combinations
Venue: arXiv cs.SC 2013
Year: 2013

This article makes the key observation that when using cylindrical algebraic decomposition (CAD) to solve a problem with respect to a set of polynomials, it is not always the signs of those polynomials that are of paramount importance but rather the truth values of certain quantifier free formulae involving them. This motivates our definition of a Truth Table Invariant CAD (TTICAD). We generalise the theory of equational constraints to design an algorithm which will efficiently construct a TTICAD for a wide class of problems, producing stronger results than when using equational constraints alone. The algorithm is implemented fully in Maple and we present promising results from experimentation.
Combining Binary Search Trees
Venue: arXiv cs.DS 2013
Year: 2013

We present a general transformation for combining a constant number of binary search tree data structures (BSTs) into a single BST whose running time is within a constant factor of the minimum of any "well-behaved" bound on the running time of the given BSTs, for any online access sequence. (A BST has a well behaved bound with $f(n)$ overhead if it spends at most \bigoh{f(n)} time per access and its bound satisfies a weak sense of closure under subsequences.) In particular, we obtain a BST data structure that is \bigoh{\log\log n} competitive, satisfies the working set bound (and thus satisfies the static finger bound and the static optimality bound), satisfies the dynamic finger bound, satisfies the unified bound with an additive \bigoh{\log\log n} factor, and performs each access in worst-case \bigoh{\log n} time.
A Nonmonotone Analysis with the Primal-Dual Approach: online routing of virtual circuits with unknown durations
Venue: arXiv cs.DS 2013
Year: 2013

We address the question of whether the primal-dual approach for the design and analysis of online algorithms can be applied to nonmonotone problems. We provide a positive answer by presenting a primal-dual analysis to the online algorithm of Awerbuch et al.[AAPW01] for routing virtual circuits with unknown durations.
The Beachcombers' Problem: Walking and Searching with Mobile Robots
Venue: arXiv cs.DS 2013
Year: 2013

We introduce and study a new problem concerning the exploration of a geometric domain by mobile robots. Consider a line segment $[0,I]$ and a set of $n$ mobile robots $r_1,r_2,..., r_n$ placed at one of its endpoints. Each robot has a {\em searching speed} $s_i$ and a {\em walking speed} $w_i$, where $s_i <w_i$. We assume that each robot is aware of the number of robots of the collection and their corresponding speeds. At each time moment a robot $r_i$ either walks along a portion of the segment not exceeding its walking speed $w_i$ or searches a portion of the segment with the speed not exceeding $s_i$. A search of segment $[0,I]$ is completed at the time when each of its points have been searched by at least one of the $n$ robots. We want to develop {\em mobility schedules} (algorithms) for the robots which complete the search of the segment as fast as possible. More exactly we want to maximize the {\em speed} of the mobility schedule (equal to the ratio of the segment length versus the time of the completion of the schedule). We analyze first the offline scenario when the robots know the length of the segment that is to be searched. We give an algorithm producing a mobility schedule for arbitrary walking and searching speeds and prove its optimality. Then we propose an online algorithm, when the robots do not know in advance the actual length of the segment to be searched. The speed $S$ of such algorithm is defined as $S = \inf_{I_L} S(I_L)$ where $S(I_L)$ denotes the speed of searching of segment $I_L=[0,L]$. We prove that the proposed online algorithm is 2-competitive. The competitive ratio is shown to be better in the case when the robots' walking speeds are all the same.