OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Systematic Distributed Storage Codes with Fast Encoding
Venue: arXiv cs.IT 2015
Year: 2015

Erasure codes are being increasingly used in distributed-storage systems in place of data-replication, since they provide the same level of reliability with much lower storage overhead. We consider the problem of constructing explicit erasure codes for distributed storage with the following desirable properties motivated by practice: (i) Maximum-Distance-Separable (MDS): to provide maximal reliability at minimum storage overhead, (ii) Optimal repair-bandwidth: to minimize the amount of data needed to be transferred to repair a failed node from remaining ones, (iii) Flexibility in repair: to allow maximal flexibility in selecting subset of nodes to use for repair, which includes not requiring that all surviving nodes be used for repair, (iv) Systematic Form: to ensure that the original data exists in uncoded form, and (v) Fast encoding: to minimize the cost of generating encoded data (enabled by a sparse generator matrix). This paper presents the first explicit code construction which theoretically guarantees all the five desired properties simultaneously. Our construction builds on a powerful class of codes called Product-Matrix (PM) codes. PM codes satisfy properties (i)-(iii), and either (iv) or (v), but not both simultaneously. Indeed, native PM codes have inherent structure that leads to sparsity, but this structure is destroyed when the codes are made systematic. We first present an analytical framework for understanding the interaction between the design of PM codes and the systematic property. Using this framework, we provide an explicit code construction that simultaneously achieves all the above desired properties. We also present general ways of transforming existing storage and repair optimal codes to enable fast encoding through sparsity. In practice, such sparse codes result in encoding speedup by a factor of about 4 for typical parameters.
Optimal Time-dependent Sequenced Route Queries in Road Networks
Venue: arXiv cs.DB 2015
Year: 2015

In this paper we present an algorithm for optimal processing of time-dependent sequenced route queries in road networks, i.e., given a road network where the travel time over an edge is time-dependent and a given ordered list of categories of interest, we find the fastest route between an origin and destination that passes through a sequence of points of interest belonging to each of the specified categories of interest. For instance, considering a city road network at a given departure time, one can find the fastest route between one's work and his/her home, passing through a bank, a supermarket and a restaurant, in this order. The main contribution of our work is the consideration of the time dependency of the network, a realistic characteristic of urban road networks, which has not been considered previously when addressing the optimal sequenced route query. Our approach uses the A* search paradigm that is equipped with an admissible heuristic function, thus guaranteed to yield the optimal solution, along with a pruning scheme for further reducing the search space. In order to compare our proposal we extended a previously proposed solution aimed at non-time dependent sequenced route queries, enabling it to deal with the time-dependency. Our experiments using real and synthetic data sets have shown our proposed solution to be up to two orders of magnitude faster than the temporally extended previous solution.
LocLinkVis: A Geographic Information Retrieval-Based System for Large-Scale Exploratory Search
Venue: arXiv cs.IR 2015
Year: 2015

In this paper we present LocLinkVis (Locate-Link-Visualize); a system which supports exploratory information access to a document collection based on geo-referencing and visualization. It uses a gazetteer which contains representations of places ranging from countries to buildings, and that is used to recognize toponyms, disambiguate them into places, and to visualize the resulting spatial footprints.
Revisiting Conventional Task Schedulers to Exploit Asymmetry in ARM big.LITTLE Architectures for Dense Linear Algebra
Venue: arXiv cs.DC 2015
Year: 2015

Dealing with asymmetry in the architecture opens a plethora of questions from the perspective of scheduling task-parallel applications, and there exist early attempts to address this problem via ad-hoc strategies embedded into a runtime framework. In this paper we take a different path, which consists in addressing the complexity of the problem at the library level, via a few asymmetry-aware fundamental kernels, hiding the architecture heterogeneity from the task scheduler. For the specific domain of dense linear algebra, we show that this is not only possible but delivers much higher performance than a naive approach based on an asymmetry-oblivious scheduler. Furthermore, this solution also outperforms an ad-hoc asymmetry-aware scheduler furnished with sophisticated scheduling techniques.
The decision problem of modal product logics with a diagonal, and faulty counter machines
Venue: arXiv cs.LO 2015
Year: 2015

In the propositional modal (and algebraic) treatment of two-variable first-order logic equality is modelled by a `diagonal' constant, interpreted in square products of universal frames as the identity (also known as the `diagonal') relation. Here we study the decision problem of products of two arbitrary modal logics equipped with such a diagonal. As the presence or absence of equality in two-variable first-order logic does not influence the complexity of its satisfiability problem, one might expect that adding a diagonal to product logics in general is similarly harmless. We show that this is far from being the case, and there can be quite a big jump in complexity, even from decidable to the highly undecidable. Our undecidable logics can also be viewed as new fragments of first- order logic where adding equality changes a decidable fragment to undecidable. We prove our results by a novel application of counter machine problems. While our formalism apparently cannot force reliable counter machine computations directly, the presence of a unique diagonal in the models makes it possible to encode both lossy and insertion-error computations, for the same sequence of instructions. We show that, given such a pair of faulty computations, it is then possible to reconstruct a reliable run from them.
Managing & Analyzing Large Volumes of Dynamic & Diverse Data
Venue: arXiv cs.CY 2015
Year: 2015

This study reviews the topic of big data management in the 21st-century. There are various developments that have facilitated the extensive use of that form of data in different organizations. The most prominent beneficiaries are internet businesses and big companies that used vast volumes of data even before the computational era. The research looks at the definitions of big data and the factors that influence its access and use for different persons around the globe. Most people consider the internet as the most significant source of this data and more specifically on cloud computing and social networking platforms. It requires sufficient and adequate management procedures to achieve the efficient use of the big data. The study revisits some of the conventional methods that companies use to attain this. There are different challenges such as cost and security that limit the use of big data. Despite these problems, there are various benefits that everyone can exploit by implementing it, and they are the focus for most enterprises.
Cache-Enabled Broadcast Packet Erasure Channels with State Feedback
Venue: arXiv cs.IT 2015
Year: 2015

We consider a cache-enabled K-user broadcast erasure packet channel in which a server with a library of N files wishes to deliver a requested file to each user who is equipped with a cache of a finite memory M. Assuming that the transmitter has state feedback and user caches can be filled during off-peak hours reliably by decentralized cache placement, we characterize the optimal rate region as a function of the memory size, the erasure probability. The proposed delivery scheme, based on the scheme proposed by Gatzianas et al., exploits the receiver side information established during the placement phase. Our results enable us to quantify the net benefits of decentralized coded caching in the presence of erasure. The role of state feedback is found useful especially when the erasure probability is large and/or the normalized memory size is small.
Scheduling rules to minimize total tardiness in a parallel machine problem with setup and calendar constraints
Venue: arXiv cs.DC 2015
Year: 2015

Quality control lead times are one of most significant causes of loss of time in the pharmaceutical and cosmetics industries. This is partly due to the organization of laboratories that feature parallel multipurpose machines for chromatographic analyses. The testing process requires long setup times and operators are needed to launch the process. The various controls are non-preemptive and are characterized by a release date, a due date and available routings. These quality processes lead to significant delays, and we therefore evaluate the total tardiness criterion. Previous heuristics were defined for the total tardiness criterion, parallel machines, and setup such as ATC (Apparent Tardiness Cost) and ATCS (ATC with setups). We propose new rules and a simulated annealing procedure in order to minimize total tardiness.
Convexity Shape Constraints for Image Segmentation
Venue: arXiv cs.CV 2015
Year: 2015

Segmenting an image into multiple components is a central task in computer vision. In many practical scenarios, prior knowledge about plausible components is available. Incorporating such prior knowledge into models and algorithms for image segmentation is highly desirable, yet can be non-trivial. In this work, we introduce a new approach that allows, for the first time, to constrain some or all components of a segmentation to have convex shapes. Specifically, we extend the Minimum Cost Multicut Problem by a class of constraints that enforce convexity. To solve instances of this APX-hard integer linear program to optimality, we separate the proposed constraints in the branch-and-cut loop of a state-of-the-art ILP solver. Results on natural and biological images demonstrate the effectiveness of the approach as well as its advantage over the state-of-the-art heuristic.
Hybrid-BCP: A Robust Load Balancing and Routing Protocol for Intra-Car Wired/Wireless Networks
Venue: arXiv cs.NI 2015
Year: 2015

With the emergence of connected and autonomous vehicles, sensors are increasingly deployed within cars to support new functionalities. Traffic generated by these sensors congest traditional intra-car networks, such as CAN buses. Furthermore, the large amount of wires needed to connect sensors makes it harder to design cars in a modular way. To alleviate these limitations, we propose, simulate, and implement a hybrid wired/wireless architecture, in which each node is connected to either a wired interface or a wireless interface or both. Specifically, we propose a new protocol, called Hybrid-Backpressure Collection Protocol (Hybrid-BCP), to efficiently collect data from sensors in intra-car networks. Hybrid-BCP is backward-compatible with the CAN bus technology, and builds on the BCP protocol, designed for wireless sensor networks. Hybrid-BCP achieves high throughput and shows resilience to dynamic network conditions, including adversarial interferences. Our testbed implementation, based on CAN and ZigBee transceivers, demonstrates the load balancing and routing functionalities of Hybrid-BCP and its resilience to DoS attacks. We further provide simulation results, obtained with the ns-3 simulator and based on real intra-car RSSI traces, that compare between the performance of Hybrid-BCP and a tree-based collection protocol. Notably, the simulations show that Hybrid-BCP can achieve the same performance as the tree-based protocol while reducing the radio transmission power by a factor of 10.
Evaluation of Variability Concepts for Simulink in the Automotive Domain
Venue: arXiv cs.SE 2015
Year: 2015

Modeling variability in Matlab/Simulink becomes more and more important. We took the two variability modeling concepts already included in Matlab/Simulink and our own one and evaluated them to find out which one is suited best for modeling variability in the automotive domain. We conducted a controlled experiment with developers at Volkswagen AG to decide which concept is preferred by developers and if their preference aligns with measurable performance factors. We found out that all existing concepts are viable approaches and that the delta approach is both the preferred concept as well as the objectively most efficient one, which makes Delta-Simulink a good solution to model variability in the automotive domain.
Towards Product Lining Model-Driven Development Code Generators
Venue: arXiv cs.SE 2015
Year: 2015

A code generator systematically transforms compact models to detailed code. Today, code generation is regarded as an integral part of model-driven development (MDD). Despite its relevance, the development of code generators is an inherently complex task and common methodologies and architectures are lacking. Additionally, reuse and extension of existing code generators only exist on individual parts. A systematic development and reuse based on a code generator product line is still in its infancy. Thus, the aim of this paper is to identify the mechanism necessary for a code generator product line by (a) analyzing the common product line development approach and (b) mapping those to a code generator specific infrastructure. As a first step towards realizing a code generator product line infrastructure, we present a component-based implementation approach based on ideas of variability-aware module systems and point out further research challenges.
On Capacity Formulation with Stationary Inputs and Application to a Bit-Patterned Media Recording Channel Model
Venue: arXiv cs.IT 2015
Year: 2015

In this correspondence, we illustrate among other things the use of the stationarity property of the set of capacity-achieving inputs in capacity calculations. In particular, as a case study, we consider a bit-patterned media recording channel model and formulate new lower and upper bounds on its capacity that yield improvements over existing results. Inspired by the observation that the new bounds are tight at low noise levels, we also characterize the capacity of this model as a series expansion in the low-noise regime. The key to these results is the realization of stationarity in the supremizing input set in the capacity formula. While the property is prevalent in capacity formulations in the ergodic-theoretic literature, we show that this realization is possible in the Shannon-theoretic framework where a channel is defined as a sequence of finite-dimensional conditional probabilities, by defining a new class of consistent stationary and ergodic channels.
Developing and Comparing Single-arm and Dual-arm Regrasp
Venue: arXiv cs.RO 2015
Year: 2015

The goal of this paper is to develop efficient regrasp algorithms for single-arm and dual-arm regrasp and compares the performance of single-arm and dual-arm regrasp by running the two algorithms thousands of times. We focus on pick-and-place regrasp which reorients an object from one placement to another by using a sequence of pick-ups and place-downs. After analyzing the simulation results, we find dual-arm regrasp is not necessarily better than single-arm regrasp: Dual-arm regrasp is flexible. When the two hands can grasp the object with good clearance, dual-arm regrasp is better and has higher successful rate than single-arm regrasp. However, dual-arm regrasp suffers from geometric constraints caused by the two arms. When the grasps overlap, dual-arm regrasp is bad. Developers need to sample grasps with high density to reduce overlapping. This leads to exploded combinatorics in previous methods, but is possible with the algorithms presented in this paper. Following the results, practitioners may choose single-arm or dual-arm robots by considering the object shapes and grasps. Meanwhile, they can reduce overlapping and implement practical dual-arm regrasp by using the presented algorithms.
Directional antennas improve the link-connectivity of interference limited ad hoc networks
Venue: arXiv cs.NI 2015
Year: 2015

We study wireless ad hoc networks in the absence of any channel contention or transmit power control and ask how antenna directivity affects network connectivity in the interference limited regime. We answer this question by deriving closed-form expressions for the outage probability, capacity and mean node degree of the network using tools from stochastic geometry. These novel results provide valuable insights for the design of future ad hoc networks. Significantly, our results suggest that the more directional the interfering transmitters are, the less detrimental are the effects of interference to individual links. We validate our analytical results through computer simulations.
RSSI-Based Distributed Self-Localization for Wireless Sensor Networks used in Precision Agriculture
Venue: arXiv cs.DC 2015
Year: 2015

Node localization algorithms that can be easily integrated into deployed wireless sensor networks (WSNs) and which run seamlessly with proprietary lower layer communication protocols running on off-the-shelf modules can help operators of large farms and orchards avoid the difficulty, cost and/or time involved with manual or satellite-based node localization techniques. Even though the state-of-the-art node localization algorithms can achieve low error rates using distributed techniques such as belief propagation (BP), they are not well suited to WSNs deployed for precision agriculture applications with large number of nodes, few number of landmarks and lack real time update capability. The algorithm proposed here is designed for applications such as pest control and irrigation in large farms and orchards where greater power efficiency and scalability are required but location accuracy requirements are less demanding. Our algorithm uses received signal strength indicator (RSSI) values to estimate the distribution of distance between nodes then updates the location probability mass function (pmf) of nodes in a distributed manner. At every time step, the most recently communicated path loss samples and location prior pmf received from neighbouring nodes is sufficient for nodes with unknown location to update their location pmf. This renders the algorithm recursive, hence results in lower computational complexity at each time step. We propose a particular realization of the method in which only one node multicasts at each time step and neighbouring nodes update their location pmf conditioned on all communicated samples over previous time steps. This is highly compatible with realistic WSN deployments, e.g., ZigBee which are based upon the ad hoc on-demand distance vector (AODV) where nodes flood route request (RREQ) and route reply (RREP) packets in the network.
Fundamentals of the Holomorphic Embedding Load-Flow Method
Venue: arXiv cs.SY 2015
Year: 2015

The Holomorphic Embedding Load-Flow Method (HELM) was recently introduced as a novel technique to constructively solve the power-flow equations in power grids, based on advanced complex analysis. In this paper, the theoretical foundations of the method are established in detail. Starting from a fundamental projective invariance of the power-flow equations, it is shown how to devise holomorphicity-preserving embeddings that ultimately allow regarding the power-flow problem as essentially a study in algebraic curves. Complementing this algebraic-geometric viewpoint, which lays the foundation of the method, it is shown how to apply standard analytic techniques (power series) for practical computation. Stahl's theorem on the maximality of the analytic continuation provided by Padé approximants then ensures the completeness of the method. On the other hand, it is shown how to extend the method to accommodate smooth controls, such as the ubiquitous generator-controlled PV bus.
Improved Twitter Sentiment Prediction through Cluster-then-Predict Model
Venue: arXiv cs.IR 2015
Year: 2015

Over the past decade humans have experienced exponential growth in the use of online resources, in particular social media and microblogging websites such as Facebook, Twitter, YouTube and also mobile applications such as WhatsApp, Line, etc. Many companies have identified these resources as a rich mine of marketing knowledge. This knowledge provides valuable feedback which allows them to further develop the next generation of their product. In this paper, sentiment analysis of a product is performed by extracting tweets about that product and classifying the tweets showing it as positive and negative sentiment. The authors propose a hybrid approach which combines unsupervised learning in the form of K-means clustering to cluster the tweets and then performing supervised learning methods such as Decision Trees and Support Vector Machines for classification.
Semantic Video Segmentation : Exploring Inference Efficiency
Venue: arXiv cs.CV 2015
Year: 2015

We explore the efficiency of the CRF inference beyond image level semantic segmentation and perform joint inference in video frames. The key idea is to combine best of two worlds: semantic co-labeling and more expressive models. Our formulation enables us to perform inference over ten thousand images within seconds and makes the system amenable to perform video semantic segmentation most effectively. On CamVid dataset, with TextonBoost unaries, our proposed method achieves up to 8% improvement in accuracy over individual semantic image segmentation without additional time overhead. The source code is available at https://github.com/subtri/video_inference
A Behavior Analysis-Based Game Bot Detection Approach Considering Various Play Styles
Venue: arXiv cs.LG 2015
Year: 2015

An approach for game bot detection in MMORPGs is proposed based on the analysis of game playing behavior. Since MMORPGs are large scale games, users can play in various ways. This variety in playing behavior makes it hard to detect game bots based on play behaviors. In order to cope with this problem, the proposed approach observes game playing behaviors of users and groups them by their behavioral similarities. Then, it develops a local bot detection model for each player group. Since the locally optimized models can more accurately detect game bots within each player group, the combination of those models brings about overall improvement. For a practical purpose of reducing the workloads of the game servers in service, the game data is collected at a low resolution in time. Behavioral features are selected and developed to accurately detect game bots with the low resolution data, considering common aspects of MMORPG playing. Through the experiment with the real data from a game currently in service, it is shown that the proposed local model approach yields more accurate results.
Accelerated graph-based spectral polynomial filters
Venue: arXiv cs.CV 2015
Year: 2015

Graph-based spectral denoising is a low-pass filtering using the eigendecomposition of the graph Laplacian matrix of a noisy signal. Polynomial filtering avoids costly computation of the eigendecomposition by projections onto suitable Krylov subspaces. Polynomial filters can be based, e.g., on the bilateral and guided filters. We propose constructing accelerated polynomial filters by running flexible Krylov subspace based linear and eigenvalue solvers such as the Block Locally Optimal Preconditioned Conjugate Gradient (LOBPCG) method.