OpenRaiser/Intern-Atlas huggingface dataset:
Compressed Differential Erasure Codes for Efficient Archival of Versioned Data
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we study the problem of storing an archive of versioned data in a reliable and efficient manner in distributed storage systems. We propose a new storage technique called differential erasure coding (DEC) where the differences (deltas) between subsequent versions are stored rather than the whole objects, akin to a typical delta encoding technique. However, unlike delta encoding techniques, DEC opportunistically exploits the sparsity (i.e., when the differences between two successive versions have few non-zero entries) in the updates to store the deltas using compressed sensing techniques applied with erasure coding. We first show that DEC provides significant savings in the storage size for versioned data whenever the update patterns are characterized by in-place alterations. Subsequently, we propose a practical DEC framework so as to reap storage size benefits against not just in-place alterations but also real-world update patterns such as insertions and deletions that alter the overall data sizes. We conduct experiments with several synthetic workloads to demonstrate that the practical variant of DEC provides significant reductions in storage overhead (up to 60\% depending on the workload) compared to baseline storage system which incorporates concepts from Rsync, a delta encoding technique to store and synchronize data across a network.
Replacing the Soft FEC Limit Paradigm in the Design of Optical Communication Systems
Venue: arXiv cs.IT 2015
Year: 2015

The FEC limit paradigm is the prevalent practice for designing optical communication systems to attain a certain bit-error rate (BER) without forward error correction (FEC). This practice assumes that there is an FEC code that will reduce the BER after decoding to the desired level. In this paper, we challenge this practice and show that the concept of a channel-independent FEC limit is invalid for soft-decision bit-wise decoding. It is shown that for low code rates and high order modulation formats, the use of the soft FEC limit paradigm can underestimate the spectral efficiencies by up to 20%. A better predictor for the BER after decoding is the generalized mutual information, which is shown to give consistent post-FEC BER predictions across different channel conditions and modulation formats. Extensive optical full-field simulations and experiments are carried out in both the linear and nonlinear transmission regimes to confirm the theoretical analysis.
Urban Magnetism Through The Lens of Geo-tagged Photography
Venue: arXiv cs.SI 2015
Year: 2015

There is an increasing trend of people leaving digital traces through social media. This reality opens new horizons for urban studies. With this kind of data, researchers and urban planners can detect many aspects of how people live in cities and can also suggest how to transform cities into more efficient and smarter places to live in. In particular, their digital trails can be used to investigate tastes of individuals, and what attracts them to live in a particular city or to spend their vacation there. In this paper we propose an unconventional way to study how people experience the city, using information from geotagged photographs that people take at different locations. We compare the spatial behavior of residents and tourists in 10 most photographed cities all around the world. The study was conducted on both a global and local level. On the global scale we analyze the 10 most photographed cities and measure how attractive each city is for people visiting it from other cities within the same country or from abroad. For the purpose of our analysis we construct the users mobility network and measure the strength of the links between each pair of cities as a level of attraction of people living in one city (i.e., origin) to the other city (i.e., destination). On the local level we study the spatial distribution of user activity and identify the photographed hotspots inside each city. The proposed methodology and the results of our study are a low cost mean to characterize a touristic activity within a certain location and can help in urban organization to strengthen their touristic potential.
Exploration of the scalability of LocFaults approach for error localization with While-loops programs
Venue: arXiv cs.AI 2015
Year: 2015

A model checker can produce a trace of counterexample, for an erroneous program, which is often long and difficult to understand. In general, the part about the loops is the largest among the instructions in this trace. This makes the location of errors in loops critical, to analyze errors in the overall program. In this paper, we explore the scala-bility capabilities of LocFaults, our error localization approach exploiting paths of CFG(Control Flow Graph) from a counterexample to calculate the MCDs (Minimal Correction Deviations), and MCSs (Minimal Correction Subsets) from each found MCD. We present the times of our approach on programs with While-loops unfolded b times, and a number of deviated conditions ranging from 0 to n. Our preliminary results show that the times of our approach, constraint-based and flow-driven, are better compared to BugAssist which is based on SAT and transforms the entire program to a Boolean formula, and further the information provided by LocFaults is more expressive for the user.
Time and Space Efficient Algorithms for RNA Folding with the Four-Russians Technique
Venue: arXiv cs.DS 2015
Year: 2015

In this paper, we develop new algorithms for the basic RNA folding problem. Given an RNA sequence that contains $n$ nucleotides, the goal of the problem is to compute a pseudoknot-free secondary structure that maximizes the number of base pairs in the sequence. We show that there exists a dynamic programming algorithm that can solve the problem in time $O(\frac{n^{3}}{\log_{2}{n}})$ while using only $O(\frac{n^{2}}{\log_{2}{n}})$ memory space. In addition, we show that the time complexity of this algorithm can be further improved to $O(\frac{n^{3}}{\log_{2}^{2}{n}})$ at the expense of a slightly increased space complexity. To the best of our knowledge, this is the first algorithm that can solve the problem with traditional dynamic programming techniques in time $O(\frac{n^{3}}{\log_{2}^{2}{n}})$. In addition, our results improve the best known upper bound of the space complexity for efficiently solving both this problem and the context-free language recognition problem.
Combinatorics and complexity of guarding polygons with edge and point 2-transmitters
Venue: arXiv cs.CG 2015
Year: 2015

We consider a generalization of the classical Art Gallery Problem, where instead of a light source, the guards, called $k$-transmitters, model a wireless device with a signal that can pass through at most $k$ walls. We show it is NP-hard to compute a minimum cover of point 2-transmitters, point $k$-transmitters, and edge 2-transmitters in a simple polygon. The point 2-transmitter result extends to orthogonal polygons. In addition, we give necessity and sufficiency results for the number of edge 2-transmitters in general, monotone, orthogonal monotone, and orthogonal polygons.
The Open Access Advantage Considering Citation, Article Usage and Social Media Attention
Venue: arXiv cs.DL 2015
Year: 2015

In this study, we compare the difference in the impact between open access (OA) and non-open access (non-OA) articles. 1761 Nature Communications articles published from 1 Jan. 2012 to 31 Aug. 2013 are selected as our research objects, including 587 OA articles and 1174 non-OA articles. Citation data and daily updated article-level metrics data are harvested directly from the platform of nature.com. Data is analyzed from the static versus temporal-dynamic perspectives. The OA citation advantage is confirmed, and the OA advantage is also applicable when extending the comparing from citation to article views and social media attention. More important, we find that OA papers not only have the great advantage of total downloads, but also have the feature of keeping sustained and steady downloads for a long time. For article downloads, non-OA papers only have a short period of attention, when the advantage of OA papers exists for a much longer time.
On Various Parameters of $Z_q$-Simplex codes for an even integer q
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we defined the $Z_q$-linear codes and discussed its various parameters. We constructed $Z_q$-Simplex code and $Z_q$-MacDonald code and found its parameters. We have given a lower and an upper bounds of its covering radius for q is an even integer.
DSpot: Test Amplification for Automatic Assessment of Computational Diversity
Venue: arXiv cs.SE 2015
Year: 2015

Context: Computational diversity, i.e., the presence of a set of programs that all perform compatible services but that exhibit behavioral differences under certain conditions, is essential for fault tolerance and security. Objective: We aim at proposing an approach for automatically assessing the presence of computational diversity. In this work, computationally diverse variants are defined as (i) sharing the same API, (ii) behaving the same according to an input-output based specification (a test-suite) and (iii) exhibiting observable differences when they run outside the specified input space. Method: Our technique relies on test amplification. We propose source code transformations on test cases to explore the input domain and systematically sense the observation domain. We quantify computational diversity as the dissimilarity between observations on inputs that are outside the specified domain. Results: We run our experiments on 472 variants of 7 classes from open-source, large and thoroughly tested Java classes. Our test amplification multiplies by ten the number of input points in the test suite and is effective at detecting software diversity. Conclusion: The key insights of this study are: the systematic exploration of the observable output space of a class provides new insights about its degree of encapsulation; the behavioral diversity that we observe originates from areas of the code that are characterized by their flexibility (caching, checking, formatting, etc.).
Sign Language Fingerspelling Classification from Depth and Color Images using a Deep Belief Network
Venue: arXiv cs.CV 2015
Year: 2015

Automatic sign language recognition is an open problem that has received a lot of attention recently, not only because of its usefulness to signers, but also due to the numerous applications a sign classifier can have. In this article, we present a new feature extraction technique for hand pose recognition using depth and intensity images captured from a Microsoft Kinect sensor. We applied our technique to American Sign Language fingerspelling classification using a Deep Belief Network, for which our feature extraction technique is tailored. We evaluated our results on a multi-user data set with two scenarios: one with all known users and one with an unseen user. We achieved 99% recall and precision on the first, and 77% recall and 79% precision on the second. Our method is also capable of real-time sign classification and is adaptive to any environment or lightning intensity.
Constant-complexity Stochastic Simulation Algorithm with Optimal Binning
Venue: arXiv cs.DS 2015
Year: 2015

At the cellular scale, biochemical processes are governed by random interactions between reactant molecules with small copy counts, leading to behavior that is inherently stochastic. Such systems are often modeled as continuous-time Markov jump processes that can be described by the Chemical Master Equation. Gillespie's Stochastic Simulation Algorithm (SSA) generates exact trajectories of these systems. The amount of computational work required for each step of the original SSA is proportional to the number of reaction channels, leading to computational complexity that scales linearly as the problem size increases. The original SSA is therefore inefficient for large problems, which has prompted the development of several alternative formulations with improved scaling properties. We describe an exact SSA that uses a table data structure with event time binning to achieve constant computational complexity. Optimal algorithm parameters and binning strategies are discussed. We compare the computational efficiency of the algorithm to existing methods and demonstrate excellent scaling for large problems. This method is well suited for generating exact trajectories of large models that can be described by the Reaction-Diffusion Master Equation arising from spatially discretized reaction-diffusion processes.
Optimal Exact Repair Strategy for the Parity Nodes of the $(k+2,k)$ Zigzag Code
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we reinterprets the $(k+2,k)$ Zigzag code in coding matrix and then propose an optimal exact repair strategy for its parity nodes, whose repair disk I/O approaches a lower bound derived in this paper.
Country-scale Exploratory Analysis of Call Detail Records through the Lens of Data Grid Models
Venue: arXiv cs.DB 2015
Year: 2015

Call Detail Records (CDRs) are data recorded by telecommunications companies, consisting of basic informations related to several dimensions of the calls made through the network: the source, destination, date and time of calls. CDRs data analysis has received much attention in the recent years since it might reveal valuable information about human behavior. It has shown high added value in many application domains like e.g., communities analysis or network planning. In this paper, we suggest a generic methodology for summarizing information contained in CDRs data. The method is based on a parameter-free estimation of the joint distribution of the variables that describe the calls. We also suggest several well-founded criteria that allows one to browse the summary at various granularities and to explore the summary by means of insightful visualizations. The method handles network graph data, temporal sequence data as well as user mobility data stemming from original CDRs data. We show the relevance of our methodology for various case studies on real-world CDRs data from Ivory Coast.
Maximizing the Sum Rate in Cellular Networks Using Multi-Convex Optimization
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we propose a novel algorithm to maximize the sum rate in interference-limited scenarios where each user decodes its own message with the presence of unknown interferences and noise considering the signal-to-interference-plus-noise-ratio. It is known that the problem of adapting the transmit and receive filters of the users to maximize the sum rate with a sum transmit power constraint is non-convex. Our novel approach is to formulate the sum rate maximization problem as an equivalent multi-convex optimization problem by adding two sets of auxiliary variables. An iterative algorithm which alternatingly adjusts the system variables and the auxiliary variables is proposed to solve the multi-convex optimization problem. The proposed algorithm is applied to a downlink cellular scenario consisting of several cells each of which contains a base station serving several mobile stations. We examine the two cases, with or without several half-duplex amplify-and-forward relays assisting the transmission. A sum power constraint at the base stations and a sum power constraint at the relays are assumed. Finally, we show that the proposed multi-convex formulation of the sum rate maximization problem is applicable to many other wireless systems in which the estimated data symbols are multi-affine functions of the system variables.
An Optimal Control Approach for the Data Harvesting Problem
Venue: arXiv cs.SY 2015
Year: 2015

We propose a new method for trajectory planning to solve the data harvesting problem. In a two-dimensional mission space, $N$ mobile agents are tasked with the collection of data generated at $M$ stationary sources and delivery to a base aiming at minimizing expected delays. An optimal control formulation of this problem provides some initial insights regarding its solution, but it is computationally intractable, especially in the case where the data generating processes are stochastic. We propose an agent trajectory parameterization in terms of general function families which can be subsequently optimized on line through the use of Infinitesimal Perturbation Analysis (IPA). Explicit results are provided for the case of elliptical and Fourier series trajectories and some properties of the solution are identified, including robustness with respect to the data generation processes and scalability in the size of an event set characterizing the underlying hybrid dynamic system.
Relationship-Based Access Control for OpenMRS
Venue: arXiv cs.CR 2015
Year: 2015

Inspired by the access control models of social network systems, Relationship-Based Access Control (ReBAC) was recently proposed as a general-purpose access control paradigm for application domains in which authorization must take into account the relationship between the access requestor and the resource owner. The healthcare domain is envisioned to be an archetypical application domain in which ReBAC is sorely needed: e.g., my patient record should be accessible only by my family doctor, but not by all doctors. In this work, we demonstrate for the first time that ReBAC can be incorporated into a production-scale medical records system, OpenMRS, with backward compatibility to the legacy RBAC mechanism. Specifically, we extend the access control mechanism of OpenMRS to enforce ReBAC policies. Our extensions incorporate and extend advanced ReBAC features recently proposed by Crampton and Sellwood. In addition, we designed and implemented the first administrative model for ReBAC. In this paper, we describe our ReBAC implementation, discuss the system engineering lessons learnt as a result, and evaluate the experimental work we have undertaken. In particular, we compare the performance of the various authorization schemes we implemented, thereby demonstrating the feasibility of ReBAC.
Identifying Similar Patients Using Self-Organising Maps: A Case Study on Type-1 Diabetes Self-care Survey Responses
Venue: arXiv cs.CE 2015
Year: 2015

Diabetes is considered a lifestyle disease and a well managed self-care plays an important role in the treatment. Clinicians often conduct surveys to understand the self-care behaviors in their patients. In this context, we propose to use Self-Organising Maps (SOM) to explore the survey data for assessing the self-care behaviors in Type-1 diabetic patients. Specifically, SOM is used to visualize high dimensional similar patient profiles, which is rarely discussed. Experiments demonstrate that our findings through SOM analysis corresponds well to the expectations of the clinicians. In addition, our findings inspire the experts to improve their understanding of the self-care behaviors for their patients. The principle findings in our study show: 1) patients who take correct dose of insulin, inject insulin at the right time, 2) patients who take correct food portions undertake regular physical activity and 3) patients who eat on time take correct food portions.
Wavelet based approach for tissue fractal parameter measurement: Pre cancer detection
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we have carried out the detail studies of pre-cancer by wavelet coherency and multifractal based detrended fluctuation analysis (MFDFA) on differential interference contrast (DIC) images of stromal region among different grades of pre-cancer tissues. Discrete wavelet transform (DWT) through Daubechies basis has been performed for identifying fluctuations over polynomial trends for clear characterization and differentiation of tissues. Wavelet coherence plots are performed for identifying the level of correlation in time scale plane between normal and various grades of DIC samples. Applying MFDFA on refractive index variations of cervical tissues, we have observed that the values of Hurst exponent (correlation) decreases from healthy (normal) to pre-cancer tissues. The width of singularity spectrum has a sudden degradation at grade-I in comparison of healthy (normal) tissue but later on it increases as cancer progresses from grade-II to grade-III.
Exploratory Data Analysis of The KelvinHelmholtz instability in Jets
Venue: arXiv cs.CE 2015
Year: 2015

The KelvinHelmholtz (KH) instability is a fundamental wave instability that is frequently observed in all kinds of shear layer (jets, wakes, atmospheric air currents etc). The study of KH-instability, coherent flow structures has a major impact in understanding the fundamentals of fluid dynamics. Therefore there is a need for methods that can identify and analyse these structures. In this Final assignment, we use machine-learning methods such as Proper Orthogonal Decomposition (POD) and Dynamic Mode Decomposition (DMD) to analyse the coherent flow structures. We used a 2D co-axial jet as our data, with Reynolds number corresponding to Re: 10,000. Results for POD modes and DMD modes are discussed and compared.
Boosting Convolutional Features for Robust Object Proposals
Venue: arXiv cs.CV 2015
Year: 2015

Deep Convolutional Neural Networks (CNNs) have demonstrated excellent performance in image classification, but still show room for improvement in object-detection tasks with many categories, in particular for cluttered scenes and occlusion. Modern detection algorithms like Regions with CNNs (Girshick et al., 2014) rely on Selective Search (Uijlings et al., 2013) to propose regions which with high probability represent objects, where in turn CNNs are deployed for classification. Selective Search represents a family of sophisticated algorithms that are engineered with multiple segmentation, appearance and saliency cues, typically coming with a significant run-time overhead. Furthermore, (Hosang et al., 2014) have shown that most methods suffer from low reproducibility due to unstable superpixels, even for slight image perturbations. Although CNNs are subsequently used for classification in top-performing object-detection pipelines, current proposal methods are agnostic to how these models parse objects and their rich learned representations. As a result they may propose regions which may not resemble high-level objects or totally miss some of them. To overcome these drawbacks we propose a boosting approach which directly takes advantage of hierarchical CNN features for detecting regions of interest fast. We demonstrate its performance on ImageNet 2013 detection benchmark and compare it with state-of-the-art methods.
Factorization in Formal Languages
Venue: arXiv cs.FL 2015
Year: 2015

We consider several novel aspects of unique factorization in formal languages. We reprove the familiar fact that the set uf(L) of words having unique factorization into elements of L is regular if L is regular, and from this deduce an quadratic upper and lower bound on the length of the shortest word not in uf(L). We observe that uf(L) need not be context-free if L is context-free. Next, we consider variations on unique factorization. We define a notion of "semi-unique" factorization, where every factorization has the same number of terms, and show that, if L is regular or even finite, the set of words having such a factorization need not be context-free. Finally, we consider additional variations, such as unique factorization "up to permutation" and "up to subset".