OpenRaiser/Intern-Atlas huggingface dataset:
Bringing SDN to the Mobile Edge
Venue: arXiv cs.NI 2017
Year: 2017

Nowadays, Software Defined Network (SDN) architectures and applications are revolutionizing the way wired networks are built and operate. However, little is known about the potential of this disruptive technology in wireless mobile networks. In fact, SDN is based on a centralized network control principle, while existing mobile network protocols give emphasis on the distribution of network resources and their management. Therefore, it is challenging to apply SDN ideas in the context of mobile networks. In this paper, we propose methods to overcome these challenges and make SDN more suitable for the mobile environment. Our main idea is to combine centralized SDN and distributed control in a hybrid design that takes the best of the two paradigms; (i) global network view and control programmability of SDN and (ii) robustness of distributed protocols. We discuss the pros and cons of each method and highlight them in an SDN prototype implementation built using off-the-shelf mobile devices.
Recent Advance in Content-based Image Retrieval: A Literature Survey
Venue: arXiv cs.MM 2017
Year: 2017

The explosive increase and ubiquitous accessibility of visual data on the Web have led to the prosperity of research activity in image search or retrieval. With the ignorance of visual content as a ranking clue, methods with text search techniques for visual retrieval may suffer inconsistency between the text words and visual content. Content-based image retrieval (CBIR), which makes use of the representation of visual content to identify relevant images, has attracted sustained attention in recent two decades. Such a problem is challenging due to the intention gap and the semantic gap problems. Numerous techniques have been developed for content-based image retrieval in the last decade. The purpose of this paper is to categorize and evaluate those algorithms proposed during the period of 2003 to 2016. We conclude with several promising directions for future research.
Endoscopic Depth Measurement and Super-Spectral-Resolution Imaging
Venue: arXiv cs.CV 2017
Year: 2017

Intra-operative measurements of tissue shape and multi/ hyperspectral information have the potential to provide surgical guidance and decision making support. We report an optical probe based system to combine sparse hyperspectral measurements and spectrally-encoded structured lighting (SL) for surface measurements. The system provides informative signals for navigation with a surgical interface. By rapidly switching between SL and white light (WL) modes, SL information is combined with structure-from-motion (SfM) from white light images, based on SURF feature detection and Lucas-Kanade (LK) optical flow to provide quasi-dense surface shape reconstruction with known scale in real-time. Furthermore, "super-spectral-resolution" was realized, whereby the RGB images and sparse hyperspectral data were integrated to recover dense pixel-level hyperspectral stacks, by using convolutional neural networks to upscale the wavelength dimension. Validation and demonstration of this system is reported on ex vivo/in vivo animal/ human experiments.
An exponential lower bound for cut sparsifiers in planar graphs
Venue: arXiv cs.DS 2017
Year: 2017

Given an edge-weighted graph $G$ with a set $Q$ of $k$ terminals, a mimicking network is a graph with the same set of terminals that exactly preserves the sizes of minimum cuts between any partition of the terminals. A natural question in the area of graph compression is to provide as small mimicking networks as possible for input graph $G$ being either an arbitrary graph or coming from a specific graph class. In this note we show an exponential lower bound for cut mimicking networks in planar graphs: there are edge-weighted planar graphs with $k$ terminals that require $2^{k-2}$ edges in any mimicking network. This nearly matches an upper bound of $O(k 2^{2k})$ of Krauthgamer and Rika [SODA 2013, arXiv:1702.05951] and is in sharp contrast with the $O(k^2)$ upper bound under the assumption that all terminals lie on a single face [Goranci, Henzinger, Peng, arXiv:1702.01136]. As a side result we show a hard instance for the double-exponential upper bounds given by Hagerup, Katajainen, Nishimura, and Ragde~[JCSS 1998], Khan and Raghavendra~[IPL 2014], and Chambers and Eppstein~[JGAA 2013].
Compressive optical interferometry
Venue: arXiv cs.IT 2017
Year: 2017

Compressive sensing (CS) combines data acquisition with compression coding to reduce the number of measurements required to reconstruct a sparse signal. In optics, this usually takes the form of projecting the field onto sequences of random spatial patterns that are selected from an appropriate random ensemble. We show here that CS can be exploited in `native' optics hardware without introducing added components. Specifically, we show that random sub-Nyquist sampling of an interferogram helps reconstruct the field modal structure. The distribution of reduced sensing matrices corresponding to random measurements is provably incoherent and isotropic, which helps us carry out CS successfully.
Unsure When to Stop? Ask Your Semantic Neighbors
Venue: arXiv cs.NE 2017
Year: 2017

In iterative supervised learning algorithms it is common to reach a point in the search where no further induction seems to be possible with the available data. If the search is continued beyond this point, the risk of overfitting increases significantly. Following the recent developments in inductive semantic stochastic methods, this paper studies the feasibility of using information gathered from the semantic neighborhood to decide when to stop the search. Two semantic stopping criteria are proposed and experimentally assessed in Geometric Semantic Genetic Programming (GSGP) and in the Semantic Learning Machine (SLM) algorithm (the equivalent algorithm for neural networks). The experiments are performed on real-world high-dimensional regression datasets. The results show that the proposed semantic stopping criteria are able to detect stopping points that result in a competitive generalization for both GSGP and SLM. This approach also yields computationally efficient algorithms as it allows the evolution of neural networks in less than 3 seconds on average, and of GP trees in at most 10 seconds. The usage of the proposed semantic stopping criteria in conjunction with the computation of optimal mutation/learning steps also results in small trees and neural networks.
The Complexity of Campaigning
Venue: arXiv cs.AI 2017
Year: 2017

In "The Logic of Campaigning", Dean and Parikh consider a candidate making campaign statements to appeal to the voters. They model these statements as Boolean formulas over variables that represent stances on the issues, and study optimal candidate strategies under three proposed models of voter preferences based on the assignments that satisfy these formulas. We prove that voter utility evaluation is computationally hard under these preference models (in one case, #P-hard), along with certain problems related to candidate strategic reasoning. Our results raise questions about the desirable characteristics of a voter preference model and to what extent a polynomial-time-evaluable function can capture them.
Lattice Codes for Physical Layer Communications
Venue: arXiv cs.IT 2017
Year: 2017

Lattices are deceptively simple mathematical structures that have become indispensable for code design for physical layer communications. While lattice-related problems are interesting in their own right, the usefulness of these discrete structures in wireless communications provides additional motivation for their study and enables a multidisciplinary line of research. This thesis is devoted to the study of lattice code design for physical layer communications. Modern wireless communication networks are required to accommodate significantly varied types of mobile devices, differing in available computational power or number of equipped antennas. Additionally, the density of the networks increases rapidly, and many communication protocols diverge from the classical direct point-to-point transmission in favor of allowing for intermediate relays to process and forward data. An important consequence of this shift towards more sophisticated transmission protocols is that traditional well-performing codes become futile for modern communications, thus the study and development of novel codes is called for. Yet, however involved a transmission protocol may be, the characteristics of the physical medium, i.e., the wireless channel, stay unaffected. It is thus natural that an underlying lattice structure for code design remains crucial. This thesis consists of several articles considering lattice code design for four different communication settings relevant in modern wireless communications.
Towards the Trustworthy Development of Active Medical Devices: A Hemodialysis Case Study
Venue: arXiv cs.SE 2017
Year: 2017

The use of embedded software is advancing in modern medical devices, so does its capabilities and complexity. This paradigm shift brings many challenges such as an increased rate of medical device failures due to software faults. In this letter, we present a rigorous correct by construction approach for the trustworthy development of hemodialysis machines, a sub-class of active medical devices. We show how informal requirements of hemodialysis machines are modeled and analyzed through a rigorous process and suggest a generalization to a larger class of active medical devices.
A Perturbation Scheme for Passivity Verification and Enforcement of Parameterized Macromodels
Venue: arXiv cs.CE 2017
Year: 2017

This paper presents an algorithm for checking and enforcing passivity of behavioral reduced-order macromodels of LTI systems, whose frequency-domain (scattering) responses depend on external parameters. Such models, which are typically extracted from sampled input-output responses obtained from numerical solution of first-principle physical models, usually expressed as Partial Differential Equations, prove extremely useful in design flows, since they allow optimization, what-if or sensitivity analyses, and design centering. Starting from an implicit parameterization of both poles and residues of the model, as resulting from well-known model identification schemes based on the Generalized Sanathanan-Koerner iteration, we construct a parameter-dependent Skew-Hamiltonian/Hamiltonian matrix pencil. The iterative extraction of purely imaginary eigenvalues ot fhe pencil, combined with an adaptive sampling scheme in the parameter space, is able to identify all regions in the frequency-parameter plane where local passivity violations occur. Then, a singular value perturbation scheme is setup to iteratively correct the model coefficients, until all local passivity violations are eliminated. The final result is a corrected model, which is uniformly passive throughout the parameter range. Several numerical examples denomstrate the effectiveness of the proposed approach.
Out-colourings of Digraphs
Venue: arXiv cs.DM 2017
Year: 2017

We study vertex colourings of digraphs so that no out-neighbourhood is monochromatic and call such a colouring an {\bf out-colouring}. The problem of deciding whether a given digraph has an out-colouring with only two colours (called a 2-out-colouring) is ${\cal NP}$-complete. We show that for every choice of positive integers $r,k$ there exists a $k$-strong bipartite tournament which needs at least $r$ colours in every out-colouring. Our main results are on tournaments and semicomplete digraphs. We prove that, except for the Paley tournament $P_7$, every strong semicomplete digraph of minimum out-degree at least 3 has a 2-out-colouring. Furthermore, we show that every semicomplete digraph on at least 7 vertices has a 2-out-colouring if and only if it has a {\bf balanced} such colouring, that is, the difference between the number of vertices that receive colour 1 and colour 2 is at most one. In the second half of the paper we consider the generalization of 2-out-colourings to vertex partitions $(V_1,V_2)$ of a digraph $D$ so that each of the three digraphs induced by respectively, the vertices of $V_1$, the vertices of $V_2$ and all arcs between $V_1$ and $V_2$ have minimum out-degree $k$ for a prescribed integer $k\geq 1$. Using probabilistic arguments we prove that there exists an absolute positive constant $c$ so that every semicomplete digraph of minimum out-degree at least $2k+c\sqrt{k}$ has such a partition. This is tight up to the value of $c$.
Towards Proof Synthesis Guided by Neural Machine Translation for Intuitionistic Propositional Logic
Venue: arXiv cs.PL 2017
Year: 2017

Inspired by the recent evolution of deep neural networks (DNNs) in machine learning, we explore their application to PL-related topics. This paper is the first step towards this goal; we propose a proof-synthesis method for the negation-free propositional logic in which we use a DNN to obtain a guide of proof search. The idea is to view the proof-synthesis problem as a translation from a proposition to its proof. We train seq2seq, which is a popular network in neural machine translation, so that it generates a proof encoded as a $λ$-term of a given proposition. We implement the whole framework and empirically observe that a generated proof term is close to a correct proof in terms of the tree edit distance of AST. This observation justifies using the output from a trained seq2seq model as a guide for proof search.
Selecting nodes and buying links to maximize the information diffusion in a network
Venue: arXiv cs.DS 2017
Year: 2017

The Independent Cascade Model (ICM) is a widely studied model that aims to capture the dynamics of the information diffusion in social networks and in general complex networks. In this model, we can distinguish between active nodes which spread the information and inactive ones. The process starts from a set of initially active nodes called seeds. Recursively, currently active nodes can activate their neighbours according to a probability distribution on the set of edges. After a certain number of these recursive cycles, a large number of nodes might become active. The process terminates when no further node gets activated. Starting from the work of Domingos and Richardson, several studies have been conducted with the aim of shaping a given diffusion process so as to maximize the number of activated nodes at the end of the process. One of the most studied problems has been formalized by Kempe et al. and consists in finding a set of initial seeds that maximizes the expected number of active nodes under a budget constraint. In this paper we study a generalization of the problem of Kempe et al. in which we are allowed to spend part of the budget to create new edges incident to the seeds. That is, the budget can be spent to buy seeds or edges according to a cost function. The problem does not admin a PTAS, unless $P=NP$. We propose two approximation algorithms: the former one gives an approximation ratio that depends on the edge costs and increases when these costs are high; the latter algorithm gives a constant approximation guarantee which is greater than that of the first algorithm when the edge costs can be small.
A finite-strain hyperviscoplastic model and undrained triaxial tests of peat
Venue: arXiv cs.CE 2017
Year: 2017

This paper presents a finite-strain hyperviscoplastic constitutive model within a thermodynamically consistent framework for peat which was categorised as a material with both rate-dependent and thermodynamic equilibrium hysteresis based on the data reported in the literature. The model was implemented numerically using implicit time integration and verified against analytical solutions under simplified conditions. Experimental studies on the undrained relaxation and loading-unloading-reloading behaviour of an undisturbed fibrous peat were carried out to define the thermodynamic equilibrium state during deviatoric loading as a prerequisite for further modelling, to fit particularly those model parameters related to solid matrix properties, and to validate the proposed model under undrained conditions. This validation performed by comparison to experimental results showed that the hyperviscoplastic model could simulate undrained triaxial compression tests carried out at five different strain rates with loading/unloading relaxation steps.
Moving Horizon Estimation for ARMAX process with t-Distribution Noise
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, instead of the usual Gaussian noise assumption, $t$-distribution noise is assumed. A Maximum Likelihood Estimator using the most recent N measurements is proposed for the Auto-Regressive-Moving-Average with eXogenous input (ARMAX) process with this assumption. The proposed estimator is robust to outliers because the `thick tail' of the t-distribution reduces the effect of large errors in the likelihood function. Instead of solving the resulting nonlinear estimator numerically, the Influence Function is used to formulate a computationally efficient recursive solution, which reduces to the traditional Moving Horizon Estimator when the noise is Gaussian. The formula for the variance of the estimate is derived. This formula shows explicitly how the variance of the estimate is affected by the number of measurements and noise variance. The simulation results show that the proposed estimator has smaller variance and is more robust to outliers than the Moving Window Least-Squares Estimator. For the same accuracy, the proposed estimator is an order of magnitude faster than the particle filter.
Combining edge and cloud computing for mobility analytics
Venue: arXiv cs.DC 2017
Year: 2017

Mobility analytics using data generated from the Internet of Mobile Things (IoMT) is facing many challenges which range from the ingestion of data streams coming from a vast number of fog nodes and IoMT devices to avoiding overflowing the cloud with useless massive data streams that can trigger bottlenecks [1]. Managing data flow is becoming an important part of the IoMT because it will dictate in which platform analytical tasks should run in the future. Data flows are usually a sequence of out-of-order tuples with a high data input rate, and mobility analytics requires a real-time flow of data in both directions, from the edge to the cloud, and vice-versa. Before pulling the data streams to the cloud, edge data stream processing is needed for detecting missing, broken, and duplicated tuples in addition to recognize tuples whose arrival time is out of order. Analytical tasks such as data filtering, data cleaning and low-level data contextualization can be executed at the edge of a network. In contrast, more complex analytical tasks such as graph processing can be deployed in the cloud, and the results of ad-hoc queries and streaming graph analytics can be pushed to the edge as needed by a user application. Graphs are efficient representations used in mobility analytics because they unify knowledge about connectivity, proximity and interaction among moving things. This poster describes the preliminary results from our experimental prototype developed for supporting transit systems, in which edge and cloud computing are combined to process transit data streams forwarded from fog nodes into a cloud. The motivation of this research is to understand how to perform meaningfulness mobility analytics on transit feeds by combining cloud and fog computing architectures in order to improve fleet management, mass transit and remote asset monitoring
Adaptive OFDM Index Modulation for Two-Hop Relay-Assisted Networks
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we propose an adaptive orthogonal frequency-division multiplexing (OFDM) index modulation (IM) scheme for two-hop relay networks. In contrast to the traditional OFDM IM scheme with a deterministic and fixed mapping scheme, in this proposed adaptive OFDM IM scheme, the mapping schemes between a bit stream and indices of active subcarriers for the first and second hops are adaptively selected by a certain criterion. As a result, the active subcarriers for the same bit stream in the first and second hops can be varied in order to combat slow frequency-selective fading. In this way, the system reliability can be enhanced. Additionally, considering the fact that a relay device is normally a simple node, which may not always be able to perform mapping scheme selection due to limited processing capability, we also propose an alternative adaptive methodology in which the mapping scheme selection is only performed at the source and the relay will simply utilize the selected mapping scheme without changing it. The analyses of average outage probability, network capacity and symbol error rate (SER) are given in closed form for decode-and-forward (DF) relaying networks and are substantiated by numerical results generated by Monte Carlo simulations.
An Empirical Model of Packet Processing Delay of the Open vSwitch
Venue: arXiv cs.NI 2017
Year: 2017

Network virtualization offers flexibility by decoupling virtual network from the underlying physical network. Software-Defined Network (SDN) could utilize the virtual network. For example, in Software-Defined Networks, the entire network can be run on commodity hardware and operating systems that use virtual elements. However, this could present new challenges of data plane performance. In this paper, we present an empirical model of the packet processing delay of a widely used OpenFlow virtual switch, the Open vSwitch. In the empirical model, we analyze the effect of varying Random Access Memory (RAM) and network parameters on the performance of the Open vSwitch. Our empirical model captures the non-network processing delays, which could be used in enhancing the network modeling and simulation.
The NAO Backpack: An Open-hardware Add-on for Fast Software Development with the NAO Robot
Venue: arXiv cs.RO 2017
Year: 2017

We present an open-source accessory for the NAO robot, which enables to test computationally demanding algorithms in an external platform while preserving robot's autonomy and mobility. The platform has the form of a backpack, which can be 3D printed and replicated, and holds an ODROID XU4 board to process algorithms externally with ROS compatibility. We provide also a software bridge between the B-Human's framework and ROS to have access to the robot's sensors close to real-time. We tested the platform in several robotics applications such as data logging, visual SLAM, and robot vision with deep learning techniques. The CAD model, hardware specifications and software are available online for the benefit of the community: https://github.com/uchile-robotics/nao-backpack
GPGPU Acceleration of the KAZE Image Feature Extraction Algorithm
Venue: arXiv cs.CV 2017
Year: 2017

The recently proposed open-source KAZE image feature detection and description algorithm offers unprecedented performance in comparison to conventional ones like SIFT and SURF as it relies on nonlinear scale spaces instead of Gaussian linear scale spaces. The improved performance, however, comes with a significant computational cost limiting its use for many applications. We report a GPGPU implementation of the KAZE algorithm without resorting to binary descriptors for gaining speedup. For a 1920 by 1200 sized image our Compute Unified Device Architecture (CUDA) C based GPU version took around 300 milliseconds on a NVIDIA GeForce GTX Titan X (Maxwell Architecture-GM200) card in comparison to nearly 2400 milliseconds for a multithreaded CPU version (16 threaded Intel(R) Xeon(R) CPU E5-2650 processsor). The CUDA based parallel implementation is described in detail with fine-grained comparison between the GPU and CPU implementations. By achieving nearly 8 fold speedup without performance degradation our work expands the applicability of the KAZE algorithm. Additionally, the strategies described here can prove useful for the GPU implementation of other nonlinear scale space based methods.