OpenRaiser/Intern-Atlas huggingface dataset:
Local error estimates for adaptive simulation of the Reaction-Diffusion Master Equation via operator splitting
Venue: arXiv cs.NA 2013
Year: 2013

The efficiency of exact simulation methods for the reaction-diffusion master equation (RDME) is severely limited by the large number of diffusion events if the mesh is fine or if diffusion constants are large. Furthermore, inherent properties of exact kinetic-Monte Carlo simulation methods limit the efficiency of parallel implementations. Several approximate and hybrid methods have appeared that enable more efficient simulation of the RDME. A common feature to most of them is that they rely on splitting the system into its reaction and diffusion parts and updating them sequentially over a discrete timestep. This use of operator splitting enables more efficient simulation but it comes at the price of a temporal discretization error that depends on the size of the timestep. So far, existing methods have not attempted to estimate or control this error in a systematic manner. This makes the solvers hard to use for practitioners since they must guess an appropriate timestep. It also makes the solvers potentially less efficient than if the timesteps are adapted to control the error. Here, we derive estimates of the local error and propose a strategy to adaptively select the timestep when the RDME is simulated via a first order operator splitting. While the strategy is general and applicable to a wide range of approximate and hybrid methods, we exemplify it here by extending a previously published approximate method, the Diffusive Finite-State Projection (DFSP) method, to incorporate temporal adaptivity.
Coding with Encoding Uncertainty
Venue: arXiv cs.IT 2013
Year: 2013

We study the channel coding problem when errors and uncertainty occur in the encoding process. For simplicity we assume the channel between the encoder and the decoder is perfect. Focusing on linear block codes, we model the encoding uncertainty as erasures on the edges in the factor graph of the encoder generator matrix. We first take a worst-case approach and find the maximum tolerable number of erasures for perfect error correction. Next, we take a probabilistic approach and derive a sufficient condition on the rate of a set of codes, such that decoding error probability vanishes as blocklength tends to infinity. In both scenarios, due to the inherent asymmetry of the problem, we derive the results from first principles, which indicates that robustness to encoding errors requires new properties of codes different from classical properties.
On the periodic behavior of real-time schedulers on identical multiprocessor platforms
Venue: arXiv cs.OS 2013
Year: 2013

This paper is proposing a general periodicity result concerning any deterministic and memoryless scheduling algorithm (including non-work-conserving algorithms), for any context, on identical multiprocessor platforms. By context we mean the hardware architecture (uniprocessor, multicore), as well as task constraints like critical sections, precedence constraints, self-suspension, etc. Since the result is based only on the releases and deadlines, it is independent from any other parameter. Note that we do not claim that the given interval is minimal, but it is an upper bound for any cycle of any feasible schedule provided by any deterministic and memoryless scheduler.
Rule-Based Semantic Tagging. An Application Undergoing Dictionary Glosses
Venue: arXiv cs.CL 2013
Year: 2013

The project presented in this article aims to formalize criteria and procedures in order to extract semantic information from parsed dictionary glosses. The actual purpose of the project is the generation of a semantic network (nearly an ontology) issued from a monolingual Italian dictionary, through unsupervised procedures. Since the project involves rule-based Parsing, Semantic Tagging and Word Sense Disambiguation techniques, its outcomes may find an interest also beyond this immediate intent. The cooperation of both syntactic and semantic features in meaning construction are investigated, and procedures which allows a translation of syntactic dependencies in semantic relations are discussed. The procedures that rise from this project can be applied also to other text types than dictionary glosses, as they convert the output of a parsing process into a semantic representation. In addition some mechanism are sketched that may lead to a kind of procedural semantics, through which multiple paraphrases of an given expression can be generated. Which means that these techniques may find an application also in 'query expansion' strategies, interesting Information Retrieval, Search Engines and Question Answering Systems.
Joint Model-Order and Step-Size Adaptation using Convex Combinations of Adaptive Reduced-Rank Filters
Venue: arXiv cs.IT 2013
Year: 2013

In this work we propose schemes for joint model-order and step-size adaptation of reduced-rank adaptive filters. The proposed schemes employ reduced-rank adaptive filters in parallel operating with different orders and step sizes, which are exploited by convex combination strategies. The reduced-rank adaptive filters used in the proposed schemes are based on a joint and iterative decimation and interpolation (JIDF) method recently proposed. The unique feature of the JIDF method is that it can substantially reduce the number of coefficients for adaptation, thereby making feasible the use of multiple reduced-rank filters in parallel. We investigate the performance of the proposed schemes in an interference suppression application for CDMA systems. Simulation results show that the proposed schemes can significantly improve the performance of the existing reduced-rank adaptive filters based on the JIDF method.
Gaussian Sensor Networks with Adversarial Nodes
Venue: arXiv cs.IT 2013
Year: 2013

This paper studies a particular sensor network model which involves one single Gaussian source observed by many sensors, subject to additive independent Gaussian observation noise. Sensors communicate with the receiver over an additive Gaussian multiple access channel. The aim of the receiver is to reconstruct the underlying source with minimum mean squared error. The scenario of interest here is one where some of the sensors act as adversary (jammer): they strive to maximize distortion. We show that the ability of transmitter sensors to secretly agree on a random event, that is "coordination", plays a key role in the analysis. Depending on the coordination capability of sensors and the receiver, we consider two problem settings. The first setting involves transmitters with coordination capabilities in the sense that all transmitters can use identical realization of randomized encoding for each transmission. In this case, the optimal strategy for the adversary sensors also requires coordination, where they all generate the same realization of independent and identically distributed Gaussian noise. In the second setting, the transmitter sensors are restricted to use fixed, deterministic encoders and this setting, which corresponds to a Stackelberg game, does not admit a saddle-point solution. We show that the the optimal strategy for all sensors is uncoded communications where encoding functions of adversaries and transmitters are in opposite directions. For both settings, digital compression and communication is strictly suboptimal.
Spectral Efficiency and Energy Efficiency of OFDM Systems: Impact of Power Amplifiers and Countermeasures
Venue: arXiv cs.IT 2013
Year: 2013

In wireless communication systems, the nonlinear effect and inefficiency of power amplifier (PA) have posed practical challenges for system designs to achieve high spectral efficiency (SE) and energy efficiency (EE). In this paper, we analyze the impact of PA on the SE-EE tradeoff of orthogonal frequency division multiplex (OFDM) systems. An ideal PA that is always linear and incurs no additional power consumption can be shown to yield a decreasing convex function in the SE-EE tradeoff. In contrast, we show that a practical PA has an SE-EE tradeoff that has a turning point and decreases sharply after its maximum EE point. In other words, the Pareto-optimal tradeoff boundary of the SE-EE curve is very narrow. A wide range of SE-EE tradeoff, however, is desired for future wireless communications that have dynamic demand depending on the traffic loads, channel conditions, and system applications, e.g., high-SE-with-low-EE for rate-limited systems and high-EE-with-low-SE for energy-limited systems. For the SE-EE tradeoff improvement, we propose a PA switching (PAS) technique. In a PAS transmitter, one or more PAs are switched on intermittently to maximize the EE and deliver an overall required SE. As a consequence, a high EE over a wide range SE can be achieved, which is verified by numerical evaluations: with 15% SE reduction for low SE demand, the PAS between a low power PA and a high power PA can improve EE by 323%, while a single high power PA transmitter improves EE by only 68%.
A Conceptual E-Governance Framework for Improving Child Immunization Process in India
Venue: arXiv cs.CY 2013
Year: 2013

India is country having high population and great variations in the educational level, economic conditions, population densities, cultures and awareness levels. Due to these variations the immunization process is not so much successful as per expectations of the state and central governments. In some zones the significant amount of vaccines are wasted whereas some are running out of vaccines. One of the reasons for such an imbalance is improper quantity estimation of vaccines in a particular zone. Further a huge amount of liquidity will be wasted in the form of vaccines. If we inculcate ICT (Information and Communication Technology) in the process of immunization then the problem can be rectified to some extent and hence we are proposing a conceptual model using ICT to improve the process of vaccination.
Wide Band Time-Correlated Model for Wireless Communications under Impulsive Noise within Power Substation
Venue: arXiv cs.NI 2013
Year: 2013

The installation of wireless technologies in power substations requires characterizing the impulsive noise produced by the high-voltage equipment. Substation impulsive noise might interfere with classic wireless communications and none of the existing models can reliably represent this noise in wide band. Previous studies have shown that impulsive noise is characterized by series of damped oscillations with the amplitude, the duration and the occurrence times of the impulses that are random. All these characteristics make this noise time-correlated and the partitioned Markov chain remains an efficient model that can ensure the correlation between the samples. In this study, we propose to design a partitioned Markov chain to generate an impulsive noise that is similar to the noise measured in existing substations, in time and frequency domains. We configure our Markov chain to produce the impulses with the damped oscillation effect, then, we determine the probability transition matrix and the distribution of each state of the Markov chain. Finally, we generate noise samples and we study the distribution of the impulsive noise characteristics. Our Markov chain model can replicate the correlation between the measured noise samples; also the distributions of the noise characteristics are similar in the simulations and the measurements.
Flying Triangulation - towards the 3D movie camera
Venue: arXiv cs.CV 2013
Year: 2013

Flying Triangulation sensors enable a free-hand and motion-robust 3D data acquisition of complex shaped objects. The measurement principle is based on a multi-line light-sectioning approach and uses sophisticated algorithms for real-time registration (S. Ettl et al., Appl. Opt. 51 (2012) 281-289). As "single-shot principle", light sectioning enables the option to get surface data from one single camera exposure. But there is a drawback: A pixel-dense measurement is not possible because of fundamental information-theoretical reasons. By "pixel-dense" we understand that each pixel displays individually measured distance information, neither interpolated from its neighbour pixels nor using lateral context information. Hence, for monomodal single-shot principles, the 3D data generated from one 2D raw image display a significantly lower space-bandwidth than the camera permits. This is the price one must pay for motion robustness. Currently, our sensors project about 10 lines (each with 1000 pixels), reaching an considerable lower data efficiency than theoretically possible for a single-shot sensor. Our aim is to push Flying Triangulation to its information-theoretical limits. Therefore, the line density as well as the measurement depth needs to be significantly increased. This causes serious indexing ambiguities. On the road to a single-shot 3D movie camera, we are working on solutions to overcome the problem of false line indexing by utilizing yet unexploited information. We will present several approaches and will discuss profound information-theoretical questions about the information efficiency of 3D sensors.
Average Stretch Factor: How Low Does It Go?
Venue: arXiv cs.CG 2013
Year: 2013

In a geometric graph, $G$, the \emph{stretch factor} between two vertices, $u$ and $w$, is the ratio between the Euclidean length of the shortest path from $u$ to $w$ in $G$ and the Euclidean distance between $u$ and $w$. The \emph{average stretch factor} of $G$ is the average stretch factor taken over all pairs of vertices in $G$. We show that, for any constant dimension, $d$, and any set, $V$, of $n$ points in $\mathbb{R}^d$, there exists a geometric graph with vertex set $V$, that has $O(n)$ edges, and that has average stretch factor $1+ o_n(1)$. More precisely, the average stretch factor of this graph is $1+O((\log n/n)^{1/(2d+1)})$. We complement this upper-bound with a lower bound: There exist $n$-point sets in $\mathbb{R}^2$ for which any graph with $O(n)$ edges has average stretch factor $1+Ω(1/\sqrt{n})$. Bounds of this type are not possible for the more commonly studied worst-case stretch factor. In particular, there exists point sets, $V$, such that any graph with worst-case stretch factor $1+o_n(1)$ has a superlinear number of edges.
Search and Result Presentation in Scientific Workflow Repositories
Venue: arXiv cs.DB 2013
Year: 2013

We study the problem of searching a repository of complex hierarchical workflows whose component modules, both composite and atomic, have been annotated with keywords. Since keyword search does not use the graph structure of a workflow, we develop a model of workflows using context-free bag grammars. We then give efficient polynomial-time algorithms that, given a workflow and a keyword query, determine whether some execution of the workflow matches the query. Based on these algorithms we develop a search and ranking solution that efficiently retrieves the top-k grammars from a repository. Finally, we propose a novel result presentation method for grammars matching a keyword query, based on representative parse-trees. The effectiveness of our approach is validated through an extensive experimental evaluation.
Machine learning on images using a string-distance
Venue: arXiv cs.LG 2013
Year: 2013

We present a new method for image feature-extraction which is based on representing an image by a finite-dimensional vector of distances that measure how different the image is from a set of image prototypes. We use the recently introduced Universal Image Distance (UID) \cite{RatsabyChesterIEEE2012} to compare the similarity between an image and a prototype image. The advantage in using the UID is the fact that no domain knowledge nor any image analysis need to be done. Each image is represented by a finite dimensional feature vector whose components are the UID values between the image and a finite set of image prototypes from each of the feature categories. The method is automatic since once the user selects the prototype images, the feature vectors are automatically calculated without the need to do any image analysis. The prototype images can be of different size, in particular, different than the image size. Based on a collection of such cases any supervised or unsupervised learning algorithm can be used to train and produce an image classifier or image cluster analysis. In this paper we present the image feature-extraction method and use it on several supervised and unsupervised learning experiments for satellite image data.
Decidability of minimization of fuzzy automata
Venue: arXiv cs.FL 2013
Year: 2013

State minimization is a fundamental problem in automata theory. The problem is also of great importance in the study of fuzzy automata. However, most work in the literature considered only state reduction of fuzzy automata, whereas the state minimization problem is almost untouched for fuzzy automata. Thus in this paper we focus on the latter problem. Formally, the decision version of the minimization problem of fuzzy automata is as follows: \begin{itemize} \item Given a fuzzy automaton $\mathcal{A}$ and a natural number $k$, that is, a pair $\langle \mathcal{A}, k\rangle$, is there a $k$-state fuzzy automaton equivalent to $\mathcal{A}$? \end{itemize} We prove for the first time that the above problem is decidable for fuzzy automata over totally ordered lattices. To this end, we first give the concept of systems of fuzzy polynomial equations and then present a procedure to solve these systems. Afterwards, we apply the solvability of a system of fuzzy polynomial equations to the minimization problem mentioned above, obtaining the decidability. Finally, we point out that the above problem is at least as hard as PSAPCE-complete.
Mobile Services and Network Proximity
Venue: arXiv cs.NI 2013
Year: 2013

This paper discusses several practical use cases for deploying network proximity in mobile services. Our research presents here mobile services oriented for either discovering new data for mobile subscribers or for delivering some customized information to them. All applications share the same approach and use the common platform, based on the Wi-Fi proximity. The typical deployment areas for our approach are context-aware services and ubiquitous computing applications. Our own examples include proximity marketing as the model use case.
Rapid mental computation system as a tool for algorithmic thinking of elementary school students development
Venue: arXiv cs.CY 2013
Year: 2013

In this paper, we describe the possibilities of using a rapid mental computation system in elementary education. The system consists of a number of readily memorized operations that allow one to perform arithmetic computations very quickly. These operations are actually simple algorithms which can develop or improve the algorithmic thinking of pupils. Using a rapid mental computation system allows forming the basis for the study of computer science in secondary school.
SHARE: A Web Service Based Framework for Distributed Querying and Reasoning on the Semantic Web
Venue: arXiv cs.DL 2013
Year: 2013

Here we describe the SHARE system, a web service based framework for distributed querying and reasoning on the semantic web. The main innovations of SHARE are: (1) the extension of a SPARQL query engine to perform on-demand data retrieval from web services, and (2) the extension of an OWL reasoner to test property restrictions by means of web service invocations. In addition to enabling queries across distributed datasets, the system allows for a target dataset that is significantly larger than is possible under current, centralized approaches. Although the architecture is equally applicable to all types of data, the SHARE system targets bioinformatics, due to the large number of interoperable web services that are already available in this area. SHARE is built entirely on semantic web standards, and is the successor of the BioMOBY project.
Robustness of Random Forest-based gene selection methods
Venue: arXiv cs.LG 2013
Year: 2013

Gene selection is an important part of microarray data analysis because it provides information that can lead to a better mechanistic understanding of an investigated phenomenon. At the same time, gene selection is very difficult because of the noisy nature of microarray data. As a consequence, gene selection is often performed with machine learning methods. The Random Forest method is particularly well suited for this purpose. In this work, four state-of-the-art Random Forest-based feature selection methods were compared in a gene selection context. The analysis focused on the stability of selection because, although it is necessary for determining the significance of results, it is often ignored in similar studies. The comparison of post-selection accuracy in the validation of Random Forest classifiers revealed that all investigated methods were equivalent in this context. However, the methods substantially differed with respect to the number of selected genes and the stability of selection. Of the analysed methods, the Boruta algorithm predicted the most genes as potentially important. The post-selection classifier error rate, which is a frequently used measure, was found to be a potentially deceptive measure of gene selection quality. When the number of consistently selected genes was considered, the Boruta algorithm was clearly the best. Although it was also the most computationally intensive method, the Boruta algorithm's computational demands could be reduced to levels comparable to those of other algorithms by replacing the Random Forest importance with a comparable measure from Random Ferns (a similar but simplified classifier). Despite their design assumptions, the minimal optimal selection methods, were found to select a high fraction of false positives.
Finite-horizon Online Transmission Rate and Power Adaptation on a Communication Link with Markovian Energy Harvesting
Venue: arXiv cs.IT 2013
Year: 2013

As energy harvesting communication systems emerge, there is a need for transmission schemes that dynamically adapt to the energy harvesting process. In this paper, after exhibiting a finite-horizon online throughput-maximizing scheduling problem formulation and the structure of its optimal solution within a dynamic programming formulation, a low complexity online scheduling policy is proposed. The policy exploits the existence of thresholds for choosing rate and power levels as a function of stored energy, harvest state and time until the end of the horizon. The policy, which is based on computing an expected threshold, performs close to optimal on a wide range of example energy harvest patterns. Moreover, it achieves higher throughput values for a given delay, than throughput-optimal online policies developed based on infinite-horizon formulations in recent literature. The solution is extended to include ergodic time-varying (fading) channels, and a corresponding low complexity policy is proposed and evaluated for this case as well.
Functional Package Management with Guix
Venue: arXiv cs.PL 2013
Year: 2013

We describe the design and implementation of GNU Guix, a purely functional package manager designed to support a complete GNU/Linux distribution. Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. It builds upon the low-level build and deployment layer of the Nix package manager. Guix uses Scheme as its programming interface. In particular, we devise an embedded domain-specific language (EDSL) to describe and compose packages. We demonstrate how it allows us to benefit from the host general-purpose programming language while not compromising on expressiveness. Second, we show the use of Scheme to write build programs, leading to "two-tier" programming system.