OpenRaiser/Intern-Atlas huggingface dataset:
A model and framework for reliable build systems
Venue: arXiv cs.SE 2012
Year: 2012

Reliable and fast builds are essential for rapid turnaround during development and testing. Popular existing build systems rely on correct manual specification of build dependencies, which can lead to invalid build outputs and nondeterminism. We outline the challenges of developing reliable build systems and explore the design space for their implementation, with a focus on non-distributed, incremental, parallel build systems. We define a general model for resources accessed by build tasks and show its correspondence to the implementation technique of minimum information libraries, APIs that return no information that the application doesn't plan to use. We also summarize preliminary experimental results from several prototype build managers.
Analysis of Finite Field Spreading for Multiple-Access Channel
Venue: arXiv cs.IT 2012
Year: 2012

Finite field spreading scheme is proposed for a synchronous multiple-access channel with Gaussian noise and equal-power users. For each user, $s$ information bits are spread \emph{jointly} into a length-$sL$ vector by $L$ multiplications on GF($2^s$). Thus, each information bit is dispersed into $sL$ transmitted symbols, and the finite field despreading (FF-DES) of each bit can take advantage of $sL$ independent receiving observations. To show the performance gain of joint spreading quantitatively, an extrinsic information transfer (EXIT) function analysis of the FF-DES is given. It shows that the asymptotic slope of this EXIT function increases as $s$ increases and is in fact the absolute slope of the bit error rate (BER) curve at the low BER region. This means that by increasing the length $s$ of information bits for joint spreading, a larger absolute slope of the BER curve is achieved. For $s, L\geq 2$, the BER curve of the finite field spreading has a larger absolute slope than that of the single-user transmission with BPSK modulation.
On the Complexity of the Minimum Latency Scheduling Problem on the Euclidean Plane
Venue: arXiv cs.NI 2012
Year: 2012

We show NP-hardness of the minimum latency scheduling (MLS) problem under the physical model of wireless networking. In this model a transmission is received successfully if the Signal to Interference-plus-Noise Ratio (SINR), is above a given threshold. In the minimum latency scheduling problem, the goal is to assign a time slot and power level to each transmission, so that all the messages are received successfully, and the number of distinct times slots is minimized. Despite its seeming simplicity and several previous hardness results for various settings of the minimum latency scheduling problem, it has remained an open question whether or not the minimum latency scheduling problem is NP-hard, when the nodes are placed in the Euclidean plane and arbitrary power levels can be chosen for the transmissions. We resolve this open question for all path loss exponent values $α\geq 3$.
Analyzing and enhancing OSKI for sparse matrix-vector multiplication
Venue: arXiv cs.NA 2012
Year: 2012

Sparse matrix-vector multiplication (SpMxV) is a kernel operation widely used in iterative linear solvers. The same sparse matrix is multiplied by a dense vector repeatedly in these solvers. Matrices with irregular sparsity patterns make it difficult to utilize cache locality effectively in SpMxV computations. In this work, we investigate single- and multiple-SpMxV frameworks for exploiting cache locality in SpMxV computations. For the single-SpMxV framework, we propose two cache-size-aware top-down row/column-reordering methods based on 1D and 2D sparse matrix partitioning by utilizing the column-net and enhancing the row-column-net hypergraph models of sparse matrices. The multiple-SpMxV framework depends on splitting a given matrix into a sum of multiple nonzero-disjoint matrices so that the SpMxV operation is performed as a sequence of multiple input- and output-dependent SpMxV operations. For an effective matrix splitting required in this framework, we propose a cache-size-aware top-down approach based on 2D sparse matrix partitioning by utilizing the row-column-net hypergraph model. The primary objective in all of the three methods is to maximize the exploitation of temporal locality. We evaluate the validity of our models and methods on a wide range of sparse matrices by performing actual runs through using OSKI. Experimental results show that proposed methods and models outperform state-of-the-art schemes.
Trade-off between cost and goodput in wireless: Replacing transmitters with coding
Venue: arXiv cs.NI 2012
Year: 2012

We study the cost of improving the goodput, or the useful data rate, to user in a wireless network. We measure the cost in terms of number of base stations, which is highly correlated to the energy cost as well as capital and operational costs of a network provider.We show that increasing the available bandwidth, or throughput, may not necessarily lead to increase in goodput, particularly in lossy wireless networks in which TCP does not perform well. As a result, much of the resources dedicated to the user may not translate to high goodput, resulting in an inefficient use of the network resources. We show that using protocols such as TCP/NC, which are more resilient to erasures and failures in the network, may lead to a goodput commensurate the throughput dedicated to each user. By increasing goodput, users' transactions are completed faster; thus, the resources dedicated to these users can be released to serve other requests or transactions. Consequently, we show that translating efficiently throughput to goodput may bring forth better connection to users while reducing the cost for the network providers.
BitPath -- Label Order Constrained Reachability Queries over Large Graphs
Venue: arXiv cs.DB 2012
Year: 2012

In this paper we focus on the following constrained reachability problem over edge-labeled graphs like RDF -- "given source node x, destination node y, and a sequence of edge labels (a, b, c, d), is there a path between the two nodes such that the edge labels on the path satisfy a regular expression "*a.*b.*c.*d.*". A "*" before "a" allows any other edge label to appear on the path before edge "a". "a.*" forces at least one edge with label "a". ".*" after "a" allows zero or more edge labels after "a" and before "b". Our query processing algorithm uses simple divide-and-conquer and greedy pruning procedures to limit the search space. However, our graph indexing technique -- based on "compressed bit-vectors" -- allows indexing large graphs which otherwise would have been infeasible. We have evaluated our approach on graphs with more than 22 million edges and 6 million nodes -- much larger compared to the datasets used in the contemporary work on path queries.
How Bad is Forming Your Own Opinion?
Venue: arXiv cs.GT 2012
Year: 2012

The question of how people form their opinion has fascinated economists and sociologists for quite some time. In many of the models, a group of people in a social network, each holding a numerical opinion, arrive at a shared opinion through repeated averaging with their neighbors in the network. Motivated by the observation that consensus is rarely reached in real opinion dynamics, we study a related sociological model in which individuals' intrinsic beliefs counterbalance the averaging process and yield a diversity of opinions. By interpreting the repeated averaging as best-response dynamics in an underlying game with natural payoffs, and the limit of the process as an equilibrium, we are able to study the cost of disagreement in these models relative to a social optimum. We provide a tight bound on the cost at equilibrium relative to the optimum; our analysis draws a connection between these agreement models and extremal problems that lead to generalized eigenvalues. We also consider a natural network design problem in this setting: which links can we add to the underlying network to reduce the cost of disagreement at equilibrium?
Hybrid Poisson and multi-Bernoulli filters
Venue: arXiv cs.SY 2012
Year: 2012

The probability hypothesis density (PHD) and multi-target multi-Bernoulli (MeMBer) filters are two leading algorithms that have emerged from random finite sets (RFS). In this paper we study a method which combines these two approaches. Our work is motivated by a sister paper, which proves that the full Bayes RFS filter naturally incorporates a Poisson component representing targets that have never been detected, and a linear combination of multi-Bernoulli components representing targets under track. Here we demonstrate the benefit (in speed of track initiation) that maintenance of a Poisson component of undetected targets provides. Subsequently, we propose a method of recycling, which projects Bernoulli components with a low probability of existence onto the Poisson component (as opposed to deleting them). We show that this allows us to achieve similar tracking performance using a fraction of the number of Bernoulli components (i.e., tracks).
A Protocol for the Atomic Capture of Multiple Molecules at Large Scale
Venue: arXiv cs.DC 2012
Year: 2012

With the rise of service-oriented computing, applications are more and more based on coordination of autonomous services. Envisioned over largely distributed and highly dynamic platforms, expressing this coordination calls for alternative programming models. The chemical programming paradigm, which models applications as chemical solutions where molecules representing digital entities involved in the computation, react together to produce a result, has been recently shown to provide the needed abstractions for autonomic coordination of services. However, the execution of such programs over large scale platforms raises several problems hindering this paradigm to be actually leveraged. Among them, the atomic capture of molecules participating in concur- rent reactions is one of the most significant. In this paper, we propose a protocol for the atomic capture of these molecules distributed and evolving over a large scale platform. As the density of possible reactions is crucial for the liveness and efficiency of such a capture, the protocol proposed is made up of two sub-protocols, each of them aimed at addressing different levels of densities of potential reactions in the solution. While the decision to choose one or the other is local to each node participating in a program's execution, a global coherent behaviour is obtained. Proof of liveness, as well as intensive simulation results showing the efficiency and limited overhead of the protocol are given.
Application of sensitivity analysis in building energy simulations: combining first and second order elementary effects Methods
Venue: arXiv cs.CE 2012
Year: 2012

Sensitivity analysis plays an important role in the understanding of complex models. It helps to identify influence of input parameters in relation to the outputs. It can be also a tool to understand the behavior of the model and then can help in its development stage. This study aims to analyze and illustrate the potential usefulness of combining first and second-order sensitivity analysis, applied to a building energy model (ESP-r). Through the example of a collective building, a sensitivity analysis is performed using the method of elementary effects (also known as Morris method), including an analysis of interactions between the input parameters (second order analysis). Importance of higher-order analysis to better support the results of first order analysis, highlighted especially in such complex model. Several aspects are tackled to implement efficiently the multi-order sensitivity analysis: interval size of the variables, management of non-linearity, usefulness of various outputs.
Set Reduction In Nonlinear Equations
Venue: arXiv cs.MS 2012
Year: 2012

In this paper, an idea to solve nonlinear equations is presented. During the solution of any problem with Newton's Method, it might happen that some of the unknowns satisfy the convergence criteria where the others fail. The convergence happens only when all variables reach to the convergence limit. A method to reduce the dimension of the overall system by excluding some of the unknowns that satisfy an intermediate tolerance is introduced. In this approach, a smaller system is solved in less amount of time and already established local solutions are preserved and kept as constants while the other variables that belong to the "set" will be relaxed. To realize the idea, an algorithm is given that utilizes applications of pointers to reduce and evaluate the sets. Matrix-free Newton-Krylov Techniques are used on a test problem and it is shown that proposed idea improves the overall convergence.
An Agile Method for E-Service Composition
Venue: arXiv cs.SE 2012
Year: 2012

Nowadays, application of Service Oriented Architecture is increasing rapidly; especially since introduction of distributed electronic services on the web. SOA software has a modular manner and works as a collaboration of independent software components. As a result, e-service approach is sufficient for software with independent components, each of which may be developed by a different company. Such software components and their cooperation form a composite service. Agile methodologies are the best candidate for developing small software components. Composite services and its building blocks are small pieces of software, making agile methodology a perfect fit for their development. In this paper, we introduce an agile method for service composition, inspired by agile patterns and practices. Therefore, across the agile manifesto, we can develop low cost, high quality composite services quickly using this method.
A Fast fixed-point Quantum Search Algorithm by using Disentanglement and Measurement
Venue: arXiv cs.IT 2012
Year: 2012

Generic quantum search algorithm searches for target entity in an unsorted database by repeatedly applying canonical Grover's quantum rotation transform to reach near the vicinity of the target entity. Thus, upon measurement, there is a high probability of finding the target entity. However, the number of times quantum rotation transform is to be applied for reaching near the vicinity of the target is a function of the number of target entities present in an unsorted database, which is generally unknown. A wrong estimate of the number of target entities can lead to overshooting or undershooting the targets, thus reducing the success probability. Some proposals have been made to overcome this limitation. These proposals either employ quantum counting to estimate the number of solutions or fixed-point schemes. This paper proposes a new scheme for stopping the application of quantum rotation transformation on reaching near the targets by disentanglement, measurement and subsequent processing to estimate the distance of the state vector from the target states. It ensures a success probability, which is greater than half for all practically significant ratios of the number of target entities to the total number of entities in a database. The search problem is trivial for remaining possible ratios. The proposed scheme is simpler than quantum counting and more efficient than the known fixed-point schemes. It has same order of computational complexity as canonical Grover`s search algorithm but is slow by a factor of two and requires two additional ancilla qubits.
An efficient algorithm for generating AoA networks
Venue: arXiv cs.DM 2012
Year: 2012

The activities, in project scheduling, can be represented graphically in two different ways, by either assigning the activities to the nodes 'AoN' directed acyclic graph (dag) or to the arcs 'AoA dag'. In this paper, a new algorithm is proposed for generating, for a given project scheduling problem, an Activity-on-Arc dag starting from the Activity-on-Node dag using the concepts of line graphs of graphs.
Revisiting the Complexity of And/Or Graph Solution
Venue: arXiv cs.CC 2012
Year: 2012

This paper presents a study on two data structures that have been used to model several problems in computer science: and/or graphs and x-y graphs. An and/or graph is an acyclic digraph containing a source, such that every vertex v has a label f(v) \in {and,or} and edges represent dependency relations between vertices: a vertex labeled and depends on all of its out-neighbors, while a vertex labeled or depends on only one of its out-neighbors. X-y graphs are defined as a natural generalization of and/or graphs: every vertex vi of an x-y graph has a label xi-yi to mean that vi depends on xi of its yi out-neighbors. We analyze the complexity of the optimization problems Min-and/or and Min-x-y, which consist of finding solution subgraphs of optimal weight for and/or and x-y graphs, respectively. Motivated by the large applicability as well as the hardness of Min-and/or and Min-x-y, we study new complexity aspects of such problems, both from a classical and a parameterized point of view. We prove that Min-and/or remains NP-hard even for a very restricted family of and/or graphs where edges have weight one and or-vertices have out-degree at most two (apart from other property related to some in-degrees), and that deciding whether there is a solution subtree with weight exactly k of a given x-y tree is also NP-hard. We also show that: (i) the parameterized problem Min-and/or(k, r), which asks whether there is a solution subgraph of weight at most k where every or-vertex has at most r out-edges with the same weight, is FPT; (ii) the parameterized problem Min-and/or0(k), whose domain includes and/or graphs allowing zero-weight edges, is W[2]-hard; (iii) the parameterized problem Min-x-y(k) is W[1]-hard.
Observability of Turing Machines: a Refinement of the Theory of Computation
Venue: arXiv cs.CC 2012
Year: 2012

The Turing machine is one of the simple abstract computational devices that can be used to investigate the limits of computability. In this paper, they are considered from several points of view that emphasize the importance and the relativity of mathematical languages used to describe the Turing machines. A deep investigation is performed on the interrelations between mechanical computations and their mathematical descriptions emerging when a human (the researcher) starts to describe a Turing machine (the object of the study) by different mathematical languages (the instruments of investigation). Together with traditional mathematical languages using such concepts as 'enumerable sets' and 'continuum' a new computational methodology allowing one to measure the number of elements of different infinite sets is used in this paper. It is shown how mathematical languages used to describe the machines limit our possibilities to observe them. In particular, notions of observable deterministic and non-deterministic Turing machines are introduced and conditions ensuring that the latter can be simulated by the former are established.
The Automorphism Group of an Extremal [72,36,16] Code does not contain elements of order 6
Venue: arXiv cs.IT 2012
Year: 2012

The existence of an extremal code of length 72 is a long-standing open problem. Let C be a putative extremal code of length 72 and suppose that C has an automorphism g of order 6. We show that C, as an F_2<g>-module, is the direct sum of two modules, one easily determinable and the other one which has a very restrictive structure. We use this fact to do an exhaustive search and we do not find any code. This proves that the automorphism group of an extremal code of length 72 does not contain elements of order 6.
A Scalable Method for Solving High-Dimensional Continuous POMDPs Using Local Approximation
Venue: arXiv cs.AI 2012
Year: 2012

Partially-Observable Markov Decision Processes (POMDPs) are typically solved by finding an approximate global solution to a corresponding belief-MDP. In this paper, we offer a new planning algorithm for POMDPs with continuous state, action and observation spaces. Since such domains have an inherent notion of locality, we can find an approximate solution using local optimization methods. We parameterize the belief distribution as a Gaussian mixture, and use the Extended Kalman Filter (EKF) to approximate the belief update. Since the EKF is a first-order filter, we can marginalize over the observations analytically. By using feedback control and state estimation during policy execution, we recover a behavior that is effectively conditioned on incoming observations despite the unconditioned planning. Local optimization provides no guarantees of global optimality, but it allows us to tackle domains that are at least an order of magnitude larger than the current state-of-the-art. We demonstrate the scalability of our algorithm by considering a simulated hand-eye coordination domain with 16 continuous state dimensions and 6 continuous action dimensions.
Robust LogitBoost and Adaptive Base Class (ABC) LogitBoost
Venue: arXiv cs.LG 2012
Year: 2012

Logitboost is an influential boosting algorithm for classification. In this paper, we develop robust logitboost to provide an explicit formulation of tree-split criterion for building weak learners (regression trees) for logitboost. This formulation leads to a numerically stable implementation of logitboost. We then propose abc-logitboost for multi-class classification, by combining robust logitboost with the prior work of abc-boost. Previously, abc-boost was implemented as abc-mart using the mart algorithm. Our extensive experiments on multi-class classification compare four algorithms: mart, abcmart, (robust) logitboost, and abc-logitboost, and demonstrate the superiority of abc-logitboost. Comparisons with other learning methods including SVM and deep learning are also available through prior publications.
Dirichlet Process Mixtures of Generalized Mallows Models
Venue: arXiv cs.LG 2012
Year: 2012

We present a Dirichlet process mixture model over discrete incomplete rankings and study two Gibbs sampling inference techniques for estimating posterior clusterings. The first approach uses a slice sampling subcomponent for estimating cluster parameters. The second approach marginalizes out several cluster parameters by taking advantage of approximations to the conditional posteriors. We empirically demonstrate (1) the effectiveness of this approximation for improving convergence, (2) the benefits of the Dirichlet process model over alternative clustering techniques for ranked data, and (3) the applicability of the approach to exploring large realworld ranking datasets.
Characterizing the Set of Coherent Lower Previsions with a Finite Number of Constraints or Vertices
Venue: arXiv cs.AI 2012
Year: 2012

The standard coherence criterion for lower previsions is expressed using an infinite number of linear constraints. For lower previsions that are essentially defined on some finite set of gambles on a finite possibility space, we present a reformulation of this criterion that only uses a finite number of constraints. Any such lower prevision is coherent if it lies within the convex polytope defined by these constraints. The vertices of this polytope are the extreme coherent lower previsions for the given set of gambles. Our reformulation makes it possible to compute them. We show how this is done and illustrate the procedure and its results.