OpenRaiser/Intern-Atlas huggingface dataset:
Components Interoperability through Mediating Connector Patterns
Venue: arXiv cs.SE 2010
Year: 2010

A key objective for ubiquitous environments is to enable system interoperability between system's components that are highly heterogeneous. In particular, the challenge is to embed in the system architecture the necessary support to cope with behavioral diversity in order to allow components to coordinate and communicate. The continuously evolving environment further asks for an automated and on-the-fly approach. In this paper we present the design building blocks for the dynamic and on-the-fly interoperability between heterogeneous components. Specifically, we describe an Architectural Pattern called Mediating Connector, that is the key enabler for communication. In addition, we present a set of Basic Mediator Patterns, that describe the basic mismatches which can occur when components try to interact, and their corresponding solutions.
A Generalized Construction of OFDM M-QAM Sequences With Low Peak-to-Average Power Ratio
Venue: arXiv cs.IT 2010
Year: 2010

A construction of $2^{2n}$-QAM sequences is given and an upper bound of the peak-to-mean envelope power ratio (PMEPR) is determined. Some former works can be viewed as special cases of this construction.
On the Construction of Finite Oscillator Dictionary
Venue: arXiv cs.IT 2010
Year: 2010

A finite oscillator dictionary which has important applications in sequences designs and the compressive sensing was introduced by Gurevich, Hadani and Sochen. In this paper, we first revisit closed formulae of the finite split oscillator dictionary $\mathfrak{S}^s$ by a simple proof. Then we study the non-split tori of the group $SL(2,\mathbb{F}_p)$. Finally, An explicit algorithm for computing the finite non-split oscillator dictionary $\mathfrak{S}^{ns}$ is described.
Steering Fragments of Instruction Sequences
Venue: arXiv cs.PL 2010
Year: 2010

A steering fragment of an instruction sequence consists of a sequence of steering instructions. These are decision points involving the check of a propositional statement in sequential logic. The question is addressed why composed propositional statements occur in steering fragments given the fact that a straightforward transformation allows their elimination. A survey is provided of constraints that may be implicitly assumed when composed propositional statements occur in a meaningful instruction sequence.
Twitter mood predicts the stock market
Venue: arXiv cs.CE 2010
Year: 2010

Behavioral economics tells us that emotions can profoundly affect individual behavior and decision-making. Does this also apply to societies at large, i.e., can societies experience mood states that affect their collective decision making? By extension is the public mood correlated or even predictive of economic indicators? Here we investigate whether measurements of collective mood states derived from large-scale Twitter feeds are correlated to the value of the Dow Jones Industrial Average (DJIA) over time. We analyze the text content of daily Twitter feeds by two mood tracking tools, namely OpinionFinder that measures positive vs. negative mood and Google-Profile of Mood States (GPOMS) that measures mood in terms of 6 dimensions (Calm, Alert, Sure, Vital, Kind, and Happy). We cross-validate the resulting mood time series by comparing their ability to detect the public's response to the presidential election and Thanksgiving day in 2008. A Granger causality analysis and a Self-Organizing Fuzzy Neural Network are then used to investigate the hypothesis that public mood states, as measured by the OpinionFinder and GPOMS mood time series, are predictive of changes in DJIA closing values. Our results indicate that the accuracy of DJIA predictions can be significantly improved by the inclusion of specific public mood dimensions but not others. We find an accuracy of 87.6% in predicting the daily up and down changes in the closing values of the DJIA and a reduction of the Mean Average Percentage Error by more than 6%.
A Stackelberg Strategy for Routing Flow over Time
Venue: arXiv cs.GT 2010
Year: 2010

Routing games are used to to understand the impact of individual users' decisions on network efficiency. Most prior work on routing games uses a simplified model of network flow where all flow exists simultaneously, and users care about either their maximum delay or their total delay. Both of these measures are surrogates for measuring how long it takes to get all of a user's traffic through the network. We attempt a more direct study of how competition affects network efficiency by examining routing games in a flow over time model. We give an efficiently computable Stackelberg strategy for this model and show that the competitive equilibrium under this strategy is no worse than a small constant times the optimal, for two natural measures of optimality.
On Object-Orientation
Venue: arXiv cs.SE 2010
Year: 2010

Although object-orientation has been around for several decades, its key concept abstraction has not been exploited for proper application of object-orientation in other phases of software development than the implementation phase. We mention some issues that lead to a lot of confusion and obscurity with object-orientation and its application in software development. We describe object-orientation as abstract as possible such that it can be applied to all phases of software development.
A Survey of Virtualization Technologies With Performance Testing
Venue: arXiv cs.DC 2010
Year: 2010

Virtualization has rapidly become a go-to technology for increasing efficiency in the data center. With virtualization technologies providing tremendous flexibility, even disparate architectures may be deployed on a single machine without interference. Awareness of limitations and requirements of physical hosts to be used for virtualization is important. This paper reviews the present virtualization methods, virtual computing software, and provides a brief analysis of the performance issues inherent to each. In the end we present testing results of KVM-QEMU on two current Multi-Core CPU Architectures and System Configurations.
A strong law for the rate of growth of long latency periods in cloud computing service
Venue: arXiv cs.DC 2010
Year: 2010

Cloud-computing shares a common pool of resources across customers at a scale that is orders of magnitude larger than traditional multi-user systems. Constituent physical compute servers are allocated multiple "virtual machines" (VM) to serve simultaneously. Each VM user should ideally be unaffected by others' demand. Naturally, this environment produces new challenges for the service providers in meeting customer expectations while extracting an efficient utilization from server resources. We study a new cloud service metric that measures prolonged latency or delay suffered by customers. We model the workload process of a cloud server and analyze the process as the customer population grows. The capacity required to ensure that average workload does not exceed a threshold over long segments is characterized. This can be used by cloud operators to provide service guarantees on avoiding long durations of latency. As part of the analysis, we provide a uniform large-deviation principle for collections of random variables that is of independent interest.
A Survey of Green Networking Research
Venue: arXiv cs.NI 2010
Year: 2010

Reduction of unnecessary energy consumption is becoming a major concern in wired networking, because of the potential economical benefits and of its expected environmental impact. These issues, usually referred to as "green networking", relate to embedding energy-awareness in the design, in the devices and in the protocols of networks. In this work, we first formulate a more precise definition of the "green" attribute. We furthermore identify a few paradigms that are the key enablers of energy-aware networking research. We then overview the current state of the art and provide a taxonomy of the relevant work, with a special focus on wired networking. At a high level, we identify four branches of green networking research that stem from different observations on the root causes of energy waste, namely (i) Adaptive Link Rate, (ii) Interface proxying, (iii) Energy-aware infrastructures and (iv) Energy-aware applications. In this work, we do not only explore specific proposals pertaining to each of the above branches, but also offer a perspective for research.
A Paradigm for Channel Assignment and Data Migration in Distributed Systems
Venue: arXiv cs.DC 2010
Year: 2010

In this manuscript, we consider the problems of channel assignment in wireless networks and data migration in heterogeneous storage systems. We show that a soft edge coloring approach to both problems gives rigorous approximation guarantees. In the channel assignment problem arising in wireless networks a pair of edges incident to a vertex are said to be conflicting if the channels assigned to them are the same. Our goal is to assign channels (color edges) so that the number of conflicts is minimized. The problem is NP-hard by a reduction from Edge coloring and we present two combinatorial algorithms for this case. The first algorithm is based on a distributed greedy method and gives a solution with at most $2(1-\frac{1}{k})|E|$ more conflicts than the optimal solution.The approximation ratio if the second algorithm is $1 + \frac{|V|}{|E|}$, which gives a ($1 + o(1)$)-factor for dense graphs and is the best possible unless P = NP. We also consider the data migration problem in heterogeneous storage systems. In such systems, data layouts may need to be reconfigured over time for load balancing or in the event of system failure/upgrades. It is critical to migrate data to their target locations as quickly as possible to obtain the best performance of the system. Most of the previous results on data migration assume that each storage node can perform only one data transfer at a time. However, storage devices tend to have heterogeneous capabilities as devices may be added over time due to storage demand increase. We develop algorithms to minimize the data migration time. We show that it is possible to find an optimal migration schedule when all $c_v$'s are even. Furthermore, though the problem is NP-hard in general, we give an efficient soft edge coloring algorithm that offers a rigorous $(1 + o(1))$-approximation guarantee.
Information Analysis of DNA Sequences
Venue: arXiv cs.CE 2010
Year: 2010

The problem of differentiating the informational content of coding (exons) and non-coding (introns) regions of a DNA sequence is one of the central problems of genomics. The introns are estimated to be nearly 95% of the DNA and since they do not seem to participate in the process of transcription of amino-acids, they have been termed "junk DNA." Although it is believed that the non-coding regions in genomes have no role in cell growth and evolution, demonstration that these regions carry useful information would tend to falsify this belief. In this paper, we consider entropy as a measure of information by modifying the entropy expression to take into account the varying length of these sequences. Exons are usually much shorter in length than introns; therefore the comparison of the entropy values needs to be normalized. A length correction strategy was employed using randomly generated nucleonic base strings built out of the alphabet of the same size as the exons under question. Our analysis shows that introns carry nearly as much of information as exons, disproving the notion that they do not carry any information. The entropy findings of this paper are likely to be of use in further study of other challenging works like the analysis of symmetry models of the genetic code.
Convex Analysis and Optimization with Submodular Functions: a Tutorial
Venue: arXiv cs.LG 2010
Year: 2010

Set-functions appear in many areas of computer science and applied mathematics, such as machine learning, computer vision, operations research or electrical networks. Among these set-functions, submodular functions play an important role, similar to convex functions on vector spaces. In this tutorial, the theory of submodular functions is presented, in a self-contained way, with all results shown from first principles. A good knowledge of convex analysis is assumed.
Wireless Capacity with Oblivious Power in General Metrics
Venue: arXiv cs.DS 2010
Year: 2010

The capacity of a wireless network is the maximum possible amount of simultaneous communication, taking interference into account. Formally, we treat the following problem. Given is a set of links, each a sender-receiver pair located in a metric space, and an assignment of power to the senders. We seek a maximum subset of links that are feasible in the SINR model: namely, the signal received on each link should be larger than the sum of the interferences from the other links. We give a constant-factor approximation that holds for any length-monotone, sub-linear power assignment and any distance metric. We use this to give essentially tight characterizations of capacity maximization under power control using oblivious power assignments. Specifically, we show that the mean power assignment is optimal for capacity maximization of bi-directional links, and give a tight $θ(\log n)$-approximation of scheduling bi-directional links with power control using oblivious power. For uni-directional links we give a nearly optimal $O(\log n + \log \log Δ)$-approximation to the power control problem using mean power, where $Δ$ is the ratio of longest and shortest links. Combined, these results clarify significantly the centralized complexity of wireless communication problems.
Large-Scale Clustering Based on Data Compression
Venue: arXiv cs.LG 2010
Year: 2010

This paper considers the clustering problem for large data sets. We propose an approach based on distributed optimization. The clustering problem is formulated as an optimization problem of maximizing the classification gain. We show that the optimization problem can be reformulated and decomposed into small-scale sub optimization problems by using the Dantzig-Wolfe decomposition method. Generally speaking, the Dantzig-Wolfe method can only be used for convex optimization problems, where the duality gaps are zero. Even though, the considered optimization problem in this paper is non-convex, we prove that the duality gap goes to zero, as the problem size goes to infinity. Therefore, the Dantzig-Wolfe method can be applied here. In the proposed approach, the clustering problem is iteratively solved by a group of computers coordinated by one center processor, where each computer solves one independent small-scale sub optimization problem during each iteration, and only a small amount of data communication is needed between the computers and center processor. Numerical results show that the proposed approach is effective and efficient.
Coalition Formation Games for Collaborative Spectrum Sensing
Venue: arXiv cs.IT 2010
Year: 2010

Collaborative Spectrum Sensing (CSS) between secondary users (SUs) in cognitive networks exhibits an inherent tradeoff between minimizing the probability of missing the detection of the primary user (PU) and maintaining a reasonable false alarm probability (e.g., for maintaining a good spectrum utilization). In this paper, we study the impact of this tradeoff on the network structure and the cooperative incentives of the SUs that seek to cooperate for improving their detection performance. We model the CSS problem as a non-transferable coalitional game, and we propose distributed algorithms for coalition formation. First, we construct a distributed coalition formation (CF) algorithm that allows the SUs to self-organize into disjoint coalitions while accounting for the CSS tradeoff. Then, the CF algorithm is complemented with a coalitional voting game for enabling distributed coalition formation with detection probability guarantees (CF-PD) when required by the PU. The CF-PD algorithm allows the SUs to form minimal winning coalitions (MWCs), i.e., coalitions that achieve the target detection probability with minimal costs. For both algorithms, we study and prove various properties pertaining to network structure, adaptation to mobility and stability. Simulation results show that CF reduces the average probability of miss per SU up to 88.45% relative to the non-cooperative case, while maintaining a desired false alarm. For CF-PD, the results show that up to 87.25% of the SUs achieve the required detection probability through MWC
Treillis des concepts skylines : Analyse multidimensionnelle des skylines fondée sur les ensembles en accord
Venue: arXiv cs.DB 2010
Year: 2010

The skyline concept has been introduced in order to exhibit the best objects according to all the criterion combinations and makes it possible to analyse the relationships between skyline objects. Like the data cube, the skycube is so voluminous that reduction approaches are really necessary. In this paper, we define an approach which partially materializes the skycube. The underlying idea is to discard from the representation the skycuboids which can be computed again the most easily. To meet this reduction objective, we characterize a formal framework: the agree concept lattice. From this structure, we derive the skyline concept lattice which is one of its constrained instances. The strong points of our approach are: (i) it is attribute oriented; (ii) it provides a boundary for the number of lattice nodes; (iii) it facilitates the navigation within the Skycuboids.
Collaborative Sources Identification in Mixed Signals via Hierarchical Sparse Modeling
Venue: arXiv cs.CV 2010
Year: 2010

A collaborative framework for detecting the different sources in mixed signals is presented in this paper. The approach is based on C-HiLasso, a convex collaborative hierarchical sparse model, and proceeds as follows. First, we build a structured dictionary for mixed signals by concatenating a set of sub-dictionaries, each one of them learned to sparsely model one of a set of possible classes. Then, the coding of the mixed signal is performed by efficiently solving a convex optimization problem that combines standard sparsity with group and collaborative sparsity. The present sources are identified by looking at the sub-dictionaries automatically selected in the coding. The collaborative filtering in C-HiLasso takes advantage of the temporal/spatial redundancy in the mixed signals, letting collections of samples collaborate in identifying the classes, while allowing individual samples to have different internal sparse representations. This collaboration is critical to further stabilize the sparse representation of signals, in particular the class/sub-dictionary selection. The internal sparsity inside the sub-dictionaries, as naturally incorporated by the hierarchical aspects of C-HiLasso, is critical to make the model consistent with the essence of the sub-dictionaries that have been trained for sparse representation of each individual class. We present applications from speaker and instrument identification and texture separation. In the case of audio signals, we use sparse modeling to describe the short-term power spectrum envelopes of harmonic sounds. The proposed pitch independent method automatically detects the number of sources on a recording.
The Capacity Region of the 3-User Gaussian Interference Channel with Mixed Strong-Very Strong Interference
Venue: arXiv cs.IT 2010
Year: 2010

We consider the 3-user Gaussian interference channel and provide an outer bound on its capacity region. Under some conditions, which we call the mixed strong-very strong interference conditions, this outer bound is achievable. These conditions correspond to the case where at each receiver, one transmitter is causing strong interference and the other is causing very strong interference. Therefore, we characterize the capacity region of the 3-user interference channel with mixed strong-very strong interference.
Towards Constraint-based High Performance Cloud System in the Process of Cloud Computing Adoption in an Organization
Venue: arXiv cs.DC 2010
Year: 2010

Cloud computing is penetrating into various domains and environments, from theoretical computer science to economy, from marketing hype to educational curriculum and from R&D lab to enterprise IT infrastructure. Yet, the currently developing state of cloud computing leaves several issues to address and also affects cloud computing adoption by organizations. In this paper, we explain how the transition into the cloud can occur in an organization and describe the mechanism for transforming legacy infrastructure into a virtual infrastructure-based cloud. We describe the state of the art of infrastructural cloud, which is essential in the decision making on cloud adoption, and highlight the challenges that can limit the scale and speed of the adoption. We then suggest a strategic framework for designing a high performance cloud system. This framework is applicable when transformation cloudbased deployment model collides with some constraints. We give an example of the implementation of the framework in a design of a budget-constrained high availability cloud system.
Server Consolidation: An Approach to make Data Centers Energy Efficient and Green
Venue: arXiv cs.OH 2010
Year: 2010

Data centers are the building blocks of IT business organizations providing the capabilities of centralized repository for storage, management, networking and dissemination of data. With the rapid increase in the capacity and size of data centers, there is a continuous increase in the demand for energy consumption. These data centers not only consume a tremendous amount of energy but are riddled with IT inefficiencies. All data center are plagued with thousands of servers as major components. These servers consume huge energy without performing useful work. In an average server environment, 30% of the servers are "dead" only consuming energy, without being properly utilized. Their utilization ratio is only 5 to 10 percent. This paper focuses on the use of an emerging technology called virtualization to achieve energy efficient data centers by providing a solution called server consolidation. It increases the utilization ratio up to 50% saving huge amount of energy. Server consolidation helps in implementing green data centers to ensure that IT infrastructure contributes as little as possible to the emission of green house gases, and helps to regain power and cooling capacity, recapture resilience and dramatically reducing energy costs and total cost of ownership.
It takes half the energy of a photon to send one bit reliably on the Poisson channel with feedback
Venue: arXiv cs.IT 2010
Year: 2010

We consider the transmission of a single bit over the continuous-time Poisson channel with noiseless feedback. We show that to send the bit reliably requires, on the average, half the energy of a photon. In the absence of peak-power constraints this holds irrespective of the intensity of the dark current. We also solve for the energy required to send $log_{2} M$ bits.
Combinatorial Characterization of Formal Languages
Venue: arXiv cs.FL 2010
Year: 2010

This paper is an extended abstract of the dissertation presented by the author for the doctoral degree in physics and mathematics (in Russia). The main characteristic studied in the dissertation is combinatorial complexity, which is a "counting" function associated with a language and returning the number of words of given length in this language. For several classes of languages, a variety of problems about combinatorial complexity and its connections to other parameters of languages are studied. A brief introduction to the topic and the formulations of results are presented. No proofs are given; instead, the papers containing the proofs are cited.