OpenRaiser/Intern-Atlas huggingface dataset:
Model and Objective Separation with Conditional Lower Bounds: Disjunction is Harder than Conjunction
Venue: arXiv cs.DS 2016
Year: 2016

Given a model of a system and an objective, the model-checking question asks whether the model satisfies the objective. We study polynomial-time problems in two classical models, graphs and Markov Decision Processes (MDPs), with respect to several fundamental $ω$-regular objectives, e.g., Rabin and Streett objectives. For many of these problems the best-known upper bounds are quadratic or cubic, yet no super-linear lower bounds are known. In this work our contributions are two-fold: First, we present several improved algorithms, and second, we present the first conditional super-linear lower bounds based on widely believed assumptions about the complexity of CNF-SAT and combinatorial Boolean matrix multiplication. A separation result for two models with respect to an objective means a conditional lower bound for one model that is strictly higher than the existing upper bound for the other model, and similarly for two objectives with respect to a model. Our results establish the following separation results: (1) A separation of models (graphs and MDPs) for disjunctive queries of reachability and Büchi objectives. (2) Two kinds of separations of objectives, both for graphs and MDPs, namely, (2a) the separation of dual objectives such as reachability/safety (for disjunctive questions) and Streett/Rabin objectives, and (2b) the separation of conjunction and disjunction of multiple objectives of the same type such as safety, Büchi, and coBüchi. In summary, our results establish the first model and objective separation results for graphs and MDPs for various classical $ω$-regular objectives. Quite strikingly, we establish conditional lower bounds for the disjunction of objectives that are strictly higher than the existing upper bounds for the conjunction of the same objectives.
Performance of 1-D and 2-D Lattice Boltzmann (LB) in Solution of the Shock Tube Problem
Venue: arXiv cs.CE 2016
Year: 2016

In this paper we presented a lattice Boltzmann with square grid for compressible flow problems. Triple level velocity is considered for each cell. Migration step use discrete velocity but continuous parameters are utilized to calculate density, velocity, and energy. So, we called this semi-discrete method. To evaluate the performance of the method the well-known shock tube problem is solved, using 1-D and 2-D version of the lattice Boltzmann method. The results of these versions are compared with each other and with the results of the analytical solution.
Integrated Interleaved Codes as Locally Recoverable Codes: Properties and Performance
Venue: arXiv cs.IT 2016
Year: 2016

Considerable interest has been paid in recent literature to codes combining local and global properties for erasure correction. Applications are in cloud type of implementations, in which fast recovery of a failed storage device is important, but additional protection is required in order to avoid data loss, and in RAID type of architectures, in which total device failures coexist with silent failures at the page or sector level in each device. Existing solutions to these problems require in general relatively large finite fields. The techniques of Integrated Interleaved Codes (which are closely related to Generalized Concatenated Codes) are proposed to reduce significantly the size of the finite field, and it is shown that when the parameters of these codes are judiciously chosen, their performance may be competitive with the one of codes optimizing the minimum distance.
Impact of Directionality on Interference Mitigation in Full-Duplex Cellular Network
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we consider two fundamental full-duplex (FD) architectures, two-node and three-node, in the context of cellular networks where the terminals employ directional antennas. The simultaneous transmission and reception of data in non-orthogonal channels makes FD radio a potential solution for the currently limited spectrum. However, its implementation generates high levels of interference either in the form of loopback interference (LI) from the output to the input antenna of a transceiver or in the form of co-channel interference in large-scale multicell networks due to the large number of active links. Using a stochastic geometry model, we investigate how directional antennas can control and mitigate the co-channel interference. Furthermore, we provide a model which characterizes the way directional antennas manage the LI in order to passively suppress it. Our results show that both architectures can benefit significantly by the employment of directional antennas. Finally, we consider the case where both architectures are employed in the network and derive the optimal values for the density fraction of each architecture which maximize the success probability and the network throughput.
Parameterizing Region Covariance: An Efficient Way To Apply Sparse Codes On Second Order Statistics
Venue: arXiv cs.CV 2016
Year: 2016

Sparse representations have been successfully applied to signal processing, computer vision and machine learning. Currently there is a trend to learn sparse models directly on structure data, such as region covariance. However, such methods when combined with region covariance often require complex computation. We present an approach to transform a structured sparse model learning problem to a traditional vectorized sparse modeling problem by constructing a Euclidean space representation for region covariance matrices. Our new representation has multiple advantages. Experiments on several vision tasks demonstrate competitive performance with the state-of-the-art methods.
Minimum Distances of the QC-LDPC Codes in IEEE 802 Communication Standards
Venue: arXiv cs.IT 2016
Year: 2016

This work applies earlier results on Quasi-Cyclic (QC) LDPC codes to the codes specified in six separate IEEE 802 standards, specifying wireless communications from 54 MHz to 60 GHz. First, we examine the weight matrices specified to upper bound the codes' minimum distance independent of block length. Next, we search for the minimum distance achieved for the parity check matrices selected at each block length. Finally, solutions to the computational challenges encountered are addressed.
Semi-External Memory Sparse Matrix Multiplication for Billion-Node Graphs
Venue: arXiv cs.DC 2016
Year: 2016

Sparse matrix multiplication is traditionally performed in memory and scales to large matrices using the distributed memory of multiple nodes. In contrast, we scale sparse matrix multiplication beyond memory capacity by implementing sparse matrix dense matrix multiplication (SpMM) in a semi-external memory (SEM) fashion; i.e., we keep the sparse matrix on commodity SSDs and dense matrices in memory. Our SEM-SpMM incorporates many in-memory optimizations for large power-law graphs. It outperforms the in-memory implementations of Trilinos and Intel MKL and scales to billion-node graphs, far beyond the limitations of memory. Furthermore, on a single large parallel machine, our SEM-SpMM operates as fast as the distributed implementations of Trilinos using five times as much processing power. We also run our implementation in memory (IM-SpMM) to quantify the overhead of keeping data on SSDs. SEM-SpMM achieves almost 100% performance of IM-SpMM on graphs when the dense matrix has more than four columns; it achieves at least 65% performance of IM-SpMM on all inputs. We apply our SpMM to three important data analysis tasks--PageRank, eigensolving, and non-negative matrix factorization--and show that our SEM implementations significantly advance the state of the art.
Joint Defogging and Demosaicking
Venue: arXiv cs.CV 2016
Year: 2016

Image defogging is a technique used extensively for enhancing visual quality of images in bad weather condition. Even though defogging algorithms have been well studied, defogging performance is degraded by demosaicking artifacts and sensor noise amplification in distant scenes. In order to improve visual quality of restored images, we propose a novel approach to perform defogging and demosaicking simultaneously. We conclude that better defogging performance with fewer artifacts can be achieved when a defogging algorithm is combined with a demosaicking algorithm simultaneously. We also demonstrate that the proposed joint algorithm has the benefit of suppressing noise amplification in distant scene. In addition, we validate our theoretical analysis and observations for both synthesized datasets with ground truth fog-free images and natural scene datasets captured in a raw format.
Secure Multi-Party Computation Based Privacy Preserving Extreme Learning Machine Algorithm Over Vertically Distributed Data
Venue: arXiv cs.CR 2016
Year: 2016

Especially in the Big Data era, the usage of different classification methods is increasing day by day. The success of these classification methods depends on the effectiveness of learning methods. Extreme learning machine (ELM) classification algorithm is a relatively new learning method built on feed-forward neural-network. ELM classification algorithm is a simple and fast method that can create a model from high-dimensional data sets. Traditional ELM learning algorithm implicitly assumes complete access to whole data set. This is a major privacy concern in most of cases. Sharing of private data (i.e. medical records) is prevented because of security concerns. In this research, we propose an efficient and secure privacy-preserving learning algorithm for ELM classification over data that is vertically partitioned among several parties. The new learning method preserves the privacy on numerical attributes, builds a classification model without sharing private data without disclosing the data of each party to others.
Blocklength-Limited Performance of Relaying under Quasi-Static Rayleigh Channels
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, the blocklength-limited performance of a relaying system is studied, where channels are assumed to experience quasi-static Rayleigh fading while at the same time only the average channel state information (CSI) is available at the source. Both the physical-layer performance (blocklength-limited throughput) and the link-layer performance (effective capacity) of the relaying system are investigated. We propose a simple system operation by introducing a factor based on which we weight the average CSI and let the source determine the coding rate accordingly. In particular, we prove that both the blocklength-limited throughput and the effective capacity are quasi-concave in the weight factor. Through numerical investigations, we show the appropriateness of our theoretical model. In addition, we observe that relaying is more efficient than direct transmission. Moreover, this performance advantage of relaying under the average CSI scenario is more significant than under the perfect CSI scenario. Finally, the speed of convergence (between the blocklength-limited performance and the performance in the Shannon capacity regime) in relaying system is faster in comparison to the direct transmission under both the average CSI scenario and the perfect CSI scenario.
A local constant factor approximation for the minimum dominating set problem on bounded genus graphs
Venue: arXiv cs.DC 2016
Year: 2016

The Minimum Dominating Set (MDS) problem is not only one of the most fundamental problems in distributed computing, it is also one of the most challenging ones. While it is well-known that minimum dominating sets cannot be approximated locally on general graphs, over the last years, several breakthroughs have been made on computing local approximations on sparse graphs. This paper presents a deterministic and local constant factor approximation for minimum dominating sets on bounded genus graphs, a very large family of sparse graphs. Our main technical contribution is a new analysis of a slightly modified, first-order definable variant of an existing algorithm by Lenzen et al. Interestingly, unlike existing proofs for planar graphs, our analysis does not rely on any topological arguments. We believe that our techniques can be useful for the study of local problems on sparse graphs beyond the scope of this paper.
Strengthening the Entropy Power Inequality
Venue: arXiv cs.IT 2016
Year: 2016

We tighten the Entropy Power Inequality (EPI) when one of the random summands is Gaussian. Our strengthening is closely connected to the concept of strong data processing for Gaussian channels and generalizes the (vector extension of) Costa's EPI. This leads to a new reverse entropy power inequality and, as a corollary, sharpens Stam's inequality relating entropy power and Fisher information. Applications to network information theory are given, including a short self-contained proof of the rate region for the two-encoder quadratic Gaussian source coding problem. Our argument is based on weak convergence and a technique employed by Geng and Nair for establishing Gaussian optimality via rotational-invariance, which traces its roots to a `doubling trick' that has been successfully used in the study of functional inequalities.
Big Graph Mining: Frameworks and Techniques
Venue: arXiv cs.DC 2016
Year: 2016

Big graph mining is an important research area and it has attracted considerable attention. It allows to process, analyze, and extract meaningful information from large amounts of graph data. Big graph mining has been highly motivated not only by the tremendously increasing size of graphs but also by its huge number of applications. Such applications include bioinformatics, chemoinformatics and social networks. One of the most challenging tasks in big graph mining is pattern mining in big graphs. This task consists on using data mining algorithms to discover interesting, unexpected and useful patterns in large amounts of graph data. It aims also to provide deeper understanding of graph data. In this context, several graph processing frameworks and scaling data mining/pattern mining techniques have been proposed to deal with very big graphs. This paper gives an overview of existing data mining and graph processing frameworks that deal with very big graphs. Then it presents a survey of current researches in the field of data mining / pattern mining in big graphs and discusses the main research issues related to this field. It also gives a categorization of both distributed data mining and machine learning techniques, graph processing frameworks and large scale pattern mining approaches.
Local Codes with Cooperative Repair in Distributed Storage System
Venue: arXiv cs.IT 2016
Year: 2016

Recently, the research on local repair codes is mainly confined to repair the failed nodes within each repair group. But if the extreme cases occur that the entire repair group has failed, the local code stored in the failed group need to be recovered as a whole. In this paper, local codes with cooperative repair, in which the local codes are constructed based on minimum storage regeneration (MSR) codes, is proposed to achieve repairing the failed groups. Specifically, the proposed local codes with cooperative repair construct a kind of mutual interleaving structure among the parity symbols, that the parity symbols of each local code, named as distributed local parity, can be generated by the parity symbols of the MSR codes in its two adjacent local codes. Taking advantage of the structure given, the failed local groups can be repaired cooperatively by their adjacent local groups with lower repair locality, and meanwhile the minimum distance of local codes with cooperative repair is derived. Theoretical analysis and simulation experiments show that, compared with codes with local regeneration (such as MSR-local codes and MBR-local codes), the proposed local codes with cooperative repair have benefits in bandwidth overhead and repair locality for the case of local groups failure.
Barbara Made the News: Mining the Behavior of Crowds for Time-Aware Learning to Rank
Venue: arXiv cs.IR 2016
Year: 2016

In Twitter, and other microblogging services, the generation of new content by the crowd is often biased towards immediacy: what is happening now. Prompted by the propagation of commentary and information through multiple mediums, users on the Web interact with and produce new posts about newsworthy topics and give rise to trending topics. This paper proposes to leverage on the behavioral dynamics of users to estimate the most relevant time periods for a topic. Our hypothesis stems from the fact that when a real-world event occurs it usually has peak times on the Web: a higher volume of tweets, new visits and edits to related Wikipedia articles, and news published about the event. In this paper, we propose a novel time-aware ranking model that leverages on multiple sources of crowd signals. Our approach builds on two major novelties. First, a unifying approach that given query q, mines and represents temporal evidence from multiple sources of crowd signals. This allows us to predict the temporal relevance of documents for query q. Second, a principled retrieval model that integrates temporal signals in a learning to rank framework, to rank results according to the predicted temporal relevance. Evaluation on the TREC 2013 and 2014 Microblog track datasets demonstrates that the proposed model achieves a relative improvement of 13.2% over lexical retrieval models and 6.2% over a learning to rank baseline.
Hazard analysis of human--robot interactions with HAZOP--UML
Venue: arXiv cs.RO 2016
Year: 2016

New safety critical systems are about to appear in our everyday life: advanced robots able to interact with humans and perform tasks at home, in hospitals , or at work. A hazardous behavior of those systems, induced by failures or extreme environment conditions, may lead to catastrophic consequences. Well-known risk analysis methods used in other critical domains (e.g., avion-ics, nuclear, medical, transportation), have to be extended or adapted due to the non-deterministic behavior of those systems, evolving in unstructured environments. One major challenge is thus to develop methods that can be applied at the very beginning of the development process, to identify hazards induced by robot tasks and their interactions with humans. In this paper we present a method which is based on an adaptation of a hazard identification technique, HAZOP (Hazard Operability), coupled with a system description notation, UML (Unified Modeling Language). This systematic approach has been applied successfully in research projects, and is now applied by robot manufacturers. Some results of those studies are presented and discussed to explain the benefits and limits of our method.
On the Instability of Sensor Orientation in Gait Verification on Mobile Phone
Venue: arXiv cs.CR 2016
Year: 2016

Authentication schemes using tokens or biometric modalities have been proposed to ameliorate the security strength on mobile devices. However, the existing approaches are obtrusive since the user is required to perform explicit gestures in order to be authenticated. While the gait signal captured by inertial sensors is understood to be a reliable profile for effective implicit authentication, recent studies have been conducted in ideal conditions and might therefore be inapplicable in the real mobile context. Particularly, the acquiring sensor is always fixed to a specific position and orientation. This paper mainly focuses on addressing the instability of sensor's orientation which mostly happens in the reality. A flexible solution taking advantages of available sensors on mobile devices which can help to handle this problem is presented. Moreover, a novel gait recognition method utilizes statistical analysis and supervised learning to adapt itself to the instability of the biometric gait under various circumstances is also proposed. By adopting PCA+SVM to construct the gait model, the proposed method outperformed other state-of-the-art studies, with an equal error rate of 2.45\% and accuracy rate of 99.14\% in terms of the verification and identification aspects being achieved, respectively.
Computing Distances between Reach Flowpipes
Venue: arXiv cs.SY 2016
Year: 2016

We investigate quantifying the difference between two hybrid dynamical systems under noise and initial-state uncertainty. While the set of traces for these systems is infinite, it is possible to symbolically approximate trace sets using \emph{reachpipes} that compute upper and lower bounds on the evolution of the reachable sets with time. We estimate distances between corresponding sets of trajectories of two systems in terms of distances between the reachpipes. In case of two individual traces, the Skorokhod distance has been proposed as a robust and efficient notion of distance which captures both value and timing distortions. In this paper, we extend the computation of the Skorokhod distance to reachpipes, and provide algorithms to compute upper and lower bounds on the distance between two sets of traces. Our algorithms use new geometric insights that are used to compute the worst-case and best-case distances between two polyhedral sets evolving with time.
A representation of a compressed de Bruijn graph for pan-genome analysis that enables search
Venue: arXiv cs.DS 2016
Year: 2016

Recently, Marcus et al. (Bioinformatics 2014) proposed to use a compressed de Bruijn graph to describe the relationship between the genomes of many individuals/strains of the same or closely related species. They devised an $O(n \log g)$ time algorithm called splitMEM that constructs this graph directly (i.e., without using the uncompressed de Bruijn graph) based on a suffix tree, where $n$ is the total length of the genomes and $g$ is the length of the longest genome. In this paper, we present a construction algorithm that outperforms their algorithm in theory and in practice. Moreover, we propose a new space-efficient representation of the compressed de Bruijn graph that adds the possibility to search for a pattern (e.g. an allele - a variant form of a gene) within the pan-genome.
Knowledge Transfer with Medical Language Embeddings
Venue: arXiv cs.CL 2016
Year: 2016

Identifying relationships between concepts is a key aspect of scientific knowledge synthesis. Finding these links often requires a researcher to laboriously search through scien- tific papers and databases, as the size of these resources grows ever larger. In this paper we describe how distributional semantics can be used to unify structured knowledge graphs with unstructured text to predict new relationships between medical concepts, using a probabilistic generative model. Our approach is also designed to ameliorate data sparsity and scarcity issues in the medical domain, which make language modelling more challenging. Specifically, we integrate the medical relational database (SemMedDB) with text from electronic health records (EHRs) to perform knowledge graph completion. We further demonstrate the ability of our model to predict relationships between tokens not appearing in the relational database.