OpenRaiser/Intern-Atlas huggingface dataset:
Adaptive Cuckoo Filters
Venue: arXiv cs.DS 2017
Year: 2017

We introduce the adaptive cuckoo filter (ACF), a data structure for approximate set membership that extends cuckoo filters by reacting to false positives, removing them for future queries. As an example application, in packet processing queries may correspond to flow identifiers, so a search for an element is likely to be followed by repeated searches for that element. Removing false positives can therefore significantly lower the false positive rate. The ACF, like the cuckoo filter, uses a cuckoo hash table to store fingerprints. We allow fingerprint entries to be changed in response to a false positive in a manner designed to minimize the effect on the performance of the filter. We show that the ACF is able to significantly reduce the false positive rate by presenting both a theoretical model for the false positive rate and simulations using both synthetic data sets and real packet traces.
A Review on Deep Learning Techniques Applied to Semantic Segmentation
Venue: arXiv cs.CV 2017
Year: 2017

Image semantic segmentation is more and more being of interest for computer vision and machine learning researchers. Many applications on the rise need accurate and efficient segmentation mechanisms: autonomous driving, indoor navigation, and even virtual or augmented reality systems to name a few. This demand coincides with the rise of deep learning approaches in almost every field or application target related to computer vision, including semantic segmentation or scene understanding. This paper provides a review on deep learning methods for semantic segmentation applied to various application areas. Firstly, we describe the terminology of this field as well as mandatory background concepts. Next, the main datasets and challenges are exposed to help researchers decide which are the ones that best suit their needs and their targets. Then, existing methods are reviewed, highlighting their contributions and their significance in the field. Finally, quantitative results are given for the described methods and the datasets in which they were evaluated, following up with a discussion of the results. At last, we point out a set of promising future works and draw our own conclusions about the state of the art of semantic segmentation using deep learning techniques.
Multiple Source Dual Fault Tolerant BFS Trees
Venue: arXiv cs.DS 2017
Year: 2017

Let $G=(V,E)$ be a graph with $n$ vertices and $m$ edges, with a designated set of $σ$ sources $S\subseteq V$. The fault tolerant subgraph for any graph problem maintains a sparse subgraph $H$ of $G$, such that for any set $F$ of $k$ failures, the solution for the graph problem on $G\setminus F$ is maintained in $H\setminus F$. We address the problem of maintaining a fault tolerant subgraph for Breath First Search tree (BFS) of the graph from a single source $s\in V$ (referred as $k$ FT-BFS) or multiple sources $S\subseteq V$ (referred as $k$ FT-MBFS). The problem of $k$ FT-BFS was first studied by Parter and Peleg [ESA13]. They designed an algorithm to compute FT-BFS subgraph of size $O(n^{3/2})$. Further, they showed how their algorithm can be easily extended to FT-MBFS requiring $O(σ^{1/2}n^{3/2})$ space. They also presented matching lower bounds for these results. The result was later extended to solve dual FT-BFS by Parter [PODC15] requiring $O(n^{5/3})$ space, again with matching lower bounds. However, their result was limited to only edge failures in undirected graphs and involved very complex analysis. Moreover, their solution doesn't seems to be directly extendible for dual FT-MBFS problem. We present a similar algorithm to solve dual FT-BFS problem with a much simpler analysis. Moreover, our algorithm also works for vertex failures and directed graphs, and can be easily extended to handle dual FT-MBFS problem, matching the lower bound of $O(σ^{1/3}n^{5/3})$ space described by Parter [PODC15].The key difference in our approach is a much simpler classification of path interactions which formed the basis of the analysis by Parter [PODC15]. Our dual FT-MBFS structure also seamlessly gives a dual fault tolerant spanner with additive stretch of +2 having size $O(n^{7/8})$.
A discount strategy in word-of-mouth marketing and its assessment
Venue: arXiv cs.SI 2017
Year: 2017

This paper addresses the discount pricing in word-of-mouth (WOM) marketing. A new discount strategy known as the Infection-Based Discount (IBD) strategy is proposed. The basic idea of the IBD strategy lies in that each customer enjoys a discount that is linearly proportional to his/her influence in the WOM network. To evaluate the performance of the IBD strategy, the WOM spreading process is modeled as a dynamic model known as the DPA model, and the performance of the IBD strategy is modeled as a function of the basic discount. Next, the influence of different factors, including the basic discount and the WOM network, on the dynamics of the DPA model is revealed experimentally. Finally, the influence of different factors on the performance of the IBD strategy is uncovered experimentally. On this basis, some promotional measures are recommended.
Stable Desynchronization for Wireless Sensor Networks: (II) Performance Evaluation
Venue: arXiv cs.NI 2017
Year: 2017

In this paper, we evaluate M-DWARF performance by experimentation and simulation. We validate its functionalities on TelosB motes and compare its performance with EXT-DESYNC, and LIGHTWEIGHT on TOSSIM. On simulation, we test the algorithms on several multihop topologies and discuss both the average and problematic cases. In addition, we investigate the impacts of period length (T) and compare channel utilization fairness among the desynchronization algorithms. Finally, we propose a method to reduce desynchronization overhead. (This paper is the second part of the series Stable Desynchronization for Wireless Sensor Networks - (I) Concepts and Algorithms (II) Performance Evaluation (III) Stability Analysis)
AMSDU vs AMPDU: A Brief Tutorial on WiFi Aggregation Support
Venue: arXiv cs.NI 2017
Year: 2017

WiFi MAC architecture supports aggregation at two layers. The MAC service data units (MSDUs) can be aggregated to form AMSDUs. Each AMSDU serves as a single MAC protocol data unit (MPDU). Another layer of aggregation is introduced when MPDUs can be packed together to deliver an aggregated MPDU (AMPDU). In this brief tutorial we discuss (1) why aggregation is useful at all, (2) why two layers of aggregation are required, (3) trade-offs for aggregating at different layers.
On the expected diameter, width, and complexity of a stochastic convex-hull
Venue: arXiv cs.CG 2017
Year: 2017

We investigate several computational problems related to the stochastic convex hull (SCH). Given a stochastic dataset consisting of $n$ points in $\mathbb{R}^d$ each of which has an existence probability, a SCH refers to the convex hull of a realization of the dataset, i.e., a random sample including each point with its existence probability. We are interested in computing certain expected statistics of a SCH, including diameter, width, and combinatorial complexity. For diameter, we establish the first deterministic 1.633-approximation algorithm with a time complexity polynomial in both $n$ and $d$. For width, two approximation algorithms are provided: a deterministic $O(1)$-approximation running in $O(n^{d+1} \log n)$ time, and a fully polynomial-time randomized approximation scheme (FPRAS). For combinatorial complexity, we propose an exact $O(n^d)$-time algorithm. Our solutions exploit many geometric insights in Euclidean space, some of which might be of independent interest.
Analysis of Vanilla Rolling Horizon Evolution Parameters in General Video Game Playing
Venue: arXiv cs.AI 2017
Year: 2017

Monte Carlo Tree Search techniques have generally dominated General Video Game Playing, but recent research has started looking at Evolutionary Algorithms and their potential at matching Tree Search level of play or even outperforming these methods. Online or Rolling Horizon Evolution is one of the options available to evolve sequences of actions for planning in General Video Game Playing, but no research has been done up to date that explores the capabilities of the vanilla version of this algorithm in multiple games. This study aims to critically analyse the different configurations regarding population size and individual length in a set of 20 games from the General Video Game AI corpus. Distinctions are made between deterministic and stochastic games, and the implications of using superior time budgets are studied. Results show that there is scope for the use of these techniques, which in some configurations outperform Monte Carlo Tree Search, and also suggest that further research in these methods could boost their performance.
Exploiting Multi-layer Graph Factorization for Multi-attributed Graph Matching
Venue: arXiv cs.CV 2017
Year: 2017

Multi-attributed graph matching is a problem of finding correspondences between two sets of data while considering their complex properties described in multiple attributes. However, the information of multiple attributes is likely to be oversimplified during a process that makes an integrated attribute, and this degrades the matching accuracy. For that reason, a multi-layer graph structure-based algorithm has been proposed recently. It can effectively avoid the problem by separating attributes into multiple layers. Nonetheless, there are several remaining issues such as a scalability problem caused by the huge matrix to describe the multi-layer structure and a back-projection problem caused by the continuous relaxation of the quadratic assignment problem. In this work, we propose a novel multi-attributed graph matching algorithm based on the multi-layer graph factorization. We reformulate the problem to be solved with several small matrices that are obtained by factorizing the multi-layer structure. Then, we solve the problem using a convex-concave relaxation procedure for the multi-layer structure. The proposed algorithm exhibits better performance than state-of-the-art algorithms based on the single-layer structure.
Beeping a Maximal Independent Set Fast
Venue: arXiv cs.DC 2017
Year: 2017

We adapt a recent algorithm by Ghaffari [SODA'16] for computing a Maximal Independent Set in the LOCAL model, so that it works in the significantly weaker BEEP model. For networks with maximum degree $Δ$, our algorithm terminates locally within time $O((\log Δ+ \log (1/ε)) \cdot \log(1/ε))$, with probability at least $1 - ε$. The key idea of the modification is to replace explicit messages about transmission probabilities with estimates based on the number of received messages. After the successful introduction (and implicit use) of local analysis, e.g., by Barenboim et al. [JACM'16], Chung et al. [PODC'14], Ghaffari [SODA'16], and Halldorsson et al. [PODC'15], we study this concept in the BEEP model for the first time. By doing so, we improve over local bounds that are implicitly derived from previous work (that uses traditional global analysis) on computing a Maximal Independent Set in the \beep model for a large range of values of the parameter $Δ$. At the same time, we show that our algorithm in the \beep model only needs to pay a $\log(1/ε)$ factor in the runtime compared to the best known MIS algorithm in the much more powerful \local model. We demonstrate that this overhead is negligible, as communication via beeps can be implemented using significantly less resources than communication in the LOCAL model. In particular, when looking at implementing these models, one round of the \local model needs at least $O(Δ)$ time units, while one round in the BEEP model needs $O(\logΔ)$ time units, an improvement that diminishes the loss of a $\log(1/ε)$ factor in most settings.
Monocular Visual Odometry with a Rolling Shutter Camera
Venue: arXiv cs.CV 2017
Year: 2017

Rolling Shutter (RS) cameras have become popularized because of low-cost imaging capability. However, the RS cameras suffer from undesirable artifacts when the camera or the subject is moving, or illumination condition changes. For that reason, Monocular Visual Odometry (MVO) with RS cameras produces inaccurate ego-motion estimates. Previous works solve this RS distortion problem with motion prediction from images and/or inertial sensors. However, the MVO still has trouble in handling the RS distortion when the camera motion changes abruptly (e.g. vibration of mobile cameras causes extremely fast motion instantaneously). To address the problem, we propose the novel MVO algorithm in consideration of the geometric characteristics of RS cameras. The key idea of the proposed algorithm is the new RS essential matrix which incorporates the instantaneous angular and linear velocities at each frame. Our algorithm produces accurate and robust ego-motion estimates in an online manner, and is applicable to various mobile applications with RS cameras. The superiority of the proposed algorithm is validated through quantitative and qualitative comparison on both synthetic and real dataset.
Supervised Adversarial Networks for Image Saliency Detection
Venue: arXiv cs.CV 2017
Year: 2017

In the past few years, Generative Adversarial Network (GAN) became a prevalent research topic. By defining two convolutional neural networks (G-Network and D-Network) and introducing an adversarial procedure between them during the training process, GAN has ability to generate good quality images that look like natural images from a random vector. Besides image generation, GAN may have potential to deal with wide range of real world problems. In this paper, we follow the basic idea of GAN and propose a novel model for image saliency detection, which is called Supervised Adversarial Networks (SAN). Specifically, SAN also trains two models simultaneously: the G-Network takes natural images as inputs and generates corresponding saliency maps (synthetic saliency maps), and the D-Network is trained to determine whether one sample is a synthetic saliency map or ground-truth saliency map. However, different from GAN, the proposed method uses fully supervised learning to learn both G-Network and D-Network by applying class labels of the training set. Moreover, a novel kind of layer call conv-comparison layer is introduced into the D-Network to further improve the saliency performance by forcing the high-level feature of synthetic saliency maps and ground-truthes as similar as possible. Experimental results on Pascal VOC 2012 database show that the SAN model can generate high quality saliency maps for many complicate natural images.
Fast PET reconstruction using Multi-scale Fully Convolutional Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

Reconstruction of PET images is an ill-posed inverse problem and often requires iterative algorithms to achieve good image quality for reliable clinical use in practice, at huge computational costs. In this paper, we consider the PET reconstruction a dense prediction problem where the large scale contextual information is essential, and propose a novel architecture of multi-scale fully convolutional neural networks (msfCNN) for fast PET image reconstruction. The proposed msfCNN gains large receptive fields with both memory and computational efficiency, by using a downscaling-upscaling structure and dilated convolutions. Instead of pooling and deconvolution, we propose to use the periodic shuffling operation from sub-pixel convolution and its inverse to scale the size of feature maps without losing resolution. Residual connections were added to improve training. We trained the proposed msfCNN model with simulated data, and applied it to clinical PET data acquired on a Siemens mMR scanner. The results from real oncological and neurodegenerative cases show that the proposed msfCNN-based reconstruction outperforms the iterative approaches in terms of computational time while achieving comparable image quality for quantification. The proposed msfCNN model can be applied to other dense prediction tasks, and fast msfCNN-based PET reconstruction could facilitate the potential use of molecular imaging in interventional/surgical procedures, where cancer surgery can particularly benefit.
Computational Notions of Quantum Min-Entropy
Venue: arXiv cs.CR 2017
Year: 2017

We initiate the study of computational entropy in the quantum setting. We investigate to what extent the classical notions of computational entropy generalize to the quantum setting, and whether quantum analogues of classical theorems hold. Our main results are as follows. (1) The classical Leakage Chain Rule for pseudoentropy can be extended to the case that the leakage information is quantum (while the source remains classical). Specifically, if the source has pseudoentropy at least $k$, then it has pseudoentropy at least $k-\ell$ conditioned on an $\ell$-qubit leakage. (2) As an application of the Leakage Chain Rule, we construct the first quantum leakage-resilient stream-cipher in the bounded-quantum-storage model, assuming the existence of a quantum-secure pseudorandom generator. (3) We show that the general form of the classical Dense Model Theorem (interpreted as the equivalence between two definitions of pseudo-relative-min-entropy) does not extend to quantum states. Along the way, we develop quantum analogues of some classical techniques (e.g. the Leakage Simulation Lemma, which is proven by a Non-uniform Min-Max Theorem or Boosting). On the other hand, we also identify some classical techniques (e.g. Gap Amplification) that do not work in the quantum setting. Moreover, we introduce a variety of notions that combine quantum information and quantum complexity, and this raises several directions for future work.
Ruminating Reader: Reasoning with Gated Multi-Hop Attention
Venue: arXiv cs.CL 2017
Year: 2017

To answer the question in machine comprehension (MC) task, the models need to establish the interaction between the question and the context. To tackle the problem that the single-pass model cannot reflect on and correct its answer, we present Ruminating Reader. Ruminating Reader adds a second pass of attention and a novel information fusion component to the Bi-Directional Attention Flow model (BiDAF). We propose novel layer structures that construct an query-aware context vector representation and fuse encoding representation with intermediate representation on top of BiDAF model. We show that a multi-hop attention mechanism can be applied to a bi-directional attention structure. In experiments on SQuAD, we find that the Reader outperforms the BiDAF baseline by a substantial margin, and matches or surpasses the performance of all other published systems.
GaKCo: a Fast GApped k-mer string Kernel using COunting
Venue: arXiv cs.LG 2017
Year: 2017

String Kernel (SK) techniques, especially those using gapped $k$-mers as features (gk), have obtained great success in classifying sequences like DNA, protein, and text. However, the state-of-the-art gk-SK runs extremely slow when we increase the dictionary size ($Σ$) or allow more mismatches ($M$). This is because current gk-SK uses a trie-based algorithm to calculate co-occurrence of mismatched substrings resulting in a time cost proportional to $O(Σ^{M})$. We propose a \textbf{fast} algorithm for calculating \underline{Ga}pped $k$-mer \underline{K}ernel using \underline{Co}unting (GaKCo). GaKCo uses associative arrays to calculate the co-occurrence of substrings using cumulative counting. This algorithm is fast, scalable to larger $Σ$ and $M$, and naturally parallelizable. We provide a rigorous asymptotic analysis that compares GaKCo with the state-of-the-art gk-SK. Theoretically, the time cost of GaKCo is independent of the $Σ^{M}$ term that slows down the trie-based approach. Experimentally, we observe that GaKCo achieves the same accuracy as the state-of-the-art and outperforms its speed by factors of 2, 100, and 4, on classifying sequences of DNA (5 datasets), protein (12 datasets), and character-based English text (2 datasets), respectively. GaKCo is shared as an open source tool at \url{https://github.com/QData/GaKCo-SVM}
Leveraging Patient Similarity and Time Series Data in Healthcare Predictive Models
Venue: arXiv cs.AI 2017
Year: 2017

Patient time series classification faces challenges in high degrees of dimensionality and missingness. In light of patient similarity theory, this study explores effective temporal feature engineering and reduction, missing value imputation, and change point detection methods that can afford similarity-based classification models with desirable accuracy enhancement. We select a piecewise aggregation approximation method to extract fine-grain temporal features and propose a minimalist method to impute missing values in temporal features. For dimensionality reduction, we adopt a gradient descent search method for feature weight assignment. We propose new patient status and directional change definitions based on medical knowledge or clinical guidelines about the value ranges for different patient status levels, and develop a method to detect change points indicating positive or negative patient status changes. We evaluate the effectiveness of the proposed methods in the context of early Intensive Care Unit mortality prediction. The evaluation results show that the k-Nearest Neighbor algorithm that incorporates methods we select and propose significantly outperform the relevant benchmarks for early ICU mortality prediction. This study makes contributions to time series classification and early ICU mortality prediction via identifying and enhancing temporal feature engineering and reduction methods for similarity-based time series classification.
Indexing Weighted Sequences: Neat and Efficient
Venue: arXiv cs.DS 2017
Year: 2017

In a \emph{weighted sequence}, for every position of the sequence and every letter of the alphabet a probability of occurrence of this letter at this position is specified. Weighted sequences are commonly used to represent imprecise or uncertain data, for example, in molecular biology where they are known under the name of Position-Weight Matrices. Given a probability threshold $\frac1z$, we say that a string $P$ of length $m$ occurs in a weighted sequence $X$ at position $i$ if the product of probabilities of the letters of $P$ at positions $i,\ldots,i+m-1$ in $X$ is at least $\frac1z$. In this article, we consider an \emph{indexing} variant of the problem, in which we are to preprocess a weighted sequence to answer multiple pattern matching queries. We present an $O(nz)$-time construction of an $O(nz)$-sized index for a weighted sequence of length $n$ over a constant-sized alphabet that answers pattern matching queries in optimal, $O(m+Occ)$ time, where $Occ$ is the number of occurrences reported. The cornerstone of our data structure is a novel construction of a family of $\lfloor z \rfloor$ special strings that carries the information about all the strings that occur in the weighted sequence with a sufficient probability. We obtain a weighted index with the same complexities as in the most efficient previously known index by Barton et al. (CPM 2016), but our construction is significantly simpler. The most complex algorithmic tool required in the basic form of our index is the suffix tree which we use to develop a new, more straightforward index for the so-called property matching problem. We provide an implementation of our data structure. Our construction allows us also to obtain a significant improvement over the complexities of the approximate variant of the weighted index presented by Biswas et al. (EDBT 2016) and an improvement of the space complexity of their general index.