OpenRaiser/Intern-Atlas huggingface dataset:
Comprehensive measurement framework for enterprise architectures
Venue: arXiv cs.SE 2011
Year: 2011

Enterprise Architecture defines the overall form and function of systems across an enterprise involving the stakeholders and providing a framework, standards and guidelines for project-specific architectures. Project-specific Architecture defines the form and function of the systems in a project or program, within the context of the enterprise as a whole with broad scope and business alignments. Application-specific Architecture defines the form and function of the applications that will be developed to realize functionality of the system with narrow scope and technical alignments. Because of the magnitude and complexity of any enterprise integration project, a major engineering and operations planning effort must be accomplished prior to any actual integration work. As the needs and the requirements vary depending on their volume, the entire enterprise problem can be broken into chunks of manageable pieces. These pieces can be implemented and tested individually with high integration effort. Therefore it becomes essential to analyze the economic and technical feasibility of realizable enterprise solution. It is difficult to migrate from one technological and business aspect to other as the enterprise evolves. The existing process models in system engineering emphasize on life-cycle management and low-level activity coordination with milestone verification. Many organizations are developing enterprise architecture to provide a clear vision of how systems will support and enable their business. The paper proposes an approach for selection of suitable enterprise architecture depending on the measurement framework. The framework consists of unique combination of higher order goals, non-functional requirement support and inputs-outcomes pair evaluation. The earlier efforts in this regard were concerned about only custom scales indicating the availability of a parameter in a range.
Maximizing the Cohesion is NP-hard
Venue: arXiv cs.NI 2011
Year: 2011

We show that the problem of finding a set with maximum cohesion in an undirected network is NP-hard.
Constraint-Based Deadlock Checking of High-Level Specifications
Venue: arXiv cs.LO 2011
Year: 2011

Establishing the absence of deadlocks is important in many applications of formal methods. The use of model checking for finding deadlocks in formal models is often limited. In this paper we propose a constraint-based approach to finding deadlocks employing the ProB constraint solver. We present the general technique, as well as various improvements that had to be performed on ProB's Prolog kernel, such as reification of membership and arithmetic constraints. This work was guided by an industrial case study, where a team from Bosch was modeling a cruise control system. Within this case study, ProB was able to quickly find counter examples to very large deadlock-freedom constraints. In the paper, we also present other successful applications of this new technique. Experiments using SAT and SMT solvers on these constraints were thus far unsuccessful.
Text mining and visualization using VOSviewer
Venue: arXiv cs.DL 2011
Year: 2011

VOSviewer is a computer program for creating, visualizing, and exploring bibliometric maps of science. In this report, the new text mining functionality of VOSviewer is presented. A number of examples are given of applications in which VOSviewer is used for analyzing large amounts of text data.
On the Impossibility of Black-Box Transformations in Mechanism Design
Venue: arXiv cs.GT 2011
Year: 2011

We consider the problem of converting an arbitrary approximation algorithm for a single-parameter optimization problem into a computationally efficient truthful mechanism. We ask for reductions that are black-box, meaning that they require only oracle access to the given algorithm and in particular do not require explicit knowledge of the problem constraints. Such a reduction is known to be possible, for example, for the social welfare objective when the goal is to achieve Bayesian truthfulness and preserve social welfare in expectation. We show that a black-box reduction for the social welfare objective is not possible if the resulting mechanism is required to be truthful in expectation and to preserve the worst-case approximation ratio of the algorithm to within a subpolynomial factor. Further, we prove that for other objectives such as makespan, no black-box reduction is possible even if we only require Bayesian truthfulness and an average-case performance guarantee.
Evidence-Based Comparison of Modularity Support Between Java and Object Teams
Venue: arXiv cs.SE 2011
Year: 2011

Background: Aspect-oriented programming (AOP) is an emerging programming paradigm whose focus is about improving modularity, with an emphasis on the modularization of crosscutting concerns. Objective: The goal of this paper is to assess the extent to which an AOP language -ObjectTeams/Java (OT/J) -improves the modularity of a software system. This improvement has been claimed but, to the best of our knowledge, this paper is the first attempting to present quantitative evidence of it. Method: We compare functionally-equivalent implementations of the Gang-of-Four design patterns, developed in Java and OT/J, using software metrics. Results: The results of our comparison support the modularity improvement claims made in the literature. For six of the seven metrics used, the OT/J versions of the patterns obtained significantly better results. Limitations: This work uses a set of metrics originally defined for object-oriented (OO) systems. It may be the case that the metrics are biased, in that they were created in the context of OO programming (OOP), before the advent of AOP. We consider this comparison a stepping stone as, ultimately, we plan to assess the modularity improvements with paradigm independent metrics, which will conceivably eliminate the bias. Each individual example from the sample used in this paper is small. In future, we plan to replicate this experiment using larger systems, where the benefits of AOP may be more noticeable. Conclusion: This work contributes with evidence to fill gaps in the body of quantitative results supporting alleged benefits to software modularity brought by AOP languages, namely OT/J.
Online Learning Algorithms for Stochastic Water-Filling
Venue: arXiv cs.LG 2011
Year: 2011

Water-filling is the term for the classic solution to the problem of allocating constrained power to a set of parallel channels to maximize the total data-rate. It is used widely in practice, for example, for power allocation to sub-carriers in multi-user OFDM systems such as WiMax. The classic water-filling algorithm is deterministic and requires perfect knowledge of the channel gain to noise ratios. In this paper we consider how to do power allocation over stochastically time-varying (i.i.d.) channels with unknown gain to noise ratio distributions. We adopt an online learning framework based on stochastic multi-armed bandits. We consider two variations of the problem, one in which the goal is to find a power allocation to maximize $\sum\limits_i \mathbb{E}[\log(1 + SNR_i)]$, and another in which the goal is to find a power allocation to maximize $\sum\limits_i \log(1 + \mathbb{E}[SNR_i])$. For the first problem, we propose a \emph{cognitive water-filling} algorithm that we call CWF1. We show that CWF1 obtains a regret (defined as the cumulative gap over time between the sum-rate obtained by a distribution-aware genie and this policy) that grows polynomially in the number of channels and logarithmically in time, implying that it asymptotically achieves the optimal time-averaged rate that can be obtained when the gain distributions are known. For the second problem, we present an algorithm called CWF2, which is, to our knowledge, the first algorithm in the literature on stochastic multi-armed bandits to exploit non-linear dependencies between the arms. We prove that the number of times CWF2 picks the incorrect power allocation is bounded by a function that is polynomial in the number of channels and logarithmic in time, implying that its frequency of incorrect allocation tends to zero.
A local strengthening of Reed's ω, Δ, χ conjecture for quasi-line graphs
Venue: arXiv cs.DM 2011
Year: 2011

Reed's $ω$, $Δ$, $χ$ conjecture proposes that every graph satisfies $χ\leq \lceil\frac 12(Δ+1+ω)\rceil$; it is known to hold for all claw-free graphs. In this paper we consider a local strengthening of this conjecture. We prove the local strengthening for line graphs, then note that previous results immediately tell us that the local strengthening holds for all quasi-line graphs. Our proofs lead to polytime algorithms for constructing colourings that achieve our bounds: $O(n^2)$ for line graphs and $O(n^3m^2)$ for quasi-line graphs. For line graphs, this is faster than the best known algorithm for constructing a colouring that achieves the bound of Reed's original conjecture.
Relational Dynamic Bayesian Networks
Venue: arXiv cs.AI 2011
Year: 2011

Stochastic processes that involve the creation of objects and relations over time are widespread, but relatively poorly studied. For example, accurate fault diagnosis in factory assembly processes requires inferring the probabilities of erroneous assembly operations, but doing this efficiently and accurately is difficult. Modeled as dynamic Bayesian networks, these processes have discrete variables with very large domains and extremely high dimensionality. In this paper, we introduce relational dynamic Bayesian networks (RDBNs), which are an extension of dynamic Bayesian networks (DBNs) to first-order logic. RDBNs are a generalization of dynamic probabilistic relational models (DPRMs), which we had proposed in our previous work to model dynamic uncertain domains. We first extend the Rao-Blackwellised particle filtering described in our earlier work to RDBNs. Next, we lift the assumptions associated with Rao-Blackwellization in RDBNs and propose two new forms of particle filtering. The first one uses abstraction hierarchies over the predicates to smooth the particle filters estimates. The second employs kernel density estimation with a kernel function specifically designed for relational domains. Experiments show these two methods greatly outperform standard particle filtering on the task of assembly plan execution monitoring.
Logical Hidden Markov Models
Venue: arXiv cs.AI 2011
Year: 2011

Logical hidden Markov models (LOHMMs) upgrade traditional hidden Markov models to deal with sequences of structured symbols in the form of logical atoms, rather than flat characters. This note formally introduces LOHMMs and presents solutions to the three central inference problems for LOHMMs: evaluation, most likely hidden state sequence and parameter estimation. The resulting representation and algorithms are experimentally evaluated on problems from the domain of bioinformatics.
mGPT: A Probabilistic Planner Based on Heuristic Search
Venue: arXiv cs.AI 2011
Year: 2011

We describe the version of the GPT planner used in the probabilistic track of the 4th International Planning Competition (IPC-4). This version, called mGPT, solves Markov Decision Processes specified in the PPDDL language by extracting and using different classes of lower bounds along with various heuristic-search algorithms. The lower bounds are extracted from deterministic relaxations where the alternative probabilistic effects of an action are mapped into different, independent, deterministic actions. The heuristic-search algorithms use these lower bounds for focusing the updates and delivering a consistent value function over all states reachable from the initial state and the greedy policy.
Macro-FF: Improving AI Planning with Automatically Learned Macro-Operators
Venue: arXiv cs.AI 2011
Year: 2011

Despite recent progress in AI planning, many benchmarks remain challenging for current planners. In many domains, the performance of a planner can greatly be improved by discovering and exploiting information about the domain structure that is not explicitly encoded in the initial PDDL formulation. In this paper we present and compare two automated methods that learn relevant information from previous experience in a domain and use it to solve new problem instances. Our methods share a common four-step strategy. First, a domain is analyzed and structural information is extracted, then macro-operators are generated based on the previously discovered structure. A filtering and ranking procedure selects the most useful macro-operators. Finally, the selected macros are used to speed up future searches. We have successfully used such an approach in the fourth international planning competition IPC-4. Our system, Macro-FF, extends Hoffmanns state-of-the-art planner FF 2.3 with support for two kinds of macro-operators, and with engineering enhancements. We demonstrate the effectiveness of our ideas on benchmarks from international planning competitions. Our results indicate a large reduction in search effort in those complex domains where structural information can be inferred.
Side Effects in Steering Fragments
Venue: arXiv cs.LO 2011
Year: 2011

In this thesis I will give a formal definition of side effects. I will do so by modifying a system for modelling program instructions and program states, Quantified Dynamic Logic, to a system called DLAf (for Dynamic Logic with Assignments as Formulas), which in contrast to QDL allows assignments in formulas and makes use of short-circuit evaluation. I will show the underlying logic in those formulas to be a variant of short-circuit logic called repetition-proof short-circuit logic. Using DLAf I will define the actual and the expected evaluation of a single instruction. The side effects are then defined to be the difference between the two. I will give rules for composing those side effects in single instructions, thus scaling up our definition of side effects to a definition of side effects in deterministic \dlaf-programs. Using this definition I will give a classification of side effects, introducing as most important class that of marginal side effects. Finally, I will show how to use our system for calculating the side effects in a real system such as Program Algebra (PGA).
A Learning Theory Approach to Non-Interactive Database Privacy
Venue: arXiv cs.DS 2011
Year: 2011

In this paper we demonstrate that, ignoring computational constraints, it is possible to privately release synthetic databases that are useful for large classes of queries -- much larger in size than the database itself. Specifically, we give a mechanism that privately releases synthetic data for a class of queries over a discrete domain with error that grows as a function of the size of the smallest net approximately representing the answers to that class of queries. We show that this in particular implies a mechanism for counting queries that gives error guarantees that grow only with the VC-dimension of the class of queries, which itself grows only logarithmically with the size of the query class. We also show that it is not possible to privately release even simple classes of queries (such as intervals and their generalizations) over continuous domains. Despite this, we give a privacy-preserving polynomial time algorithm that releases information useful for all halfspace queries, given a slight relaxation of the utility guarantee. This algorithm does not release synthetic data, but instead another data structure capable of representing an answer for each query. We also give an efficient algorithm for releasing synthetic data for the class of interval queries and axis-aligned rectangles of constant dimension. Finally, inspired by learning theory, we introduce a new notion of data privacy, which we call distributional privacy, and show that it is strictly stronger than the prevailing privacy notion, differential privacy.
On Phase Transition of Compressed Sensing in the Complex Domain
Venue: arXiv cs.IT 2011
Year: 2011

The phase transition is a performance measure of the sparsity-undersampling tradeoff in compressed sensing (CS). This letter reports our first observation and evaluation of an empirical phase transition of the $\ell_1$ minimization approach to the complex valued CS (CVCS), which is positioned well above the known phase transition of the real valued CS in the phase plane. This result can be considered as an extension of the existing phase transition theory of the block-sparse CS (BSCS) based on the universality argument, since the CVCS problem does not meet the condition required by the phase transition theory of BSCS but its observed phase transition coincides with that of BSCS. Our result is obtained by applying the recently developed ONE-L1 algorithms to the empirical evaluation of the phase transition of CVCS.
Convergence Analysis of Saddle Point Problems in Time Varying Wireless Systems - Control Theoretical Approach
Venue: arXiv cs.IT 2011
Year: 2011

Saddle point problems arise from many wireless applications, and primal-dual iterative algorithms are widely applied to find the saddle points. In the existing literature, the convergence results of such algorithms are established assuming the problem specific parameters remain unchanged during the iterations. However, this assumption is unrealistic in time varying wireless systems, as explicit message passing is usually involved in the iterations and the channel state information (CSI) may change in a time scale comparable to the algorithm update period. This paper investigates the convergence behavior and the tracking error of primal-dual iterative algorithms under time varying CSI. The convergence results are established by studying the stability of an equivalent virtual dynamic system derived in the paper, and the Lyapunov theory is applied for the stability analysis. We show that the average tracking error is proportional to the time variation rate of the CSI. Based on these analyses, we also derive an adaptive primal-dual algorithm by introducing a compensation term to reduce the tracking error under the time varying CSI.
Spherical coverage verification
Venue: arXiv cs.CG 2011
Year: 2011

We consider the problem of covering hypersphere by a set of spherical hypercaps. This sort of problem has numerous practical applications such as error correcting codes and reverse k-nearest neighbor problem. Using the reduction of non degenerated concave quadratic programming (QP) problem, we demonstrate that spherical coverage verification is NP hard. We propose a recursive algorithm based on reducing the problem to several lower dimension subproblems. We test the performance of the proposed algorithm on a number of generated constellations. We demonstrate that the proposed algorithm, in spite of its exponential worst-case complexity, is applicable in practice. In contrast, our results indicate that spherical coverage verification using QP solvers that utilize heuristics, due to numerical instability, may produce false positives.
Stratified Static Analysis Based on Variable Dependencies
Venue: arXiv cs.PL 2011
Year: 2011

In static analysis by abstract interpretation, one often uses widening operators in order to enforce convergence within finite time to an inductive invariant. Certain widening operators, including the classical one over finite polyhedra, exhibit an unintuitive behavior: analyzing the program over a subset of its variables may lead a more precise result than analyzing the original program! In this article, we present simple workarounds for such behavior.
The Evolution of the Cuban HIV/AIDS Network
Venue: arXiv cs.SI 2011
Year: 2011

An individual detected as HIV positive in Cuba is asked to provide a list of his/her sexual contacts for the previous 2 years. This allows one to gather detailed information on the spread of the HIV epidemic. Here we study the evolution of the sexual contact graph of detected individuals and also the directed graph of HIV infections. The study covers the Cuban HIV epidemic between the years 1986 and 2004 inclusive and is motivated by an earlier study on the static properties of the network at the end of 2004. We use a variety of advanced graph algorithms to paint a picture of the growth of the epidemic, including an examination of diameters, geodesic distances, community structure and centrality amongst others characteristics. The analysis contrasts the HIV network with other real networks, and graphs generated using the configuration model. We find that the early epidemic starts in the heterosexual population and then grows mainly through MSM (Men having Sex with Men) contact. The epidemic exhibits a giant component which is shown to have degenerate chains of vertices and after 1989, diameters are larger than that expected by the equivalent configuration model graphs. In 1997 there is an significant increase in the detection rate from 73 to 256 detections/year covering mainly MSMs which results in a rapid increase of distances and diameters in the giant component.
Quantization of Prior Probabilities for Collaborative Distributed Hypothesis Testing
Venue: arXiv cs.IT 2011
Year: 2011

This paper studies the quantization of prior probabilities, drawn from an ensemble, for distributed detection and data fusion. Design and performance equivalences between a team of N agents tied by a fixed fusion rule and a more powerful single agent are obtained. Effects of identical quantization and diverse quantization are compared. Consideration of perceived common risk enables agents using diverse quantizers to collaborate in hypothesis testing, and it is proven that the minimum mean Bayes risk error is achieved by diverse quantization. The comparison shows that optimal diverse quantization with K cells per quantizer performs as well as optimal identical quantization with N(K-1)+1 cells per quantizer. Similar results are obtained for maximum Bayes risk error as the distortion criterion.
In Things We Trust? Towards trustability in the Internet of Things
Venue: arXiv cs.CR 2011
Year: 2011

This essay discusses the main privacy, security and trustability issues with the Internet of Things.
Secure Broadcasting With Side-Information
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we derive information-theoretic performance limits for secure and reliable communications over the general two-user discrete memoryless broadcast channel with side-information at the transmitter. The sender wishes to broadcast two independent messages to two receivers, under the constraint that each message should be kept confidential from the unintended receiver. Furthermore, the encoder has side-information - for example, fading in the wireless medium, interference caused by neighboring nodes in the network, etc. - provided to it in a noncausal manner, i.e., before the process of transmission. We derive an inner bound on the capacity region of this channel, by employing an extension of Marton's coding technique used for the classical two-user broadcast channel, in conjunction with a stochastic encoder to satisfy confidentiality constraints. Based on previously known results, we discuss a procedure to present a schematic of the achievable rate region. The rate-penalties for dealing with side-information and confidentiality constraints make the achievable region for this channel strictly smaller than the rate regions of those channels where one or both of these constraints are relaxed.