OpenRaiser/Intern-Atlas huggingface dataset:
Executing Bag of Distributed Tasks on the Cloud: Investigating the Trade-offs Between Performance and Cost
Venue: arXiv cs.DC 2014
Year: 2014

Bag of Distributed Tasks (BoDT) can benefit from decentralised execution on the Cloud. However, there is a trade-off between the performance that can be achieved by employing a large number of Cloud VMs for the tasks and the monetary constraints that are often placed by a user. The research reported in this paper is motivated towards investigating this trade-off so that an optimal plan for deploying BoDT applications on the cloud can be generated. A heuristic algorithm, which considers the user's preference of performance and cost is proposed and implemented. The feasibility of the algorithm is demonstrated by generating execution plans for a sample application. The key result is that the algorithm generates optimal execution plans for the application over 91\% of the time.
On The Dynamical Nature Of Computation
Venue: arXiv cs.OH 2014
Year: 2014

Dynamical Systems theory generally deals with fixed point iterations of continuous functions. Computation by Turing machine although is a fixed point iteration but is not continuous. This specific category of fixed point iterations can only be studied using their orbits. Therefore the standard notion of chaos is not immediately applicable. However, when a suitable definition is used, it is found that the notion of chaos and fractal sets exists even in computation. It is found that a non terminating Computation will be almost surely chaotic, and autonomous learning will almost surely identify fractal only sets.
Learning circuits with few negations
Venue: arXiv cs.CC 2014
Year: 2014

Monotone Boolean functions, and the monotone Boolean circuits that compute them, have been intensively studied in complexity theory. In this paper we study the structure of Boolean functions in terms of the minimum number of negations in any circuit computing them, a complexity measure that interpolates between monotone functions and the class of all functions. We study this generalization of monotonicity from the vantage point of learning theory, giving near-matching upper and lower bounds on the uniform-distribution learnability of circuits in terms of the number of negations they contain. Our upper bounds are based on a new structural characterization of negation-limited circuits that extends a classical result of A. A. Markov. Our lower bounds, which employ Fourier-analytic tools from hardness amplification, give new results even for circuits with no negations (i.e. monotone functions).
Photomapping Using Aerial Vehicle
Venue: arXiv cs.OH 2014
Year: 2014

Creating a photomap plays a critical role in navigation. Therefore, flying vehicles are usually used to create topdown maps of the environment. In this report we used two different aerial vehicles to create a map in a simulated environment
A Comparison of learning algorithms on the Arcade Learning Environment
Venue: arXiv cs.LG 2014
Year: 2014

Reinforcement learning agents have traditionally been evaluated on small toy problems. With advances in computing power and the advent of the Arcade Learning Environment, it is now possible to evaluate algorithms on diverse and difficult problems within a consistent framework. We discuss some challenges posed by the arcade learning environment which do not manifest in simpler environments. We then provide a comparison of model-free, linear learning algorithms on this challenging problem set.
Algorithmic Design for Competitive Influence Maximization Problems
Venue: arXiv cs.SI 2014
Year: 2014

Given the popularity of the viral marketing campaign in online social networks, finding an effective method to identify a set of most influential nodes so to compete well with other viral marketing competitors is of upmost importance. We propose a "General Competitive Independent Cascade (GCIC)" model to describe the general influence propagation of two competing sources in the same network. We formulate the "Competitive Influence Maximization (CIM)" problem as follows: Under a prespecified influence propagation model and that the competitor's seed set is known, how to find a seed set of $k$ nodes so as to trigger the largest influence cascade? We propose a general algorithmic framework TCIM for the CIM problem under the GCIC model. TCIM returns a $(1-1/e-ε)$-approximate solution with probability at least $1-n^{-\ell}$, and has an efficient time complexity of $O(c(k+\ell)(m+n)\log n/ε^2)$, where $c$ depends on specific propagation model and may also depend on $k$ and underlying network $G$. To the best of our knowledge, this is the first general algorithmic framework that has both $(1-1/e-ε)$ performance guarantee and practical efficiency. We conduct extensive experiments on real-world datasets under three specific influence propagation models, and show the efficiency and accuracy of our framework. In particular, we achieve up to four orders of magnitude speedup as compared to the previous state-of-the-art algorithms with the approximate guarantee.
A simple interpretation of the growth of scientific/technological research impact leading to hype-type evolution curves
Venue: arXiv cs.DL 2014
Year: 2014

The empirical and theoretical justification of Gartner hype curves is a very relevant open question in the field of Technological Life Cycle analysis. The scope of the present paper is to introduce a simple model describing the growth of scientific/technological research impact, in the specific case where science is the main source of a new idea driving a technological development, leading to hype-type evolution curves. The main idea of the model is that, in a first stage, the growth of the scientific interest of a new specific field (as can be measured by publication numbers) basically follows the classical logistic growth curve. At a second stage, starting at a later trigger time, the technological development based on that scientific idea (as can be measured by patent deposits) can be described as the integral (in a mathematical sense) of the first curve, since technology is based on the overall accumulated scientific knowledge. The model is tested through a bibliometric analysis of the publication and patent deposit rate for Organic Light Emitting Diodes (OLED) scientific research and technology, as well as for other emerging technologies.
Programming the Adapteva Epiphany 64-core Network-on-chip Coprocessor
Venue: arXiv cs.AR 2014
Year: 2014

In the construction of exascale computing systems energy efficiency and power consumption are two of the major challenges. Low-power high performance embedded systems are of increasing interest as building blocks for large scale high- performance systems. However, extracting maximum performance out of such systems presents many challenges. Various aspects from the hardware architecture to the programming models used need to be explored. The Epiphany architecture integrates low-power RISC cores on a 2D mesh network and promises up to 70 GFLOPS/Watt of processing efficiency. However, with just 32 KB of memory per eCore for storing both data and code, and only low level inter-core communication support, programming the Epiphany system presents several challenges. In this paper we evaluate the performance of the Epiphany system for a variety of basic compute and communication operations. Guided by this data we explore strategies for implementing scientific applications on memory constrained low-powered devices such as the Epiphany. With future systems expected to house thousands of cores in a single chip, the merits of such architectures as a path to exascale is compared to other competing systems.
Supervised learning model for parsing Arabic language
Venue: arXiv cs.CL 2014
Year: 2014

Parsing the Arabic language is a difficult task given the specificities of this language and given the scarcity of digital resources (grammars and annotated corpora). In this paper, we suggest a method for Arabic parsing based on supervised machine learning. We used the SVMs algorithm to select the syntactic labels of the sentence. Furthermore, we evaluated our parser following the cross validation method by using the Penn Arabic Treebank. The obtained results are very encouraging.
ContactTrees: A Technique for Studying Personal Network Data
Venue: arXiv cs.SI 2014
Year: 2014

Network visualization allows a quick glance at how nodes (or actors) are connected by edges (or ties). A conventional network diagram of "contact tree" maps out a root and branches that represent the structure of nodes and edges, often without further specifying leaves or fruits that would have grown from small branches. By furnishing such a network structure with leaves and fruits, we reveal details about "contacts" in our ContactTrees that underline ties and relationships. Our elegant design employs a bottom-up approach that resembles a recent attempt to understand subjective well-being by means of a series of emotions. Such a bottom-up approach to social-network studies decomposes each tie into a series of interactions or contacts, which help deepen our understanding of the complexity embedded in a network structure. Unlike previous network visualizations, ContactTrees can highlight how relationships form and change based upon interactions among actors, and how relationships and networks vary by contact attributes. Based on a botanical tree metaphor, the design is easy to construct and the resulting tree-like visualization can display many properties at both tie and contact levels, a key ingredient missing from conventional techniques of network visualization. We first demonstrate ContactTrees using a dataset consisting of three waves of 3-month contact diaries over the 2004-2012 period, then compare ContactTrees with alternative tools and discuss how this tool can be applied to other types of datasets.
The Burden of Risk Aversion in Mean-Risk Selfish Routing
Venue: arXiv cs.GT 2014
Year: 2014

Considering congestion games with uncertain delays, we compute the inefficiency introduced in network routing by risk-averse agents. At equilibrium, agents may select paths that do not minimize the expected latency so as to obtain lower variability. A social planner, who is likely to be more risk neutral than agents because it operates at a longer time-scale, quantifies social cost with the total expected delay along routes. From that perspective, agents may make suboptimal decisions that degrade long-term quality. We define the {\em price of risk aversion} (PRA) as the worst-case ratio of the social cost at a risk-averse Wardrop equilibrium to that where agents are risk-neutral. For networks with general delay functions and a single source-sink pair, we show that the PRA depends linearly on the agents' risk tolerance and on the degree of variability present in the network. In contrast to the {\em price of anarchy}, in general the PRA increases when the network gets larger but it does not depend on the shape of the delay functions. To get this result we rely on a combinatorial proof that employs alternating paths that are reminiscent of those used in max-flow algorithms. For {\em series-parallel} (SP) graphs, the PRA becomes independent of the network topology and its size. As a result of independent interest, we prove that for SP networks with deterministic delays, Wardrop equilibria {\em maximize} the shortest-path objective among all feasible flows.
On the Transmit Beamforming for MIMO Wiretap Channels: Large-System Analysis
Venue: arXiv cs.IT 2014
Year: 2014

With the growth of wireless networks, security has become a fundamental issue in wireless communications due to the broadcast nature of these networks. In this work, we consider MIMO wiretap channels in a fast fading environment, for which the overall performance is characterized by the ergodic MIMO secrecy rate. Unfortunately, the direct solution to finding ergodic secrecy rates is prohibitive due to the expectations in the rates expressions in this setting. To overcome this difficulty, we invoke the large-system assumption, which allows a deterministic approximation to the ergodic mutual information. Leveraging results from random matrix theory, we are able to characterize the achievable ergodic secrecy rates. Based on this characterization, we address the problem of covariance optimization at the transmitter. Our numerical results demonstrate a good match between the large-system approximation and the actual simulated secrecy rates, as well as some interesting features of the precoder optimization.
A Two-phase Decision Support Framework for the Automatic Screening of Digital Fundus Images
Venue: arXiv cs.CV 2014
Year: 2014

In this paper we give a brief review on the present status of automated detection systems describe for the screening of diabetic retinopathy. We further detail an enhanced detection procedure that consists of two steps. First, a pre-screening algorithm is considered to classify the input digital fundus images based on the severity of abnormalities. If an image is found to be seriously abnormal, it will not be analysed further with robust lesion detector algorithms. As a further improvement, we introduce a novel feature extraction approach based on clinical observations. The second step of the proposed method detects regions of interest with possible lesions on the images that previously passed the pre-screening step. These regions will serve as input to the specific lesion detectors for detailed analysis. This procedure can increase the computational performance of a screening system. Experimental results show that both two steps of the proposed approach are capable to efficiently exclude a large amount of data from further processing, thus, to decrease the computational burden of the automatic screening system.
Estimating the Spatial Reuse with Configuration Models
Venue: arXiv cs.NI 2014
Year: 2014

We propose a new methodology to estimate the spatial reuse of CSMA-like scheduling. Instead of focusing on spatial configurations of users, we model the interferences between users as a random graph. Using configuration models for random graphs, we show how the properties of the medium access mechanism are captured by some deterministic differential equations, when the size of the graph gets large. Performance indicators such as the probability of connection of a given node can then be efficiently computed from these equations. We also perform simulations to illustrate the results on different types of random graphs. Even on spatial structures, these estimates get very accurate as soon as the variance of the interference is not negligible.
Surrogate Search As a Way to Combat Harmful Effects of Ill-behaved Evaluation Functions
Venue: arXiv cs.AI 2014
Year: 2014

Recently, several researchers have found that cost-based satisficing search with A* often runs into problems. Although some "work arounds" have been proposed to ameliorate the problem, there has been little concerted effort to pinpoint its origin. In this paper, we argue that the origins of this problem can be traced back to the fact that most planners that try to optimize cost also use cost-based evaluation functions (i.e., f(n) is a cost estimate). We show that cost-based evaluation functions become ill-behaved whenever there is a wide variance in action costs; something that is all too common in planning domains. The general solution to this malady is what we call a surrogatesearch, where a surrogate evaluation function that doesn't directly track the cost objective, and is resistant to cost-variance, is used. We will discuss some compelling choices for surrogate evaluation functions that are based on size rather that cost. Of particular practical interest is a cost-sensitive version of size-based evaluation function -- where the heuristic estimates the size of cheap paths, as it provides attractive quality vs. speed tradeoffs
Algorithmic randomness for Doob's martingale convergence theorem in continuous time
Venue: arXiv cs.LO 2014
Year: 2014

We study Doob's martingale convergence theorem for computable continuous time martingales on Brownian motion, in the context of algorithmic randomness. A characterization of the class of sample points for which the theorem holds is given. Such points are given the name of Doob random points. It is shown that a point is Doob random if its tail is computably random in a certain sense. Moreover, Doob randomness is strictly weaker than computable randomness and is incomparable with Schnorr randomness.
Synchronization Clustering based on a Linearized Version of Vicsek model
Venue: arXiv cs.LG 2014
Year: 2014

This paper presents a kind of effective synchronization clustering method based on a linearized version of Vicsek model. This method can be represented by an Effective Synchronization Clustering algorithm (ESynC), an Improved version of ESynC algorithm (IESynC), a Shrinking Synchronization Clustering algorithm based on another linear Vicsek model (SSynC), and an effective Multi-level Synchronization Clustering algorithm (MSynC). After some analysis and comparisions, we find that ESynC algorithm based on the Linearized version of the Vicsek model has better synchronization effect than SynC algorithm based on an extensive Kuramoto model and a similar synchronization clustering algorithm based on the original Vicsek model. By simulated experiments of some artificial data sets, we observe that ESynC algorithm, IESynC algorithm, and SSynC algorithm can get better synchronization effect although it needs less iterative times and less time than SynC algorithm. In some simulations, we also observe that IESynC algorithm and SSynC algorithm can get some improvements in time cost than ESynC algorithm. At last, it gives some research expectations to popularize this algorithm.
An Adaptive MAC Protocol for Wireless LANs
Venue: arXiv cs.NI 2014
Year: 2014

This paper focuses on contention-based Medium Access Control (MAC) protocols used in Wireless Local Area Networks (WLANs). We propose a novel MAC protocol called Adaptive Backoff Tuning MAC (ABTMAC) based on IEEE 802.11 DCF. In our proposed MAC protocol, we utilize a fixed transmission attempt rate and each node dynamically adjusts its backoff window size considering the current network status. We determined the appropriate transmission attempt rate for both cases where the Request-To-Send/Clear-To-Send (RTS/CTS) mechanism was and was not employed. Robustness against performance degradation caused by the difference between desired and actual values of the attempt rate parameter is considered when setting it. The performance of the protocol is evaluated analytically and through simulations. These results indicate that a wireless network utilizing ABTMAC performs better than one using IEEE 802.11 DCF.
On the Shoulders of Giants: The Growing Impact of Older Articles
Venue: arXiv cs.DL 2014
Year: 2014

In this paper, we examine the evolution of the impact of older scholarly articles. We attempt to answer four questions. First, how often are older articles cited and how has this changed over time. Second, how does the impact of older articles vary across different research fields. Third, is the change in the impact of older articles accelerating or slowing down. Fourth, are these trends different for much older articles. To answer these questions, we studied citations from articles published in 1990-2013. We computed the fraction of citations to older articles from articles published each year as the measure of impact. We considered articles that were published at least 10 years before the citing article as older articles. We computed these numbers for 261 subject categories and 9 broad areas of research. Finally, we repeated the computation for two other definitions of older articles, 15 years and older and 20 years and older. There are three conclusions from our study. First, the impact of older articles has grown substantially over 1990-2013. In 2013, 36% of citations were to articles that are at least 10 years old; this fraction has grown 28% since 1990. The fraction of older citations increased over 1990-2013 for 7 out of 9 broad areas and 231 out of 261 subject categories. Second, the increase over the second half (2002-2013) was double the increase in the first half (1990-2001). Third, the trend of a growing impact of older articles also holds for even older articles. In 2013, 21% of citations were to articles >= 15 years old with an increase of 30% since 1990 and 13% of citations were to articles >= 20 years old with an increase of 36%. Now that finding and reading relevant older articles is about as easy as finding and reading recently published articles, significant advances aren't getting lost on the shelves and are influencing work worldwide for years after.
Geodesic Exponential Kernels: When Curvature and Linearity Conflict
Venue: arXiv cs.LG 2014
Year: 2014

We consider kernel methods on general geodesic metric spaces and provide both negative and positive results. First we show that the common Gaussian kernel can only be generalized to a positive definite kernel on a geodesic metric space if the space is flat. As a result, for data on a Riemannian manifold, the geodesic Gaussian kernel is only positive definite if the Riemannian manifold is Euclidean. This implies that any attempt to design geodesic Gaussian kernels on curved Riemannian manifolds is futile. However, we show that for spaces with conditionally negative definite distances the geodesic Laplacian kernel can be generalized while retaining positive definiteness. This implies that geodesic Laplacian kernels can be generalized to some curved spaces, including spheres and hyperbolic spaces. Our theoretical results are verified empirically.
Link Reassignment based Snapshot Partition for Polar-orbit LEO Satellite Networks
Venue: arXiv cs.NI 2014
Year: 2014

Snapshot is a fundamental notion proposed for routing in mobile low earth orbit (LEO) satellite networks which is characterized with predictable topology dynamics. Its distribution has a great impact on the routing performance and on-board storage. Originally, the snapshot distribution is invariable by using the static snapshot partition method based on the mechanical steering antenna. Utilizing nowadays advanced phased-array antenna technology, we proposed a quasi-dynamic snapshot partition method based on the inter-satellite links (ISLs) reassignment for the polar-orbit LEO satellite networks. By steering the inter-satellite antennas when snapshot switches, we can reassign the ISLs and add available ISLs for a better following snapshot. Results show that our method can gain more stable routing performance by obtaining constant snapshot duration, constant ISL number and lower end to end delay. Especially for Iridium system, our method can gain not only longer merged snapshot duration, half of the snapshot number, but also higher utilization ratio of inter-plane ISLs. Potentially, our method could be very useful for the Iridium-next system.