OpenRaiser/Intern-Atlas huggingface dataset:
Minimal Actuator Placement with Optimal Control Constraints
Venue: arXiv cs.SY 2015
Year: 2015

We introduce the problem of minimal actuator placement in a linear control system so that a bound on the minimum control effort for a given state transfer is satisfied while controllability is ensured. We first show that this is an NP-hard problem following the recent work of Olshevsky. Next, we prove that this problem has a supermodular structure. Afterwards, we provide an efficient algorithm that approximates up to a multiplicative factor of O(logn), where n is the size of the multi-agent network, any optimal actuator set that meets the specified energy criterion. Moreover, we show that this is the best approximation factor one can achieve in polynomial-time for the worst case. Finally, we test this algorithm over large Erdos-Renyi random networks to further demonstrate its efficiency.
An Automated System for Discovering Neighborhood Patterns in Ego Networks
Venue: arXiv cs.SI 2015
Year: 2015

Generally, social network analysis has often focused on the topology of the network without considering the characteristics of individuals involved in them. Less attention is given to study the behavior of individuals, considering they are the basic entity of a graph. Given a mobile social network graph, what are good features to extract key information from the nodes? How many distinct neighborhood patterns exist for ego nodes? What clues does such information provide to study nodes over a long period of time? In this report, we develop an automated system in order to discover the occurrences of prototypical ego-centric patterns from data. We aim to provide a data-driven instrument to be used in behavioral sciences for graph interpretations. We analyze social networks derived from real-world data collected with smart-phones. We select 13 well-known network measures, especially those concerned with ego graphs. We form eight feature subsets and then assess their performance using unsupervised clustering techniques to discover distinguishing ego-centric patterns. From clustering analysis, we discover that eight distinct neighborhood patterns have emerged. This categorization allows concise analysis of users' data as they change over time. The results provide a fine-grained analysis for the contribution of different feature sets to detect unique clustering patterns. Last, as a case study, two datasets are studied over long periods to demonstrate the utility of this method. The study shows the effectiveness of the proposed approach in discovering important trends from data.
Indexed linear logic and higher-order model checking
Venue: arXiv cs.LO 2015
Year: 2015

In recent work, Kobayashi observed that the acceptance by an alternating tree automaton A of an infinite tree T generated by a higher-order recursion scheme G may be formulated as the typability of the recursion scheme G in an appropriate intersection type system associated to the automaton A. The purpose of this article is to establish a clean connection between this line of work and Bucciarelli and Ehrhard's indexed linear logic. This is achieved in two steps. First, we recast Kobayashi's result in an equivalent infinitary intersection type system where intersection is not idempotent anymore. Then, we show that the resulting type system is a fragment of an infinitary version of Bucciarelli and Ehrhard's indexed linear logic. While this work is very preliminary and does not integrate key ingredients of higher-order model-checking like priorities, it reveals an interesting and promising connection between higher-order model-checking and linear logic.
Typing Classes and Mixins with Intersection Types
Venue: arXiv cs.PL 2015
Year: 2015

We study an assignment system of intersection types for a lambda-calculus with records and a record-merge operator, where types are preserved both under subject reduction and expansion. The calculus is expressive enough to naturally represent mixins as functions over recursively defined classes, whose fixed points, the objects, are recursive records. In spite of the double recursion that is involved in their definition, classes and mixins can be meaningfully typed without resorting to neither recursive nor F-bounded polymorphic types. We then adapt mixin construct and composition to Java and C#, relying solely on existing features in such a way that the resulting code remains typable in the respective type systems. We exhibit some example code, and study its typings in the intersection type system via interpretation into the lambda-calculus with records we have proposed.
Fast Multiplication of Large Integers: Implementation and Analysis of the DKSS Algorithm
Venue: arXiv cs.MS 2015
Year: 2015

The Schönhage-Strassen algorithm (SSA) is the de-facto standard for multiplication of large integers. For $N$-bit numbers it has a time bound of $O(N \cdot \log N \cdot \log \log N)$. De, Kurur, Saha and Saptharishi (DKSS) presented an asymptotically faster algorithm with a better time bound of $N \cdot \log N \cdot 2^{O(\log^* N)}$. In this diploma thesis, results of an implementation of DKSS multiplication are presented: run-time is about 30 times larger than SSA, while memory requirements are about 3.75 times higher than SSA. A possible crossover point is estimated to be out of reach even if we utilized the whole universe for computer memory.
Conformance Checking Based on Multi-Perspective Declarative Process Models
Venue: arXiv cs.SE 2015
Year: 2015

Process mining is a family of techniques that aim at analyzing business process execution data recorded in event logs. Conformance checking is a branch of this discipline embracing approaches for verifying whether the behavior of a process, as recorded in a log, is in line with some expected behaviors provided in the form of a process model. The majority of these approaches require the input process model to be procedural (e.g., a Petri net). However, in turbulent environments, characterized by high variability, the process behavior is less stable and predictable. In these environments, procedural process models are less suitable to describe a business process. Declarative specifications, working in an open world assumption, allow the modeler to express several possible execution paths as a compact set of constraints. Any process execution that does not contradict these constraints is allowed. One of the open challenges in the context of conformance checking with declarative models is the capability of supporting multi-perspective specifications. In this paper, we close this gap by providing a framework for conformance checking based on MP-Declare, a multi-perspective version of the declarative process modeling language Declare. The approach has been implemented in the process mining tool ProM and has been experimented in three real life case studies.
The blind detection for palette image watermarking without changing the color
Venue: arXiv cs.MM 2015
Year: 2015

To hide a binary pattern in the palette image a steganographic scheme with blind detection is considered. The embedding algorithm uses the Lehmer code by palette color permutations for which the cover image palette is generally required. The found transformation between the palette and RGB images allows to extract the hidden data without any cover work.
On Extreme Pruning of Random Forest Ensembles for Real-time Predictive Applications
Venue: arXiv cs.LG 2015
Year: 2015

Random Forest (RF) is an ensemble supervised machine learning technique that was developed by Breiman over a decade ago. Compared with other ensemble techniques, it has proved its accuracy and superiority. Many researchers, however, believe that there is still room for enhancing and improving its performance accuracy. This explains why, over the past decade, there have been many extensions of RF where each extension employed a variety of techniques and strategies to improve certain aspect(s) of RF. Since it has been proven empiricallthat ensembles tend to yield better results when there is a significant diversity among the constituent models, the objective of this paper is twofold. First, it investigates how data clustering (a well known diversity technique) can be applied to identify groups of similar decision trees in an RF in order to eliminate redundant trees by selecting a representative from each group (cluster). Second, these likely diverse representatives are then used to produce an extension of RF termed CLUB-DRF that is much smaller in size than RF, and yet performs at least as good as RF, and mostly exhibits higher performance in terms of accuracy. The latter refers to a known technique called ensemble pruning. Experimental results on 15 real datasets from the UCI repository prove the superiority of our proposed extension over the traditional RF. Most of our experiments achieved at least 95% or above pruning level while retaining or outperforming the RF accuracy.
CSR5: An Efficient Storage Format for Cross-Platform Sparse Matrix-Vector Multiplication
Venue: arXiv cs.MS 2015
Year: 2015

Sparse matrix-vector multiplication (SpMV) is a fundamental building block for numerous applications. In this paper, we propose CSR5 (Compressed Sparse Row 5), a new storage format, which offers high-throughput SpMV on various platforms including CPUs, GPUs and Xeon Phi. First, the CSR5 format is insensitive to the sparsity structure of the input matrix. Thus the single format can support an SpMV algorithm that is efficient both for regular matrices and for irregular matrices. Furthermore, we show that the overhead of the format conversion from the CSR to the CSR5 can be as low as the cost of a few SpMV operations. We compare the CSR5-based SpMV algorithm with 11 state-of-the-art formats and algorithms on four mainstream processors using 14 regular and 10 irregular matrices as a benchmark suite. For the 14 regular matrices in the suite, we achieve comparable or better performance over the previous work. For the 10 irregular matrices, the CSR5 obtains average performance improvement of 17.6\%, 28.5\%, 173.0\% and 293.3\% (up to 213.3\%, 153.6\%, 405.1\% and 943.3\%) over the best existing work on dual-socket Intel CPUs, an nVidia GPU, an AMD GPU and an Intel Xeon Phi, respectively. For real-world applications such as a solver with only tens of iterations, the CSR5 format can be more practical because of its low-overhead for format conversion. The source code of this work is downloadable at https://github.com/bhSPARSE/Benchmark_SpMV_using_CSR5
Exploring Coverage and Distribution of Identifiers on the Scholarly Web
Venue: arXiv cs.DL 2015
Year: 2015

In a scientific publishing environment that is increasingly moving online, identifiers of scholarly work are gaining in importance. In this paper, we analysed identifier distribution and coverage of articles from the discipline of quantitative biology using arXiv, Mendeley and CrossRef as data sources. The results show that when retrieving arXiv articles from Mendeley, we were able to find more papers using the DOI than the arXiv ID. This indicates that DOI may be a better identifier with respect to findability. We also find that coverage of articles on Mendeley decreases in the most recent years, whereas the coverage of DOIs does not decrease in the same order of magnitude. This hints at the fact that there is a certain time lag involved, before articles are covered in crowd-sourced services on the scholarly web.
Prediction Using Note Text: Synthetic Feature Creation with word2vec
Venue: arXiv cs.CL 2015
Year: 2015

word2vec affords a simple yet powerful approach of extracting quantitative variables from unstructured textual data. Over half of healthcare data is unstructured and therefore hard to model without involved expertise in data engineering and natural language processing. word2vec can serve as a bridge to quickly gather intelligence from such data sources. In this study, we ran 650 megabytes of unstructured, medical chart notes from the Providence Health & Services electronic medical record through word2vec. We used two different approaches in creating predictive variables and tested them on the risk of readmission for patients with COPD (Chronic Obstructive Lung Disease). As a comparative benchmark, we ran the same test using the LACE risk model (a single score based on length of stay, acuity, comorbid conditions, and emergency department visits). Using only free text and mathematical might, we found word2vec comparable to LACE in predicting the risk of readmission of COPD patients.
How Retailers at different Stages of E-Commerce Maturity Evaluate Their Entry to E-Commerce Activities?
Venue: arXiv cs.CY 2015
Year: 2015

This paper investigates how retailers at different stages of e-commerce maturity evaluate their entry to e-commerce activities. The study was conducted using qualitative approach interviewing 16 retailers in Saudi Arabia. It comes up with 22 factors that are believed the most influencing factors for retailers in Saudi Arabia. Interestingly, there seem to be differences between retailers in companies at different maturity stages in terms of having different attitudes regarding the issues of using e-commerce. The businesses that have reached a high stage of e-commerce maturity provide practical evidence of positive and optimistic attitudes and practices regarding use of e-commerce, whereas the businesses that have not reached higher levels of maturity provide practical evidence of more negative and pessimistic attitudes and practices. The study, therefore, should contribute to efforts leading to greater e-commerce development in Saudi Arabia and other countries with similar context.
An Outlier Detection-based Tree Selection Approach to Extreme Pruning of Random Forests
Venue: arXiv cs.LG 2015
Year: 2015

Random Forest (RF) is an ensemble classification technique that was developed by Breiman over a decade ago. Compared with other ensemble techniques, it has proved its accuracy and superiority. Many researchers, however, believe that there is still room for enhancing and improving its performance in terms of predictive accuracy. This explains why, over the past decade, there have been many extensions of RF where each extension employed a variety of techniques and strategies to improve certain aspect(s) of RF. Since it has been proven empirically that ensembles tend to yield better results when there is a significant diversity among the constituent models, the objective of this paper is twofolds. First, it investigates how an unsupervised learning technique, namely, Local Outlier Factor (LOF) can be used to identify diverse trees in the RF. Second, trees with the highest LOF scores are then used to produce an extension of RF termed LOFB-DRF that is much smaller in size than RF, and yet performs at least as good as RF, but mostly exhibits higher performance in terms of accuracy. The latter refers to a known technique called ensemble pruning. Experimental results on 10 real datasets prove the superiority of our proposed extension over the traditional RF. Unprecedented pruning levels reaching 99% have been achieved at the time of boosting the predictive accuracy of the ensemble. The notably high pruning level makes the technique a good candidate for real-time applications.
Sketching, Embedding, and Dimensionality Reduction for Information Spaces
Venue: arXiv cs.DS 2015
Year: 2015

Information distances like the Hellinger distance and the Jensen-Shannon divergence have deep roots in information theory and machine learning. They are used extensively in data analysis especially when the objects being compared are high dimensional empirical probability distributions built from data. However, we lack common tools needed to actually use information distances in applications efficiently and at scale with any kind of provable guarantees. We can't sketch these distances easily, or embed them in better behaved spaces, or even reduce the dimensionality of the space while maintaining the probability structure of the data. In this paper, we build these tools for information distances---both for the Hellinger distance and Jensen--Shannon divergence, as well as related measures, like the $χ^2$ divergence. We first show that they can be sketched efficiently (i.e. up to multiplicative error in sublinear space) in the aggregate streaming model. This result is exponentially stronger than known upper bounds for sketching these distances in the strict turnstile streaming model. Second, we show a finite dimensionality embedding result for the Jensen-Shannon and $χ^2$ divergences that preserves pair wise distances. Finally we prove a dimensionality reduction result for the Hellinger, Jensen--Shannon, and $χ^2$ divergences that preserves the information geometry of the distributions (specifically, by retaining the simplex structure of the space). While our second result above already implies that these divergences can be explicitly embedded in Euclidean space, retaining the simplex structure is important because it allows us to continue doing inference in the reduced space. In essence, we preserve not just the distance structure but the underlying geometry of the space.
Feeder Load Balancing using Fuzzy Logic and Combinatorial Optimization-based Implementation
Venue: arXiv cs.OH 2015
Year: 2015

The distribution system problems, such as planning, loss minimization, and energy restoration, usually involve the phase balancing or network reconfiguration procedures. The determination of an optimal phase balance is, in general, a combinatorial optimization problem. This paper proposes a novel reconfiguration of the phase balancing using the fuzzy logic and the combinatorial optimization-based implementation step back to back. Input to the fuzzy step is the total load per phase of the feeders. Output of the fuzzy step is the load change values, negative value for load releasing and positive value for load receiving. The output of the fuzzy step is the input to the load changing system. The load changing system uses combinatorial optimization techniques to translate the change values (kW) into number of load points and then selects the specific load points. It also performs the inter-changing of the load points between the releasing and the receiving phases in an optimal fashion. Application results using the distribution feeder network of South Africa are presented in this paper.
Design and Implementation of a GUI based Offline GIFT Tool to exchange data between different systems
Venue: arXiv cs.CY 2015
Year: 2015

Multiple Choice Questions or MCQs are very important for e-learning. Many MCQ Tools allow us to generate MCQs very easily. However, in most of the cases they are not portable. That means MCQs generated for one system cannot be used for other unless a common format is used. So, collaboration and/or up gradation becomes a time consuming tedious task. In this paper, we will examine how tool could be designed which can produce portable MCQs and that too generating in the laptop and/or desktop without any need for going online.
NFV Based Gateways for Virtualized Wireless Sensors Networks: A Case Study
Venue: arXiv cs.NI 2015
Year: 2015

Virtualization enables the sharing of a same wireless sensor network (WSN) by multiple applications. However, in heterogeneous environments, virtualized wireless sensor networks (VWSN) raises new challenges such as the need for on-the-fly, dynamic, elastic and scalable provisioning of gateways. Network Functions Virtualization (NFV) is an emerging paradigm that can certainly aid in tackling these new challenges. It leverages standard virtualization technology to consolidate special-purpose network elements on top of commodity hardware. This article presents a case study on NFV based gateways for VWSNs. In the study, a VWSN gateway provider, operates and manages an NFV based infrastructure. We use two different brands of wireless sensors. The NFV infrastructure makes possible the dynamic, elastic and scalable deployment of gateway modules in this heterogeneous VWSN environment. The prototype built with Openstack as platform is described.
Distributed on-line multidimensional scaling for self-localization in wireless sensor networks
Venue: arXiv cs.DC 2015
Year: 2015

The present work considers the localization problem in wireless sensor networks formed by fixed nodes. Each node seeks to estimate its own position based on noisy measurements of the relative distance to other nodes. In a centralized batch mode, positions can be retrieved (up to a rigid transformation) by applying Principal Component Analysis (PCA) on a so-called similarity matrix built from the relative distances. In this paper, we propose a distributed on-line algorithm allowing each node to estimate its own position based on limited exchange of information in the network. Our framework encompasses the case of sporadic measurements and random link failures. We prove the consistency of our algorithm in the case of fixed sensors. Finally, we provide numerical and experimental results from both simulated and real data. Simulations issued to real data are conducted on a wireless sensor network testbed.
Barrier Coverage in Mobile Camera Sensor Networks with Grid-Based Deployment
Venue: arXiv cs.NI 2015
Year: 2015

Barrier coverage is a critical issue in wireless sensor networks for many practical applications,e.g., national border monitoring, security surveillance and intruder detection, etc. Its aim is to detect intruders that attempt to cross the protected region. In this paper, we study how to efficiently improve barrier coverage using mobile camera sensors, where camera sensors are deployed by a grid-based strategy.
Downlink Coverage Probability in a Cellular Network with Ginibre Deployed Base Stations and Nakagami-m Fading Channels
Venue: arXiv cs.IT 2015
Year: 2015

Recently, spatial stochastic models based on determinantal point processes (DPP) are studied as promising models for analysis of cellular wireless networks. Indeed, the DPPs can express the repulsive nature of the macro base station (BS) configuration observed in a real cellular network and have many desirable mathematical properties to analyze the network performance. However, almost all the prior works on the DPP based models assume the Rayleigh fading while the spatial models based on Poisson point processes have been developed to allow arbitrary distributions of fading/shadowing propagation effects. In order for the DPP based model to be more promising, it is essential to extend it to allow non-Rayleigh propagation effects. In the present paper, we propose the downlink cellular network model where the BSs are deployed according to the Ginibre point process, which is one of the main examples of the DPPs, over Nakagami-m fading. For the proposed model, we derive a numerically computable form of the coverage probability and reveal some properties of it numerically and theoretically.