OpenRaiser/Intern-Atlas huggingface dataset:
Aligning Software-related Strategies in Multi-Organizational Settings
Venue: arXiv cs.SE 2014
Year: 2014

Aligning the activities of an organization with its business goals is a challenging task that is critical for success. Alignment in a multi-organizational setting requires the integration of different internal or external organizational units. The anticipated benefits of multi-organizational alignment consist of clarified contributions and increased transparency of the involved organizational units. The GQM+Strategies approach provides mechanisms for explicitly linking goals and strategies within an organization and is based on goal-oriented measurement. This paper presents the process and first-hand experience of applying GQM+Strategies in a multi-organizational setting from the aerospace industry. Additionally, the resulting GQM+Strategies grid is sketched and selected parts are discussed. Finally, the results are reflected on and an overview of future work is given.
A PSO and Pattern Search based Memetic Algorithm for SVMs Parameters Optimization
Venue: arXiv cs.LG 2014
Year: 2014

Addressing the issue of SVMs parameters optimization, this study proposes an efficient memetic algorithm based on Particle Swarm Optimization algorithm (PSO) and Pattern Search (PS). In the proposed memetic algorithm, PSO is responsible for exploration of the search space and the detection of the potential regions with optimum solutions, while pattern search (PS) is used to produce an effective exploitation on the potential regions obtained by PSO. Moreover, a novel probabilistic selection strategy is proposed to select the appropriate individuals among the current population to undergo local refinement, keeping a well balance between exploration and exploitation. Experimental results confirm that the local refinement with PS and our proposed selection strategy are effective, and finally demonstrate effectiveness and robustness of the proposed PSO-PS based MA for SVMs parameters optimization.
A study of Monte-Carlo method in a teachers' training institute
Venue: arXiv cs.CY 2014
Year: 2014

The problem of Monte-Carlo method study at computer simulation lessons in a Teachers' Training Institute is reviewed in the article. The suggested technique envisages the simulation modelling of various stochastic processes. They include transmission of information via a communication link, oscillation of a pendulum in an air stream, deflection of alpha particles by Au atoms, formation of a percolating cluster, etc. (New educational technologies in higher education institution: the collection of reports of the tenth international scientific and methodical conference. Yekaterinburg, UGTU UPI, 2013).
Binary Jumbled Pattern Matching via All-Pairs Shortest Paths
Venue: arXiv cs.DS 2014
Year: 2014

In binary jumbled pattern matching we wish to preprocess a binary string $S$ in order to answer queries $(i,j)$ which ask for a substring of $S$ that is of size $i$ and has exactly $j$ 1-bits. The problem naturally generalizes to node-labeled trees and graphs by replacing "substring" with "connected subgraph". In this paper, we give an ${n^2}/{2^{Ω(\log n/\log \log n)^{1/2}}}$ time solution for both strings and trees. This odd-looking time complexity improves the state of the art $O(n^2/\log^2 n)$ solutions by more than any poly-logarithmic factor. It originates from the recent seminal algorithm of Williams for min-plus matrix multiplication. We obtain the result by giving a black box reduction from trees to strings. This is then combined with a reduction from strings to min-plus matrix multiplications.
Latent Sentiment Detection in Online Social Networks: A Communications-oriented View
Venue: arXiv cs.SI 2014
Year: 2014

In this paper, we consider the problem of latent sentiment detection in Online Social Networks such as Twitter. We demonstrate the benefits of using the underlying social network as an Ising prior to perform network aided sentiment detection. We show that the use of the underlying network results in substantially lower detection error rates compared to strictly features-based detection. In doing so, we introduce a novel communications-oriented framework for characterizing the probability of error, based on information-theoretic analysis. We study the variation of the calculated error exponent for several stylized network topologies such as the complete network, the star network and the closed-chain network, and show the importance of the network structure in determining detection performance.
Achievability of Nonlinear Degrees of Freedom in Correlatively Changing Fading Channels
Venue: arXiv cs.IT 2014
Year: 2014

A new approach toward the noncoherent communications over the time varying fading channels is presented. In this approach, the relationship between the input signal space and the output signal space of a correlatively changing fading channel is shown to be a nonlinear mapping between manifolds of different dimensions. Studying this mapping, it is shown that using nonlinear decoding algorithms for single input-multiple output (SIMO) and multiple input multiple output (MIMO) systems, extra numbers of degrees of freedom (DOF) are available. We call them the nonlinear degrees of freedom.
Foresighted Demand Side Management
Venue: arXiv cs.MA 2014
Year: 2014

We consider a smart grid with an independent system operator (ISO), and distributed aggregators who have energy storage and purchase energy from the ISO to serve its customers. All the entities in the system are foresighted: each aggregator seeks to minimize its own long-term payments for energy purchase and operational costs of energy storage by deciding how much energy to buy from the ISO, and the ISO seeks to minimize the long-term total cost of the system (e.g. energy generation costs and the aggregators' costs) by dispatching the energy production among the generators. The decision making of the entities is complicated for two reasons. First, the information is decentralized: the ISO does not know the aggregators' states (i.e. their energy consumption requests from customers and the amount of energy in their storage), and each aggregator does not know the other aggregators' states or the ISO's state (i.e. the energy generation costs and the status of the transmission lines). Second, the coupling among the aggregators is unknown to them. Specifically, each aggregator's energy purchase affects the price, and hence the payments of the other aggregators. However, none of them knows how its decision influences the price because the price is determined by the ISO based on its state. We propose a design framework in which the ISO provides each aggregator with a conjectured future price, and each aggregator distributively minimizes its own long-term cost based on its conjectured price as well as its local information. The proposed framework can achieve the social optimum despite being decentralized and involving complex coupling among the various entities.
Using the Buffer to Avoid Rebuffers: Evidence from a Large Video Streaming Service
Venue: arXiv cs.NI 2014
Year: 2014

To provide a better streaming experience, video clients today select their video rates by observing and estimating the available capacity. Recent work has shown that capacity estimation is fraught with difficulties because of complex interactions between the ABR control loop, HTTP server performance and TCP congestion control. Estimation-based rate selection algorithms can lead to unnecessary rebuffering events and suboptimal video quality. This paper argues that we should do away with estimating network capacity, and instead directly observe and control the playback buffer--which is the state variable we are most interested in controlling. We present a class of "buffer-based" rate selection algorithms that reduce the rebuffering rate while allowing us to control the delivered video quality. We implemented our algorithms inside the Netflix video client and ran a series of experiments spanning millions of Netflix users around the world. Our results show that by doing away with estimating network capacity and instead focusing on buffer occupancy, we can reduce rebuffer rates by 20% while holding video rate constant.
Multistage Compute-and-Forward with Multilevel Lattice Codes Based on Product Constructions
Venue: arXiv cs.IT 2014
Year: 2014

A novel construction of lattices is proposed. This construction can be thought of as Construction A with codes that can be represented as the Cartesian product of $L$ linear codes over $\mathbb{F}_{p_1},\ldots,\mathbb{F}_{p_L}$, respectively; hence, is referred to as the product construction. The existence of a sequence of such lattices that are good for quantization and Poltyrev-good under multistage decoding is shown. This family of lattices is then used to generate a sequence of nested lattice codes which allows one to achieve the same computation rate of Nazer and Gastpar for compute-and-forward under multistage decoding, which is referred to as lattice-based multistage compute-and-forward. Motivated by the proposed lattice codes, two families of signal constellations are then proposed for the separation-based compute-and-forward framework proposed by Tunali \textit{et al.} together with a multilevel coding/multistage decoding scheme tailored specifically for these constellations. This scheme is termed separation-based multistage compute-and-forward and is shown having a complexity of the channel coding dominated by the greatest common divisor of the constellation size (may not be a prime number) instead of the constellation size itself.
BPP: Large Graph Storage for Efficient Disk Based Processing
Venue: arXiv cs.DS 2014
Year: 2014

Processing very large graphs like social networks, biological and chemical compounds is a challenging task. Distributed graph processing systems process the billion-scale graphs efficiently but incur overheads of efficient partitioning and distribution of the graph over a cluster of nodes. Distributed processing also requires cluster management and fault tolerance. In order to overcome these problems GraphChi was proposed recently. GraphChi significantly outperformed all the representative distributed processing frameworks. Still, we observe that GraphChi incurs some serious degradation in performance due to 1) high number of non-sequential I/Os for processing every chunk of graph; and 2) lack of true parallelism to process the graph. In this paper we propose a simple yet powerful engine BiShard Parallel Processor (BPP) to efficiently process billions-scale graphs on a single PC. We extend the storage structure proposed by GraphChi and introduce a new processing model called BiShard Parallel (BP). BP enables full CPU parallelism for processing the graph and significantly reduces the number of non-sequential I/Os required to process every chunk of the graph. Our experiments on real large graphs show that our solution significantly outperforms GraphChi.
Iterative Dynamic Water-filling for Fading Multiple-Access Channels with Energy Harvesting
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we develop optimal energy scheduling algorithms for $N$-user fading multiple-access channels with energy harvesting to maximize the channel sum-rate, assuming that the side information of both the channel states and energy harvesting states for $K$ time slots is known {\em a priori}, and the battery capacity and the maximum energy consumption in each time slot are bounded. The problem is formulated as a convex optimization problem with ${\cal O}(NK)$ constraints making it hard to solve using a general convex solver since the computational complexity of a generic convex solver is exponential in the number of constraints. This paper gives an efficient energy scheduling algorithm, called the iterative dynamic water-filling algorithm, that has a computational complexity of ${\cal O}(NK^2)$ per iteration. For the single-user case, a dynamic water-filling method is shown to be optimal. Unlike the traditional water-filling algorithm, in dynamic water-filling, the water level is not constant but changes when the battery overflows or depletes. An iterative version of the dynamic water-filling algorithm is shown to be optimal for the case of multiple users. Even though in principle the optimality is achieved under large number of iterations, in practice convergence is reached in only a few iterations. Moreover, a single iteration of the dynamic water-filling algorithm achieves a sum-rate that is within $(N-1)K/2$ nats of the optimal sum-rate.
Satellite image classification and segmentation using non-additive entropy
Venue: arXiv cs.CV 2014
Year: 2014

Here we compare the Boltzmann-Gibbs-Shannon (standard) with the Tsallis entropy on the pattern recognition and segmentation of coloured images obtained by satellites, via "Google Earth". By segmentation we mean split an image to locate regions of interest. Here, we discriminate and define an image partition classes according to a training basis. This training basis consists of three pattern classes: aquatic, urban and vegetation regions. Our numerical experiments demonstrate that the Tsallis entropy, used as a feature vector composed of distinct entropic indexes $q$ outperforms the standard entropy. There are several applications of our proposed methodology, once satellite images can be used to monitor migration form rural to urban regions, agricultural activities, oil spreading on the ocean etc.
Codes with Locality for Two Erasures
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we study codes with locality that can recover from two erasures via a sequence of two local, parity-check computations. By a local parity-check computation, we mean recovery via a single parity-check equation associated to small Hamming weight. Earlier approaches considered recovery in parallel; the sequential approach allows us to potentially construct codes with improved minimum distance. These codes, which we refer to as locally 2-reconstructible codes, are a natural generalization along one direction, of codes with all-symbol locality introduced by Gopalan \textit{et al}, in which recovery from a single erasure is considered. By studying the Generalized Hamming Weights of the dual code, we derive upper bounds on the minimum distance of locally 2-reconstructible codes and provide constructions for a family of codes based on Turán graphs, that are optimal with respect to this bound. The minimum distance bound derived here is universal in the sense that no code which permits all-symbol local recovery from $2$ erasures can have larger minimum distance regardless of approach adopted. Our approach also leads to a new bound on the minimum distance of codes with all-symbol locality for the single-erasure case.
Estimation of Medium Access Control Layer Packet Delay Distribution for IEEE 802.11
Venue: arXiv cs.NI 2014
Year: 2014

The most important standard in wireless local area networks is IEEE 802.11. This is why much of the research work for the enhancement of wireless network is usually based on the behavior of IEEE 802.11 protocol. However, some of the ways in which IEEE 802.11 medium access control layer behaves is still unreliable to guarantee quality of service. For instance, medium access control layer packet delay, jitter and packet loss rate still remain a challenge. The main objective of this research is to propose an accurate estimation of the medium access control layer packet delay distribution for IEEE 802.11. This estimation considers the differences between busy probability and collision probability. These differences are employed to achieve a more accurate estimation. Finally, the proposed model and simulation are implemented and validated - using MATLAB program for the purpose of simulation, and Maple program to undertake the calculation of the equations.
Axioms and Decidability for Type Isomorphism in the Presence of Sums
Venue: arXiv cs.LO 2014
Year: 2014

We consider the problem of characterizing isomorphisms of types, or, equivalently, constructive cardinality of sets, in the simultaneous presence of disjoint unions, Cartesian products, and exponentials. Mostly relying on results about polynomials with exponentiation that have not been used in our context, we derive: that the usual finite axiomatization known as High-School Identities (HSI) is complete for a significant subclass of types; that it is decidable for that subclass when two types are isomorphic; that, for the whole of the set of types, a recursive extension of the axioms of HSI exists that is complete; and that, for the whole of the set of types, the question as to whether two types are isomorphic is decidable when base types are to be interpreted as finite sets. We also point out certain related open problems.
On the Optimality of Treating Interference as Noise: General Message Sets
Venue: arXiv cs.IT 2014
Year: 2014

In a K-user Gaussian interference channel, it has been shown that if for each user the desired signal strength is no less than the sum of the strengths of the strongest interference from this user and the strongest interference to this user (all values in dB scale), then treating interference as noise (TIN) is optimal from the perspective of generalized degrees-of-freedom (GDoF) and achieves the entire channel capacity region to within a constant gap. In this work, we show that for such TIN-optimal interference channels, even if the message set is expanded to include an independent message from each transmitter to each receiver, operating the new channel as the original interference channel and treating interference as noise is still optimal for the sum capacity up to a constant gap. Furthermore, we extend the result to the sum-GDoF optimality of TIN in the general setting of X channels with arbitrary numbers of transmitters and receivers.
Scale-free interpersonal influences on opinions in complex systems
Venue: arXiv cs.SI 2014
Year: 2014

An important side effect of the evolution of the human brain is an increased capacity to form opinions in a very large domain of issues, which become points of aggressive interpersonal disputes. Remarkably, such disputes are often no less vigorous on small differences of opinion than large differences. Opinion differences that may be measured on the real number line may not directly correspond to the subjective importance of an issue and extent of resistance to opinion change. This is a hard problem for field of opinion dynamics, a field that has become increasingly prominent as it has attracted more contributions to it from investigators in the natural and engineering sciences. The paper contributes a scale-free approach to assessing the extents to which individuals, with unknown heterogeneous resistances to influence, have been influenced by the opinions of others.
An Overview of Schema Theory
Venue: arXiv cs.NE 2014
Year: 2014

The purpose of this paper is to give an introduction to the field of Schema Theory written by a mathematician and for mathematicians. In particular, we endeavor to to highlight areas of the field which might be of interest to a mathematician, to point out some related open problems, and to suggest some large-scale projects. Schema theory seeks to give a theoretical justification for the efficacy of the field of genetic algorithms, so readers who have studied genetic algorithms stand to gain the most from this paper. However, nothing beyond basic probability theory is assumed of the reader, and for this reason we write in a fairly informal style. Because the mathematics behind the theorems in schema theory is relatively elementary, we focus more on the motivation and philosophy. Many of these results have been proven elsewhere, so this paper is designed to serve a primarily expository role. We attempt to cast known results in a new light, which makes the suggested future directions natural. This involves devoting a substantial amount of time to the history of the field. We hope that this exposition will entice some mathematicians to do research in this area, that it will serve as a road map for researchers new to the field, and that it will help explain how schema theory developed. Furthermore, we hope that the results collected in this document will serve as a useful reference. Finally, as far as the author knows, the questions raised in the final section are new.
Erasure List-Decodable Codes from Random and Algebraic Geometry Codes
Venue: arXiv cs.IT 2014
Year: 2014

Erasure list decoding was introduced to correct a larger number of erasures with output of a list of possible candidates. In the present paper, we consider both random linear codes and algebraic geometry codes for list decoding erasure errors. The contributions of this paper are two-fold. Firstly, we show that, for arbitrary $0<R<1$ and $ε>0$ ($R$ and $ε$ are independent), with high probability a random linear code is an erasure list decodable code with constant list size $2^{O(1/ε)}$ that can correct a fraction $1-R-ε$ of erasures, i.e., a random linear code achieves the information-theoretic optimal trade-off between information rate and fraction of erasure errors. Secondly, we show that algebraic geometry codes are good erasure list-decodable codes. Precisely speaking, for any $0<R<1$ and $ε>0$, a $q$-ary algebraic geometry code of rate $R$ from the Garcia-Stichtenoth tower can correct $1-R-\frac{1}{\sqrt{q}-1}+\frac{1}{q}-ε$ fraction of erasure errors with list size $O(1/ε)$. This improves the Johnson bound applied to algebraic geometry codes. Furthermore, list decoding of these algebraic geometry codes can be implemented in polynomial time.
Estimating the Effort Overhead in Global Software Development
Venue: arXiv cs.SE 2014
Year: 2014

Models for effort and cost estimation are important for distributed software development as well as for collocated software and system development. Standard cost models only insufficiently consider the characteristics of distributed development such as dissimilar abilities at the different sites or significant overhead due to remote collaboration. Therefore, explicit cost models for distributed development are needed. In this article, we present the initial development of a cost overhead model for a Spanish global software development organization. The model was developed using the CoBRA approach for cost estimation. As a result, cost drivers for the specific distributed development context were identified and their impact was quantified on an empirical basis. The article presents related work, an overview of the approach, and its application in the industrial context. Finally, we sketch the inclusion of the model in an approach for systematic task allocation and give an overview of future work.
Design of novel architectures and field programmable gate arrays implementation of two dimensional gaussian surround function
Venue: arXiv cs.AR 2014
Year: 2014

A new design and novel architecture suitable for FPGA/ASIC implementation of a 2D Gaussian surround function for image processing application is presented in this paper. The proposed scheme results in enormous savings of memory normally required for 2D Gaussian function implementation. In the present work, the Gaussian symmetric characteristics which quickly falls off toward plus/minus infinity has been used in order to save the memory. The 2D Gaussian function implementation is presented for use in applications such as image enhancement, smoothing, edge detection and filtering etc. The FPGA implementation of the proposed 2D Gaussian function is capable of processing (blurring, smoothing, and convolution) high resolution color pictures of size up to $1600\times1200$ pixels at the real time video rate of 30 frames/sec. The Gaussian design exploited here has been used in the core part of retinex based color image enhancement. Therefore, the design presented produces Gaussian output with three different scales, namely, 16, 64 and 128. The design was coded in Verilog, a popular hardware design language used in industries, conforming to RTL coding guidelines and fits onto a single chip with a gate count utilization of 89,213 gates. Experimental results presented confirms that the proposed method offers a new approach for development of large sized Gaussian pyramid while reducing the on-chip memory utilization.