OpenRaiser/Intern-Atlas huggingface dataset:
Scheduling Advantages of Network Coded Storage in Point-to-Multipoint Networks
Venue: arXiv cs.IT 2014
Year: 2014

We consider scheduling strategies for point-to-multipoint (PMP) storage area networks (SANs) that use network coded storage (NCS). In particular, we present a simple SAN system model, two server scheduling algorithms for PMP networks, and analytical expressions for internal and external blocking probability. We point to select scheduling advantages in NCS systems under normal operating conditions, where content requests can be temporarily denied owing to finite system capacity from drive I/O access or storage redundancy limitations. NCS can lead to improvements in throughput and blocking probability due to increased immediate scheduling options, and complements other well documented NCS advantages such as regeneration, and can be used as a guide for future storage system design.
A graph-theoretical approach for the computation of connected iso-surfaces based on volumetric data
Venue: arXiv cs.CG 2014
Year: 2014

The existing combinatorial methods for iso-surface computation are efficient for pure visualization purposes, but it is known that the resulting iso-surfaces can have holes, and topological problems like missing or wrong connectivity can appear. To avoid such problems, we introduce a graph-theoretical method for the computation of iso-surfaces on cuboid meshes in $\mathbb{R}^3$. The method for the generation of iso-surfaces employs labeled cuboid graphs $G(V,E,\mathcal{F})$ such that $V$ is the set of vertices of a cuboid $C\subset\mathbb{R}^3$, $E$ is the set of edges of $C$ and $\mathcal{F}\,:\,V\rightarrow [0,1]$. The nodes of $G$ are weighted by the values of $\mathcal{F}$ which represents the volumetric information, e.g.\ from a Volume of Fluid method. Using a given iso-level $c\in (0,1)$, we first obtain all iso-points, i.e.\ points where the value $c$ is attained by the edge-interpolated $\mathcal{F}$-field. The iso-surface is then built from iso-elements which are composed of triangles and are such that their polygonal boundary has only iso-points as vertices. All vertices lie on the faces of a single mesh cell. We give a proof that the generated iso-surface is connected up to the boundary of the domain and it can be decomposed into different oriented components. Two different components may have discrete points or line segments in common. The graph-theoretical method for the computation of iso-surfaces developed in this paper enables to recover local information of the iso-surface that can be used e.g.\ to compute discrete mean curvature and to solve surface PDEs. Concerning the computational effort, the resulting algorithm is as efficient as existing combinatorial methods.
Partitioning Complex Networks via Size-constrained Clustering
Venue: arXiv cs.DC 2014
Year: 2014

The most commonly used method to tackle the graph partitioning problem in practice is the multilevel approach. During a coarsening phase, a multilevel graph partitioning algorithm reduces the graph size by iteratively contracting nodes and edges until the graph is small enough to be partitioned by some other algorithm. A partition of the input graph is then constructed by successively transferring the solution to the next finer graph and applying a local search algorithm to improve the current solution. In this paper, we describe a novel approach to partition graphs effectively especially if the networks have a highly irregular structure. More precisely, our algorithm provides graph coarsening by iteratively contracting size-constrained clusterings that are computed using a label propagation algorithm. The same algorithm that provides the size-constrained clusterings can also be used during uncoarsening as a fast and simple local search algorithm. Depending on the algorithm's configuration, we are able to compute partitions of very high quality outperforming all competitors, or partitions that are comparable to the best competitor in terms of quality, hMetis, while being nearly an order of magnitude faster on average. The fastest configuration partitions the largest graph available to us with 3.3 billion edges using a single machine in about ten minutes while cutting less than half of the edges than the fastest competitor, kMetis.
Two Steps to Obfuscation
Venue: arXiv cs.SI 2014
Year: 2014

This note addresses the historical antecedents of the 1998 PageRank measure of centrality. An identity relation links it to 1990-1991 models of Friedkin and Johnsen.
Distributed synthesis for acyclic architectures
Venue: arXiv cs.LO 2014
Year: 2014

The distributed synthesis problem is about constructing cor- rect distributed systems, i.e., systems that satisfy a given specification. We consider a slightly more general problem of distributed control, where the goal is to restrict the behavior of a given distributed system in order to satisfy the specification. Our systems are finite state machines that communicate via rendez-vous (Zielonka automata). We show decidability of the synthesis problem for all omega-regular local specifications, under the restriction that the communication graph of the system is acyclic. This result extends a previous decidability result for a restricted form of local reachability specifications.
Multiple Window Moving Horizon Estimation
Venue: arXiv cs.SY 2014
Year: 2014

Long horizon lengths in Moving Horizon Estimation are desirable to reach the performance limits of the full information estimator. However, the conventional MHE technique suffers from a number of deficiencies in this respect. First, the problem complexity scales at least linearly with the horizon length selected, which restrains from selecting long horizons if computational limitations are present. Second, there is no monitoring of constraint activity/inactivity which results in conducting redundant constrained minimizations even when no constraints are active. In this study we develop a Multiple-Window Moving Horizon Estimation strategy (MW-MHE) that exploits constraint inactivity to reduce the problem size in long horizon estimation problems. The arrival cost is approximated using the unconstrained full information estimator arrival cost to guarantee stability of the technique. A new horizon length selection criteria is developed based on maximum sensitivity between remote states in time. The development will be in terms of general causal descriptor systems, which includes the standard state space representation as a special case. The potential of the new estimation algorithm will be demonstrated with an example showing a significant reduction in both computation time and numerical errors compared to conventional MHE.
Machine Learning of Phonologically Conditioned Noun Declensions For Tamil Morphological Generators
Venue: arXiv cs.CL 2014
Year: 2014

This paper presents machine learning solutions to a practical problem of Natural Language Generation (NLG), particularly the word formation in agglutinative languages like Tamil, in a supervised manner. The morphological generator is an important component of Natural Language Processing in Artificial Intelligence. It generates word forms given a root and affixes. The morphophonemic changes like addition, deletion, alternation etc., occur when two or more morphemes or words joined together. The Sandhi rules should be explicitly specified in the rule based morphological analyzers and generators. In machine learning framework, these rules can be learned automatically by the system from the training samples and subsequently be applied for new inputs. In this paper we proposed the machine learning models which learn the morphophonemic rules for noun declensions from the given training data. These models are trained to learn sandhi rules using various learning algorithms and the performance of those algorithms are presented. From this we conclude that machine learning of morphological processing such as word form generation can be successfully learned in a supervised manner, without explicit description of rules. The performance of Decision trees and Bayesian machine learning algorithms on noun declensions are discussed.
Short sequences of improvement moves lead to approximate equilibria in constraint satisfaction games
Venue: arXiv cs.GT 2014
Year: 2014

We present an algorithm that computes approximate pure Nash equilibria in a broad class of constraint satisfaction games that generalize the well-known cut and party affiliation games. Our results improve previous ones by Bhalgat et al.~(EC 10) in terms of the obtained approximation guarantee. More importantly, our algorithm identifies a polynomially-long sequence of improvement moves from any initial state to an approximate equilibrium in these games. The existence of such short sequences is an interesting structural property which, to the best of our knowledge, was not known before. Our techniques adapt and extend our previous work for congestion games (FOCS 11) but the current analysis is considerably simpler.
News Cohesiveness: an Indicator of Systemic Risk in Financial Markets
Venue: arXiv cs.SI 2014
Year: 2014

Motivated by recent financial crises significant research efforts have been put into studying contagion effects and herding behaviour in financial markets. Much less has been said about influence of financial news on financial markets. We propose a novel measure of collective behaviour in financial news on the Web, News Cohesiveness Index (NCI), and show that it can be used as a systemic risk indicator. We evaluate the NCI on financial documents from large Web news sources on a daily basis from October 2011 to July 2013 and analyse the interplay between financial markets and financially related news. We hypothesized that strong cohesion in financial news reflects movements in the financial markets. Cohesiveness is more general and robust measure of systemic risk expressed in news, than measures based on simple occurrences of specific terms. Our results indicate that cohesiveness in the financial news is highly correlated with and driven by volatility on the financial markets.
Spatially-Coupled LDPC Codes for Decode-and-Forward Relaying of Two Correlated Sources over the BEC
Venue: arXiv cs.IT 2014
Year: 2014

We present a decode-and-forward transmission scheme based on spatially-coupled low-density parity-check (SC-LDPC) codes for a network consisting of two (possibly correlated) sources, one relay, and one destination. The links between the nodes are modeled as binary erasure channels. Joint source-channel coding with joint channel decoding is used to exploit the correlation. The relay performs network coding. We derive analytical bounds on the achievable rates for the binary erasure time-division multiple-access relay channel with correlated sources. We then design bilayer SC-LDPC codes and analyze their asymptotic performance for this scenario. We prove analytically that the proposed coding scheme achieves the theoretical limit for symmetric channel conditions and uncorrelated sources. Using density evolution, we furthermore demonstrate that our scheme approaches the theoretical limit also for non-symmetric channel conditions and when the sources are correlated, and we observe the threshold saturation effect that is typical for spatially-coupled systems. Finally, we give simulation results for large block lengths, which validate the DE analysis.
Temperature Control using Fuzzy Logic
Venue: arXiv cs.SY 2014
Year: 2014

The aim of the temperature control is to heat the system up todelimitated temperature, afterwardhold it at that temperature in insured manner. Fuzzy Logic Controller (FLC) is best way in which this type of precision control can be accomplished by controller. During past twenty yearssignificant amount of research using fuzzy logichas done in this field of control of non-linear dynamical system. Here we have developed temperature control system using fuzzy logic. Control theory techniques are the root from which convention controllers are deducted. The desired response of the output can be guaranteed by the feedback controller.
Note on fair coin toss via Bitcoin
Venue: arXiv cs.CR 2014
Year: 2014

In this short note we show that the Bitcoin network can allow remote parties to gamble with their bitcoins by tossing a fair or biased coin, with no need for a trusted party, and without the possibility of extortion by dishonest parties who try to abort. The superfluousness of having a trusted party implies that there is no house edge, as is the case with centralized services that are supposed to generate a profit.
word2vec Explained: deriving Mikolov et al.'s negative-sampling word-embedding method
Venue: arXiv cs.CL 2014
Year: 2014

The word2vec software of Tomas Mikolov and colleagues (https://code.google.com/p/word2vec/ ) has gained a lot of traction lately, and provides state-of-the-art word embeddings. The learning models behind the software are described in two research papers. We found the description of the models in these papers to be somewhat cryptic and hard to follow. While the motivations and presentation may be obvious to the neural-networks language-modeling crowd, we had to struggle quite a bit to figure out the rationale behind the equations. This note is an attempt to explain equation (4) (negative sampling) in "Distributed Representations of Words and Phrases and their Compositionality" by Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado and Jeffrey Dean.
QTC3D: Extending the Qualitative Trajectory Calculus to Three Dimensions
Venue: arXiv cs.OH 2014
Year: 2014

Spatial interactions between agents (humans, animals, or machines) carry information of high value to human or electronic observers. However, not all the information contained in a pair of continuous trajectories is important and thus the need for qualitative descriptions of interaction trajectories arises. The Qualitative Trajectory Calculus (QTC) (Van de Weghe, 2004) is a promising development towards this goal. Numerous variants of QTC have been proposed in the past and QTC has been applied towards analyzing various interaction domains. However, an inherent limitation of those QTC variations that deal with lateral movements is that they are limited to two-dimensional motion; therefore, complex three-dimensional interactions, such as those occurring between flying planes or birds, cannot be captured. Towards that purpose, in this paper QTC3Dis presented: a novel qualitative trajectory calculus that can deal with full three-dimensional interactions. QTC3D is based on transformations of the Frenet-Serret frames accompanying the trajectories of the moving objects. Apart from the theoretical exposition, including definition and properties, as well as computational aspects, we also present an application of QTC3D towards modeling bird flight. Thus, the power of QTC is now extended to the full dimensionality of physical space, enabling succinct yet rich representations of spatial interactions between agents.
Towards the reproducibility in soil erosion modeling: a new Pan-European soil erosion map
Venue: arXiv cs.SY 2014
Year: 2014

Soil erosion by water is a widespread phenomenon throughout Europe and has the potentiality, with his on-site and off-site effects, to affect water quality, food security and floods. Despite the implementation of numerous and different models for estimating soil erosion by water in Europe, there is still a lack of harmonization of assessment methodologies. Often, different approaches result in soil erosion rates significantly different. Even when the same model is applied to the same region the results may differ. This can be due to the way the model is implemented (i.e. with the selection of different algorithms when available) and/or to the use of datasets having different resolution or accuracy. Scientific computation is emerging as one of the central topic of the scientific method, for overcoming these problems there is thus the necessity to develop reproducible computational method where codes and data are available. The present study illustrates this approach. Using only public available datasets, we applied the Revised Universal Soil loss Equation (RUSLE) to locate the most sensitive areas to soil erosion by water in Europe. A significant effort was made for selecting the better simplified equations to be used when a strict application of the RUSLE model is not possible. In particular for the computation of the Rainfall Erosivity factor (R) the reproducible research paradigm was applied. The calculation of the R factor was implemented using public datasets and the GNU R language. An easily reproducible validation procedure based on measured precipitation time series was applied using MATLAB language. Designing the computational modelling architecture with the aim to ease as much as possible the future reuse of the model in analysing climate change scenarios is also a challenging goal of the research.
Bounding Multiple Unicasts through Index Coding and Locally Repairable Codes
Venue: arXiv cs.IT 2014
Year: 2014

We establish a duality result between linear index coding and Locally Repairable Codes (LRCs). Specifically, we show that a natural extension of LRCs we call Generalized Locally Repairable Codes (GLCRs) are exactly dual to linear index codes. In a GLRC, every node is decodable from a specific set of other nodes and these sets induce a recoverability directed graph. We show that the dual linear subspace of a GLRC is a solution to an index coding instance where the side information graph is this GLRC recoverability graph. We show that the GLRC rate is equivalent to the complementary index coding rate, i.e. the number of transmissions saved by coding. Our second result uses this duality to establish a new upper bound for the multiple unicast network coding problem. In multiple unicast network coding, we are given a directed acyclic graph and r sources that want to send independent messages to r corresponding destinations. Our new upper bound is efficiently computable and relies on a strong approximation result for complementary index coding. We believe that our bound could lead to a logarithmic approximation factor for multiple unicast network coding if a plausible connection we state is verified.
A Framework for the Implementation of Industrial Automation Systems Based on PLCs
Venue: arXiv cs.SE 2014
Year: 2014

Industrial automation systems (IASs) are traditionally developed using a sequential approach where the automation software, which is commonly based on the IEC 61131 languages, is developed when the design and in many cases the implementation of mechanical parts have been completed. However, it is claimed that this approach does not lead to the optimal system design and that the IEC 61131 does not meet new challenges in this domain. In this paper, a system engineering process based on the new version of IEC 61131, which supports Object Orientation, is presented. SysML and UML are utilized to introduce a higher layer of abstraction in the design space of IAS and Internet of Things (IoT) is considered as an enabling technology for the integration of Cyber and Cyber-physical components of the system, bringing into the industrial automation domain the benefits of these technologies.
Sparse Coding Approach for Multi-Frame Image Super Resolution
Venue: arXiv cs.CV 2014
Year: 2014

An image super-resolution method from multiple observation of low-resolution images is proposed. The method is based on sub-pixel accuracy block matching for estimating relative displacements of observed images, and sparse signal representation for estimating the corresponding high-resolution image. Relative displacements of small patches of observed low-resolution images are accurately estimated by a computationally efficient block matching method. Since the estimated displacements are also regarded as a warping component of image degradation process, the matching results are directly utilized to generate low-resolution dictionary for sparse image representation. The matching scores of the block matching are used to select a subset of low-resolution patches for reconstructing a high-resolution patch, that is, an adaptive selection of informative low-resolution images is realized. When there is only one low-resolution image, the proposed method works as a single-frame super-resolution method. The proposed method is shown to perform comparable or superior to conventional single- and multi-frame super-resolution methods through experiments using various real-world datasets.
Parametrization of completeness in symbolic abstraction of bounded input linear systems
Venue: arXiv cs.SY 2014
Year: 2014

A good state-time quantized symbolic abstraction of an already input quantized control system would satisfy three conditions: proximity, soundness and completeness. Extant approaches for symbolic abstraction of unstable systems limit to satisfying proximity and soundness but not completeness. Instability of systems is an impediment to constructing fully complete state-time quantized symbolic models for bounded and quantized input unstable systems, even using supervisory feedback. Therefore, in this paper we come up with a way of parametrization of completeness of the symbolic model through the quintessential notion of Trimmed-Input Approximate Bisimulation which is introduced in the paper. The amount of completeness is specified by a parameter called trimming of the set of input trajectories. We subsequently discuss a procedure of constructing state-time quantized symbolic models which are near-complete in addition to being sound and proximate with respect to the time quantized models.
The Saddlepoint Approximation: Unified Random Coding Asymptotics for Fixed and Varying Rates
Venue: arXiv cs.IT 2014
Year: 2014

This paper presents a saddlepoint approximation of the random-coding union bound of Polyanskiy et al. for i.i.d. random coding over discrete memoryless channels. The approximation is single-letter, and can thus be computed efficiently. Moreover, it is shown to be asymptotically tight for both fixed and varying rates, unifying existing achievability results in the regimes of error exponents, second-order coding rates, and moderate deviations. For fixed rates, novel exact-asymptotics expressions are specified to within a multiplicative 1+o(1) term. A numerical example is provided for which the approximation is remarkably accurate even at short block lengths.
Trends in Computer Network Modeling Towards the Future Internet
Venue: arXiv cs.NI 2014
Year: 2014

This article provides a taxonomy of current and past network modeling efforts. In all these efforts over the last few years we see a trend towards not only describing the network, but connected devices as well. This is especially current given the many Future Internet projects, which are combining different models, and resources in order to provide complete virtual infrastructures to users. An important mechanism for managing complexity is the creation of an abstract model, a step which has been undertaken in computer networks too. The fact that more and more devices are network capable, coupled with increasing popularity of the Internet, has made computer networks an important focus area for modeling. The large number of connected devices creates an increasing complexity which must be harnessed to keep the networks functioning. Over the years many different models for computer networks have been proposed, and used for different purposes. While for some time the community has moved away from the need of full topology exchange, this requirement resurfaced for optical networks. Subsequently, research on topology descriptions has seen a rise in the last few years. Many different models have been created and published, yet there is no publication that shows an overview of the different approaches.