OpenRaiser/Intern-Atlas huggingface dataset:
Least reliable messages based early termination method for LT soft decoder
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we propose a new early termination method (ETM) for Luby transform (LT) belief propagation (BP) decoder. The proposed ETM, which we call least reliable messages (LRM), observes only sign alterations of a small cluster in log-likelihood ratio (LLR) messages passing between nodes in BP decoder. Simulation results and complexity analyzes show that LRM significantly lower computational complexity of early termination section in decoder without any performance degradation and decreases the average decoding iteration amounts compared to conventional ETMs in literature. The method can be easily applied to code families which can be decoded by BP such as low density parity check (LDPC) codes, polar codes and Raptor codes.
A general purpose algorithm for counting simple cycles and simple paths of any length
Venue: arXiv cs.DS 2016
Year: 2016

We describe a general purpose algorithm for counting simple cycles and simple paths of any length $\ell$ on a (weighted di)graph on $N$ vertices and $M$ edges, achieving a time complexity of $O\left(N+M+\big(\ell^ω+\ellΔ\big) |S_\ell|\right)$. In this expression, $|S_\ell|$ is the number of (weakly) connected induced subgraphs of $G$ on at most $\ell$ vertices, $Δ$ is the maximum degree of any vertex and $ω$ is the exponent of matrix multiplication. We compare the algorithm complexity both theoretically and experimentally with most of the existing algorithms for the same task. These comparisons show that the algorithm described here is the best general purpose algorithm for the class of graphs where $(\ell^{ω-1}Δ^{-1}+1) |S_\ell|\leq |\text{Cycle}_\ell|$, with $|\text{Cycle}_\ell|$ the total number of simple cycles of length at most $\ell$, including backtracks and self-loops. On Erdős-Rényi random graphs, we find empirically that this happens when the edge probability is larger than circa $4/N$. In addition, we show that some real-world networks also belong to this class. Finally, the algorithm permits the enumeration of simple cycles and simple paths on networks where vertices are labeled from an alphabet on $n$ letters with a time complexity of $O\left(N+M+\big(n^\ell\ell^ω+\ellΔ\big) |S_\ell|\right)$. A Matlab implementation of the algorithm proposed here is available for download.
A Generalized Performance Evaluation Framework for Parallel Systems with Output Synchronization
Venue: arXiv cs.PF 2016
Year: 2016

Frameworks, such as MapReduce and Hadoop are abundant nowadays. They seek to reap benefits of parallelization, albeit subject to a synchronization constraint at the output. Fork-Join (FJ) queuing models are used to analyze such systems. Arriving jobs are split into tasks each of which is mapped to exactly one server. A job leaves the system when all of its tasks are executed. As a metric of performance, we consider waiting times for both work-conserving and non-work conserving server systems under a mathematical set-up general enough to take into account possible phase-type behavior of the servers, and as suggested by recent evidences, bursty arrivals. To this end, we present a Markov-additive process framework for an FJ system and provide computable bounds on tail probabilities of steady-state waiting times, for both types of servers separately. We apply our results to three scenarios, namely, non-renewal (Markov-modulated) arrivals, servers showing phase-type behavior, and Markov-modulated arrivals and services. We compare our bounds against estimates obtained through simulations and also provide a theoretical conceptualization of provisions in FJ systems. Finally, we calibrate our model with real data traces, and illustrate how our bounds can be used to devise provisions.
Prototyping RISC Based, Reconfigurable Networking Applications in Open Source
Venue: arXiv cs.AR 2016
Year: 2016

In the last decade we have witnessed a rapid growth in data center systems, requiring new and highly complex networking devices. The need to refresh networking infrastructure whenever new protocols or functions are introduced, and the increasing costs that this entails, are of a concern to all data center providers. New generations of Systems on Chip (SoC), integrating microprocessors and higher bandwidth interfaces, are an emerging solution to this problem. These devices permit entirely new systems and architectures that can obviate the replacement of existing networking devices while enabling seamless functionality change. In this work, we explore open source, RISC based, SoC architectures with high performance networking capabilities. The prototype architectures are implemented on the NetFPGA-SUME platform. Beyond details of the architecture, we also describe the hardware implementation and the porting of operating systems to the platform. The platform can be exploited for the development of practical networking appliances, and we provide use case examples.
Building Efficient Query Engines in a High-Level Language
Venue: arXiv cs.DB 2016
Year: 2016

Abstraction without regret refers to the vision of using high-level programming languages for systems development without experiencing a negative impact on performance. A database system designed according to this vision offers both increased productivity and high performance, instead of sacrificing the former for the latter as is the case with existing, monolithic implementations that are hard to maintain and extend. In this article, we realize this vision in the domain of analytical query processing. We present LegoBase, a query engine written in the high-level language Scala. The key technique to regain efficiency is to apply generative programming: LegoBase performs source-to-source compilation and optimizes the entire query engine by converting the high-level Scala code to specialized, low-level C code. We show how generative programming allows to easily implement a wide spectrum of optimizations, such as introducing data partitioning or switching from a row to a column data layout, which are difficult to achieve with existing low-level query compilers that handle only queries. We demonstrate that sufficiently powerful abstractions are essential for dealing with the complexity of the optimization effort, shielding developers from compiler internals and decoupling individual optimizations from each other. We evaluate our approach with the TPC-H benchmark and show that: (a) With all optimizations enabled, LegoBase significantly outperforms a commercial database and an existing query compiler. (b) Programmers need to provide just a few hundred lines of high-level code for implementing the optimizations, instead of complicated low-level code that is required by existing query compilation approaches. (c) The compilation overhead is low compared to the overall execution time, thus making our approach usable in practice for compiling query engines.
Optimal Differentially Private Mechanisms for Randomised Response
Venue: arXiv cs.CR 2016
Year: 2016

We examine a generalised Randomised Response (RR) technique in the context of differential privacy and examine the optimality of such mechanisms. Strict and relaxed differential privacy are considered for binary outputs. By examining the error of a statistical estimator, we present closed solutions for the optimal mechanism(s) in both cases. The optimal mechanism is also given for the specific case of the original RR technique as introduced by Warner in 1965.
Approximating Approximate Distance Oracles
Venue: arXiv cs.DS 2016
Year: 2016

Given a finite metric space $(V,d)$, an approximate distance oracle is a data structure which, when queried on two points $u,v \in V$, returns an approximation to the the actual distance between $u$ and $v$ which is within some bounded stretch factor of the true distance. There has been significant work on the tradeoff between the important parameters of approximate distance oracles (and in particular between the size, stretch, and query time), but in this paper we take a different point of view, that of per-instance optimization. If we are given an particular input metric space and stretch bound, can we find the smallest possible approximate distance oracle for that particular input? Since this question is not even well-defined, we restrict our attention to well-known classes of approximate distance oracles, and study whether we can optimize over those classes. In particular, we give an $O(\log n)$-approximation to the problem of finding the smallest stretch $3$ Thorup-Zwick distance oracle, as well as the problem of finding the smallest Pǎtraşcu-Roditty distance oracle. We also prove a matching $Ω(\log n)$ lower bound for both problems, and an $Ω(n^{\frac{1}{k}-\frac{1}{2^{k-1}}})$ integrality gap for the more general stretch $(2k-1)$ Thorup-Zwick distance oracle. We also consider the problem of approximating the best TZ or PR approximate distance oracle \emph{with outliers}, and show that more advanced techniques (SDP relaxations in particular) allow us to optimize even in the presence of outliers.
On the Non-existence of certain classes of perfect p-ary sequences and perfect almost p-ary sequences
Venue: arXiv cs.IT 2016
Year: 2016

We obtain new non-existence results of perfect p-ary sequences with period n (called type $[p, n]$). The first case is a class with type [p\equiv5\pmod 8,p^aqn']. The second case contains five types [p\equiv3\pmod 4,p^aq^ln'] for certain $p, q$ and $l$. Moreover, we also have similar non-existence results for perfect almost p-ary sequences.
Multi-modal Mining and Modeling of Big Mobile Networks Based on Users Behavior and Interest
Venue: arXiv cs.NI 2016
Year: 2016

Usage of mobile wireless Internet has grown very fast in recent years. This radical change in availability of Internet has led to communication of big amount of data over mobile networks and consequently new challenges and opportunities for modeling of mobile Internet characteristics. While the traditional approach toward network modeling suggests finding a generic traffic model for the whole network, in this paper, we show that this approach does not capture all the dynamics of big mobile networks and does not provide enough accuracy. Our case study based on a big dataset including billions of netflow records collected from a campus-wide wireless mobile network shows that user interests acquired based on accessed domains and visited locations as well as user behavioral groups have a significant impact on traffic characteristics of big mobile networks. For this purpose, we utilize a novel graph-based approach based on KS-test as well as a novel co-clustering technique. Our study shows that interest-based modeling of big mobile networks can significantly improve the accuracy and reduce the KS distance by factor of 5 comparing to the generic approach.
Microscopic Muscle Image Enhancement
Venue: arXiv cs.CV 2016
Year: 2016

We propose a robust image enhancement algorithm dedicated for muscle fiber specimen images captured by optical microscopes. Blur or out of focus problems are prevalent in muscle images during the image acquisition stage. Traditional image deconvolution methods do not work since they assume the blur kernels are known and also produce ring artifacts. We provide a compact framework which involves a novel spatially non-uniform blind deblurring approach specialized to muscle images which automatically detects and alleviates degraded regions. Ring artifacts problems are addressed and a kernel propagation strategy is proposed to speedup the algorithm and deals with the high non-uniformity of the blur kernels on muscle images. Experiments show that the proposed framework performs well on muscle images taken with modern advanced optical microscopes. Our framework is free of laborious parameter settings and is computationally efficient.
Web-based Semantic Similarity for Emotion Recognition in Web Objects
Venue: arXiv cs.CL 2016
Year: 2016

In this project we propose a new approach for emotion recognition using web-based similarity (e.g. confidence, PMI and PMING). We aim to extract basic emotions from short sentences with emotional content (e.g. news titles, tweets, captions), performing a web-based quantitative evaluation of semantic proximity between each word of the analyzed sentence and each emotion of a psychological model (e.g. Plutchik, Ekman, Lovheim). The phases of the extraction include: text preprocessing (tokenization, stop words, filtering), search engine automated query, HTML parsing of results (i.e. scraping), estimation of semantic proximity, ranking of emotions according to proximity measures. The main idea is that, since it is possible to generalize semantic similarity under the assumption that similar concepts co-occur in documents indexed in search engines, therefore also emotions can be generalized in the same way, through tags or terms that express them in a particular language, ranking emotions. Training results are compared to human evaluation, then additional comparative tests on results are performed, both for the global ranking correlation (e.g. Kendall, Spearman, Pearson) both for the evaluation of the emotion linked to each single word. Different from sentiment analysis, our approach works at a deeper level of abstraction, aiming at recognizing specific emotions and not only the positive/negative sentiment, in order to predict emotions as semantic data.
New Architecture for Dynamic Spectrum Allocation in Cognitive Heterogeneous Network using Self Organizing Map
Venue: arXiv cs.NI 2016
Year: 2016

This paper introduces the Hybrid Architecture of Dynamic Spectrum Allocation in the hierarchical network combining centralized and distributed architecture to get optimum allocation of radio resources. It can limit the interference by interacting dynamically and enhance the spectrum efficiency while maintaining the desired QoS in the network. This paper presented dynamic framework for the interaction. The proposed architecture employed simple learning rule based on hebbian learning for sensing the primary network and allocating the spectrum.
Physical-Layer Security of a Buffer-Aided Full-Duplex Relaying~System
Venue: arXiv cs.NI 2016
Year: 2016

This letter proposes a novel hybrid half-/full-duplex relaying scheme to enhance the relay channel security. A source node (Alice) communicates with her destination node (Bob) in the presence of a buffer-aided full-duplex relay node (Rooney) and a potential eavesdropper (Eve). Rooney adopts two different relaying strategies, namely randomize-and-forward and decode-and-forward relaying strategies, to improve the security of the legitimate system. In the first relaying strategy, Rooney uses a codebook different from that used at Alice. In the second relaying strategy, Rooney and Alice use the same codebooks. In addition, Rooney switches between half-duplex and full-duplex modes to further enhance the security of the legitimate system. The numerical results demonstrate that our proposed scheme achieves a significant average secrecy end-to-end throughput improvement relative to the conventional bufferless full-duplex relaying scheme.
A Probabilistic Representation for Dynamic Movement Primitives
Venue: arXiv cs.RO 2016
Year: 2016

Dynamic Movement Primitives have successfully been used to realize imitation learning, trial-and-error learning, reinforce- ment learning, movement recognition and segmentation and control. Because of this they have become a popular represen- tation for motor primitives. In this work, we showcase how DMPs can be reformulated as a probabilistic linear dynamical system with control inputs. Through this probabilistic repre- sentation of DMPs, algorithms such as Kalman filtering and smoothing are directly applicable to perform inference on pro- prioceptive sensor measurements during execution. We show that inference in this probabilistic model automatically leads to a feedback term to online modulate the execution of a DMP. Furthermore, we show how inference allows us to measure the likelihood that we are successfully executing a given motion primitive. In this context, we show initial results of using the probabilistic model to detect execution failures on a simulated movement primitive dataset.
A Hidden Absorbing Semi-Markov Model for Informatively Censored Temporal Data: Learning and Inference
Venue: arXiv cs.AI 2016
Year: 2016

Modeling continuous-time physiological processes that manifest a patient's evolving clinical states is a key step in approaching many problems in healthcare. In this paper, we develop the Hidden Absorbing Semi-Markov Model (HASMM): a versatile probabilistic model that is capable of capturing the modern electronic health record (EHR) data. Unlike exist- ing models, an HASMM accommodates irregularly sampled, temporally correlated, and informatively censored physiological data, and can describe non-stationary clinical state transitions. Learning an HASMM from the EHR data is achieved via a novel forward- filtering backward-sampling Monte-Carlo EM algorithm that exploits the knowledge of the end-point clinical outcomes (informative censoring) in the EHR data, and implements the E-step by sequentially sampling the patients' clinical states in the reverse-time direction while conditioning on the future states. Real-time inferences are drawn via a forward- filtering algorithm that operates on a virtually constructed discrete-time embedded Markov chain that mirrors the patient's continuous-time state trajectory. We demonstrate the di- agnostic and prognostic utility of the HASMM in a critical care prognosis setting using a real-world dataset for patients admitted to the Ronald Reagan UCLA Medical Center.
The Observability Radius of Networks
Venue: arXiv cs.SY 2016
Year: 2016

This paper studies the observability radius of network systems, which measures the robustness of a network to perturbations of the edges. We consider linear networks, where the dynamics are described by a weighted adjacency matrix, and dedicated sensors are positioned at a subset of nodes. We allow for perturbations of certain edge weights, with the objective of preventing observability of some modes of the network dynamics. To comply with the network setting, our work considers perturbations with a desired sparsity structure, thus extending the classic literature on the observability radius of linear systems. The paper proposes two sets of results. First, we propose an optimization framework to determine a perturbation with smallest Frobenius norm that renders a desired mode unobservable from the existing sensor nodes. Second, we study the expected observability radius of networks with given structure and random edge weights. We provide fundamental robustness bounds dependent on the connectivity properties of the network and we analytically characterize optimal perturbations of line and star networks, showing that line networks are inherently more robust than star networks.
A modified Physarum-inspired model for the user equilibrium traffic assignment problem
Venue: arXiv cs.ET 2016
Year: 2016

The user equilibrium traffic assignment principle is very important in the traffic assignment problem. Mathematical programming models are designed to solve the user equilibrium problem in traditional algorithms. Recently, the Physarum shows the ability to address the user equilibrium and system optimization traffic assignment problems. However, the Physarum model are not efficient in real traffic networks with two-way traffic characteristics and multiple origin-destination pairs. In this article, a modified Physarum-inspired model for the user equilibrium problem is proposed. By decomposing traffic flux based on origin nodes, the traffic flux from different origin-destination pairs can be distinguished in the proposed model. The Physarum can obtain the equilibrium traffic flux when no shorter path can be discovered between each origin-destination pair. Finally, numerical examples use the Sioux Falls network to demonstrate the rationality and convergence properties of the proposed model.
The Authorization Policy Existence Problem
Venue: arXiv cs.CR 2016
Year: 2016

Constraints such as separation-of-duty are widely used to specify requirements that supplement basic authorization policies. However, the existence of constraints (and authorization policies) may mean that a user is unable to fulfill her/his organizational duties because access to resources has been denied. In short, there is a tension between the need to protect resources (using policies and constraints) and the availability of resources. Recent work on workflow satisfiability and resiliency in access control asks whether this tension compromises the ability of an organization to achieve its objectives. In this paper, we develop a new method of specifying constraints which subsumes much related work and allows a wider range of constraints to be specified. The use of such constraints leads naturally to a range of questions related to "policy existence", where a positive answer means that an organization's objectives can be realized. We analyze the complexity of these policy existence questions and, for particular sub-classes of constraints defined by our language, develop fixed-parameter tractable algorithms to solve them.
Photo-Quality Evaluation based on Computational Aesthetics: Review of Feature Extraction Techniques
Venue: arXiv cs.CV 2016
Year: 2016

Researchers try to model the aesthetic quality of photographs into low and high- level features, drawing inspiration from art theory, psychology and marketing. We attempt to describe every feature extraction measure employed in the above process. The contribution of this literature review is the taxonomy of each feature by its implementation complexity, considering real-world applications and integration in mobile apps and digital cameras. Also, we discuss the machine learning results along with some unexplored research areas as future work.
VAST : The Virtual Acoustic Space Traveler Dataset
Venue: arXiv cs.SD 2016
Year: 2016

This paper introduces a new paradigm for sound source lo-calization referred to as virtual acoustic space traveling (VAST) and presents a first dataset designed for this purpose. Existing sound source localization methods are either based on an approximate physical model (physics-driven) or on a specific-purpose calibration set (data-driven). With VAST, the idea is to learn a mapping from audio features to desired audio properties using a massive dataset of simulated room impulse responses. This virtual dataset is designed to be maximally representative of the potential audio scenes that the considered system may be evolving in, while remaining reasonably compact. We show that virtually-learned mappings on this dataset generalize to real data, overcoming some intrinsic limitations of traditional binaural sound localization methods based on time differences of arrival.