OpenRaiser/Intern-Atlas huggingface dataset:
Physical Layer Network Coding: A Cautionary Story with Interference and Spatial Reservation
Venue: arXiv cs.IT 2013
Year: 2013

Physical layer network coding (PLNC) has the potential to improve throughput of multi-hop networks. However, most of the works are focused on the simple, three-node model with two-way relaying, not taking into account the fact that there can be other neighboring nodes that can cause/receive interference. The way to deal with this problem in distributed wireless networks is usage of MAC-layer mechanisms that make a spatial reservation of the shared wireless medium, similar to the well-known RTS/CTS in IEEE 802.11 wireless networks. In this paper, we investigate two-way relaying in presence of interfering nodes and usage of spatial reservation mechanisms. Specifically, we introduce a reserved area in order to protect the nodes involved in two-way relaying from the interference caused by neighboring nodes. We analytically derive the end-to-end rate achieved by PLNC considering the impact of interference and reserved area. A relevant performance measure is data rate per unit area, in order to reflect the fact that any spatial reservation blocks another data exchange in the reserved area. The numerical results carry a cautionary message that the gains brought by PLNC over one-way relaying may be vanishing when the two-way relaying is considered in a broader context of a larger wireless network.
Verification for Reliable Product Lines
Venue: arXiv cs.SE 2013
Year: 2013

Many product lines are critical, and therefore reliability is a vital part of their requirements. Reliability is a probabilistic property. We therefore propose a model for feature-aware discrete-time Markov chains as a basis for verifying probabilistic properties of product lines, including reliability. We compare three verification techniques: The enumerative technique uses PRISM, a state-of-the-art symbolic probabilistic model checker, on each product. The parametric technique exploits our recent advances in parametric model checking. Finally, we propose a new bounded technique that performs a single bounded verification for the whole product line, and thus takes advantage of the common behaviours of the product line. Experimental results confirm the advantages of the last two techniques.
Minimum-Variance Importance-Sampling Bernoulli Estimator for Fast Simulation of Linear Block Codes over Binary Symmetric Channels
Venue: arXiv cs.IT 2013
Year: 2013

In this paper the choice of the Bernoulli distribution as biased distribution for importance sampling (IS) Monte-Carlo (MC) simulation of linear block codes over binary symmetric channels (BSCs) is studied. Based on the analytical derivation of the optimal IS Bernoulli distribution, with explicit calculation of the variance of the corresponding IS estimator, two novel algorithms for fast-simulation of linear block codes are proposed. For sufficiently high signal-to-noise ratios (SNRs) one of the proposed algorithm is SNR-invariant, i.e. the IS estimator does not depend on the cross-over probability of the channel. Also, the proposed algorithms are shown to be suitable for the estimation of the error-correcting capability of the code and the decoder. Finally, the effectiveness of the algorithms is confirmed through simulation results in comparison to standard Monte Carlo method.
Unfaithful Glitch Propagation in Existing Binary Circuit Models
Venue: arXiv cs.OH 2013
Year: 2013

We show that no existing continuous-time, binary value-domain model for digital circuits is able to correctly capture glitch propagation. Prominent examples of such models are based on pure delay channels (P), inertial delay channels (I), or the elaborate PID channels proposed by Bellido-Díaz et al. We accomplish our goal by considering the solvability/non-solvability border of a simple problem called Short-Pulse Filtration (SPF), which is closely related to arbitration and synchronization. On one hand, we prove that SPF is solvable in bounded time in any such model that provides channels with non-constant delay, like I and PID. This is in opposition to the impossibility of solving bounded SPF in real (physical) circuit models. On the other hand, for binary circuit models with constant-delay channels, we prove that SPF cannot be solved even in unbounded time; again in opposition to physical circuit models. Consequently, indeed none of the binary value-domain models proposed so far (and that we are aware of) faithfully captures glitch propagation of real circuits. We finally show that these modeling mismatches do not hold for the weaker eventual SPF problem.
The Maximum Entropy Relaxation Path
Venue: arXiv cs.LG 2013
Year: 2013

The relaxed maximum entropy problem is concerned with finding a probability distribution on a finite set that minimizes the relative entropy to a given prior distribution, while satisfying relaxed max-norm constraints with respect to a third observed multinomial distribution. We study the entire relaxation path for this problem in detail. We show existence and a geometric description of the relaxation path. Specifically, we show that the maximum entropy relaxation path admits a planar geometric description as an increasing, piecewise linear function in the inverse relaxation parameter. We derive fast algorithms for tracking the path. In various realistic settings, our algorithms require $O(n\log(n))$ operations for probability distributions on $n$ points, making it possible to handle large problems. Once the path has been recovered, we show that given a validation set, the family of admissible models is reduced from an infinite family to a small, discrete set. We demonstrate the merits of our approach in experiments with synthetic data and discuss its potential for the estimation of compact n-gram language models.
The probabilistic approach to limited packings in graphs
Venue: arXiv cs.DM 2013
Year: 2013

We consider (closed neighbourhood) packings and their generalization in graphs. A vertex set X in a graph G is a k-limited packing if for any vertex $v\in V(G)$, $\left|N[v] \cap X\right| \le k$, where N[v] is the closed neighbourhood of v. The k-limited packing number $L_k(G)$ of a graph G is the largest size of a k-limited packing in G. Limited packing problems can be considered as secure facility location problems in networks. In this paper, we develop a new probabilistic approach to limited packings in graphs, resulting in lower bounds for the k-limited packing number and a randomized algorithm to find k-limited packings satisfying the bounds. In particular, we prove that for any graph G of order n with maximum vertex degree $Δ$, $$L_k(G) \ge {kn \over (k+1)\sqrt[k]{\pmatrix{Δ\cr k} (Δ+1)}}.$$ The problem of finding a maximum size k-limited packing is known to be NP-complete even in split or bipartite graphs.
On Coinductive Equivalences for Higher-Order Probabilistic Functional Programs (Long Version)
Venue: arXiv cs.PL 2013
Year: 2013

We study bisimulation and context equivalence in a probabilistic $λ$-calculus. The contributions of this paper are threefold. Firstly we show a technique for proving congruence of probabilistic applicative bisimilarity. While the technique follows Howe's method, some of the technicalities are quite different, relying on non-trivial "disentangling" properties for sets of real numbers. Secondly we show that, while bisimilarity is in general strictly finer than context equivalence, coincidence between the two relations is attained on pure $λ$-terms. The resulting equality is that induced by Levy-Longo trees, generally accepted as the finest extensional equivalence on pure $λ$-terms under a lazy regime. Finally, we derive a coinductive characterisation of context equivalence on the whole probabilistic language, via an extension in which terms akin to distributions may appear in redex position. Another motivation for the extension is that its operational semantics allows us to experiment with a different congruence technique, namely that of logical bisimilarity.
Suffix Trays and Suffix Trists: Structures for Faster Text Indexing
Venue: arXiv cs.DS 2013
Year: 2013

Suffix trees and suffix arrays are two of the most widely used data structures for text indexing. Each uses linear space and can be constructed in linear time for polynomially sized alphabets. However, when it comes to answering queries with worst-case deterministic time bounds, the prior does so in $O(m\log|Σ|)$ time, where $m$ is the query size, $|Σ|$ is the alphabet size, and the latter does so in $O(m+\log n)$ time, where $n$ is the text size. If one wants to output all appearances of the query, an additive cost of $O(occ)$ time is sufficient, where $occ$ is the size of the output. We propose a novel way of combining the two into, what we call, a {\em suffix tray}. The space and construction time remain linear and the query time improves to $O(m+\log|Σ|)$ for integer alphabets from a linear range, i.e. $Σ\subset \{1,\cdots, cn\}$, for an arbitrary constant $c$. The construction and query are deterministic. Here also an additive $O(occ)$ time is sufficient if one desires to output all appearances of the query. We also consider the online version of indexing, where the text arrives online, one character at a time, and indexing queries are answered in tandem. In this variant we create a cross between a suffix tree and a suffix list (a dynamic variant of suffix array) to be called a {\em suffix trist}; it supports queries in $O(m+\log|Σ|)$ time. The suffix trist also uses linear space. Furthermore, if there exists an online construction for a linear-space suffix tree such that the cost of adding a character is worst-case deterministic $f(n,|Σ|)$ ($n$ is the size of the current text), then one can further update the suffix trist in $O(f(n,|Σ|)+\log |Σ|)$ time. The best currently known worst-case deterministic bound for $f(n,|Σ|)$ is $O(\log n)$ time.
Automatic ontology generation for data mining using fca and clustering
Venue: arXiv cs.DB 2013
Year: 2013

Motivated by the increased need for formalized representations of the domain of Data Mining, the success of using Formal Concept Analysis (FCA) and Ontology in several Computer Science fields, we present in this paper a new approach for automatic generation of Fuzzy Ontology of Data Mining (FODM), through the fusion of conceptual clustering, fuzzy logic, and FCA. In our approach, we propose to generate ontology taking in consideration another degree of granularity into the process of generation. Indeed, we suggest to define an ontology between classes resulting from a preliminary classification on the data. We prove that this approach optimize the definition of the ontology, offered a better interpretation of the data and optimized both the space memory and the execution time for exploiting this data.
Wave-absorbing vehicular platoon controller
Venue: arXiv cs.SY 2013
Year: 2013

The paper tailors the so-called wave-based control popular in the field of flexible mechanical structures to the field of distributed control of vehicular platoons. The proposed solution augments the symmetric bidirectional control algorithm with a wave-absorbing controller implemented on the leader, and/or on the rear-end vehicle. The wave-absorbing controller actively absorbs an incoming wave of positional changes in the platoon and thus prevents oscillations of inter-vehicle distances. The proposed controller significantly improves the performance of platoon manoeuvrers such as acceleration/deceleration or changing the distances between vehicles without making the platoon string unstable. Numerical simulations show that the wave-absorbing controller performs efficiently even for platoons with a large number of vehicles, for which other platooning algorithms are inefficient or require wireless communication between vehicles.
Querying Knowledge Graphs by Example Entity Tuples
Venue: arXiv cs.DB 2013
Year: 2013

We witness an unprecedented proliferation of knowledge graphs that record millions of entities and their relationships. While knowledge graphs are structure-flexible and content rich, they are difficult to use. The challenge lies in the gap between their overwhelming complexity and the limited database knowledge of non-professional users. If writing structured queries over simple tables is difficult, complex graphs are only harder to query. As an initial step toward improving the usability of knowledge graphs, we propose to query such data by example entity tuples, without requiring users to form complex graph queries. Our system, GQBE (Graph Query By Example), automatically derives a weighted hidden maximal query graph based on input query tuples, to capture a user's query intent. It efficiently finds and ranks the top approximate answer tuples. For fast query processing, GQBE only partially evaluates query graphs. We conducted experiments and user studies on the large Freebase and DBpedia datasets and observed appealing accuracy and efficiency. Our system provides a complementary approach to the existing keyword-based methods, facilitating user-friendly graph querying. To the best of our knowledge, there was no such proposal in the past in the context of graphs.
Betweenness Centrality -- Incremental and Faster
Venue: arXiv cs.DS 2013
Year: 2013

We consider the incremental computation of the betweenness centrality of all vertices in a large complex network modeled as a graph G = (V, E), directed or undirected, with positive real edge-weights. The current widely used algorithm to compute the betweenness centrality of all vertices in G is the Brandes algorithm that runs in O(mn + n^2 log n) time, where n = |V| and m = |E|. We present an incremental algorithm that updates the betweenness centrality score of all vertices in G when a new edge is added to G, or the weight of an existing edge is reduced. Our incremental algorithm runs in O(m' n + n^2) time, where m' is the size of a certain subset of E*, the set of edges in G that lie on a shortest path. We achieve the same bound for the more general incremental update of a vertex v, where the edge update can be performed on any subset of edges incident to v. Our incremental algorithm is the first algorithm that is asymptotically faster on sparse graphs than recomputing with the Brandes algorithm. Our algorithm is also likely to be much faster than the Brandes algorithm on dense graphs since m*, the size of E*, is often close to linear in n. Our incremental algorithm is very simple and the only data structures it uses are arrays, lists, and stack. We give an efficient cache-oblivious implementation that incurs O(scan(n^2) + n sort(m')) cache misses, where scan and sort are well-known measures for efficient caching. We also give a static algorithm for computing betweenness centrality of all vertices that runs in time O(m* n + n^2 log n), which is faster than the Brandes algorithm on any graph with n log n = o(m) and m* = o(m).
Some New Results on Equivalency of Collusion-Secure Properties for Reed-Solomon Codes
Venue: arXiv cs.IT 2013
Year: 2013

A. Silverberg (IEEE Trans. Inform. Theory 49, 2003) proposed a question on the equivalence of identifiable parent property and traceability property for Reed-Solomon code family. Earlier studies on Silverberg's problem motivate us to think of the stronger version of the question on equivalence of separation and traceability properties. Both, however, still remain open. In this article, we integrate all the previous works on this problem with an algebraic way, and present some new results. It is notable that the concept of subspace subcode of Reed-Solomon code, which was introduced in error-correcting code theory, provides an interesting prospect for our topic.
An Empirical Evaluation of Sequence-Tagging Trainers
Venue: arXiv cs.LG 2013
Year: 2013

The task of assigning label sequences to a set of observed sequences is common in computational linguistics. Several models for sequence labeling have been proposed over the last few years. Here, we focus on discriminative models for sequence labeling. Many batch and online (updating model parameters after visiting each example) learning algorithms have been proposed in the literature. On large datasets, online algorithms are preferred as batch learning methods are slow. These online algorithms were designed to solve either a primal or a dual problem. However, there has been no systematic comparison of these algorithms in terms of their speed, generalization performance (accuracy/likelihood) and their ability to achieve steady state generalization performance fast. With this aim, we compare different algorithms and make recommendations, useful for a practitioner. We conclude that the selection of an algorithm for sequence labeling depends on the evaluation criterion used and its implementation simplicity.
Covert Ephemeral Communication in Named Data Networking
Venue: arXiv cs.CR 2013
Year: 2013

In the last decade, there has been a growing realization that the current Internet Protocol is reaching the limits of its senescence. This has prompted several research efforts that aim to design potential next-generation Internet architectures. Named Data Networking (NDN), an instantiation of the content-centric approach to networking, is one such effort. In contrast with IP, NDN routers maintain a significant amount of user-driven state. In this paper we investigate how to use this state for covert ephemeral communication (CEC). CEC allows two or more parties to covertly exchange ephemeral messages, i.e., messages that become unavailable after a certain amount of time. Our techniques rely only on network-layer, rather than application-layer, services. This makes our protocols robust, and communication difficult to uncover. We show that users can build high-bandwidth CECs exploiting features unique to NDN: in-network caches, routers' forwarding state and name matching rules. We assess feasibility and performance of proposed cover channels using a local setup and the official NDN testbed.
Deployment of Stream Control Transmission Protocol (SCTP) to Maintain the Applications of Data Centers
Venue: arXiv cs.NI 2013
Year: 2013

With developments of real-time applications into data centers, the need for alternatives of the standard TCP protocol has been prime demand in several applications of data centers. The several alternatives of TCP protocol has been proposed but SCTP has edge due to its several well-built characteristics that make it capable to work efficiently. In this paper, we examine the features of SCTP into data centers like Multi-streaming and Multi-homing over the features of TCP protocol. In this paper, our objective is to introduce internal problems of data centers. Robust transport protocol reduces the problems with some extend. Focusing the problems of data centers, we also examine weakness of highly deployed standard TCP, and evaluate the performance of SCTP in context of faster communication for data centers. We also discover some weaknesses and shortcomings of SCTP into data centers and try to propose some ways to avoid them by maintaining SCTP native features. To validate strength and weakness of TCP and SCTP, we use ns2 for simulation in context of data center. On basis of findings, we highlight major strength of SCTP. At the end, we Implemen
Deep neural networks for single channel source separation
Venue: arXiv cs.NE 2013
Year: 2013

In this paper, a novel approach for single channel source separation (SCSS) using a deep neural network (DNN) architecture is introduced. Unlike previous studies in which DNN and other classifiers were used for classifying time-frequency bins to obtain hard masks for each source, we use the DNN to classify estimated source spectra to check for their validity during separation. In the training stage, the training data for the source signals are used to train a DNN. In the separation stage, the trained DNN is utilized to aid in estimation of each source in the mixed signal. Single channel source separation problem is formulated as an energy minimization problem where each source spectra estimate is encouraged to fit the trained DNN model and the mixed signal spectrum is encouraged to be written as a weighted sum of the estimated source spectra. The proposed approach works regardless of the energy scale differences between the source signals in the training and separation stages. Nonnegative matrix factorization (NMF) is used to initialize the DNN estimate for each source. The experimental results show that using DNN initialized by NMF for source separation improves the quality of the separated signal compared with using NMF for source separation.
Visualizing and Understanding Convolutional Networks
Venue: arXiv cs.CV 2013
Year: 2013

Large Convolutional Network models have recently demonstrated impressive classification performance on the ImageNet benchmark. However there is no clear understanding of why they perform so well, or how they might be improved. In this paper we address both issues. We introduce a novel visualization technique that gives insight into the function of intermediate feature layers and the operation of the classifier. We also perform an ablation study to discover the performance contribution from different model layers. This enables us to find model architectures that outperform Krizhevsky \etal on the ImageNet classification benchmark. We show our ImageNet model generalizes well to other datasets: when the softmax classifier is retrained, it convincingly beats the current state-of-the-art results on Caltech-101 and Caltech-256 datasets.
Asynchronous Distributed Downlink Beamforming and Power Control in Multi-cell Networks
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we consider a multi-cell network where every base station (BS) serves multiple users with an antenna array. Each user is associated with only one BS and has a single antenna. Assume that only long-term channel state information (CSI) is available in the system. The objective is to minimize the network downlink transmission power needed to meet the users' signal-to-interference-plus-noise ratio (SINR) requirements. For this objective, we propose an asynchronous distributed beamforming and power control algorithm which provides the same optimal solution as given by centralized algorithms. To design the algorithm, the power minimization problem is formulated mathematically as a non-convex problem. For distributed implementation, the non-convex problem is cast into the dual decomposition framework. Resorting to the theory about matrix pencil, a novel asynchronous iterative method is proposed for solving the dual of the non-convex problem. The methods for beamforming and power control are obtained by investigating the primal problem. At last, simulation results are provided to demonstrate the convergence and performance of the algorithm.
Contribution of Information and Communication Technology (ICT) in Country'S H-Index
Venue: arXiv cs.DL 2013
Year: 2013

The aim of this study is to examine the effect of Information and Communication Technology (ICT) development on country's scientific ranking as measured by H-index. Moreover, this study applies ICT development sub-indices including ICT Use, ICT Access and ICT skill to find the distinct effect of these sub-indices on country's H-index. To this purpose, required data for the panel of 14 Middle East countries over the period 1995 to 2009 is collected. Findings of the current study show that ICT development increases the H-index of the sample countries. The results also indicate that ICT Use and ICT Skill sub-indices positively contribute to higher H-index but the effect of ICT access on country's H-index is not clear.