OpenRaiser/Intern-Atlas huggingface dataset:
Edge Coloring and Stopping Sets Analysis in Product Codes with MDS components
Venue: arXiv cs.IT 2016
Year: 2016

We consider non-binary product codes with MDS components and their iterative row-column algebraic decoding on the erasure channel. Both independent and block erasures are considered in this paper. A compact graph representation is introduced on which we define double-diversity edge colorings via the rootcheck concept. An upper bound of the number of decoding iterations is given as a function of the graph size and the color palette size $M$. Stopping sets are defined in the context of MDS components and a relationship is established with the graph representation. A full characterization of these stopping sets is given up to a size $(d_1+1)(d_2+1)$, where $d_1$ and $d_2$ are the minimum Hamming distances of the column and row MDS components respectively. Then, we propose a differential evolution edge coloring algorithm that produces colorings with a large population of minimal rootcheck order symbols. The complexity of this algorithm per iteration is $o(M^{\aleph})$, for a given differential evolution parameter $\aleph$, where $M^{\aleph}$ itself is small with respect to the huge cardinality of the coloring ensemble. The performance of MDS-based product codes with and without double-diversity coloring is analyzed in presence of both block and independent erasures. In the latter case, ML and iterative decoding are proven to coincide at small channel erasure probability. Furthermore, numerical results show excellent performance in presence of unequal erasure probability due to double-diversity colorings.
Performance Localisation
Venue: arXiv cs.SE 2016
Year: 2016

Performance becomes an issue particularly when execution cost hinders the functionality of a program. Typically a profiler can be used to find program code execution which represents a large portion of the overall execution cost of a program. Pinpointing where a performance issue exists provides a starting point for tracing cause back through a program. While profiling shows where a performance issue manifests, we use mutation analysis to show where a performance improvement is likely to exist. We find that mutation analysis can indicate locations within a program which are highly impactful to the overall execution cost of a program yet are executed relatively infrequently. By better locating potential performance improvements in programs we hope to make performance improvement more amenable to automation.
Delta State Replicated Data Types
Venue: arXiv cs.DC 2016
Year: 2016

CRDTs are distributed data types that make eventual consistency of a distributed object possible and non ad-hoc. Specifically, state-based CRDTs ensure convergence through disseminating the entire state, that may be large, and merging it to other replicas; whereas operation-based CRDTs disseminate operations (i.e., small states) assuming an exactly-once reliable dissemination layer. We introduce Delta State Conflict-Free Replicated Data Types ($δ$-CRDTs) that can achieve the best of both worlds: small messages with an incremental nature, as in operation-based CRDTs, disseminated over unreliable communication channels, as in traditional state-based CRDTs. This is achieved by defining delta mutators to return a delta-state, typically with a much smaller size than the full state, that to be joined with both local and remote states. We introduce the $δ$-CRDT framework, and we explain it through establishing a correspondence to current state-based CRDTs. In addition, we present an anti-entropy algorithm for eventual convergence, and another one that ensures causal consistency. Finally, we introduce several $δ$-CRDT specifications of both well-known replicated datatypes and novel datatypes, including a generic map composition.
Parallel Texts in the Hebrew Bible, New Methods and Visualizations
Venue: arXiv cs.CL 2016
Year: 2016

In this article we develop an algorithm to detect parallel texts in the Masoretic Text of the Hebrew Bible. The results are presented online and chapters in the Hebrew Bible containing parallel passages can be inspected synoptically. Differences between parallel passages are highlighted. In a similar way the MT of Isaiah is presented synoptically with 1QIsaa. We also investigate how one can investigate the degree of similarity between parallel passages with the help of a case study of 2 Kings 19-25 and its parallels in Isaiah, Jeremiah and 2 Chronicles.
Randomized algorithms for finding a majority element
Venue: arXiv cs.DS 2016
Year: 2016

Given $n$ colored balls, we want to detect if more than $\lfloor n/2\rfloor$ of them have the same color, and if so find one ball with such majority color. We are only allowed to choose two balls and compare their colors, and the goal is to minimize the total number of such operations. A well-known exercise is to show how to find such a ball with only $2n$ comparisons while using only a logarithmic number of bits for bookkeeping. The resulting algorithm is called the Boyer--Moore majority vote algorithm. It is known that any deterministic method needs $\lceil 3n/2\rceil-2$ comparisons in the worst case, and this is tight. However, it is not clear what is the required number of comparisons if we allow randomization. We construct a randomized algorithm which always correctly finds a ball of the majority color (or detects that there is none) using, with high probability, only $7n/6+o(n)$ comparisons. We also prove that the expected number of comparisons used by any such randomized method is at least $1.019n$.
Phase Retrieval of Real-Valued Signals in a Shift-Invariant Space
Venue: arXiv cs.IT 2016
Year: 2016

Phase retrieval arises in various fields of science and engineering and it is well studied in a finite-dimensional setting. In this paper, we consider an infinite-dimensional phase retrieval problem to reconstruct real-valued signals living in a shift-invariant space from its phaseless samples taken either on the whole line or on a set with finite sampling rate. We find the equivalence between nonseparability of signals in a linear space and its phase retrievability with phaseless samples taken on the whole line. For a spline signal of order $N$, we show that it can be well approximated, up to a sign, from its noisy phaseless samples taken on a set with sampling rate $2N-1$. We propose an algorithm to reconstruct nonseparable signals in a shift-invariant space generated by a compactly supported continuous function. The proposed algorithm is robust against bounded sampling noise and it could be implemented in a distributed manner.
Intracell Interference Characterization and Cluster Inference for D2D Communication
Venue: arXiv cs.IT 2016
Year: 2016

The homogeneous poisson point process (PPP) is widely used to model temporal, spatial or both topologies of base stations (BSs) and mobile terminals (MTs). However, negative spatial correlation in BSs, due to strategical deployments, and positive spatial correlations in MTs, due to homophilic relations, cannot be captured by homogeneous spatial PPP (SPPP). In this paper, we assume doubly stochastic poisson process, a generalization of homogeneous PPP, with intensity measure as another stochastic process. To this end, we assume Permanental Cox Process (PCP) to capture positive spatial correlation in MTs. We consider product density to derive closed-form approximation (CFA) of spatial summary statistics. We propose Euler Characteristic (EC) based novel approach to approximate intractable random intensity measure and subsequently derive nearest neighbor distribution function. We further propose the threshold and spatial extent of excursion set of chi-square random field as interference control parameters to select different cluster sizes for device-to-device (D2D) communication. The spatial extent of clusters is controlled by nearest neighbor distribution function which is incorporated into Laplace functional of SPPP to analyze the effect of D2D interfering clusters on average coverage probability of cellular user. The CFA and empirical results are in good agreement and its comparison with SPPP clearly shows spatial correlation between D2D nodes.
Underwater Fish Tracking for Moving Cameras based on Deformable Multiple Kernels
Venue: arXiv cs.CV 2016
Year: 2016

Fishery surveys that call for the use of single or multiple underwater cameras have been an emerging technology as a non-extractive mean to estimate the abundance of fish stocks. Tracking live fish in an open aquatic environment posts challenges that are different from general pedestrian or vehicle tracking in surveillance applications. In many rough habitats fish are monitored by cameras installed on moving platforms, where tracking is even more challenging due to inapplicability of background models. In this paper, a novel tracking algorithm based on the deformable multiple kernels (DMK) is proposed to address these challenges. Inspired by the deformable part model (DPM) technique, a set of kernels is defined to represent the holistic object and several parts that are arranged in a deformable configuration. Color histogram, texture histogram and the histogram of oriented gradients (HOG) are extracted and serve as object features. Kernel motion is efficiently estimated by the mean-shift algorithm on color and texture features to realize tracking. Furthermore, the HOG-feature deformation costs are adopted as soft constraints on kernel positions to maintain the part configuration. Experimental results on practical video set from underwater moving cameras show the reliable performance of the proposed method with much less computational cost comparing with state-of-the-art techniques.
Understanding the Sparse Vector Technique for Differential Privacy
Venue: arXiv cs.CR 2016
Year: 2016

The Sparse Vector Technique (SVT) is a fundamental technique for satisfying differential privacy and has the unique quality that one can output some query answers without apparently paying any privacy cost. SVT has been used in both the interactive setting, where one tries to answer a sequence of queries that are not known ahead of the time, and in the non-interactive setting, where all queries are known. Because of the potential savings on privacy budget, many variants for SVT have been proposed and employed in privacy-preserving data mining and publishing. However, most variants of SVT are actually not private. In this paper, we analyze these errors and identify the misunderstandings that likely contribute to them. We also propose a new version of SVT that provides better utility, and introduce an effective technique to improve the performance of SVT. These enhancements can be applied to improve utility in the interactive setting. Through both analytical and experimental comparisons, we show that, in the non-interactive setting (but not the interactive setting), the SVT technique is unnecessary, as it can be replaced by the Exponential Mechanism (EM) with better accuracy.
A Linked Data Scalability Challenge: Concept Reuse Leads to Semantic Decay
Venue: arXiv cs.AI 2016
Year: 2016

The increasing amount of available Linked Data resources is laying the foundations for more advanced Semantic Web applications. One of their main limitations, however, remains the general low level of data quality. In this paper we focus on a measure of quality which is negatively affected by the increase of the available resources. We propose a measure of semantic richness of Linked Data concepts and we demonstrate our hypothesis that the more a concept is reused, the less semantically rich it becomes. This is a significant scalability issue, as one of the core aspects of Linked Data is the propagation of semantic information on the Web by reusing common terms. We prove our hypothesis with respect to our measure of semantic richness and we validate our model empirically. Finally, we suggest possible future directions to address this scalability problem.
Approaches to Modeling Insurgency
Venue: arXiv cs.MA 2016
Year: 2016

This paper begins with an introduction to qualitative theories and models of insurgency, quantitative measures of insurgency, influence diagrams, system dynamics models of insurgency, agent based molding of insurgency, human-in-the-loop wargaming of insurgency, and statistical models of insurgency. The paper then presents a detailed case study of an agent-based model that focuses on the Troubles in Northern Ireland starting in 1968. The model is agent-based and uses a modeling tool called Simulation of Cultural Identities for Prediction of Reactions (SCIPR). The objective in this modeling effort was to predict trends in the degree of population's support to parties in this conflict. The case studies describes in detail the agents, their actions, model initialization and simulation process, and the results of the simulation compared to actual historical results of elections.
Variational methods for Conditional Multimodal Deep Learning
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we address the problem of conditional modality learning, whereby one is interested in generating one modality given the other. While it is straightforward to learn a joint distribution over multiple modalities using a deep multimodal architecture, we observe that such models aren't very effective at conditional generation. Hence, we address the problem by learning conditional distributions between the modalities. We use variational methods for maximizing the corresponding conditional log-likelihood. The resultant deep model, which we refer to as conditional multimodal autoencoder (CMMA), forces the latent representation obtained from a single modality alone to be `close' to the joint representation obtained from multiple modalities. We use the proposed model to generate faces from attributes. We show that the faces generated from attributes using the proposed model, are qualitatively and quantitatively more representative of the attributes from which they were generated, than those obtained by other deep generative models. We also propose a secondary task, whereby the existing faces are modified by modifying the corresponding attributes. We observe that the modifications in face introduced by the proposed model are representative of the corresponding modifications in attributes.
A Latent Variable Recurrent Neural Network for Discourse Relation Language Models
Venue: arXiv cs.CL 2016
Year: 2016

This paper presents a novel latent variable recurrent neural network architecture for jointly modeling sequences of words and (possibly latent) discourse relations between adjacent sentences. A recurrent neural network generates individual words, thus reaping the benefits of discriminatively-trained vector representations. The discourse relations are represented with a latent variable, which can be predicted or marginalized, depending on the task. The resulting model can therefore employ a training objective that includes not only discourse relation classification, but also word prediction. As a result, it outperforms state-of-the-art alternatives for two tasks: implicit discourse relation classification in the Penn Discourse Treebank, and dialog act classification in the Switchboard corpus. Furthermore, by marginalizing over latent discourse relations at test time, we obtain a discourse informed language model, which improves over a strong LSTM baseline.
A Two-Stage Shape Retrieval (TSR) Method with Global and Local Features
Venue: arXiv cs.CV 2016
Year: 2016

A robust two-stage shape retrieval (TSR) method is proposed to address the 2D shape retrieval problem. Most state-of-the-art shape retrieval methods are based on local features matching and ranking. Their retrieval performance is not robust since they may retrieve globally dissimilar shapes in high ranks. To overcome this challenge, we decompose the decision process into two stages. In the first irrelevant cluster filtering (ICF) stage, we consider both global and local features and use them to predict the relevance of gallery shapes with respect to the query. Irrelevant shapes are removed from the candidate shape set. After that, a local-features-based matching and ranking (LMR) method follows in the second stage. We apply the proposed TSR system to MPEG-7, Kimia99 and Tari1000 three datasets and show that it outperforms all other existing methods. The robust retrieval performance of the TSR system is demonstrated.
Partially Block Markov Superposition Transmission of Gaussian Source with Nested Lattice Codes
Venue: arXiv cs.IT 2016
Year: 2016

This paper studies the transmission of Gaussian sources through additive white Gaussian noise (AWGN) channels in bandwidth expansion regime, i.e., the channel bandwidth is greater than the source bandwidth. To mitigate the error propagation phenomenon of conventional digital transmission schemes, we propose in this paper a new capacity-approaching joint source channel coding (JSCC) scheme based on partially block Markov superposition transmission (BMST) of nested lattice codes. In the proposed scheme, first, the Gaussian source sequence is discretized by a lattice-based quantizer, resulting in a sequence of lattice points. Second, these lattice points are encoded by a short systematic group code. Third, the coded sequence is partitioned into blocks of equal length and then transmitted in the BMST manner. Main characteristics of the proposed JSCC scheme include: 1) Entropy coding is not used explicitly. 2) Only parity-check sequence is superimposed, hence, termed partially BMST (PBMST). This is different from the original BMST. To show the superior performance of the proposed scheme, we present extensive simulation results which show that the proposed scheme performs within 1.0 dB of the Shannon limits. Hence, the proposed scheme provides an attractive candidate for transmission of Gaussian sources.
Independent Sets in Classes Related to Chair/Fork-free Graphs
Venue: arXiv cs.DM 2016
Year: 2016

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. MWIS is known to be $NP$-complete in general, even under various restrictions. Let $S_{i,j,k}$ be the graph consisting of three induced paths of lengths $i, j, k$ with a common initial vertex. The complexity of the MWIS problem for $S_{1, 2, 2}$-free graphs, and for $S_{1, 1, 3}$-free graphs are open. In this paper, we show that the MWIS problem can solved in polynomial time for ($S_{1, 2, 2}$, $S_{1, 1, 3}$, co-chair)-free graphs, by analyzing the structure of the subclasses of this class of graphs. This extends some known results in the literature.
Aggregated 2D Range Queries on Clustered Points
Venue: arXiv cs.DS 2016
Year: 2016

Efficient processing of aggregated range queries on two-dimensional grids is a common requirement in information retrieval and data mining systems, for example in Geographic Information Systems and OLAP cubes. We introduce a technique to represent grids supporting aggregated range queries that requires little space when the data points in the grid are clustered, which is common in practice. We show how this general technique can be used to support two important types of aggregated queries, which are ranked range queries and counting range queries. Our experimental evaluation shows that this technique can speed up aggregated queries up to more than an order of magnitude, with a small space overhead.
From Design Contracts to Component Requirements Verification
Venue: arXiv cs.SE 2016
Year: 2016

During the development and verification of complex airborne systems, a variety of languages and development environments are used for different levels of the system hierarchy. As a result, there may be manual steps to translate requirements between these different environments. This paper presents a tool-supported export technique that translates high-level requirements from the software architecture modeling environment into observers of requirements that can be used for verification in the software component environment. This allows efficient verification that the component designs comply with their high-level requirements. It also provides an automated tool chain supporting formal verification from system requirements down to low-level software requirements that is consistent with certification guidance for avionics systems. The effectiveness of the technique has been evaluated and demonstrated on a medical infusion pump and an aircraft wheel braking system.
Authenticating users through their arm movement patterns
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we propose four continuous authentication designs by using the characteristics of arm movements while individuals walk. The first design uses acceleration of arms captured by a smartwatch's accelerometer sensor, the second design uses the rotation of arms captured by a smartwatch's gyroscope sensor, third uses the fusion of both acceleration and rotation at the feature-level and fourth uses the fusion at score-level. Each of these designs is implemented by using four classifiers, namely, k nearest neighbors (k-NN) with Euclidean distance, Logistic Regression, Multilayer Perceptrons, and Random Forest resulting in a total of sixteen authentication mechanisms. These authentication mechanisms are tested under three different environments, namely an intra-session, inter-session on a dataset of 40 users and an inter-phase on a dataset of 12 users. The sessions of data collection were separated by at least ten minutes, whereas the phases of data collection were separated by at least three months. Under the intra-session environment, all of the twelve authentication mechanisms achieve a mean dynamic false accept rate (DFAR) of 0% and dynamic false reject rate (DFRR) of 0%. For the inter-session environment, feature level fusion-based design with classifier k-NN achieves the best error rates that are a mean DFAR of 2.2% and DFRR of 4.2%. The DFAR and DFRR increased from 5.68% and 4.23% to 15.03% and 14.62% respectively when feature level fusion-based design with classifier k-NN was tested under the inter-phase environment on a dataset of 12 users.
Blur Robust Optical Flow using Motion Channel
Venue: arXiv cs.CV 2016
Year: 2016

It is hard to estimate optical flow given a realworld video sequence with camera shake and other motion blur. In this paper, we first investigate the blur parameterization for video footage using near linear motion elements. we then combine a commercial 3D pose sensor with an RGB camera, in order to film video footage of interest together with the camera motion. We illustrates that this additional camera motion/trajectory channel can be embedded into a hybrid framework by interleaving an iterative blind deconvolution and warping based optical flow scheme. Our method yields improved accuracy within three other state-of-the-art baselines given our proposed ground truth blurry sequences; and several other realworld sequences filmed by our imaging system.
Auditing spreadsheets: With or without a tool?
Venue: arXiv cs.SE 2016
Year: 2016

Spreadsheets are known to be error-prone. Over the last decade, research has been done to determine the causes of the high rate of errors in spreadsheets. This paper examines the added value of a spreadsheet tool (PerfectXL) that visualizes spreadsheet dependencies and determines possible errors in spreadsheets by defining risk areas based on previous work. This paper will firstly discuss the most common mistakes in spreadsheets. Then we will summarize research on spreadsheet tools, focussing on the PerfectXL tool. To determine the perceptions of the usefulness of a spreadsheet tool in general and the PerfectXL tool in particular, we have shown the functionality of PerfectXL to several auditors and have also interviewed them. The results of these interviews indicate that spreadsheet tools support a more effective and efficient audit of spreadsheets; the visualization feature in particular is mentioned by the auditors as being highly supportive for their audit task, whereas the risk feature was deemed of lesser value.