OpenRaiser/Intern-Atlas huggingface dataset:
Scalable Analytics over Distributed Time-series Graphs using GoFFish
Venue: arXiv cs.DC 2014
Year: 2014

Graphs are a key form of Big Data, and performing scalable analytics over them is invaluable to many domains. As our ability to collect data grows, there is an emerging class of inter-connected data which accumulates or varies over time, and on which novel analytics - both over the network structure and across the time-variant attribute values - is necessary. We introduce the notion of time-series graph analytics and propose Gopher, a scalable programming abstraction to develop algorithms and analytics on such datasets. Our abstraction leverages a sub-graph centric programming model and extends it to the temporal dimension using an iterative BSP (Bulk Synchronous Parallel) approach. Gopher is co-designed with GoFS, a distributed storage specialized for time-series graphs, as part of the GoFFish distributed analytics platform. We examine storage optimizations for GoFS, design patterns in Gopher to leverage the distributed data layout, and evaluate the GoFFish platform using time-series graph data and applications on a commodity cluster.
Floe: A Continuous Dataflow Framework for Dynamic Cloud Applications
Venue: arXiv cs.DC 2014
Year: 2014

Applications in cyber-physical systems are increasingly coupled with online instruments to perform long running, continuous data processing. Such "always on" dataflow applications are dynamic, where they need to change the applications logic and performance at runtime, in response to external operational needs. Floe is a continuous dataflow framework that is designed to be adaptive for dynamic applications on Cloud infrastructure. It offers advanced dataflow patterns like BSP and MapReduce for flexible and holistic composition of streams and files, and supports dynamic recomposition at runtime with minimal impact on the execution. Adaptive resource allocation strategies allow our framework to effectively use elastic Cloud resources to meet varying data rates. We illustrate the design patterns of Floe by running an integration pipeline and a tweet clustering application from the Smart Power Grids domain on a private Eucalyptus Cloud. The responsiveness of our resource adaptation is validated through simulations for periodic, bursty and random workloads.
Designing Sound Collaboratively - Perceptually Motivated Audio Synthesis
Venue: arXiv cs.MM 2014
Year: 2014

In this contribution, we will discuss a prototype that allows a group of users to design sound collaboratively in real time using a multi-touch tabletop. We make use of a machine learning method to generate a mapping from perceptual audio features to synthesis parameters. This mapping is then used for visualization and interaction. Finally, we discuss the results of a comparative evaluation study.
Initialization Algorithms For Convolutional Network Coding
Venue: arXiv cs.IT 2014
Year: 2014

We present algorithms for initializing a convolutional network coding scheme in networks that may contain cycles. An initialization process is needed if the network is unknown or if local encoding kernels are chosen randomly. During the initialization process every source node transmits basis vectors and every sink node measures the impulse response of the network. The impulse response is then used to find a relationship between the transmitted and the received symbols, which is needed for a decoding algorithm and to find the set of all achievable rates. Unlike acyclic networks, for which it is enough to transmit basis vectors one after another, the initialization of cyclic networks is more involved, as pilot symbols interfere with each other and the impulse response is of infinite duration.
Incorporating Near-Infrared Information into Semantic Image Segmentation
Venue: arXiv cs.CV 2014
Year: 2014

Recent progress in computational photography has shown that we can acquire near-infrared (NIR) information in addition to the normal visible (RGB) band, with only slight modifications to standard digital cameras. Due to the proximity of the NIR band to visible radiation, NIR images share many properties with visible images. However, as a result of the material dependent reflection in the NIR part of the spectrum, such images reveal different characteristics of the scene. We investigate how to effectively exploit these differences to improve performance on the semantic image segmentation task. Based on a state-of-the-art segmentation framework and a novel manually segmented image database (both indoor and outdoor scenes) that contain 4-channel images (RGB+NIR), we study how to best incorporate the specific characteristics of the NIR response. We show that adding NIR leads to improved performance for classes that correspond to a specific type of material in both outdoor and indoor scenes. We also discuss the results with respect to the physical properties of the NIR response.
Fault Tolerant Approximate BFS Structures
Venue: arXiv cs.DS 2014
Year: 2014

This paper addresses the problem of designing a {\em fault-tolerant} $(α, β)$ approximate BFS structure (or {\em FT-ABFS structure} for short), namely, a subgraph $H$ of the network $G$ such that subsequent to the failure of some subset $F$ of edges or vertices, the surviving part of $H$ still contains an \emph{approximate} BFS spanning tree for (the surviving part of) $G$, satisfying $dist(s,v,H\setminus F) \leq α\cdot dist(s,v,G\setminus F)+β$ for every $v \in V$. We first consider {\em multiplicative} $(α,0)$ FT-ABFS structures resilient to a failure of a single edge and present an algorithm that given an $n$-vertex unweighted undirected graph $G$ and a source $s$ constructs a $(3,0)$ FT-ABFS structure rooted at $s$ with at most $4n$ edges (improving by an $O(\log n)$ factor on the near-tight result of \cite{BS10} for the special case of edge failures). Assuming at most $f$ edge failures, for constant integer $f>1$, we prove that there exists a (poly-time constructible) $(3(f+1), (f+1) \log n)$ FT-ABFS structure with $O(f n)$ edges. We then consider {\em additive} $(1,β)$ FT-ABFS structures. In contrast to the linear size of $(α,0)$ FT-ABFS structures, we show that for every $β\in [1, O(\log n)]$ there exists an $n$-vertex graph $G$ with a source $s$ for which any $(1,β)$ FT-ABFS structure rooted at $s$ has $Ω(n^{1+ε(β)})$ edges, for some function $ε(β) \in (0,1)$. In particular, $(1,3)$ FT-ABFS structures admit a lower bound of $Ω(n^{5/4})$ edges. Our lower bounds are complemented by an upper bound, showing that there exists a poly-time algorithm that for every $n$-vertex unweighted undirected graph $G$ and source $s$ constructs a $(1,4)$ FT-ABFS structure rooted at $s$ with at most $O(n^{4/3})$ edges.
Distributed Storage Systems based on Equidistant Subspace Codes
Venue: arXiv cs.IT 2014
Year: 2014

Distributed storage systems based on equidistant constant dimension codes are presented. These equidistant codes are based on the Plücker embedding, which is essential in the repair and the reconstruction algorithms. These systems posses several useful properties such as high failure resilience, minimum bandwidth, low storage, simple algebraic repair and reconstruction algorithms, good locality, and compatibility with small fields.
Generalized Concatenated Types of Codes for Erasure Correction
Venue: arXiv cs.IT 2014
Year: 2014

Generalized Concatenated (GC), also known as Integrated Interleaved (II) Codes, are studied from an erasure correction point of view making them useful for Redundant Arrays of Independent Disks (RAID) types of architectures combining global and local properties. The fundamental erasure-correcting properties of the codes are proven and efficient encoding and decoding algorithms are provided. Although less powerful than the recently developed PMDS codes, this implementation has the advantage of allowing generalization to any range of parameters while the size of the field is much smaller than the one required for PMDS codes.
Midiendo la calidad de la informacion gestionada: algunas reflexiones conceptuales-metodologicas
Venue: arXiv cs.OH 2014
Year: 2014

The study, based on a documental classic analysis, presents conceptual and methodological guidelines concerning the design of methodologies that help to measure the quality of information that is managed in organizations. It is described the process of information management and the importance of implementing quality principles in it. There are exposed the four dimensions of information quality as part of an indicators integration which characterize the informational contents. There are defined each of the phases in the methodological design to evaluate the information. There also are indicated the implications of this activity for information professionals.
Image patch analysis and clustering of sunspots: a dimensionality reduction approach
Venue: arXiv cs.CV 2014
Year: 2014

Sunspots, as seen in white light or continuum images, are associated with regions of high magnetic activity on the Sun, visible on magnetogram images. Their complexity is correlated with explosive solar activity and so classifying these active regions is useful for predicting future solar activity. Current classification of sunspot groups is visually based and suffers from bias. Supervised learning methods can reduce human bias but fail to optimally capitalize on the information present in sunspot images. This paper uses two image modalities (continuum and magnetogram) to characterize the spatial and modal interactions of sunspot and magnetic active region images and presents a new approach to cluster the images. Specifically, in the framework of image patch analysis, we estimate the number of intrinsic parameters required to describe the spatial and modal dependencies, the correlation between the two modalities and the corresponding spatial patterns, and examine the phenomena at different scales within the images. To do this, we use linear and nonlinear intrinsic dimension estimators, canonical correlation analysis, and multiresolution analysis of intrinsic dimension.
The Links Have It: Infobox Generation by Summarization over Linked Entities
Venue: arXiv cs.IR 2014
Year: 2014

Online encyclopedia such as Wikipedia has become one of the best sources of knowledge. Much effort has been devoted to expanding and enriching the structured data by automatic information extraction from unstructured text in Wikipedia. Although remarkable progresses have been made, their effectiveness and efficiency is still limited as they try to tackle an extremely difficult natural language understanding problems and heavily relies on supervised learning approaches which require large amount effort to label the training data. In this paper, instead of performing information extraction over unstructured natural language text directly, we focus on a rich set of semi-structured data in Wikipedia articles: linked entities. The idea of this paper is the following: If we can summarize the relationship between the entity and its linked entities, we immediately harvest some of the most important information about the entity. To this end, we propose a novel rank aggregation approach to remove noise, an effective clustering and labeling algorithm to extract knowledge.
Wireless Networks with RF Energy Harvesting: A Contemporary Survey
Venue: arXiv cs.NI 2014
Year: 2014

Radio frequency (RF) energy transfer and harvesting techniques have recently become alternative methods to power the next generation wireless networks. As this emerging technology enables proactive energy replenishment of wireless devices, it is advantageous in supporting applications with quality of service (QoS) requirement. In this paper, we present an extensive literature review on the research progresses in wireless networks with RF energy harvesting capability, referred to as RF energy harvesting networks (RF-EHNs). First, we present an overview of the RF-EHNs including system architecture, RF energy harvesting techniques and existing applications. Then, we present the background in circuit design as well as the state-of-the-art circuitry implementations, and review the communication protocols specially designed for RF-EHNs. We also explore various key design issues in the development of RF-EHNs according to the network types, i.e., single-hop network, multi-antenna network, relay network and cognitive radio network. Finally, we envision some open research directions.
Variance Competitiveness for Monotone Estimation: Tightening the Bounds
Venue: arXiv cs.DB 2014
Year: 2014

Random samples are extensively used to summarize massive data sets and facilitate scalable analytics. Coordinated sampling, where samples of different data sets "share" the randomization, is a powerful method which facilitates more accurate estimation of many aggregates and similarity measures. We recently formulated a model of {\it Monotone Estimation Problems} (MEP), which can be applied to coordinated sampling, projected on a single item. MEP estimators can then be used to estimate sum aggregates, such as distances, over coordinated samples. For MEP, we are interested in estimators that are unbiased and nonnegative. We proposed {\it variance competitiveness} as a quality measure of estimators: For each data vector, we consider the minimum variance attainable on it by an unbiased and nonnegative estimator. We then define the competitiveness of an estimator as the maximum ratio, over data, of the expectation of the square to the minimum possible. We also presented a general construction of the L$^*$ estimator, which is defined for any MEP for which a nonnegative unbiased estimator exists, and is at most 4-competitive. Our aim here is to obtain tighter bounds on the {\em universal ratio}, which we define to be the smallest competitive ratio that can be obtained for any MEP. We obtain an upper bound of 3.375, improving over the bound of $4$ of the L$^*$ estimator. We also establish a lower bound of 1.44. The lower bound is obtained by constructing the {\it optimally competitive} estimator for particular MEPs. The construction is of independent interest, as it facilitates estimation with instance-optimal competitiveness.
Comments on 'Maximally permissive supervisor synthesis based on a new constraint transformation method'
Venue: arXiv cs.SY 2014
Year: 2014

Luo et al. proposed a new method to design the maximally permissive and efficient supervisor for enforcing linear constraints on an ordinary Petri net with uncontrollable transitions. In order to develop this method, Theorem 3 is given. It is claimed that 'a linear constraint can be equivalently transformed at an uncontrollable transition into a disjunction of weakly admissible ones.' However, this result is erroneous. In this correspondence paper, a counterexample contradicting it is presented.
A Method for Characterizing Communities in Dynamic Attributed Complex Networks
Venue: arXiv cs.SI 2014
Year: 2014

Many methods have been proposed to detect communities, not only in plain, but also in attributed, directed or even dynamic complex networks. In its simplest form, a community structure takes the form of a partition of the node set. From the modeling point of view, to be of some utility, this partition must then be characterized relatively to the properties of the studied system. However, if most of the existing works focus on defining methods for the detection of communities, only very few try to tackle this interpretation problem. Moreover, the existing approaches are limited either in the type of data they handle, or by the nature of the results they output. In this work, we propose a method to efficiently support such a characterization task. We first define a sequence-based representation of networks, combining temporal information, topological measures, and nodal attributes. We then describe how to identify the most emerging sequential patterns of this dataset, and use them to characterize the communities. We also show how to detect unusual behavior in a community, and highlight outliers. Finally, as an illustration, we apply our method to a network of scientific collaborations.
Identifying the Community Roles of Social Capitalists in the Twitter Network
Venue: arXiv cs.SI 2014
Year: 2014

In the context of Twitter, social capitalists are specific users trying to increase their number of followers and interactions by any means. These users are not healthy for the Twitter network since they flaw notions of influence and visibility. Indeed, it has recently been observed that they are real and active users that can help malicious users such as spammers gaining influence. Studying their behavior and understanding their position in Twitter is thus of important interest. A recent work provided an efficient way to detect social capitalists using two simple topological measures. Based on this detection method, we study how social capitalists are distributed over Twitter's friend-to-follower network. We are especially interested in analyzing how they are organized, and how their links spread across the network. Answering these questions allows to know whether the social capitalism methods increase the actual visibility on the service. To that aim, we study the position of social capitalists on Twitter w.r.t. the community structure of the network. We base our work on the concept of community role of a node, which describes its position in a network depending on its connectivity at the community level. The topological measures originally defined to characterize these roles consider only some aspects of community-related connectivity and rely on a set of empirically fixed thresholds. We first show the limitations of such measures and then extend and generalize them by considering new aspects of the community-related connectivity. Moreover, we use an unsupervised approach to distinguish the roles, in order to provide more flexibility relatively to the studied system. We then apply our method to the case of social capitalists and show that they are highly visible on Twitter, due to the specific roles they occupy.
Information Spectrum Approach to Strong Converse Theorems for Degraded Wiretap Channels
Venue: arXiv cs.IT 2014
Year: 2014

We consider block codes for degraded wiretap channels in which the legitimate receiver decodes the message with an asymptotic error probability no larger than $\varepsilon$ but the leakage to the eavesdropper vanishes. For discrete memoryless and Gaussian wiretap channels, we show that the maximum rate of transmission does not depend on $\varepsilon\in [0,1)$, i.e., such channels possess the partial strong converse property. Furthermore, we derive sufficient conditions for the partial strong converse property to hold for memoryless but non-stationary symmetric and degraded wiretap channels. Our proof techniques leverage the information spectrum method, which allows us to establish a necessary and sufficient condition for the partial strong converse to hold for general wiretap channels without any information stability assumptions.
Evaluation of Codes with Inherent Double Replication for Hadoop
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we evaluate the efficacy, in a Hadoop setting, of two coding schemes, both possessing an inherent double replication of data. The two coding schemes belong to the class of regenerating and locally regenerating codes respectively, and these two classes are representative of recent advances made in designing codes for the efficient storage of data in a distributed setting. In comparison with triple replication, double replication permits a significant reduction in storage overhead, while delivering good MapReduce performance under moderate work loads. The two coding solutions under evaluation here, add only moderately to the storage overhead of double replication, while simultaneously offering reliability levels similar to that of triple replication. One might expect from the property of inherent data duplication that the performance of these codes in executing a MapReduce job would be comparable to that of double replication. However, a second feature of this class of code comes into play here, namely that under both coding schemes analyzed here, multiple blocks from the same coded stripe are required to be stored on the same node. This concentration of data belonging to a single stripe negatively impacts MapReduce execution times. However, much of this effect can be undone by simply adding a larger number of processors per node. Further improvements are possible if one tailors the Map task scheduler to the codes under consideration. We present both experimental and simulation results that validate these observations.
Online learning in MDPs with side information
Venue: arXiv cs.LG 2014
Year: 2014

We study online learning of finite Markov decision process (MDP) problems when a side information vector is available. The problem is motivated by applications such as clinical trials, recommendation systems, etc. Such applications have an episodic structure, where each episode corresponds to a patient/customer. Our objective is to compete with the optimal dynamic policy that can take side information into account. We propose a computationally efficient algorithm and show that its regret is at most $O(\sqrt{T})$, where $T$ is the number of rounds. To best of our knowledge, this is the first regret bound for this setting.
Designing a minimalist socially aware robotic agent for the home
Venue: arXiv cs.RO 2014
Year: 2014

We present a minimalist social robot that relies on long timeseries of low resolution data such as mechanical vibration, temperature, lighting, sounds and collisions. Our goal is to develop an experimental system for growing socially situated robotic agents whose behavioral repertoire is subsumed by the social order of the space. To get there we are designing robots that use their simple sensors and motion feedback routines to recognize different classes of human activity and then associate to each class a range of appropriate behaviors. We use the Katie Family of robots, built on the iRobot Create platform, an Arduino Uno, and a Raspberry Pi. We describe its sensor abilities and exploratory tests that allow us to develop hypotheses about what objects (sensor data) correspond to something known and observable by a human subject. We use machine learning methods to classify three social scenarios from over a hundred experiments, demonstrating that it is possible to detect social situations with high accuracy, using the low-resolution sensors from our minimalist robot.
A Family of Simulation Criteria to Guide DEVS Models Validation Rigorously, Systematically and Semi-Automatically
Venue: arXiv cs.SE 2014
Year: 2014

The most common method to validate a DEVS model against the requirements is to simulate it several times under different conditions, with some simulation tool. The behavior of the model is compared with what the system is supposed to do. The number of different scenarios to simulate is usually infinite, therefore, selecting them becomes a crucial task. This selection, actually, is made following the experience or intuition of an engineer. Here we present a family of criteria to conduct DEVS model simulations in a disciplined way and covering the most significant simulations to increase the confidence on the model. This is achieved by analyzing the mathematical representation of the DEVS model and, thus, part of the validation process can be automatized.
Towards a Pattern-based Automatic Generation of Logical Specifications for Software Models
Venue: arXiv cs.SE 2014
Year: 2014

The work relates to the automatic generation of logical specifications, considered as sets of temporal logic formulas, extracted directly from developed software models. The extraction process is based on the assumption that the whole developed model is structured using only predefined workflow patterns. A method of automatic transformation of workflow patterns to logical specifications is proposed. Applying the presented concepts enables bridging the gap between the benefits of deductive reasoning for the correctness verification process and the difficulties in obtaining complete logical specifications for this process.