OpenRaiser/Intern-Atlas huggingface dataset:
Bufferless NOC Simulation of Large Multicore System on GPU Hardware
Venue: arXiv cs.DC 2015
Year: 2015

Last level cache management and core interconnection network play important roles in performance and power consumption in multicore system. Large scale chip multicore uses mesh interconnect widely due to scalability and simplicity of the mesh interconnection design. As interconnection network occupied significant area and consumes significant percent of system power, bufferless network is an appealing alternative design to reduce power consumption and hardware cost. We have designed and implemented a simulator for simulation of distributed cache management of large chip multicore where cores are connected using bufferless interconnection network. Also, we have redesigned and implemented the our simulator which is a GPU compatible parallel version of the same simulator using CUDA programming model. We have simulated target large chip multicore with up to 43,000 cores and achieved up to 25 times speedup on NVIDIA GeForce GTX 690 GPU over serial simulation.
Toward Order-of-Magnitude Cascade Prediction
Venue: arXiv cs.SI 2015
Year: 2015

When a piece of information (microblog, photograph, video, link, etc.) starts to spread in a social network, an important question arises: will it spread to "viral" proportions -- where "viral" is defined as an order-of-magnitude increase. However, several previous studies have established that cascade size and frequency are related through a power-law - which leads to a severe imbalance in this classification problem. In this paper, we devise a suite of measurements based on "structural diversity" -- the variety of social contexts (communities) in which individuals partaking in a given cascade engage. We demonstrate these measures are able to distinguish viral from non-viral cascades, despite the severe imbalance of the data for this problem. Further, we leverage these measurements as features in a classification approach, successfully predicting microblogs that grow from 50 to 500 reposts with precision of 0.69 and recall of 0.52 for the viral class - despite this class comprising under 2\% of samples. This significantly outperforms our baseline approach as well as the current state-of-the-art. Our work also demonstrates how we can tradeoff between precision and recall.
Several classes of bent, near-bent and 2-plateaued functions over finite fields of odd characteristic
Venue: arXiv cs.IT 2015
Year: 2015

Inspired by a recent work of Mesnager, we present several new infinite families of quadratic ternary bent, near-bent and 2-plateaued functions from some known quadratic ternary bent functions. Meanwhile, the distribution of the Walsh spectrum of two class of 2-plateaued functions obtained in this paper is completely determined. Additionally, we construct the first class of $p$-ary bent functions of algebraic degree $p$ over the fields of an arbitrary odd characteristic. The proposed class contains non-quadratic $p$-ary bent functions that are affinely inequivalent to known monomial and binomial ones.
Total Variation Discrepancy of Deterministic Random Walks for Ergodic Markov Chains
Venue: arXiv cs.DM 2015
Year: 2015

Motivated by a derandomization of Markov chain Monte Carlo (MCMC), this paper investigates deterministic random walks, which is a deterministic process analogous to a random walk. While there are several progresses on the analysis of the vertex-wise discrepancy (i.e., $L_\infty$ discrepancy), little is known about the {\em total variation discrepancy} (i.e., $L_1$ discrepancy), which plays a significant role in the analysis of an FPRAS based on MCMC. This paper investigates upper bounds of the $L_1$ discrepancy between the expected number of tokens in a Markov chain and the number of tokens in its corresponding deterministic random walk. First, we give a simple but nontrivial upper bound ${\rm O}(mt^*)$ of the $L_1$ discrepancy for any ergodic Markov chains, where $m$ is the number of edges of the transition diagram and $t^*$ is the mixing time of the Markov chain. Then, we give a better upper bound ${\rm O}(m\sqrt{t^*\log t^*})$ for non-oblivious deterministic random walks, if the corresponding Markov chain is ergodic and lazy. We also present some lower bounds.
Proceedings of the 3rd Workshop on Domain-Specific Language Design and Implementation (DSLDI 2015)
Venue: arXiv cs.PL 2015
Year: 2015

The goal of the DSLDI workshop is to bring together researchers and practitioners interested in sharing ideas on how DSLs should be designed, implemented, supported by tools, and applied in realistic application contexts. We are both interested in discovering how already known domains such as graph processing or machine learning can be best supported by DSLs, but also in exploring new domains that could be targeted by DSLs. More generally, we are interested in building a community that can drive forward the development of modern DSLs. These informal post-proceedings contain the submitted talk abstracts to the 3rd DSLDI workshop (DSLDI'15), and a summary of the panel discussion on Language Composition.
Virtualization of Multi-Cell 802.11 Networks: Association and Airtime Control
Venue: arXiv cs.NI 2015
Year: 2015

This paper investigates the virtualization and optimization of a multi-cell WLAN. We consider the station (STA)-access point (AP) association and airtime control for virtualized 802.11 networks to provide service customization and fairness across multiple internet service providers (ISPs) sharing the common physical infrastructure and network capacity. More specifically, an optimization problem is formulated on the STAs transmission probabilities to maximize the overall network throughput, while providing airtime usage guarantees for the ISPs. Subsequently, an algorithm to reach the optimal solution is developed by applying monomial approximation and geometric programming iteratively. Based on the proposed three-dimensional Markov-chain model of the enhanced distributed channel access (EDCA) protocol, the detailed implementation of the optimal transmission probability is also discussed. The accuracy of the proposed Markov-chain model and the performance of the developed association and airtime control scheme are evaluated through numerical results.
A Coverage Based Decentralised Routing Algorithm for Vehicular Traffic Networks
Venue: arXiv cs.NI 2015
Year: 2015

We present a simple yet effective routing strategy inspired by coverage control, which delays the onset of congestion on traffic networks, by introducing a control parameter. The routing algorithm allows a trade-off between the congestion level and the distance to the destination. Numerical verification of the strategy is provided on a number of representative examples in SUMO, a well known micro agent simulator used for the analysis of traffic networks. We find that it is crucial in many cases to tune the given control parameters to some optimal value in order to reduce congestion in the most effective way. The effects of different network structural properties are connected to the level of congestion and the optimal range for setting the control parameters.
Metric embedding with outliers
Venue: arXiv cs.DS 2015
Year: 2015

We initiate the study of metric embeddings with \emph{outliers}. Given some metric space $(X,ρ)$ we wish to find a small set of outlier points $K \subset X$ and either an isometric or a low-distortion embedding of $(X\setminus K,ρ)$ into some target metric space. This is a natural problem that captures scenarios where a small fraction of points in the input corresponds to noise. For the case of isometric embeddings we derive polynomial-time approximation algorithms for minimizing the number of outliers when the target space is an ultrametric, a tree metric, or constant-dimensional Euclidean space. The approximation factors are 3, 4 and 2, respectively. For the case of embedding into an ultrametric or tree metric, we further improve the running time to $O(n^2)$ for an $n$-point input metric space, which is optimal. We complement these upper bounds by showing that outlier embedding into ultrametrics, trees, and $d$-dimensional Euclidean space for any $d\geq 2$ are all NP-hard, as well as NP-hard to approximate within a factor better than 2 assuming the Unique Game Conjecture. For the case of non-isometries we consider embeddings with small $\ell_{\infty}$ distortion. We present polynomial-time \emph{bi-criteria} approximation algorithms. Specifically, given some $ε> 0$, let $k_ε$ denote the minimum number of outliers required to obtain an embedding with distortion $ε$. For the case of embedding into ultrametrics we obtain a polynomial-time algorithm which computes a set of at most $3k_ε$ outliers and an embedding of the remaining points into an ultrametric with distortion $O(ε\log n)$. For embedding a metric of unit diameter into constant-dimensional Euclidean space we present a polynomial-time algorithm which computes a set of at most $2k_ε$ outliers and an embedding of the remaining points with distortion $O(\sqrtε)$.
Exploring Ancient Architectural Designs with Cellular Automata
Venue: arXiv cs.CY 2015
Year: 2015

The paper discusses the utilization of three-dimensional cellular automata employing the two-dimensional totalistic cellular automata to simulate how simple rules could emerge a highly complex architectural designs of some Indonesian heritages. A detailed discussion is brought to see the simple rules applied in Borobudur Temple, the largest ancient Buddhist temple in the country with very complex detailed designs within. The simulation confirms some previous findings related to measurement of the temple as well as some other ancient buildings in Indonesia. This happens to open further exploitation of the explanatory power presented by cellular automata for complex architectural designs built by civilization not having any supporting sophisticated tools, even standard measurement systems.
A hybrid TIM-NOMA scheme for the Broadcast Channel
Venue: arXiv cs.IT 2015
Year: 2015

Future mobile communication networks will require enhanced network efficiency and reduced system overhead. Research on Blind Interference Alignment and Topological Interference Management (TIM) has shown that optimal Degrees of Freedom can be achieved, in the absence of Channel State Information at the transmitters. Moreover, the recently emerged Non-Orthogonal Multiple Access (NOMA) scheme suggests a different multiple access approach, compared to the orthogonal methods employed in 4G, resulting in high capacity gains. Our contribution is a hybrid TIM-NOMA scheme in K-user cells, where users are divided into T groups. By superimposing users in the power domain, we introduce a two-stage decoding process, managing inter-group interference based on the TIM principles, and intra-group interference based on Successful Interference Cancellation, as proposed by NOMA. We show that the hybrid scheme can improve the sum rate by at least 100% compared to Time Division Multiple Access, for high SNR values.
Rethinking the Intercept Probability of Random Linear Network Coding
Venue: arXiv cs.CR 2015
Year: 2015

This letter considers a network comprising a transmitter, which employs random linear network coding to encode a message, a legitimate receiver, which can recover the message if it gathers a sufficient number of linearly independent coded packets, and an eavesdropper. Closed-form expressions for the probability of the eavesdropper intercepting enough coded packets to recover the message are derived. Transmission with and without feedback is studied. Furthermore, an optimization model that minimizes the intercept probability under delay and reliability constraints is presented. Results validate the proposed analysis and quantify the secrecy gain offered by a feedback link from the legitimate receiver.
Anticipatory Mobile Digital Health: Towards Personalised Proactive Therapies and Prevention Strategies
Venue: arXiv cs.CY 2015
Year: 2015

The last two centuries saw groundbreaking advances in the field of healthcare: from the invention of the vaccine to organ transplant, and eradication of numerous deadly diseases. Yet, these breakthroughs have only illuminated the role that individual traits and behaviours play in the health state of a person. Continuous patient monitoring and individually-tailored therapies can help in early detection and efficient tackling of health issues. However, even the most developed nations cannot afford proactive personalised healthcare at scale. Mobile computing devices, nowadays equipped with an array of sensors, high-performance computing power, and carried by their owners at all time, promise to revolutionise modern healthcare. These devices can enable continuous patient monitoring, and, with the help of machine learning, can build predictive models of patient's health and behaviour. Finally, through their close integration with a user's lifestyle mobiles can be used to deliver personalised proactive therapies. In this article, we develop the concept of anticipatory mobile-based healthcare - anticipatory mobile digital health - and examine the opportunities and challenges associated with its practical realisation.
Formal Reasoning Using an Iterative Approach with an Integrated Web IDE
Venue: arXiv cs.SE 2015
Year: 2015

This paper summarizes our experience in communicating the elements of reasoning about correctness, and the central role of formal specifications in reasoning about modular, component-based software using a language and an integrated Web IDE designed for the purpose. Our experience in using such an IDE, supported by a 'push-button' verifying compiler in a classroom setting, reveals the highly iterative process learners use to arrive at suitably specified, automatically provable code. We explain how the IDE facilitates reasoning at each step of this process by providing human readable verification conditions (VCs) and feedback from an integrated prover that clearly indicates unprovable VCs to help identify obstacles to completing proofs. The paper discusses the IDE's usage in verified software development using several examples drawn from actual classroom lectures and student assignments to illustrate principles of design-by-contract and the iterative process of creating and subsequently refining assertions, such as loop invariants in object-based code.
A Holistic Approach in Embedded System Development
Venue: arXiv cs.SE 2015
Year: 2015

We present pState, a tool for developing "complex" embedded systems by integrating validation into the design process. The goal is to reduce validation time. To this end, qualitative and quantitative properties are specified in system models expressed as pCharts, an extended version of hierarchical state machines. These properties are specified in an intuitive way such that they can be written by engineers who are domain experts, without needing to be familiar with temporal logic. From the system model, executable code that preserves the verified properties is generated. The design is documented on the model and the documentation is passed as comments into the generated code. On the series of examples we illustrate how models and properties are specified using pState.
A Calculus of Mobility and Communication for Ubiquitous Computing
Venue: arXiv cs.DC 2015
Year: 2015

We propose a Calculus of Mobility and Communication (CMC) for the modelling of mobility, communication and context-awareness in the setting of ubiquitous computing. CMC is an ambient calculus with the in and out capabilities of Cardelli and Gordon's Mobile Ambients. The calculus has a new form of global communication similar to that in Milner's CCS. In CMC an ambient is tagged with a set of ports that agents executing inside the ambient are allowed to communicate on. It also has a new context-awareness feature that allows ambients to query their location. We present reduction semantics and labelled transition system semantics of CMC and prove that the semantics coincide. A new notion of behavioural equivalence is given by defining capability barbed bisimulation and congruence which is proved to coincide with barbed bisimulation congruence. The expressiveness of the calculus is illustrated by two case studies.
Using Bluetooth Low Energy in smartphones to map social networks
Venue: arXiv cs.SI 2015
Year: 2015

Social networks have an important role in an individual's health, with the propagation of health-related features through a network, and correlations between network structures and symptomatology. Using Bluetooth-enabled smartphones to measure social connectivity is an alternative to traditional paper-based data collection; however studies employing this technology have been restricted to limited sets of homogenous handsets. We investigated the feasibility of using the Bluetooth Low Energy (BLE) protocol, present on users' own smartphones, to measure social connectivity. A custom application was designed for Android and iOS handsets. The app was configured to simultaneously broadcast via BLE and perform periodic discovery scans for other nearby devices. The app was installed on two Android handsets and two iOS handsets, and each combination of devices was tested in the foreground, background and locked states. Connectivity was successfully measured in all test cases, except between two iOS devices when both were in a locked state with their screens off. As smartphones are in a locked state for the majority of a day, this severely limits the ability to measure social connectivity on users' own smartphones. It is not currently feasible to use Bluetooth Low Energy to map social networks, due to the inability of iOS devices to detect another iOS device when both are in a locked state. While the technology was successfully implemented on Android devices, this represents a smaller market share of partially or fully compatible devices.
Immersion and Invariance Stabilization of Nonlinear Systems: A Horizontal Contraction Approach
Venue: arXiv cs.SY 2015
Year: 2015

The main objective of this paper is to propose an alternative procedure to carry out one of the key steps of immersion and invariance stabilising controller design. Namely, the one that ensures attractivity of the manifold whose internal dynamics contains a copy of the desired system behaviour. Towards this end we invoke contraction theory principles and ensure the attractivity of the manifold rendering it horizontally contractive. The main advantage of adopting this alternative approach is to make more systematic the last step of the design with more explicit degrees of freedom to accomplish the task. The classical case of systems in feedback form is used to illustrate the proposed controller design.
On The Exact Recovery Condition of Simultaneous Orthogonal Matching Pursuit
Venue: arXiv cs.IT 2015
Year: 2015

Several exact recovery criteria (ERC) ensuring that orthogonal matching pursuit (OMP) identifies the correct support of sparse signals have been developed in the last few years. These ERC rely on the restricted isometry property (RIP), the associated restricted isometry constant (RIC) and sometimes the restricted orthogonality constant (ROC). In this paper, three of the most recent ERC for OMP are examined. The contribution is to show that these ERC remain valid for a generalization of OMP, entitled simultaneous orthogonal matching pursuit (SOMP), that is capable to process several measurement vectors simultaneously and return a common support estimate for the underlying sparse vectors. The sharpness of the bounds is also briefly discussed in light of previous works focusing on OMP.
PTILE: A framework for the Evaluation of Power Transformer Insulation Life in Electric Power System
Venue: arXiv cs.CE 2015
Year: 2015

In this paper, a framework is developed for power transformer (Generator Step up Unit) insulation life evaluation (PTILE) study on power system Network. Parameters used for studies include real time sample data obtained from power transformer field studies in the South-South Niger Delta region of Nigeria. It is used for performing simulations over varying number of years. Simulation reports shows a polynomial running time complexity and validates the stochastic Hot Spot theory indicating that the transformers in such region should be replaced sooner due to higher hot spots and transformer loading in such regions
Evaluating Classifiers in Detecting 419 Scams in Bilingual Cybercriminal Communities
Venue: arXiv cs.SI 2015
Year: 2015

Incidents of organized cybercrime are rising because of criminals are reaping high financial rewards while incurring low costs to commit crime. As the digital landscape broadens to accommodate more internet-enabled devices and technologies like social media, more cybercriminals who are not native English speakers are invading cyberspace to cash in on quick exploits. In this paper we evaluate the performance of three machine learning classifiers in detecting 419 scams in a bilingual Nigerian cybercriminal community. We use three popular classifiers in text processing namely: Naïve Bayes, k-nearest neighbors (IBK) and Support Vector Machines (SVM). The preliminary results on a real world dataset reveal the SVM significantly outperforms Naïve Bayes and IBK at 95% confidence level.
Reflective Oracles: A Foundation for Classical Game Theory
Venue: arXiv cs.AI 2015
Year: 2015

Classical game theory treats players as special---a description of a game contains a full, explicit enumeration of all players---even though in the real world, "players" are no more fundamentally special than rocks or clouds. It isn't trivial to find a decision-theoretic foundation for game theory in which an agent's coplayers are a non-distinguished part of the agent's environment. Attempts to model both players and the environment as Turing machines, for example, fail for standard diagonalization reasons. In this paper, we introduce a "reflective" type of oracle, which is able to answer questions about the outputs of oracle machines with access to the same oracle. These oracles avoid diagonalization by answering some queries randomly. We show that machines with access to a reflective oracle can be used to define rational agents using causal decision theory. These agents model their environment as a probabilistic oracle machine, which may contain other agents as a non-distinguished part. We show that if such agents interact, they will play a Nash equilibrium, with the randomization in mixed strategies coming from the randomization in the oracle's answers. This can be seen as providing a foundation for classical game theory in which players aren't special.
Reasoning in complex environments with the SelectScript declarative language
Venue: arXiv cs.PL 2015
Year: 2015

SelectScript is an extendable, adaptable, and declarative domain-specific language aimed at information retrieval from simulation environments and robotic world models in an SQL-like manner. In this work we have extended the language in two directions. First, we have implemented hierarchical queries; second, we improve efficiency enabling manual design space exploration on different "search" strategies. We demonstrate the applicability of such extensions in two application problems; the basic language concepts are explained by solving the classical problem of the Towers of Hanoi and then a common path planning problem in a complex 3D environment is implemented.