OpenRaiser/Intern-Atlas huggingface dataset:
Approximation Algorithms for Bayesian Multi-Armed Bandit Problems
Venue: arXiv cs.DS 2013
Year: 2013

In this paper, we consider several finite-horizon Bayesian multi-armed bandit problems with side constraints which are computationally intractable (NP-Hard) and for which no optimal (or near optimal) algorithms are known to exist with sub-exponential running time. All of these problems violate the standard exchange property, which assumes that the reward from the play of an arm is not contingent upon when the arm is played. Not only are index policies suboptimal in these contexts, there has been little analysis of such policies in these problem settings. We show that if we consider near-optimal policies, in the sense of approximation algorithms, then there exists (near) index policies. Conceptually, if we can find policies that satisfy an approximate version of the exchange property, namely, that the reward from the play of an arm depends on when the arm is played to within a constant factor, then we have an avenue towards solving these problems. However such an approximate version of the idling bandit property does not hold on a per-play basis and are shown to hold in a global sense. Clearly, such a property is not necessarily true of arbitrary single arm policies and finding such single arm policies is nontrivial. We show that by restricting the state spaces of arms we can find single arm policies and that these single arm policies can be combined into global (near) index policies where the approximate version of the exchange property is true in expectation. The number of different bandit problems that can be addressed by this technique already demonstrate its wide applicability.
Approximate Nearest Neighbor Search in $\ell_p$
Venue: arXiv cs.DS 2013
Year: 2013

We present a new locality sensitive hashing (LSH) algorithm for $c$-approximate nearest neighbor search in $\ell_p$ with $1<p<2$. For a database of $n$ points in $\ell_p$, we achieve $O(dn^ρ)$ query time and $O(dn+n^{1+ρ})$ space, where $ρ\le O((\ln c)^2/c^p)$. This improves upon the previous best upper bound $ρ\le 1/c$ by Datar et al. (SOCG 2004), and is close to the lower bound $ρ\ge 1/c^p$ by O'Donnell, Wu and Zhou (ITCS 2011). The proof is a simple generalization of the LSH scheme for $\ell_2$ by Andoni and Indyk (FOCS 2006).
The Role of Emotions in Contributors Activity: A Case Study on the GENTOO Community
Venue: arXiv cs.SE 2013
Year: 2013

We analyse the relation between the emotions and the activity of contributors in the Open Source Software project Gentoo. Our case study builds on extensive data sets from the project's bug tracking platform Bugzilla, to quantify the activity of contributors, and its mail archives, to quantify the emotions of contributors by means of sentiment analysis. The Gentoo project is known for a period of centralization within its bug triaging community. This was followed by considerable changes in community organization and performance after the sudden retirement of the central contributor. We analyse how this event correlates with the negative emotions, both in bilateral email discussions with the central contributor, and at the level of the whole community of contributors. We then extend our study to consider the activity patterns on Gentoo contributors in general. We find that contributors are more likely to become inactive when they express strong positive or negative emotions in the bug tracker, or when they deviate from the expected value of emotions in the mailing list. We use these insights to develop a Bayesian classifier that detects the risk of contributors leaving the project. Our analysis opens new perspectives for measuring online contributor motivation by means of sentiment analysis and for real-time predictions of contributor turnover in Open Source Software projects.
Reporting an Experience on Design and Implementation of e-Health Systems on Azure Cloud
Venue: arXiv cs.CY 2013
Year: 2013

Electronic Health (e-Health) technology has brought the world with significant transformation from traditional paper-based medical practice to Information and Communication Technologies (ICT)-based systems for automatic management (storage, processing, and archiving) of information. Traditionally e-Health systems have been designed to operate within stovepipes on dedicated networks, physical computers, and locally managed software platforms that make it susceptible to many serious limitations including: 1) lack of on-demand scalability during critical situations; 2) high administrative overheads and costs; and 3) in-efficient resource utilization and energy consumption due to lack of automation. In this paper, we present an approach to migrate the ICT systems in the e-Health sector from traditional in-house Client/Server (C/S) architecture to the virtualised cloud computing environment. To this end, we developed two cloud-based e-Health applications (Medical Practice Management System and Telemedicine Practice System) for demonstrating how cloud services can be leveraged for developing and deploying such applications. The Windows Azure cloud computing platform is selected as an example public cloud platform for our study. We conducted several performance evaluation experiments to understand the Quality Service (QoS) tradeoffs of our applications under variable workload on Azure.
Computing Tree-depth Faster Than $2^{n}$
Venue: arXiv cs.DS 2013
Year: 2013

A connected graph has tree-depth at most $k$ if it is a subgraph of the closure of a rooted tree whose height is at most $k$. We give an algorithm which for a given $n$-vertex graph $G$, in time $\mathcal{O}(1.9602^n)$ computes the tree-depth of $G$. Our algorithm is based on combinatorial results revealing the structure of minimal rooted trees whose closures contain $G$.
Roughening Methods to Prevent Sample Impoverishment in the Particle PHD Filter
Venue: arXiv cs.OH 2013
Year: 2013

Mahler's PHD (Probability Hypothesis Density) filter and its particle implementation (as called the particle PHD filter) have gained popularity to solve general MTT (Multi-target Tracking) problems. However, the resampling procedure used in the particle PHD filter can cause sample impoverishment. To rejuvenate the diversity of particles, two easy-to-implement roughening approaches are presented to enhance the particle PHD filter. One termed as "separate-roughening" is inspired by Gordon's roughening procedure that is applied on the resampled particles. Another termed as "direct-roughening" is implemented by increasing the simulation noise of the state propagation of particles. Four proposals are presented to customize the roughening approach. Simulations are presented showing that the roughening approach can benefit the particle PHD filter, especially when the sample size is small.
A New Approach for Quality Management in Pervasive Computing Environments
Venue: arXiv cs.SE 2013
Year: 2013

This paper provides an extension of MDA called Context-aware Quality Model Driven Architecture (CQ-MDA) which can be used for quality control in pervasive computing environments. The proposed CQ-MDA approach based on ContextualArchRQMM (Contextual ARCHitecture Quality Requirement MetaModel), being an extension to the MDA, allows for considering quality and resources-awareness while conducting the design process. The contributions of this paper are a meta-model for architecture quality control of context-aware applications and a model driven approach to separate architecture concerns from context and quality concerns and to configure reconfigurable software architectures of distributed systems. To demonstrate the utility of our approach, we use a videoconference system.
Modeling the guaranteed delivery of bulk data
Venue: arXiv cs.NI 2013
Year: 2013

The delivery of bulk data is an increasingly pressing problem in modern networks. While in some cases these transfers happen in background without specific constraints in terms of delivery times, there are a number of scenarios in which the transfer of tens of GB of data must occur in specific, limited time windows. In order to face this task, a suitable solution is the deployment of virtual links with guaranteed bandwidth between endpoints provided by a Service Overlay Network (SON) provider. We model this scenario as an optimization problem, in which the target consists of minimizing the costs of the virtual links provided by the SON and the unknowns are the provisioned bandwidths of these links. Since the resulting objective function is neither continuous nor convex, the solution of this problem is really challenging for standard optimization tools in terms of both convergence time and solution optimality. We propose a solution based on an heuristic approach which uses the min-plus algebra. Numerical results show that the proposed heuristic outperforms the considered optimization tools, whilst maintaining an affordable computation time.
Physical-layer encryption on the public internet: a stochastic approach to the Kish-Sethuraman cipher
Venue: arXiv cs.CR 2013
Year: 2013

While information-theoretic security is often associated with the one-time pad and quantum key distribution, noisy transport media leave room for classical techniques and even covert operation. Transit times across the public internet exhibit a degree of randomness, and cannot be determined noiselessly by an eavesdropper. We demonstrate the use of these measurements for information-theoretically secure communication over the public internet.
A bad 2-dimensional instance for k-means++
Venue: arXiv cs.DS 2013
Year: 2013

The k-means++ seeding algorithm is one of the most popular algorithms that is used for finding the initial $k$ centers when using the k-means heuristic. The algorithm is a simple sampling procedure and can be described as follows: {quote} Pick the first center randomly from among the given points. For $i > 1$, pick a point to be the $i^{th}$ center with probability proportional to the square of the Euclidean distance of this point to the previously $(i-1)$ chosen centers. {quote} The k-means++ seeding algorithm is not only simple and fast but gives an $O(\log{k})$ approximation in expectation as shown by Arthur and Vassilvitskii \cite{av07}. There are datasets \cite{av07,adk09} on which this seeding algorithm gives an approximation factor $Ω(\log{k})$ in expectation. However, it is not clear from these results if the algorithm achieves good approximation factor with reasonably large probability (say $1/poly(k)$). Brunsch and Röglin \cite{br11} gave a dataset where the k-means++ seeding algorithm achieves an approximation ratio of $(2/3 - ε)\cdot \log{k}$ only with probability that is exponentially small in $k$. However, this and all other known {\em lower-bound examples} \cite{av07,adk09} are high dimensional. So, an open problem is to understand the behavior of the algorithm on low dimensional datasets. In this work, we give a simple two dimensional dataset on which the seeding algorithm achieves an approximation ratio $c$ (for some universal constant $c$) only with probability exponentially small in $k$. This is the first step towards solving open problems posed by Mahajan et al \cite{mnv12} and by Brunsch and Röglin \cite{br11}.
Certified Impossibility Results for Byzantine-Tolerant Mobile Robots
Venue: arXiv cs.LO 2013
Year: 2013

We propose a framework to build formal developments for robot networks using the COQ proof assistant, to state and to prove formally various properties. We focus in this paper on impossibility proofs, as it is natural to take advantage of the COQ higher order calculus to reason about algorithms as abstract objects. We present in particular formal proofs of two impossibility results forconvergence of oblivious mobile robots if respectively more than one half and more than one third of the robots exhibit Byzantine failures, starting from the original theorems by Bouzid et al.. Thanks to our formalization, the corresponding COQ developments are quite compact. To our knowledge, these are the first certified (in the sense of formally proved) impossibility results for robot networks.
Symbol and Bit Mapping Optimization for Physical-Layer Network Coding with Pulse Amplitude Modulation
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we consider a two-way relay network in which two users exchange messages through a single relay using a physical-layer network coding (PNC) based protocol. The protocol comprises two phases of communication. In the multiple access (MA) phase, two users transmit their modulated signals concurrently to the relay, and in the broadcast (BC) phase, the relay broadcasts a network-coded (denoised) signal to both users. Nonbinary and binary network codes are considered for uniform and nonuniform pulse amplitude modulation (PAM) adopted in the MA phase, respectively. We examine the effect of different choices of symbol mapping (i.e., mapping from the denoised signal to the modulation symbols at the relay) and bit mapping (i.e., mapping from the modulation symbols to the source bits at the user) on the system error-rate performance. A general optimization framework is proposed to determine the optimal symbol/bit mappings with joint consideration of noisy transmissions in both communication phases. Complexity-reduction techniques are developed for solving the optimization problems. It is shown that the optimal symbol/bit mappings depend on the signal-to-noise ratio (SNR) of the channel and the modulation scheme. A general strategy for choosing good symbol/bit mappings is also presented based on a high-SNR analysis, which suggests using a symbol mapping that aligns the error patterns in both communication phases and Gray and binary bit mappings for uniform and nonuniform PAM, respectively.
Keyphrase Cloud Generation of Broadcast News
Venue: arXiv cs.IR 2013
Year: 2013

This paper describes an enhanced automatic keyphrase extraction method applied to Broadcast News. The keyphrase extraction process is used to create a concept level for each news. On top of words resulting from a speech recognition system output and news indexation and it contributes to the generation of a tag/keyphrase cloud of the top news included in a Multimedia Monitoring Solution system for TV and Radio news/programs, running daily, and monitoring 12 TV channels and 4 Radios.
Hourly Traffic Prediction of News Stories
Venue: arXiv cs.IR 2013
Year: 2013

The process of predicting news stories popularity from several news sources has become a challenge of great importance for both news producers and readers. In this paper, we investigate methods for automatically predicting the number of clicks on a news story during one hour. Our approach is a combination of additive regression and bagging applied over a M5P regression tree using a logarithmic scale (log10). The features included are social-based (social network metadata from Facebook), content-based (automatically extracted keyphrases, and stylometric statistics from news titles), and time-based. In 1st Sapo Data Challenge we obtained 11.99% as mean relative error value which put us in the 4th place out of 26 participants.
Parallel Algorithm for Longest Common Subsequence in a String
Venue: arXiv cs.DS 2013
Year: 2013

In the area of Pattern Recognition and Matching, finding a Longest Common Subsequence plays an important role. In this paper, we have proposed one algorithm based on parallel computation. We have used OpenMP API package as middleware to send the data to different processors. We have tested our algorithm in a system having four processors and 2 GB physical memory. The best result showed that the parallel algorithm increases the performance (speed of computation) by 3.22.
Impact of Facebook Usage on Undergraduate Students Performance in Irbid National University: Case Study
Venue: arXiv cs.CY 2013
Year: 2013

The aim of this study is to investigate the style of Facebook usage between undergraduate students and the impact on their academics performance. Also, this paper was evaluated in the view of student the using of Facebook. A questioner was design for collecting data from a sample of 480 undergraduate students in Irbid National University. The survey revealed that 77% of the students have an account on Facebook. One of the main findings is that there was a significant relationship between gender and Facebook usage. Moreover, the survey revealed that whenever the less time spent on Facebook, the higher the performance will be in grade point average. This was conducted by the negative correlation between time spent on Facebook and the performance of undergraduate student. Statistically speaking, the study has seven hypotheses; two of them were rejecting against five acceptable hypotheses.
Cannibal Animal Games: a new variant of Tic-Tac-Toe
Venue: arXiv cs.GT 2013
Year: 2013

This paper presents a new partial two-player game, called the \emph{cannibal animal game}, which is a variant of Tic-Tac-Toe. The game is played on the infinite grid, where in each round a player chooses and occupies free cells. The first player Alice can occupy a cell in each turn and wins if she occupies a set of cells, the union of a subset of which is a translated, reflected and/or rotated copy of a previously agreed upon polyomino $P$ (called an \emph{animal}). The objective of the second player Bob is to prevent Alice from creating her animal by occupying in each round a translated, reflected and/or rotated copy of $P$. An animal is a \emph{cannibal} if Bob has a winning strategy, and a \emph{non-cannibal} otherwise. This paper presents some new tools, such as the \emph{bounding strategy} and the \emph{punching lemma}, to classify animals into cannibals or non-cannibals. We also show that the \emph{pairing strategy} works for this problem.
Key Phrase Extraction of Lightly Filtered Broadcast News
Venue: arXiv cs.CL 2013
Year: 2013

This paper explores the impact of light filtering on automatic key phrase extraction (AKE) applied to Broadcast News (BN). Key phrases are words and expressions that best characterize the content of a document. Key phrases are often used to index the document or as features in further processing. This makes improvements in AKE accuracy particularly important. We hypothesized that filtering out marginally relevant sentences from a document would improve AKE accuracy. Our experiments confirmed this hypothesis. Elimination of as little as 10% of the document sentences lead to a 2% improvement in AKE precision and recall. AKE is built over MAUI toolkit that follows a supervised learning approach. We trained and tested our AKE method on a gold standard made of 8 BN programs containing 110 manually annotated news stories. The experiments were conducted within a Multimedia Monitoring Solution (MMS) system for TV and radio news/programs, running daily, and monitoring 12 TV and 4 radio channels.
Signal Transmission Across Tile Assemblies: 3D Static Tiles Simulate Active Self-Assembly by 2D Signal-Passing Tiles
Venue: arXiv cs.ET 2013
Year: 2013

The 2-Handed Assembly Model (2HAM) is a tile-based self-assembly model in which, typically beginning from single tiles, arbitrarily large aggregations of static tiles combine in pairs to form structures. The Signal-passing Tile Assembly Model (STAM) is an extension of the 2HAM in which the tiles are dynamically changing components which are able to alter their binding domains as they bind together. For our first result, we demonstrate useful techniques and transformations for converting an arbitrarily complex STAM$^+$ tile set into an STAM$^+$ tile set where every tile has a constant, low amount of complexity, in terms of the number and types of ``signals'' they can send, with a trade off in scale factor. Using these simplifications, we prove that for each temperature $τ>1$ there exists a 3D tile set in the 2HAM which is intrinsically universal for the class of all 2D STAM$^+$ systems at temperature $τ$ (where the STAM$^+$ does not make use of the STAM's power of glue deactivation and assembly breaking, as the tile components of the 2HAM are static and unable to change or break bonds). This means that there is a single tile set $U$ in the 3D 2HAM which can, for an arbitrarily complex STAM$^+$ system $S$, be configured with a single input configuration which causes $U$ to exactly simulate $S$ at a scale factor dependent upon $S$. Furthermore, this simulation uses only two planes of the third dimension. This implies that there exists a 3D tile set at temperature $2$ in the 2HAM which is intrinsically universal for the class of all 2D STAM$^+$ systems at temperature $1$. Moreover, we show that for each temperature $τ>1$ there exists an STAM$^+$ tile set which is intrinsically universal for the class of all 2D STAM$^+$ systems at temperature $τ$, including the case where $τ= 1$.
Fake Run-Time Selection of Template Arguments in C++
Venue: arXiv cs.PL 2013
Year: 2013

C++ does not support run-time resolution of template type arguments. To circumvent this restriction, we can instantiate a template for all possible combinations of type arguments at compile time and then select the proper instance at run time by evaluation of some provided conditions. However, for templates with multiple type parameters such a solution may easily result in a branching code bloat. We present a template metaprogramming algorithm called for_id that allows the user to select the proper template instance at run time with theoretical minimum sustained complexity of the branching code.
Towards modelling cost and risks of infrequent events in the cargo screening process
Venue: arXiv cs.CE 2013
Year: 2013

We introduce a simulation model of the port of Calais with a focus on the operation of immigration controls. Our aim is to compare the cost and benefits of different screening policies. Methodologically, we are trying to understand the limits of discrete event simulation of rare events. When will they become 'too rare' for simulation to give meaningful results?
A Comparative study of Analog and digital Controller On DC/DC Buck-Boost Converter Four Switch for Mobile Device Applications
Venue: arXiv cs.OH 2013
Year: 2013

This paper presents comparative performance between Analog and digital controller on DC/DC buck-boost converter four switch. The design of power electronic converter circuit with the use of closed loop scheme needs modeling and then simulating the converter using the modeled equations. This can easily be done with the help of state equations and MATLAB/SIMULINK as a tool for simulation of those state equations. DC/DC Buckboost converter in this study is operated in buck (step-down) and boost (step-up) modes.
A Physical-layer Rateless Code for Wireless Channels
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we propose a physical-layer rateless code for wireless channels. A novel rateless encoding scheme is developed to overcome the high error floor problem caused by the low-density generator matrix (LDGM)-like encoding scheme in conventional rateless codes. This is achieved by providing each symbol with approximately equal protection in the encoding process. An extrinsic information transfer (EXIT) chart based optimization approach is proposed to obtain a robust check node degree distribution, which can achieve near-capacity performances for a wide range of signal to noise ratios (SNR). Simulation results show that, under the same channel conditions and transmission overheads, the bit-error-rate (BER) performance of the proposed scheme considerably outperforms the existing rateless codes in additive white Gaussian noise (AWGN) channels, particularly at low BER regions.