OpenRaiser/Intern-Atlas huggingface dataset:
When majority voting fails: Comparing quality assurance methods for noisy human computation environment
Venue: arXiv cs.SI 2012
Year: 2012

Quality assurance remains a key topic in human computation research. Prior work indicates that majority voting is effective for low difficulty tasks, but has limitations for harder tasks. This paper explores two methods of addressing this problem: tournament selection and elimination selection, which exploit 2-, 3- and 4-way comparisons between different answers to human computation tasks. Our experimental results and statistical analyses show that both methods produce the correct answer in noisy human computation environment more often than majority voting. Furthermore, we find that the use of 4-way comparisons can significantly reduce the cost of quality assurance relative to the use of 2-way comparisons.
An Algorithmic Solution for Computing Circle Intersection Areas and its Applications to Wireless Communications
Venue: arXiv cs.CG 2012
Year: 2012

A novel iterative algorithm for the efficient computation of the intersection areas of an arbitrary number of circles is presented. The algorithm, based on a trellis-structure, hinges on two geometric results which allow the existence-check and the computation of the area of the intersection regions generated by more than three circles by simple algebraic manipulations of the intersection areas of a smaller number of circles. The presented algorithm is a powerful tool for the performance analysis of wireless networks, and finds many applications, ranging from sensor to cellular networks. As an example of practical application, an insightful study of the uplink outage probability of in a wireless network with cooperative access points as a function of the transmission power and access point density is presented.
Distributed Iterative Processing for Interference Channels with Receiver Cooperation
Venue: arXiv cs.IT 2012
Year: 2012

We propose a framework for the derivation and evaluation of distributed iterative algorithms for receiver cooperation in interference-limited wireless systems. Our approach views the processing within and collaboration between receivers as the solution to an inference problem in the probabilistic model of the whole system. The probabilistic model is formulated to explicitly incorporate the receivers' ability to share information of a predefined type. We employ a recently proposed unified message-passing tool to infer the variables of interest in the factor graph representation of the probabilistic model. The exchange of information between receivers arises in the form of passing messages along some specific edges of the factor graph; the rate of updating and passing these messages determines the communication overhead associated with cooperation. Simulation results illustrate the high performance of the proposed algorithm even with a low number of message exchanges between receivers.
Biographical Social Networks on Wikipedia - A cross-cultural study of links that made history
Venue: arXiv cs.SI 2012
Year: 2012

It is arguable whether history is made by great men and women or vice versa, but undoubtably social connections shape history. Analysing Wikipedia, a global collective memory place, we aim to understand how social links are recorded across cultures. Starting with the set of biographies in the English Wikipedia we focus on the networks of links between these biographical articles on the 15 largest language Wikipedias. We detect the most central characters in these networks and point out culture-related peculiarities. Furthermore, we reveal remarkable similarities between distinct groups of language Wikipedias and highlight the shared knowledge about connections between persons across cultures.
Distance Optimal Formation Control on Graphs with a Tight Convergence Time Guarantee
Venue: arXiv cs.SY 2012
Year: 2012

For the task of moving a set of indistinguishable agents on a connected graph with unit edge distance to an arbitrary set of goal vertices, free of collisions, we propose a fast distance optimal control algorithm that guides the agents into the desired formation. Moreover, we show that the algorithm also provides a tight convergence time guarantee (time optimality and distance optimality cannot be simultaneously satisfied). Our generic graph formulation allows the algorithm to be applied to scenarios such as grids with holes (modeling obstacles) in arbitrary dimensions. Simulations, available online, confirm our theoretical developments.
On how percolation threshold affects PSO performance
Venue: arXiv cs.AI 2012
Year: 2012

Statistical evidence of the influence of neighborhood topology on the performance of particle swarm optimization (PSO) algorithms has been shown in many works. However, little has been done about the implications could have the percolation threshold in determining the topology of this neighborhood. This work addresses this problem for individuals that, like robots, are able to sense in a limited neighborhood around them. Based on the concept of percolation threshold, and more precisely, the disk percolation model in 2D, we show that better results are obtained for low values of radius, when individuals occasionally ask others their best visited positions, with the consequent decrease of computational complexity. On the other hand, since percolation threshold is a universal measure, it could have a great interest to compare the performance of different hybrid PSO algorithms.
Low-Complexity Energy-Efficient Broadcasting in One-Dimensional Wireless Networks
Venue: arXiv cs.NI 2012
Year: 2012

In this paper, we investigate the transmission range assignment for N wireless nodes located on a line (a linear wireless network) for broadcasting data from one specific node to all the nodes in the network with minimum energy. Our goal is to find a solution that has low complexity and yet performs close to optimal. We propose an algorithm for finding the optimal assignment (which results in the minimum energy consumption) with complexity O(N^2). An approximation algorithm with complexity O(N) is also proposed. It is shown that, for networks with uniformly distributed nodes, the linear-time approximate solution obtained by this algorithm on average performs practically identical to the optimal assignment. Both the optimal and the suboptimal algorithms require the full knowledge of the network topology and are thus centralized. We also propose a distributed algorithm of negligible complexity, i.e., with complexity O(1), which only requires the knowledge of the adjacent neighbors at each wireless node. Our simulations demonstrate that the distributed solution on average performs almost as good as the optimal one for networks with uniformly distributed nodes.
Solution Representations and Local Search for the bi-objective Inventory Routing Problem
Venue: arXiv cs.AI 2012
Year: 2012

The solution of the biobjective IRP is rather challenging, even for metaheuristics. We are still lacking a profound understanding of appropriate solution representations and effective neighborhood structures. Clearly, both the delivery volumes and the routing aspects of the alternatives need to be reflected in an encoding, and must be modified when searching by means of local search. Our work contributes to the better understanding of such solution representations. On the basis of an experimental investigation, the advantages and drawbacks of two encodings are studied and compared.
Utilizing RxNorm to Support Practical Computing Applications: Capturing Medication History in Live Electronic Health Records
Venue: arXiv cs.DB 2012
Year: 2012

RxNorm was utilized as the basis for direct-capture of medication history data in a live EHR system deployed in a large, multi-state outpatient behavioral healthcare provider in the United States serving over 75,000 distinct patients each year across 130 clinical locations. This tool incorporated auto-complete search functionality for medications and proper dosage identification assistance. The overarching goal was to understand if and how standardized terminologies like RxNorm can be used to support practical computing applications in live EHR systems. We describe the stages of implementation, approaches used to adapt RxNorm's data structure for the intended EHR application, and the challenges faced. We evaluate the implementation using a four-factor framework addressing flexibility, speed, data integrity, and medication coverage. RxNorm proved to be functional for the intended application, given appropriate adaptations to address high-speed input/output (I/O) requirements of a live EHR and the flexibility required for data entry in multiple potential clinical scenarios. Future research around search optimization for medication entry, user profiling, and linking RxNorm to drug classification schemes holds great potential for improving the user experience and utility of medication data in EHRs.
Connectivity Oracles for Planar Graphs
Venue: arXiv cs.DS 2012
Year: 2012

We consider dynamic subgraph connectivity problems for planar graphs. In this model there is a fixed underlying planar graph, where each edge and vertex is either "off" (failed) or "on" (recovered). We wish to answer connectivity queries with respect to the "on" subgraph. The model has two natural variants, one in which there are $d$ edge/vertex failures that precede all connectivity queries, and one in which failures/recoveries and queries are intermixed. We present a $d$-failure connectivity oracle for planar graphs that processes any $d$ edge/vertex failures in $sort(d,n)$ time so that connectivity queries can be answered in $pred(d,n)$ time. (Here $sort$ and $pred$ are the time for integer sorting and integer predecessor search over a subset of $[n]$ of size $d$.) Our algorithm has two discrete parts. The first is an algorithm tailored to triconnected planar graphs. It makes use of Barnette's theorem, which states that every triconnected planar graph contains a degree-3 spanning tree. The second part is a generic reduction from general (planar) graphs to triconnected (planar) graphs. Our algorithm is, moreover, provably optimal. An implication of Patrascu and Thorup's lower bound on predecessor search is that no $d$-failure connectivity oracle (even on trees) can beat $pred(d,n)$ query time. We extend our algorithms to the subgraph connectivity model where edge/vertex failures (but no recoveries) are intermixed with connectivity queries. In triconnected planar graphs each failure and query is handled in $O(\log n)$ time (amortized), whereas in general planar graphs both bounds become $O(\log^2 n)$.
Entry and Spectrum Sharing Scheme Selection in Femtocell Markets
Venue: arXiv cs.GT 2012
Year: 2012

Focusing on a femtocell communications market, we study the entrant network service provider's (NSP's) long-term decision: whether to enter the market and which spectrum sharing technology to select to maximize its profit. This long-term decision is closely related to the entrant's pricing strategy and the users' aggregate demand, which we model as medium-term and short-term decisions, respectively. We consider two markets, one with no incumbent and the other with one incumbent. For both markets, we show the existence and uniqueness of an equilibrium point in the user subscription dynamics, and provide a sufficient condition for the convergence of the dynamics. For the market with no incumbent, we derive upper and lower bounds on the optimal price and market share that maximize the entrant's revenue, based on which the entrant selects an available technology to maximize its long-term profit. For the market with one incumbent, we model competition between the two NSPs as a non-cooperative game, in which the incumbent and the entrant choose their market shares independently, and provide a sufficient condition that guarantees the existence of at least one pure Nash equilibrium. Finally, we formalize the problem of entry and spectrum sharing scheme selection for the entrant and provide numerical results to complement our analysis.
Learning in Riemannian Orbifolds
Venue: arXiv cs.LG 2012
Year: 2012

Learning in Riemannian orbifolds is motivated by existing machine learning algorithms that directly operate on finite combinatorial structures such as point patterns, trees, and graphs. These methods, however, lack statistical justification. This contribution derives consistency results for learning problems in structured domains and thereby generalizes learning in vector spaces and manifolds.
Avian Influenza (H5N1) Warning System using Dempster-Shafer Theory and Web Mapping
Venue: arXiv cs.AI 2012
Year: 2012

Based on Cumulative Number of Confirmed Human Cases of Avian Influenza (H5N1) Reported to World Health Organization (WHO) in the 2011 from 15 countries, Indonesia has the largest number death because Avian Influenza which 146 deaths. In this research, the researcher built a Web Mapping and Dempster-Shafer theory as early warning system of avian influenza. Early warning is the provision of timely and effective information, through identified institutions, that allows individuals exposed to a hazard to take action to avoid or reduce their risk and prepare for effective response. In this paper as example we use five symptoms as major symptoms which include depression, combs, wattle, bluish face region, swollen face region, narrowness of eyes, and balance disorders. Research location is in the Lampung Province, South Sumatera. The researcher reason to choose Lampung Province in South Sumatera on the basis that has a high poultry population. Geographically, Lampung province is located at 103040' to 105050' East Longitude and 6045' - 3045' South latitude, confined with: South Sumatera and Bengkulu on North Side, Sunda Strait on the Side, Java Sea on the East Side, Indonesia Ocean on the West Side. Our approach uses Dempster Shafer theory to combine beliefs in certain hypotheses under conditions of uncertainty and ignorance, and allows quantitative measurement of the belief and plausibility in our identification result. Web Mapping is also used for displaying maps on a screen to visualize the result of the identification process. The result reveal that avian influenza warning system has successfully identified the existence of avian influenza and the maps can be displayed as the visualization.
Change-Of-Bases Abstractions for Non-Linear Systems
Venue: arXiv cs.SC 2012
Year: 2012

We present abstraction techniques that transform a given non-linear dynamical system into a linear system or an algebraic system described by polynomials of bounded degree, such that, invariant properties of the resulting abstraction can be used to infer invariants for the original system. The abstraction techniques rely on a change-of-basis transformation that associates each state variable of the abstract system with a function involving the state variables of the original system. We present conditions under which a given change of basis transformation for a non-linear system can define an abstraction. Furthermore, the techniques developed here apply to continuous systems defined by Ordinary Differential Equations (ODEs), discrete systems defined by transition systems and hybrid systems that combine continuous as well as discrete subsystems. The techniques presented here allow us to discover, given a non-linear system, if a change of bases transformation involving degree-bounded polynomials yielding an algebraic abstraction exists. If so, our technique yields the resulting abstract system, as well. This approach is further extended to search for a change of bases transformation that abstracts a given non-linear system into a system of linear differential inclusions. Our techniques enable the use of analysis techniques for linear systems to infer invariants for non-linear systems. We present preliminary evidence of the practical feasibility of our ideas using a prototype implementation.
First-Order Quantifiers and the Syntactic Monoid of Height Fragments of Picture Languages
Venue: arXiv cs.FL 2012
Year: 2012

We investigate the expressive power of first-order quantifications in the context of monadic second-order logic over pictures. We show that k+1 set quantifier alternations allow to define a picture language that cannot be defined using k set quantifier alternations preceded by arbitrarily many first-order quantifier alternations. The approach uses, for a given picture language L and an integer m > 0 the height-m fragment of L, which is defined as the word language obtained by considering each picture p of height m in L as a word, where the letters of that word are the columns of p. A key idea is to measure the complexity of a regular word language by the group complexity of its syntactic monoid. Given a picture language L, such a word language measure may be applied to each of its height fragments, so that the complexity of the picture language is a function that maps each m to the complexity of the height-m fragment of L. The asymptotic growth rate of that function may be bounded based on the structure of a monadic second-order formula that defines L. The core argument for that lower bound proof is based on Straubing's algebraic characterization of the effect of first-order quantifiers on the syntactic monoid of word languages by means of Rhodes' and Tilson's block product.
Providing End-to-End Delay Guarantees for Multi-hop Wireless Sensor Networks over Unreliable Channels
Venue: arXiv cs.NI 2012
Year: 2012

Wireless sensor networks have been increasingly used for real-time surveillance over large areas. In such applications, it is important to support end-to-end delay constraints for packet deliveries even when the corresponding flows require multi-hop transmissions. In addition to delay constraints, each flow of real-time surveillance may require some guarantees on throughput of packets that meet the delay constraints. Further, as wireless sensor networks are usually deployed in challenging environments, it is important to specifically consider the effects of unreliable wireless transmissions. In this paper, we study the problem of providing end-to-end delay guarantees for multi-hop wireless networks. We propose a model that jointly considers the end-to-end delay constraints and throughput requirements of flows, the need for multi-hop transmissions, and the unreliable nature of wireless transmissions. We develop a framework for designing feasibility-optimal policies. We then demonstrate the utility of this framework by considering two types of systems: one where sensors are equipped with full-duplex radios, and the other where sensors are equipped with half-duplex radios. When sensors are equipped with full-duplex radios, we propose an online distributed scheduling policy and proves the policy is feasibility-optimal. We also provide a heuristic for systems where sensors are equipped with half-duplex radios. We show that this heuristic is still feasibility-optimal for some topologies.
A New Guess-and-Determine Attack on the A5/1 Stream Cipher
Venue: arXiv cs.CR 2012
Year: 2012

In Europe and North America, the most widely used stream cipher to ensure privacy and confidentiality of conversations in GSM mobile phones is the A5/1. In this paper, we present a new attack on the A5/1 stream cipher with an average time complexity of 2^(48.5), which is much less than the brute-force attack with a complexity of 2^(64). The attack has a 100% success rate and requires about 5.65GB storage. We provide a detailed description of our new attack along with its implementation and results.
A Fast and Effective Local Search Algorithm for Optimizing the Placement of Wind Turbines
Venue: arXiv cs.NE 2012
Year: 2012

The placement of wind turbines on a given area of land such that the wind farm produces a maximum amount of energy is a challenging optimization problem. In this article, we tackle this problem, taking into account wake effects that are produced by the different turbines on the wind farm. We significantly improve upon existing results for the minimization of wake effects by developing a new problem-specific local search algorithm. One key step in the speed-up of our algorithm is the reduction in computation time needed to assess a given wind farm layout compared to previous approaches. Our new method allows the optimization of large real-world scenarios within a single night on a standard computer, whereas weeks on specialized computing servers were required for previous approaches.
Mariages et Trahisons
Venue: arXiv cs.DC 2012
Year: 2012

A self-stabilizing protocol tolerates by definition transient faults (faults of finite duration). Recently, a new class of self-stabilizing protocols that are able to tolerate a given number of permanent faults. In this paper, we focus on self-stabilizing protocols able to tolerate Byzantine faults, that is faults that introduce an arbitrary behaviour. We focus on strict-stabilization in which the system have to contain the effects of Byzantine faults. Specificaly, we study the possibility to construct in a self-stabilizing way a maximal matching in a network where an arbitrary number of process may become Byzantine.
Fast and Robust Parametric Estimation of Jointly Sparse Channels
Venue: arXiv cs.SY 2012
Year: 2012

We consider the joint estimation of multipath channels obtained with a set of receiving antennas and uniformly probed in the frequency domain. This scenario fits most of the modern outdoor communication protocols for mobile access or digital broadcasting among others. Such channels verify a Sparse Common Support property (SCS) which was used in a previous paper to propose a Finite Rate of Innovation (FRI) based sampling and estimation algorithm. In this contribution we improve the robustness and computational complexity aspects of this algorithm. The method is based on projection in Krylov subspaces to improve complexity and a new criterion called the Partial Effective Rank (PER) to estimate the level of sparsity to gain robustness. If P antennas measure a K-multipath channel with N uniformly sampled measurements per channel, the algorithm possesses an O(KPNlogN) complexity and an O(KPN) memory footprint instead of O(PN^3) and O(PN^2) for the direct implementation, making it suitable for K << N. The sparsity is estimated online based on the PER, and the algorithm therefore has a sense of introspection being able to relinquish sparsity if it is lacking. The estimation performances are tested on field measurements with synthetic AWGN, and the proposed algorithm outperforms non-sparse reconstruction in the medium to low SNR range (< 0dB), increasing the rate of successful symbol decodings by 1/10th in average, and 1/3rd in the best case. The experiments also show that the algorithm does not perform worse than a non-sparse estimation algorithm in non-sparse operating conditions, since it may fall-back to it if the PER criterion does not detect a sufficient level of sparsity. The algorithm is also tested against a method assuming a "discrete" sparsity model as in Compressed Sensing (CS). The conducted test indicates a trade-off between speed and accuracy.