OpenRaiser/Intern-Atlas huggingface dataset:
Programmable Restoration Granularity in Constraint Programming
Venue: arXiv cs.PL 2016
Year: 2016

In most constraint programming systems, a limited number of search engines is offered while the programming of user-customized search algorithms requires low-level efforts, which complicates the deployment of such algorithms. To alleviate this limitation, concepts such as computation spaces have been developed. Computation spaces provide a coarse-grained restoration mechanism, because they store all information contained in a search tree node. Other granularities are possible, and in this paper we make the case for dynamically adapting the restoration granularity during search. In order to elucidate programmable restoration granularity, we present restoration as an aspect of a constraint programming system, using the model of aspect-oriented programming. A proof-of-concept implementation using Gecode shows promising results.
Interpolant Tree Automata and their Application in Horn Clause Verification
Venue: arXiv cs.LO 2016
Year: 2016

This paper investigates the combination of abstract interpretation over the domain of convex polyhedra with interpolant tree automata, in an abstraction-refinement scheme for Horn clause verification. These techniques have been previously applied separately, but are combined in a new way in this paper. The role of an interpolant tree automaton is to provide a generalisation of a spurious counterexample during refinement, capturing a possibly infinite set of spurious counterexample traces. In our approach these traces are then eliminated using a transformation of the Horn clauses. We compare this approach with two other methods; one of them uses interpolant tree automata in an algorithm for trace abstraction and refinement, while the other uses abstract interpretation over the domain of convex polyhedra without the generalisation step. Evaluation of the results of experiments on a number of Horn clause verification problems indicates that the combination of interpolant tree automaton with abstract interpretation gives some increase in the power of the verification tool, while sometimes incurring a performance overhead.
Throughput Analysis of Wireless Powered Cognitive Radio Networks with Compressive Sensing and Matrix Completion
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we consider a cognitive radio network in which energy constrained secondary users (SUs) can harvest energy from the randomly deployed power beacons (PBs). A new frame structure is proposed for the considered network. A wireless power transfer (WPT) model and a compressive spectrum sensing model are introduced. In the WPT model, a new WPT scheme is proposed, and the closed-form expressions for the power outage probability are derived. In compressive spectrum sensing model, two scenarios are considered: 1) Single SU, and 2) Multiple SUs. In the single SU scenario, in order to reduce the energy consumption at the SU, compressive sensing technique which enables sub-Nyquist sampling is utilized. In the multiple SUs scenario, cooperative spectrum sensing (CSS) is performed with adopting low-rank matrix completion technique to obtain the complete matrix at the fusion center. Throughput optimizations of the secondary network are formulated into two linear constrained problems, which aim to maximize the throughput of single SU and the CSS networks, respectively. Three methods are provided to obtain the maximal throughput of secondary network by optimizing the time slots allocation and the transmit power. Simulation results show that: 1) Multiple SUs scenario can achieve lower power outage probability than single SU scenario; and 2) The optimal throughput can be improved by implementing compressive spectrum sensing in the proposed frame structure design.
Large-Scale MIMO is Capable of Eliminating Power-Thirsty Channel Coding for Wireless Transmission of HEVC/H.265 Video
Venue: arXiv cs.IT 2016
Year: 2016

A wireless video transmission architecture relying on the emerging large-scale multiple-input--multiple-output (LS-MIMO) technique is proposed. Upon using the most advanced High Efficiency Video Coding (HEVC) (also known as H.265), we demonstrate that the proposed architecture invoking the low-complexity linear zero-forcing (ZF) detector and dispensing with any channel coding is capable of significantly outperforming the conventional small-scale MIMO based architecture, even if the latter employs the high-complexity optimal maximum-likelihood (ML) detector and a rate-$1/3$ recursive systematic convolutional (RSC) channel codec. Specifically, compared to the conventional small-scale MIMO system, the effective system throughput of the proposed LS-MIMO based scheme is increased by a factor of up to three and the quality of reconstructed video quantified in terms of the peak signal-to-noise ratio (PSNR) is improved by about $22.5\, \text{dB}$ at a channel-SNR of $E_b/N_0 \approx 6\,\text{dB}$ for delay-tolerant video-file delivery applications, and about $20\,\text{dB}$ for lip-synchronized real-time interactive video applications. Alternatively, viewing the attainable improvement from a power-saving perspective, a channel-SNR gain as high as $Δ_{E_b/N_0}\approx 5\,\text{dB}$ is observed at a PSNR of $36\, \text{dB}$ for the scenario of delay-tolerant video applications and again, an even higher gain is achieved in the real-time video application scenario. Therefore, we envisage that LS-MIMO aided wireless multimedia communications is capable of dispensing with power-thirsty channel codec altogether!
Concept Generation in Language Evolution
Venue: arXiv cs.AI 2016
Year: 2016

This thesis investigates the generation of new concepts from combinations of existing concepts as a language evolves. We give a method for combining concepts, and will be investigating the utility of composite concepts in language evolution and thence the utility of concept generation.
Very Efficient Training of Convolutional Neural Networks using Fast Fourier Transform and Overlap-and-Add
Venue: arXiv cs.NE 2016
Year: 2016

Convolutional neural networks (CNNs) are currently state-of-the-art for various classification tasks, but are computationally expensive. Propagating through the convolutional layers is very slow, as each kernel in each layer must sequentially calculate many dot products for a single forward and backward propagation which equates to $\mathcal{O}(N^{2}n^{2})$ per kernel per layer where the inputs are $N \times N$ arrays and the kernels are $n \times n$ arrays. Convolution can be efficiently performed as a Hadamard product in the frequency domain. The bottleneck is the transformation which has a cost of $\mathcal{O}(N^{2}\log_2 N)$ using the fast Fourier transform (FFT). However, the increase in efficiency is less significant when $N\gg n$ as is the case in CNNs. We mitigate this by using the "overlap-and-add" technique reducing the computational complexity to $\mathcal{O}(N^2\log_2 n)$ per kernel. This method increases the algorithm's efficiency in both the forward and backward propagation, reducing the training and testing time for CNNs. Our empirical results show our method reduces computational time by a factor of up to 16.3 times the traditional convolution implementation for a 8 $\times$ 8 kernel and a 224 $\times$ 224 image.
Edge-Disjoint Node-Independent Spanning Trees in Dense Gaussian Networks
Venue: arXiv cs.DC 2016
Year: 2016

Independent trees are used in building secure and/or fault-tolerant network communication protocols. They have been investigated for different network topologies including tori. Dense Gaussian networks are potential alternatives for 2-dimensional tori. They have similar topological properties; however, they are superiors in carrying communications due to their node-distance distributions and smaller diameters. In this paper, we present constructions of edge-disjoint node-independent spanning trees in dense Gaussian networks. Based on the constructed trees, we design algorithms that could be used in fault-tolerant routing or secure message distribution.
BUbiNG: Massive Crawling for the Masses
Venue: arXiv cs.IR 2016
Year: 2016

Although web crawlers have been around for twenty years by now, there is virtually no freely available, opensource crawling software that guarantees high throughput, overcomes the limits of single-machine systems and at the same time scales linearly with the amount of resources available. This paper aims at filling this gap, through the description of BUbiNG, our next-generation web crawler built upon the authors' experience with UbiCrawler [Boldi et al. 2004] and on the last ten years of research on the topic. BUbiNG is an opensource Java fully distributed crawler; a single BUbiNG agent, using sizeable hardware, can crawl several thousands pages per second respecting strict politeness constraints, both host- and IP-based. Unlike existing open-source distributed crawlers that rely on batch techniques (like MapReduce), BUbiNG job distribution is based on modern high-speed protocols so to achieve very high throughput.
Simple and Efficient Fully-Functional Succinct Trees
Venue: arXiv cs.DS 2016
Year: 2016

The fully-functional succinct tree representation of Navarro and Sadakane (ACM Transactions on Algorithms, 2014) supports a large number of operations in constant time using $2n+o(n)$ bits. However, the full idea is hard to implement. Only a simplified version with $O(\log n)$ operation time has been implemented and shown to be practical and competitive. We describe a new variant of the original idea that is much simpler to implement and has worst-case time $O(\log\log n)$ for the operations. An implementation based on this version is experimentally shown to be superior to existing implementations.
Exact Finite-State Machine Identification from Scenarios and Temporal Properties
Venue: arXiv cs.SE 2016
Year: 2016

Finite-state models, such as finite-state machines (FSMs), aid software engineering in many ways. They are often used in formal verification and also can serve as visual software models. The latter application is associated with the problems of software synthesis and automatic derivation of software models from specification. Smaller synthesized models are more general and are easier to comprehend, yet the problem of minimum FSM identification has received little attention in previous research. This paper presents four exact methods to tackle the problem of minimum FSM identification from a set of test scenarios and a temporal specification represented in linear temporal logic. The methods are implemented as an open-source tool. Three of them are based on translations of the FSM identification problem to SAT or QSAT problem instances. Accounting for temporal properties is done via counterexample prohibition. Counterexamples are either obtained from previously identified FSMs, or based on bounded model checking. The fourth method uses backtracking. The proposed methods are evaluated on several case studies and on a larger number of randomly generated instances of increasing complexity. The results show that the Iterative SAT-based method is the leader among the proposed methods. The methods are also compared with existing inexact approaches, i.e. the ones which do not necessarily identify the minimum FSM, and these comparisons show encouraging results.
Asymptotic analysis of downlink MIMO systems over Rician fading channels
Venue: arXiv cs.IT 2016
Year: 2016

In this work, we focus on the ergodic sum rate in the downlink of a single-cell large-scale multi-user MIMO system in which the base station employs N antennas to communicate with $K$ single-antenna user equipments. A regularized zero-forcing (RZF) scheme is used for precoding under the assumption that each link forms a spatially correlated MIMO Rician fading channel. The analysis is conducted assuming $N$ and $K$ grow large with a non trivial ratio and perfect channel state information is available at the base station. Recent results from random matrix theory and large system analysis are used to compute an asymptotic expression of the signal-to-interference- plus-noise ratio as a function of the system parameters, the spatial correlation matrix and the Rician factor. Numerical results are used to evaluate the performance gap in the finite system regime under different operating conditions.
Greedy Subspace Pursuit for Joint Sparse Recovery
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we address the sparse multiple measurement vector (MMV) problem where the objective is to recover a set of sparse nonzero row vectors or indices of a signal matrix from incomplete measurements. Ideally, regardless of the number of columns in the signal matrix, the sparsity (k) plus one measurements is sufficient for the uniform recovery of signal vectors for almost all signals, i.e., excluding a set of Lebesgue measure zero. To approach the "k+1" lower bound with computational efficiency even when the rank of signal matrix is smaller than k, we propose a greedy algorithm called Two-stage orthogonal Subspace Matching Pursuit (TSMP) whose theoretical results approach the lower bound with less restriction than the Orthogonal Subspace Matching Pursuit (OSMP) and Subspace-Augmented MUltiple SIgnal Classification (SA-MUSIC) algorithms. We provide non-asymptotical performance guarantees of OSMP and TSMP by covering both noiseless and noisy cases. Variants of restricted isometry property and mutual coherence are used to improve the performance guarantees. Numerical simulations demonstrate that the proposed scheme has low complexity and outperforms most existing greedy methods. This shows that the minimum number of measurements for the success of TSMP converges more rapidly to the lower bound than the existing methods as the number of columns of the signal matrix increases.
Centrality Measures for Networks with Community Structure
Venue: arXiv cs.SI 2016
Year: 2016

Understanding the network structure, and finding out the influential nodes is a challenging issue in the large networks. Identifying the most influential nodes in the network can be useful in many applications like immunization of nodes in case of epidemic spreading, during intentional attacks on complex networks. A lot of research is done to devise centrality measures which could efficiently identify the most influential nodes in the network. There are two major approaches to the problem: On one hand, deterministic strategies that exploit knowledge about the overall network topology in order to find the influential nodes, while on the other end, random strategies are completely agnostic about the network structure. Centrality measures that can deal with a limited knowledge of the network structure are required. Indeed, in practice, information about the global structure of the overall network is rarely available or hard to acquire. Even if available, the structure of the network might be too large that it is too much computationally expensive to calculate global centrality measures. To that end, a centrality measure is proposed that requires information only at the community level to identify the influential nodes in the network. Indeed, most of the real-world networks exhibit a community structure that can be exploited efficiently to discover the influential nodes. We performed a comparative evaluation of prominent global deterministic strategies together with stochastic strategies with an available and the proposed deterministic community-based strategy. Effectiveness of the proposed method is evaluated by performing experiments on synthetic and real-world networks with community structure in the case of immunization of nodes for epidemic control.
Recurrent Neural Network Postfilters for Statistical Parametric Speech Synthesis
Venue: arXiv cs.CL 2016
Year: 2016

In the last two years, there have been numerous papers that have looked into using Deep Neural Networks to replace the acoustic model in traditional statistical parametric speech synthesis. However, far less attention has been paid to approaches like DNN-based postfiltering where DNNs work in conjunction with traditional acoustic models. In this paper, we investigate the use of Recurrent Neural Networks as a potential postfilter for synthesis. We explore the possibility of replacing existing postfilters, as well as highlight the ease with which arbitrary new features can be added as input to the postfilter. We also tried a novel approach of jointly training the Classification And Regression Tree and the postfilter, rather than the traditional approach of training them independently.
Fairness in Communication for Omniscience
Venue: arXiv cs.IT 2016
Year: 2016

We consider the problem of how to fairly distribute the minimum sum-rate among the users in communication for omniscience (CO). We formulate a problem of minimizing a weighted quadratic function over a submodular base polyhedron which contains all achievable rate vectors, or transmission strategies, for CO that have the same sum-rate. By solving it, we can determine the rate vector that optimizes the Jain's fairness measure, a more commonly used fairness index than the Shapley value in communications engineering. We show that the optimizer is a lexicographically optimal (lex-optimal) base and can be determined by a decomposition algorithm (DA) that is based on submodular function minimization (SFM) algorithm and completes in strongly polynomial time. We prove that the lex-optimal minimum sum-rate strategy for CO can be determined by finding the lex-optimal base in each user subset in the fundamental partition and the complexity can be reduced accordingly.
Downlink Outage Performance of Heterogeneous Cellular Networks
Venue: arXiv cs.IT 2016
Year: 2016

This paper derives tight performance upper and lower bounds on the downlink outage efficiency of K-tier heterogeneous cellular networks (HCNs) for general signal propagation models with Poisson distributed base stations in each tier. In particular, the proposed approach to analyze the outage metrics in a K-tier HCN allows for the use of general bounded path-loss functions and random fading processes of general distributions. Considering two specific base station (BS) association policies, it is shown that the derived performance bounds track the actual outage metrics reasonably well for a wide range of BS densities, with the gap among them becoming negligibly small for denser HCN deployments. A simulation study is also performed for 2-tier and 3-tier HCN scenarios to illustrate the closeness of the derived bounds to the actual outage performance with various selections of the HCN parameters.
DoF Analysis of the MIMO Broadcast Channel with Alternating/Hybrid CSIT
Venue: arXiv cs.IT 2016
Year: 2016

We consider a $K$-user multiple-input single-output (MISO) broadcast channel (BC) where the channel state information (CSI) of user $i(i=1,2,\ldots,K)$ may be instantaneously perfect (P), delayed (D) or not known (N) at the transmitter with probabilities $λ_P^i$, $λ_D^i$ and $λ_N^i$, respectively. In this setting, according to the three possible CSIT for each user, knowledge of the joint CSIT of the $K$ users could have at most $3^K$ states. In this paper, given the marginal probabilities of CSIT (i.e., $λ_P^i$, $λ_D^i$ and $λ_N^i$), we derive an outer bound for the DoF region of the $K$-user MISO BC. Subsequently, we tighten this outer bound by taking into account a set of inequalities that capture some of the $3^K$ states of the joint CSIT. One of the consequences of this set of inequalities is that for $K\geq3$, it is shown that the DoF region is not completely characterized by the marginal probabilities in contrast to the two-user case. Afterwards, the tightness of these bounds are investigated through the discussion on the achievability. Finally, a two user MIMO BC having CSIT among P and N is considered in which an outer bound for the DoF region is provided and it is shown that in some scenarios it is tight.
Optimal Energy Management for SmartGrids Considering Thermal Load and Dynamic Pricing
Venue: arXiv cs.SY 2016
Year: 2016

More active participation of the demand side and efficient integration of distributed energy resources (DERs) such as electric vehicles (trVs), energy storage (ES), and renewable energy sources (RESs) into the existing power systems are important design objectives of the future smart grid. In general, effective demand side management (DSM) would benefit both system operators (e.g., peak demand reduction) and electricity customers (e.g., cost saving). For building and home energy scheduling design, heating, ventilation, and air-conditioning (HVAC) systems play a very important role since HVAC power consumption is very significant and the HVAC load can be scheduled flexibly while still maintaining user comfort requirements. This thesis focuses on energy scheduling design for two different application scenarios where HVAC and various DERs are considered to optimize the benefits electric users.
Game Theoretic Analysis of Tree Based Referrals for Crowd Sensing Social Systems with Passive Rewards
Venue: arXiv cs.GT 2016
Year: 2016

Participatory crowd sensing social systems rely on the participation of large number of individuals. Since humans are strategic by nature, effective incentive mechanisms are needed to encourage participation. A popular mechanism to recruit individuals is through referrals and passive incentives such as geometric incentive mechanisms used by the winning team in the 2009 DARPA Network Challenge and in multi level marketing schemes. The effect of such recruitment schemes on the effort put in by recruited strategic individuals is not clear. This paper attempts to fill this gap. Given a referral tree and the direct and passive reward mechanism, we formulate a network game where agents compete for finishing crowd sensing tasks. We characterize the Nash equilibrium efforts put in by the agents and derive closed form expressions for the same. We discover free riding behavior among nodes who obtain large passive rewards. This work has implications on designing effective recruitment mechanisms for crowd sourced tasks. For example, usage of geometric incentive mechanisms to recruit large number of individuals may not result in proportionate effort because of free riding.
A Method for RFO Estimation Using Phase Analysis of Pilot Symbols in OFDM Systems
Venue: arXiv cs.OH 2016
Year: 2016

In this paper, a method for CFO/RFO estimation based on proportional coefficients extraction in OFDM system is proposed, which may be applied to any pilot symbol pattern.
Combining Maps and Street Level Images for Building Height and Facade Estimation
Venue: arXiv cs.CV 2016
Year: 2016

We propose a method that integrates two widely available data sources, building footprints from 2D maps and street level images, to derive valuable information that is generally difficult to acquire -- building heights and building facade masks in images. Building footprints are elevated in world coordinates and projected onto images. Building heights are estimated by scoring projected footprints based on their alignment with building features in images. Building footprints with estimated heights can be converted to simple 3D building models, which are projected back to images to identify buildings. In this procedure, accurate camera projections are critical. However, camera position errors inherited from external sensors commonly exist, which adversely affect results. We derive a solution to precisely locate cameras on maps using correspondence between image features and building footprints. Experiments on real-world datasets show the promise of our method.