OpenRaiser/Intern-Atlas huggingface dataset:
On the Fusion of Compton Scatter and Attenuation Data for Limited-view X-ray Tomographic Applications
Venue: arXiv cs.CV 2017
Year: 2017

In this paper we demonstrate the utility of fusing energy-resolved observations of Compton scattered photons with traditional attenuation data for the joint recovery of mass density and photoelectric absorption in the context of limited view tomographic imaging applications. We begin with the development of a physical and associated numerical model for the Compton scatter process. Using this model, we propose a variational approach recovering these two material properties. In addition to the typical data-fidelity terms, the optimization functional includes regularization for both the mass density and photoelectric coefficients. We consider a novel edge-preserving method in the case of mass density. To aid in the recovery of the photoelectric information, we draw on our recent method in \cite{r15} and employ a non-local regularization scheme that builds on the fact that mass density is more stably imaged. Simulation results demonstrate clear advantages associated with the use of both scattered photon data and energy resolved information in mapping the two material properties of interest. Specifically, comparing images obtained using only conventional attenuation data with those where we employ only Compton scatter photons and images formed from the combination of the two, shows that taking advantage of both types of data for reconstruction provides far more accurate results.
Finding Substitutable Binary Code By Synthesizing Adapters
Venue: arXiv cs.SE 2017
Year: 2017

Independently developed codebases typically contain many segments of code that perform same or closely related operations (semantic clones). Finding functionally equivalent segments enables applications like replacing a segment by a more efficient or more secure alternative. Such related segments often have different interfaces, so some glue code (an adapter) is needed to replace one with the other. We present an algorithm that searches for replaceable code segments at the function level by attempting to synthesize an adapter between them from some family of adapters; it terminates if it finds no possible adapter. We implement our technique using (1) concrete adapter enumeration based on Intel's Pin framework (2) binary symbolic execution, and explore the relation between size of adapter search space and total search time. We present examples of applying adapter synthesis for improving security and efficiency of binary functions, deobfuscating binary functions, and switching between binary implementations of RC4. We present two large-scale evaluations, (1) we run adapter synthesis on more than 13,000 function pairs from the Linux C library, (2) using more than 61,000 fragments of binary code extracted from a ARM image built for the iPod Nano 2g device and known functions from the VLC media player, we evaluate our adapter synthesis implementation on more than a million synthesis tasks . Our results confirm that several instances of adaptably equivalent binary functions exist in real-world code, and suggest that adapter synthesis can be applied for reverse engineering and for constructing cleaner, less buggy, more efficient programs.
Improved User-Private Information Retrieval via Finite Geometry
Venue: arXiv cs.IT 2017
Year: 2017

In a User-Private Information Retrieval (UPIR) scheme, a set of users collaborate to retrieve files from a database without revealing to observers which participant in the scheme requested the file. Protocols have been proposed based on pairwise balanced designs and symmetric designs. Wepropose a new class of UPIR schemes based on generalised quadrangles (GQ). We prove that while the privacy of users in the previously proposed schemes could be compromised by a single user, the new GQ-UPIR schemes proposed in this paper maintain privacy with high probability even when up to $O(n^{1/4 - ε})$ users collude, where $n$ is the total number of users in the scheme.
On Differential Modulation in Downlink Multiuser MIMO Systems
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we consider a space time block coded multiuser multiple-input multiple-output (MU-MIMO) system with downlink transmission. Specifically, we propose to use downlink precoding combined with differential modulation (DM) to shift the complexity from the receivers to the transmitter. The block diagonalization (BD) precoding scheme is used to cancel co-channel interference (CCI) in addition to exploiting its advantage of enhancing diversity. Since the BD scheme requires channel knowledge at the transmitter, we propose to use downlink spreading along with DM, which does not require channel knowledge neither at the transmitter nor at the receivers. The orthogonal spreading (OS) scheme is employed in order to separate the data streams of different users. As a space time block code, we use the Alamouti code that can be encoded/decoded using DM thereby eliminating the need for channel knowledge at the receiver. The proposed schemes yield low complexity transceivers while providing good performance. Monte Carlo simulation results demonstrate the effectiveness of the proposed schemes.
Distributed Event-Based State Estimation for Networked Systems: An LMI-Approach
Venue: arXiv cs.SY 2017
Year: 2017

In this work, a dynamic system is controlled by multiple sensor-actuator agents, each of them commanding and observing parts of the system's input and output. The different agents sporadically exchange data with each other via a common bus network according to local event-triggering protocols. From these data, each agent estimates the complete dynamic state of the system and uses its estimate for feedback control. We propose a synthesis procedure for designing the agents' state estimators and the event triggering thresholds. The resulting distributed and event-based control system is guaranteed to be stable and to satisfy a predefined estimation performance criterion. The approach is applied to the control of a vehicle platoon, where the method's trade-off between performance and communication, and the scalability in the number of agents is demonstrated.
Algorithmic Properties of Sparse Digraphs
Venue: arXiv cs.DM 2017
Year: 2017

The notions of bounded expansion and nowhere denseness have been applied very successfully in algorithmic graph theory. We study the corresponding notions of directed bounded expansion and nowhere crownfulness on directed graphs. We show that many of the algorithmic tools that were developed for undirected bounded expansion classes can, with some care, also be applied in their directed counterparts, and thereby we highlight a rich algorithmic structure theory of directed bounded expansion classes. More specifically, we show that the directed Steiner tree problem is fixed-parameter tractable on any class of directed bounded expansion parameterized by the number $k$ of non-terminals plus the maximal diameter $s$ of a strongly connected component in the subgraph induced by the terminals. Our result strongly generalizes a result of Jones et al., who proved that the problem is fixed parameter tractable on digraphs of bounded degeneracy if the set of terminals is required to be acyclic. We furthermore prove that for every integer $r\geq 1$, the distance-$r$ dominating set problem can be approximated up to a factor $O(\log k)$ and the connected distance-$r$ dominating set problem can be approximated up to a factor $O(k\cdot \log k)$ on any class of directed bounded expansion, where $k$ denotes the size of an optimal solution. If furthermore, the class is nowhere crownful, we are able to compute a polynomial kernel for distance-$r$ dominating sets. Polynomial kernels for this problem were not known to exist on any other existing digraph measure for sparse classes.
Optimizing Signalized Intersections Performance under Conventional and Automated Vehicles Traffic
Venue: arXiv cs.SY 2017
Year: 2017

Automated vehicles, or AVs (i.e. those that have the ability to operate without a driver and can communicate with the infrastructure) may transform the transportation system. This study develops and simulates an algorithm that can optimize signal control simultaneously with the AV trajectories under undersaturated traffic flow of AV and conventional vehicles. This proposed Intelligent Intersection Control System (IICS) operates based on real-time collected arrival data at detection ranges around the center of intersection. Parallel to detecting arrivals, the optimized trajectories and signal control parameters will be transmitted to AVs and the signal controller to be implemented. Simulation experiments using the proposed IICS algorithm successfully prevented queue formation up to undersaturated condition. Comparison of the algorithm to operations with conventional actuated control shows 38-52% reduction in average travel time compared to conventional signal control.
Embodied Flight with a Drone
Venue: arXiv cs.RO 2017
Year: 2017

Most human-robot interfaces, such as joysticks and keyboards, require training and constant cognitive effort and provide a limited degree of awareness of the robots state and its environment. Embodied interactions, instead of interfaces, could bridge the gap between humans and robots, allowing humans to naturally perceive and act through a distal robotic body. Establishing an embodied interaction and mapping human movements and a non-anthropomorphic robot is particularly challenging. In this paper, we describe a natural and immersive embodied interaction that allows users to control and experience drone flight with their own bodies. The setup uses a commercial flight simulator that tracks hand movements and provides haptic and visual feedback. The paper discusses how to integrate the simulator with a real drone, how to map body movement with drone motion, and how the resulting embodied interaction provides a more natural and immersive flight experience to unskilled users with respect to a conventional RC remote controller.
Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor
Venue: arXiv cs.DS 2017
Year: 2017

The notion of Turing kernelization investigates whether a polynomial-time algorithm can solve an NP-hard problem, when it is aided by an oracle that can be queried for the answers to bounded-size subproblems. One of the main open problems in this direction is whether k-Path admits a polynomial Turing kernel: can a polynomial-time algorithm determine whether an undirected graph has a simple path of length k, using an oracle that answers queries of size poly(k)? We show this can be done when the input graph avoids a fixed graph H as a topological minor, thereby significantly generalizing an earlier result for bounded-degree and $K_{3,t}$-minor-free graphs. Moreover, we show that k-Path even admits a polynomial Turing kernel when the input graph is not H-topological-minor-free itself, but contains a known vertex modulator of size bounded polynomially in the parameter, whose deletion makes it so. To obtain our results, we build on the graph minors decomposition to show that any H-topological-minor-free graph that does not contain a k-path, has a separation that can safely be reduced after communication with the oracle.
Simultaneous Optimization of Neural Network Weights and Active Nodes using Metaheuristics
Venue: arXiv cs.NE 2017
Year: 2017

Optimization of neural network (NN) significantly influenced by the transfer function used in its active nodes. It has been observed that the homogeneity in the activation nodes does not provide the best solution. Therefore, the customizable transfer functions whose underlying parameters are subjected to optimization were used to provide heterogeneity to NN. For the experimental purpose, a meta-heuristic framework using a combined genotype representation of connection weights and transfer function parameter was used. The performance of adaptive Logistic, Tangent-hyperbolic, Gaussian and Beta functions were analyzed. In present research work, concise comparisons between different transfer function and between the NN optimization algorithms are presented. The comprehensive analysis of the results obtained over the benchmark dataset suggests that the Artificial Bee Colony with adaptive transfer function provides the best results in terms of classification accuracy over the particle swarm optimization and differential evolution.
Cardiologist-Level Arrhythmia Detection with Convolutional Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

We develop an algorithm which exceeds the performance of board certified cardiologists in detecting a wide range of heart arrhythmias from electrocardiograms recorded with a single-lead wearable monitor. We build a dataset with more than 500 times the number of unique patients than previously studied corpora. On this dataset, we train a 34-layer convolutional neural network which maps a sequence of ECG samples to a sequence of rhythm classes. Committees of board-certified cardiologists annotate a gold standard test set on which we compare the performance of our model to that of 6 other individual cardiologists. We exceed the average cardiologist performance in both recall (sensitivity) and precision (positive predictive value).
An Online Development Environment for Answer Set Programming
Venue: arXiv cs.OH 2017
Year: 2017

Recent progress in logic programming (e.g., the development of the Answer Set Programming paradigm) has made it possible to teach it to general undergraduate and even high school students. Given the limited exposure of these students to computer science, the complexity of downloading, installing and using tools for writing logic programs could be a major barrier for logic programming to reach a much wider audience. We developed an online answer set programming environment with a self contained file system and a simple interface, allowing users to write logic programs and perform several tasks over the programs.
Blockchain Consensus Protocols in the Wild
Venue: arXiv cs.DC 2017
Year: 2017

A blockchain is a distributed ledger for recording transactions, maintained by many nodes without central authority through a distributed cryptographic protocol. All nodes validate the information to be appended to the blockchain, and a consensus protocol ensures that the nodes agree on a unique order in which entries are appended. Consensus protocols for tolerating Byzantine faults have received renewed attention because they also address blockchain systems. This work discusses the process of assessing and gaining confidence in the resilience of a consensus protocols exposed to faults and adversarial nodes. We advocate to follow the established practice in cryptography and computer security, relying on public reviews, detailed models, and formal proofs; the designers of several practical systems appear to be unaware of this. Moreover, we review the consensus protocols in some prominent permissioned blockchain platforms with respect to their fault models and resilience against attacks. The protocol comparison covers Hyperledger Fabric, Tendermint, Symbiont, R3~Corda, Iroha, Kadena, Chain, Quorum, MultiChain, Sawtooth Lake, Ripple, Stellar, and IOTA.
Project Makespan Estimation: Computational Load of Interval and Point Estimates
Venue: arXiv cs.OH 2017
Year: 2017

The estimation of project completion time is to be repeated several times in the project planning phase to reach the optimal tradeoff between time, cost, and quality. Estimation procedures provide either an interval or a point estimate. The computational load of several estimation procedures is reviewed. A multiple polynomial regression model is provided for major interval estimation procedures and shows that the accuracy in the probability model for activities is the most influential factor. The computational time does not appear to be an impeding factor, though it is larger for MonteCarlo simulation, so that the computational time can be traded off in search of a simpler estimation procedure.
High-Performance FPGA Implementation of Equivariant Adaptive Separation via Independence Algorithm for Independent Component Analysis
Venue: arXiv cs.LG 2017
Year: 2017

Independent Component Analysis (ICA) is a dimensionality reduction technique that can boost efficiency of machine learning models that deal with probability density functions, e.g. Bayesian neural networks. Algorithms that implement adaptive ICA converge slower than their nonadaptive counterparts, however, they are capable of tracking changes in underlying distributions of input features. This intrinsically slow convergence of adaptive methods combined with existing hardware implementations that operate at very low clock frequencies necessitate fundamental improvements in both algorithm and hardware design. This paper presents an algorithm that allows efficient hardware implementation of ICA. Compared to previous work, our FPGA implementation of adaptive ICA improves clock frequency by at least one order of magnitude and throughput by at least two orders of magnitude. Our proposed algorithm is not limited to ICA and can be used in various machine learning problems that use stochastic gradient descent optimization.
Simple Classification using Binary Data
Venue: arXiv cs.LG 2017
Year: 2017

Binary, or one-bit, representations of data arise naturally in many applications, and are appealing in both hardware implementations and algorithm design. In this work, we study the problem of data classification from binary data and propose a framework with low computation and resource costs. We illustrate the utility of the proposed approach through stylized and realistic numerical experiments, and provide a theoretical analysis for a simple case. We hope that our framework and analysis will serve as a foundation for studying similar types of approaches.
Significance of Disk Failure Prediction in Datacenters
Venue: arXiv cs.DC 2017
Year: 2017

Modern datacenters assemble a very large number of disk drives under a single roof. Even if economic and technical factors where to make individual drives more reliable (which is not at all clear, given the commoditization of the technology), their sheer numbers combined with their ever increasing utilization in a well-balanced design makes achieving storage reliability a major challenge. In this paper, we assess the challenge of storage system reliability in the modern datacenter, and demonstrate how good disk failure prediction models can significantly improve the reliability of such systems.
Well-Founded Operators for Normal Hybrid MKNF Knowledge Bases
Venue: arXiv cs.AI 2017
Year: 2017

Hybrid MKNF knowledge bases have been considered one of the dominant approaches to combining open world ontology languages with closed world rule-based languages. Currently, the only known inference methods are based on the approach of guess-and-verify, while most modern SAT/ASP solvers are built under the DPLL architecture. The central impediment here is that it is not clear what constitutes a constraint propagator, a key component employed in any DPLL-based solver. In this paper, we address this problem by formulating the notion of unfounded sets for nondisjunctive hybrid MKNF knowledge bases, based on which we propose and study two new well-founded operators. We show that by employing a well-founded operator as a constraint propagator, a sound and complete DPLL search engine can be readily defined. We compare our approach with the operator based on the alternating fixpoint construction by Knorr et al [2011] and show that, when applied to arbitrary partial partitions, the new well-founded operators not only propagate more truth values but also circumvent the non-converging behavior of the latter. In addition, we study the possibility of simplifying a given hybrid MKNF knowledge base by employing a well-founded operator, and show that, out of the two operators proposed in this paper, the weaker one can be applied for this purpose and the stronger one cannot. These observations are useful in implementing a grounder for hybrid MKNF knowledge bases, which can be applied before the computation of MKNF models. The paper is under consideration for acceptance in TPLP.
Local Large deviation: A McMillian Theorem for Coloured Random Graph Processes
Venue: arXiv cs.IT 2017
Year: 2017

For a finite typed graph on $n$ nodes and with type law $μ,$ we define the so-called spectral potential $ρ_λ(\,\cdot,\,μ),$ of the graph.From the $ρ_λ(\,\cdot,\,μ)$ we obtain Kullback action or the deviation function, $\mathcal{H}_λ(π\,\|\,ν),$ with respect to an empirical pair measure, $π,$ as the Legendre dual. For the finite typed random graph conditioned to have an empirical link measure $π$ and empirical type measure $μ$, we prove a Local large deviation principle (LLDP), with rate function $\mathcal{H}_λ(π\,\|\,ν)$ and speed $n.$ We deduce from this LLDP, a full conditional large deviation principle and a weak variant of the classical McMillian Theorem for the typed random graphs. Given the typical empirical link measure, $λμ\otimesμ,$ the number of typed random graphs is approximately equal $e^{n\|λμ\otimesμ\|H\big(λμ\otimesμ/\|λμ\otimesμ\|\big)}.$ Note that we do not require any topological restrictions on the space of finite graphs for these LLDPs.
Dissipative Stability Conditions for Linear Coupled Differential-Difference Systems via a Dynamical Constraints Approach
Venue: arXiv cs.SY 2017
Year: 2017

In this short note, we derive dissipative conditions with slack variables for a linear coupled differential-difference (CDDS) via constructing a Krasovskii functional. The approach can be interpreted as a generalization of the Finsler Lemma approach for standard LTI systems proposed previously in \cite{de2001stability}. We also show that the proposed slack variables scheme is equivalent to the approach based on directly substituting the system trajectory $\dot{\bm{x}}(t)$, similar to the case of LTI system.
Image Segmentation Algorithms Overview
Venue: arXiv cs.CV 2017
Year: 2017

The technology of image segmentation is widely used in medical image processing, face recognition pedestrian detection, etc. The current image segmentation techniques include region-based segmentation, edge detection segmentation, segmentation based on clustering, segmentation based on weakly-supervised learning in CNN, etc. This paper analyzes and summarizes these algorithms of image segmentation, and compares the advantages and disadvantages of different algorithms. Finally, we make a prediction of the development trend of image segmentation with the combination of these algorithms.
Integrated Safety and Security Risk Assessment Methods: A Survey of Key Characteristics and Applications
Venue: arXiv cs.CR 2017
Year: 2017

Over the last years, we have seen several security incidents that compromised system safety, of which some caused physical harm to people. Meanwhile, various risk assessment methods have been developed that integrate safety and security, and these could help to address the corresponding threats by implementing suitable risk treatment plans. However, an overarching overview of these methods, systematizing the characteristics of such methods, is missing. In this paper, we conduct a systematic literature review, and identify 7 integrated safety and security risk assessment methods. We analyze these methods based on 5 different criteria, and identify key characteristics and applications. A key outcome is the distinction between sequential and non-sequential integration of safety and security, related to the order in which safety and security risks are assessed. This study provides a basis for developing more effective integrated safety and security risk assessment methods in the future.