OpenRaiser/Intern-Atlas huggingface dataset:
An adaptive quasi harmonic broadcasting scheme with optimal bandwidth requirement
Venue: arXiv cs.MM 2014
Year: 2014

The aim of Harmonic Broadcasting protocol is to reduce the bandwidth usage in video-on-demand service where a video is divided into some equal sized segments and every segment is repeatedly transmitted over a number of channels that follows harmonic series for channel bandwidth assignment. As the bandwidth of channels differs from each other and users can join at any time to these multicast channels, they may experience a synchronization problem between download and playback. To deal with this issue, some schemes have been proposed, however, at the cost of additional or wastage of bandwidth or sudden extreme bandwidth requirement. In this paper we present an adaptive quasi harmonic broadcasting scheme (AQHB) which delivers all data segment on time that is the download and playback synchronization problem is eliminated while keeping the bandwidth consumption as same as traditional harmonic broadcasting scheme without cost of any additional or wastage of bandwidth. It also ensures the video server not to increase the channel bandwidth suddenly that is, also eliminates the sudden buffer requirement at the client side. We present several analytical results to exhibit the efficiency of our proposed broadcasting scheme over the existing ones.
Fuzzy Categories
Venue: arXiv cs.LO 2014
Year: 2014

Since categories are graphs with additional "structure", one should start from fuzzy graphs in order to define a theory of fuzzy categories. Thus is makes sense to introduce categories whose morphisms are associated with a plausibility degree that determines to what extend it is possible to "go" from one object to another one. These categories are called {\em fuzzy categories}. Of course, the basic properties of these categories are similar but not identical to their ordinary counterparts. Thus, it is necessary to introduce notion like fuzzy commutative diagrams, fuzzy initial and fuzzy terminal objects, etc.
Ghost-in-the-Wireless: Energy Depletion Attack on ZigBee
Venue: arXiv cs.CR 2014
Year: 2014

ZigBee has been recently drawing a lot of attention as a promising solution for ubiquitous computing. The ZigBee devices are normally resource-limited, making the network susceptible to a variety of security threats. This paper presents a severe attack on ZigBee networks termed as ghost, which leverages the underlying vulnerabilities of the IEEE 802.15.4 security suites to deplete the energy of the devices. We manifest that the impact of ghost is severe as it can reduce the lifetime of devices from years to days and facilitate a variety of threats including denial of service and replay attacks. We highlight that merely deploying a standard suite of advanced security techniques does not necessarily guarantee improved security, but instead might be leveraged by adversaries to cause severe disruption in the network. We propose several recommendations on how to localize and withstand the ghost and other related attacks in ZigBee networks. Extensive simulations are provided to show the impact of the ghost and the performance of the proposed recommendations. Moreover, physical experiments also have been conducted and the observations confirm the severity of the impact by the ghost attack. We believe that the presented work will aid the researchers to improve the security of ZigBee further.
KBLAS: An Optimized Library for Dense Matrix-Vector Multiplication on GPU Accelerators
Venue: arXiv cs.MS 2014
Year: 2014

KBLAS is a new open source high performance library that provides optimized kernels for a subset of Level 2 BLAS functionalities on CUDA-enabled GPUs. Since performance of dense matrix-vector multiplication is hindered by the overhead of memory accesses, a double-buffering optimization technique is employed to overlap data motion with computation. After identifying a proper set of tuning parameters, KBLAS is able to efficiently run on various GPU architectures across different generations, avoiding the time-consuming step of code rewriting, while still being compliant with the standard BLAS API. Another advanced optimization technique allows to ensure coalesced memory access when dealing with submatrices, especially in the context of high level dense linear algebra algorithms. All four precisions KBLAS kernels have been leveraged to multi-GPUs environment, which requires the introduction of new APIs to ease users' experiences on these challenging systems. The KBLAS performance outperforms existing state-of-the-art implementations on all matrix sizes, achieves asymptotically up to 50% and 60% speedup on single GPU and multi-GPUs systems, respectively, and validates our performance model. A subset of KBLAS high performance kernels has been integrated into NVIDIA's standard BLAS implementation (cuBLAS) for larger dissemination, starting version 6.0.
A Formal Approach to Distributed System Tests Design
Venue: arXiv cs.SE 2014
Year: 2014

Deployment of distributed systems sets high requirements for procedures and tools for the complex testing of these systems. This work introduces a formal four-layered model for test generation mission on the basis of the component-based approach and the concept of layered networks. Based on this model, we describe the test generation strategy that covers every interaction from the end-user requirements on all coexisting architectural layers, and checks the internal consistency of the system technical specifications with respect to the end-user requirements. The next step introduces the Prolog-based approach to representing this model and the requirements-coverage strategy
Systems for Near Real-Time Analysis of Large-Scale Dynamic Graphs
Venue: arXiv cs.DC 2014
Year: 2014

Graphs are widespread data structures used to model a wide variety of problems. The sheer amount of data to be processed has prompted the creation of a myriad of systems that help us cope with massive scale graphs. The pressure to deliver fast responses to queries on the graph is higher than ever before, as it is demanded by many applications (e.g. online recommendations, auctions, terrorism protection, etc.). In addition, graphs change continuously (so do the real world entities that typically represent). Systems must be ready for both: near real-time and dynamic massive graphs. We survey systems taking their scalability, real-time potential and capability to support dynamic changes to the graph as driving guidelines. The main techniques and limitations are distilled and categorised. The algorithms run on top of graph systems are not ready for prime time dynamism either. Therefore,a short overview on dynamic graph algorithms has also been included.
Energy Management and Cross Layer Optimization for Wireless Sensor Network Powered by Heterogeneous Energy Sources
Venue: arXiv cs.NI 2014
Year: 2014

Recently, utilizing renewable energy for wireless system has attracted extensive attention. However, due to the instable energy supply and the limited battery capacity, renewable energy cannot guarantee to provide the perpetual operation for wireless sensor networks (WSN). The coexistence of renewable energy and electricity grid is expected as a promising energy supply manner to remain function for a potentially infinite lifetime. In this paper, we propose a new system model suitable for WSN, taking into account multiple energy consumptions due to sensing, transmission and reception, heterogeneous energy supplies from renewable energy, electricity grid and mixed energy, and multidimension stochastic natures due to energy harvesting profile, electricity price and channel condition. A discrete-time stochastic cross-layer optimization problem is formulated to achieve the optimal trade-off between the time-average rate utility and electricity cost subject to the data and energy queuing stability constraints. The Lyapunov drift-plus-penalty with perturbation technique and block coordinate descent method is applied to obtain a fully distributed and low-complexity cross-layer algorithm only requiring knowledge of the instantaneous system state. The explicit trade-off between the optimization objective and queue backlog is theoretically proven. Finally, the extensive simulations verify the theoretic claims.
Squares of $3$-sun-free split graphs
Venue: arXiv cs.CC 2014
Year: 2014

The square of a graph $G$, denoted by $G^2$, is obtained from $G$ by putting an edge between two distinct vertices whenever their distance is two. Then $G$ is called a square root of $G^2$. Deciding whether a given graph has a square root is known to be NP-complete, even if the root is required to be a split graph, that is, a graph in which the vertex set can be partitioned into a stable set and a clique. We give a wide range of polynomial time solvable cases for the problem of recognizing if a given graph is the square of some special kind of split graph. To the best of our knowledge, our result properly contains all previously known such cases. Our polynomial time algorithms are build on a structural investigation of graphs that admit a split square root that is 3-sun-free, and may pave the way toward a dichotomy theorem for recognizing squares of (3-sun-free) split graphs.
Language-based Examples in the Statistics Classroom
Venue: arXiv cs.CL 2014
Year: 2014

Statistics pedagogy values using a variety of examples. Thanks to text resources on the Web, and since statistical packages have the ability to analyze string data, it is now easy to use language-based examples in a statistics class. Three such examples are discussed here. First, many types of wordplay (e.g., crosswords and hangman) involve finding words with letters that satisfy a certain pattern. Second, linguistics has shown that idiomatic pairs of words often appear together more frequently than chance. For example, in the Brown Corpus, this is true of the phrasal verb to throw up (p-value=7.92E-10.) Third, a pangram contains all the letters of the alphabet at least once. These are searched for in Charles Dickens' A Christmas Carol, and their lengths are compared to the expected value given by the unequal probability coupon collector's problem as well as simulations.
Image Denoising using New Adaptive Based Median Filters
Venue: arXiv cs.CV 2014
Year: 2014

Noise is a major issue while transferring images through all kinds of electronic communication. One of the most common noise in electronic communication is an impulse noise which is caused by unstable voltage. In this paper, the comparison of known image denoising techniques is discussed and a new technique using the decision based approach has been used for the removal of impulse noise. All these methods can primarily preserve image details while suppressing impulsive noise. The principle of these techniques is at first introduced and then analysed with various simulation results using MATLAB. Most of the previously known techniques are applicable for the denoising of images corrupted with less noise density. Here a new decision based technique has been presented which shows better performances than those already being used. The comparisons are made based on visual appreciation and further quantitatively by Mean Square error (MSE) and Peak Signal to Noise Ratio (PSNR) of different filtered images..
Learning manifold to regularize nonnegative matrix factorization
Venue: arXiv cs.LG 2014
Year: 2014

Inthischapterwediscusshowtolearnanoptimalmanifoldpresentationto regularize nonegative matrix factorization (NMF) for data representation problems. NMF,whichtriestorepresentanonnegativedatamatrixasaproductoftwolowrank nonnegative matrices, has been a popular method for data representation due to its ability to explore the latent part-based structure of data. Recent study shows that lots of data distributions have manifold structures, and we should respect the manifold structure when the data are represented. Recently, manifold regularized NMF used a nearest neighbor graph to regulate the learning of factorization parameter matrices and has shown its advantage over traditional NMF methods for data representation problems. However, how to construct an optimal graph to present the manifold prop- erly remains a difficultproblem due to the graph modelselection, noisy features, and nonlinear distributed data. In this chapter, we introduce three effective methods to solve these problems of graph construction for manifold regularized NMF. Multiple graph learning is proposed to solve the problem of graph model selection, adaptive graph learning via feature selection is proposed to solve the problem of constructing a graph from noisy features, while multi-kernel learning-based graph construction is used to solve the problem of learning a graph from nonlinearly distributed data.
Families with infants: speeding up algorithms for NP-hard problems using FFT
Venue: arXiv cs.DS 2014
Year: 2014

Assume that a group of people is going to an excursion and our task is to seat them into buses with several constraints each saying that a pair of people does not want to see each other in the same bus. This is a well-known coloring problem and it can be solved in $O^*(2^n)$ time by the inclusion-exclusion principle as shown by Björklund, Husfeldt, and Koivisto in 2009.Another approach to solve this problem in $O^*(2^n)$ time is to use the fast Fourier transform. A graph is $k$-colorable if and only if the $k$-th power of a polynomial containing a monomial $\prod_{i=1}^n x_i^{[i \in I]}$ for each independent set $I \subseteq [n]$ of the graph, contains the monomial $x_1x_2... x_n$. Assume now that we have additional constraints: the group of people contains several infants and these infants should be accompanied by their relatives in a bus. We show that if the number of infants is linear then the problem can be solved in $O^*((2-\varepsilon)^n)$ time. We use this approach to improve known bounds for several NP-hard problems (the traveling salesman problem, the graph coloring problem, the problem of counting perfect matchings) on graphs of bounded average degree, as well as to simplify the proofs of several known results.
Testing Identity of Structured Distributions
Venue: arXiv cs.DS 2014
Year: 2014

We study the question of identity testing for structured distributions. More precisely, given samples from a {\em structured} distribution $q$ over $[n]$ and an explicit distribution $p$ over $[n]$, we wish to distinguish whether $q=p$ versus $q$ is at least $ε$-far from $p$, in $L_1$ distance. In this work, we present a unified approach that yields new, simple testers, with sample complexity that is information-theoretically optimal, for broad classes of structured distributions, including $t$-flat distributions, $t$-modal distributions, log-concave distributions, monotone hazard rate (MHR) distributions, and mixtures thereof.
Zero-Delay Sequential Transmission of Markov Sources Over Burst Erasure Channels
Venue: arXiv cs.IT 2014
Year: 2014

A setup involving zero-delay sequential transmission of a vector Markov source over a burst erasure channel is studied. A sequence of source vectors is compressed in a causal fashion at the encoder, and the resulting output is transmitted over a burst erasure channel. The destination is required to reconstruct each source vector with zero-delay, but those source sequences that are observed either during the burst erasure, or in the interval of length $W$ following the burst erasure need not be reconstructed. The minimum achievable compression rate is called the rate-recovery function. We assume that each source vector is sampled i.i.d. across the spatial dimension and from a stationary, first-order Markov process across the temporal dimension. For discrete sources the case of lossless recovery is considered, and upper and lower bounds on the rate-recovery function are established. Both these bounds can be expressed as the rate for predictive coding, plus a term that decreases at least inversely with the recovery window length $W$. For Gauss-Markov sources and a quadratic distortion measure, upper and lower bounds on the minimum rate are established when $W=0$. These bounds are shown to coincide in the high resolution limit. Finally another setup involving i.i.d. Gaussian sources is studied and the rate-recovery function is completely characterized in this case.
Improvement of Spectrum Sharing using Traffic pattern prediction
Venue: arXiv cs.NI 2014
Year: 2014

The paper focuses on improving the spectrum sharing using NSU, FLS and Traffic Pattern Prediction and also made comparison that traffic pattern prediction provides a better way of improving the spectrum utilization and avoids the spectrum scarcity. This helps to increase the number of active users, ease of identification of optimal users to use the spectrum with maximized coverage of the spectrum.. We experimentally evaluated the effectiveness of our approach using NS2 simulator and showed that after predicting the traffic, we can accommodate more number of users and avoiding Interference.
On the Stable Throughput of Cooperative Cognitive Radio Networks with Finite Relaying Buffer
Venue: arXiv cs.NI 2014
Year: 2014

In this paper, we study the problem of cooperative communications in cognitive radio systems where the secondary user has limited relaying room for the overheard primary packets. More specifically, we characterize the stable throughput region of a cognitive radio network with a finite relaying buffer at the secondary user. Towards this objective, we formulate a constrained optimization problem for maximizing the secondary user throughput while guaranteeing the stability of the primary user queue. We consider a general cooperation policy where the packet admission and queue selection probabilities, at the secondary user, are both dependent on the state (length) of the finite relaying buffer. Despite the sheer complexity of the optimization problem, attributed to its non-convexity, we transform it to a linear program. Our numerical results reveal a number of valuable insights, e.g., it is always mutually beneficial to cooperate in delivering the primary packets in terms of expanding the stable throughput region. In addition, the stable throughput region of the system, compared to the case of infinite relaying queue capacity, marginally shrinks for limited relaying queue capacity.
Transmit without regrets: Online optimization in MIMO-OFDM cognitive radio systems
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we examine cognitive radio systems that evolve dynamically over time due to changing user and environmental conditions. To combine the advantages of orthogonal frequency division multiplexing (OFDM) and multiple-input, multiple-output (MIMO) technologies, we consider a MIMO-OFDM cognitive radio network where wireless users with multiple antennas communicate over several non-interfering frequency bands. As the network's primary users (PUs) come and go in the system, the communication environment changes constantly (and, in many cases, randomly). Accordingly, the network's unlicensed, secondary users (SUs) must adapt their transmit profiles "on the fly" in order to maximize their data rate in a rapidly evolving environment over which they have no control. In this dynamic setting, static solution concepts (such as Nash equilibrium) are no longer relevant, so we focus on dynamic transmit policies that lead to no regret: specifically, we consider policies that perform at least as well as (and typically outperform) even the best fixed transmit profile in hindsight. Drawing on the method of matrix exponential learning and online mirror descent techniques, we derive a no-regret transmit policy for the system's SUs which relies only on local channel state information (CSI). Using this method, the system's SUs are able to track their individually evolving optimum transmit profiles remarkably well, even under rapidly (and randomly) changing conditions. Importantly, the proposed augmented exponential learning (AXL) policy leads to no regret even if the SUs' channel measurements are subject to arbitrarily large observation errors (the imperfect CSI case), thus ensuring the method's robustness in the presence of uncertainties.
Spatial mixing and the connective constant: Optimal bounds
Venue: arXiv cs.DS 2014
Year: 2014

We study the problem of deterministic approximate counting of matchings and independent sets in graphs of bounded connective constant. More generally, we consider the problem of evaluating the partition functions of the monomer-dimer model (which is defined as a weighted sum over all matchings where each matching is given a weight $γ^{|V| - 2 |M|}$ in terms of a fixed parameter gamma called the monomer activity) and the hard core model (which is defined as a weighted sum over all independent sets where an independent set I is given a weight $λ^{|I|}$ in terms of a fixed parameter lambda called the vertex activity). The connective constant is a natural measure of the average degree of a graph which has been studied extensively in combinatorics and mathematical physics, and can be bounded by a constant even for certain unbounded degree graphs such as those sampled from the sparse Erdős-Rényi model $G(n, d/n)$. Our main technical contribution is to prove the best possible rates of decay of correlations in the natural probability distributions induced by both the hard core model and the monomer-dimer model in graphs with a given bound on the connective constant. These results on decay of correlations are obtained using a new framework based on the so-called message approach that has been extensively used recently to prove such results for bounded degree graphs. We then use these optimal decay of correlations results to obtain FPTASs for the two problems on graphs of bounded connective constant. Our techniques also allow us to improve upon known bounds for decay of correlations for the hard core model on various regular lattices, including those obtained by Restrepo, Shin, Vigoda and Tetali (2011) for the special case of Z^2 using sophisticated numerically intensive methods tailored to that special case.
Secure Key Establishment for Device-to-Device Communications
Venue: arXiv cs.CR 2014
Year: 2014

With the rapid growth of smartphone and tablet users, Device-to-Device (D2D) communications have become an attractive solution for enhancing the performance of traditional cellular networks. However, relevant security issues involved in D2D communications have not been addressed yet. In this paper, we investigate the security requirements and challenges for D2D communications, and present a secure and efficient key agreement protocol, which enables two mobile devices to establish a shared secret key for D2D communications without prior knowledge. Our approach is based on the Diffie-Hellman key agreement protocol and commitment schemes. Compared to previous work, our proposed protocol introduces less communication and computation overhead. We present the design details and security analysis of the proposed protocol. We also integrate our proposed protocol into the existing Wi-Fi Direct protocol, and implement it using Android smartphones.