OpenRaiser/Intern-Atlas huggingface dataset:
Versinus: a visualization method for graphs in evolution
Venue: arXiv cs.SI 2014
Year: 2014

This article presents a novel visualization approach for dynamic graphs, the versinus method, specially useful for real world networks exhibiting free-scale properties. With a simple and fixed layout, and a small set of visual markups, the method has been useful for understanding network dynamics. Local community often suggests that it be reported, which motivated this article. Online resources deliver videos and computer scripts for rendering new animations. This article has a concise description of the method.
Verifiable Elections with Commitment Consistent Encryption -- A Primer
Venue: arXiv cs.CR 2014
Year: 2014

This note provides an introduction to the PPATS Commitment Consistent Encryption (CCE) scheme proposed by Cuvelier, Pereira and Peters and its use in the design of end-to-end verifiable elections with a perfectly private audit trail. These elections can be verified using audit data that will never leak any information about the vote, even if all the private keys of the elections are compromised, or if the cryptographic assumptions are broken.
Erasure coding for fault oblivious linear system solvers
Venue: arXiv cs.NA 2014
Year: 2014

Dealing with hardware and software faults is an important problem as parallel and distributed systems scale to millions of processing cores and wide area networks. Traditional methods for dealing with faults include checkpoint-restart, active replicas, and deterministic replay. Each of these techniques has associated resource overheads and constraints. In this paper, we propose an alternate approach to dealing with faults, based on input augmentation. This approach, which is an algorithmic analog of erasure coded storage, applies a minimally modified algorithm on the augmented input to produce an augmented output. The execution of such an algorithm proceeds completely oblivious to faults in the system. In the event of one or more faults, the real solution is recovered using a rapid reconstruction method from the augmented output. We demonstrate this approach on the problem of solving sparse linear systems using a conjugate gradient solver. We present input augmentation and output recovery techniques. Through detailed experiments, we show that our approach can be made oblivious to a large number of faults with low computational overhead. Specifically, we demonstrate cases where a single fault can be corrected with less than 10% overhead in time, and even in extreme cases (fault rates of 20%), our approach is able to compute a solution with reasonable overhead. These results represent a significant improvement over the state of the art.
The Approximation Ratio of the Greedy Algorithm for the Metric Traveling Salesman Problem
Venue: arXiv cs.DM 2014
Year: 2014

We prove that the approximation ratio of the greedy algorithm for the metric Traveling Salesman Problem is $Θ(\log n)$. Moreover, we prove that the same result also holds for graphic, Euclidean, and rectilinear instances of the Traveling Salesman Problem. Finally we show that the approximation ratio of the Clarke-Wright savings heuristic for the metric Traveling Salesman Problem is $Θ(\log n)$.
Toward Refactoring of DMARF and GIPSY Case Studies -- A Team XI SOEN6471-S14 Project Report
Venue: arXiv cs.SE 2014
Year: 2014

This report focuses on improving the internal structure of the Distributed Modular Audio recognition Framework (DMARF) and the General Intensional Programming System (GIPSY) case studies without affecting their original behavior. At first, the general principles, and the working of DMARF and GIPSY are understood by mainly stressing on the architecture of the systems by looking at their frameworks and running them in the Eclipse environment. To improve the quality of the structure of the code, a furtherance of understanding of the architecture of the case studies and this is achieved by analyzing the design patterns present in the code. The improvement is done by the identification and removal of code smells in the code of the case studies. Code smells are identified by analyzing the source code by using Logiscope and JDeodorant. Some refactoring techniques are suggested, out of which the best suited ones are implemented to improve the code. Finally, Test cases are implemented to check if the behavior of the code has changed or not.
Differential Privacy and Machine Learning: a Survey and Review
Venue: arXiv cs.LG 2014
Year: 2014

The objective of machine learning is to extract useful information from data, while privacy is preserved by concealing information. Thus it seems hard to reconcile these competing interests. However, they frequently must be balanced when mining sensitive data. For example, medical research represents an important application where it is necessary both to extract useful information and protect patient privacy. One way to resolve the conflict is to extract general characteristics of whole populations without disclosing the private information of individuals. In this paper, we consider differential privacy, one of the most popular and powerful definitions of privacy. We explore the interplay between machine learning and differential privacy, namely privacy-preserving machine learning algorithms and learning-based data release mechanisms. We also describe some theoretical results that address what can be learned differentially privately and upper bounds of loss functions for differentially private algorithms. Finally, we present some open questions, including how to incorporate public data, how to deal with missing data in private datasets, and whether, as the number of observed samples grows arbitrarily large, differentially private machine learning algorithms can be achieved at no cost to utility as compared to corresponding non-differentially private algorithms.
Greedy Algorithms for Steiner Forest
Venue: arXiv cs.DS 2014
Year: 2014

In the Steiner Forest problem, we are given terminal pairs $\{s_i, t_i\}$, and need to find the cheapest subgraph which connects each of the terminal pairs together. In 1991, Agrawal, Klein, and Ravi, and Goemans and Williamson gave primal-dual constant-factor approximation algorithms for this problem; until now, the only constant-factor approximations we know are via linear programming relaxations. We consider the following greedy algorithm: Given terminal pairs in a metric space, call a terminal "active" if its distance to its partner is non-zero. Pick the two closest active terminals (say $s_i, t_j$), set the distance between them to zero, and buy a path connecting them. Recompute the metric, and repeat. Our main result is that this algorithm is a constant-factor approximation. We also use this algorithm to give new, simpler constructions of cost-sharing schemes for Steiner forest. In particular, the first "group-strict" cost-shares for this problem implies a very simple combinatorial sampling-based algorithm for stochastic Steiner forest.
Fronthaul Compression and Precoding Design for C-RANs over Ergodic Fading Channel
Venue: arXiv cs.IT 2014
Year: 2014

This work investigates the joint design of fronthaul compression and precoding for the downlink of Cloud Radio Access Networks (C-RANs). In a C-RAN, a central unit (CU) performs the baseband processing for a cluster of radio units (RUs) that receive compressed baseband samples from the CU through low-latency fronthaul links. Most previous works on the design of fronthaul compression and precoding assume constant channels and instantaneous channel state information (CSI) at the CU. This work, in contrast, concentrates on a more practical scenario with block-ergodic channels and considers either instantaneous or stochastic CSI at the CU. Moreover, the analysis encompasses both the Compression-After-Precoding (CAP) and the Compression-Before-Precoding (CBP) schemes. With the CAP approach, which is the standard C-RAN solution, the CU performs channel coding and precoding and then the CU compresses and forwards the resulting baseband signals on the fronthaul links to the RUs. With the CBP scheme, instead, the CU does not perform precoding but rather forwards separately the information messages of a subset of mobile stations (MSs) along with the compressed precoding matrices to the each RU, which then performs precoding. Optimization algorithms over fronthaul compression and precoding for both CAP and CBP are proposed that are based on a stochastic successive upper-bound minimization approach. Via numerical results, the relative merits of the two strategies under either instantaneous or stochastic CSI are evaluated as a function of system parameters such as fronthaul capacity and channel coherence time.
Interactive Visual Exploration of Halos in Large Scale Cosmology Simulation
Venue: arXiv cs.GR 2014
Year: 2014

Halo is one of the most important basic elements in cosmology simulation, which merges from small clumps to ever larger objects. The processes of the birth and merging of the halos play a fundamental role in studying the evolution of large scale cosmological structures. In this paper, a visual analysis system is developed to interactively identify and explore the evolution histories of thousands of halos. In this system, an intelligent structure-aware selection method in What You See Is What You Get manner is designed to efficiently define the interesting region in 3D space with 2D hand-drawn lasso input. Then the exact information of halos within this 3D region is identified by data mining in the merger tree files. To avoid visual clutter, all the halos are projected in 2D space with a MDS method. Through the linked view of 3D View and 2D graph, Users can interactively explore these halos, including the tracing path and evolution history tree.
Multi Time Scale Behaviour of The Formation of Multiple Groups of Nonholonomic Wheeled Mobile Robots
Venue: arXiv cs.SY 2014
Year: 2014

Different geometric patterns and shapes are generated using groups of agents, and this needs formation control. In this paper, Centroid Based Transformation (CBT), has been applied to decompose the combined dynamics of nonholonomic Wheeled Mobile Robots (WMRs) into three subsystems: intra and inter group shape dynamics, and the dynamics of the centroid. The intra group shape dynamics can further be partitioned into the shape dynamics of each group, giving the notion of multiple group. Thus separate controllers have been designed for each subsystem. The gains of the controllers are such chosen that the overall system becomes singularly perturbed system, and different subsystems converge to their desired values at different times. Then multi-time scale convergence analysis has been carried out in this paper. Negative gradient of a potential based function has been added to the controller to ensure collision avoidance among the robots. Simulation results have been provided to demonstrate the effectiveness of the proposed controller.
Brachiaria species identification using imaging techniques based on fractal descriptors
Venue: arXiv cs.CV 2014
Year: 2014

The use of a rapid and accurate method in diagnosis and classification of species and/or cultivars of forage has practical relevance, scientific and trade in various areas of study. Thus, leaf samples of fodder plant species \textit{Brachiaria} were previously identified, collected and scanned to be treated by means of artificial vision to make the database and be used in subsequent classifications. Forage crops used were: \textit{Brachiaria decumbens} cv. IPEAN; \textit{Brachiaria ruziziensis} Germain \& Evrard; \textit{Brachiaria Brizantha} (Hochst. ex. A. Rich.) Stapf; \textit{Brachiaria arrecta} (Hack.) Stent. and \textit{Brachiaria spp}. The images were analyzed by the fractal descriptors method, where a set of measures are obtained from the values of the fractal dimension at different scales. Therefore such values are used as inputs for a state-of-the-art classifier, the Support Vector Machine, which finally discriminates the images according to the respective species.
Fast Partial Distance Estimation and Applications
Venue: arXiv cs.DC 2014
Year: 2014

We study approximate distributed solutions to the weighted {\it all-pairs-shortest-paths} (APSP) problem in the CONGEST model. We obtain the following results. $1.$ A deterministic $(1+o(1))$-approximation to APSP in $\tilde{O}(n)$ rounds. This improves over the best previously known algorithm, by both derandomizing it and by reducing the running time by a $Θ(\log n)$ factor. In many cases, routing schemes involve relabeling, i.e., assigning new names to nodes and require that these names are used in distance and routing queries. It is known that relabeling is necessary to achieve running times of $o(n/\log n)$. In the relabeling model, we obtain the following results. $2.$ A randomized $O(k)$-approximation to APSP, for any integer $k>1$, running in $\tilde{O}(n^{1/2+1/k}+D)$ rounds, where $D$ is the hop diameter of the network. This algorithm simplifies the best previously known result and reduces its approximation ratio from $O(k\log k)$ to $O(k)$. Also, the new algorithm uses uses labels of asymptotically optimal size, namely $O(\log n)$ bits. $3.$ A randomized $O(k)$-approximation to APSP, for any integer $k>1$, running in time $\tilde{O}((nD)^{1/2}\cdot n^{1/k}+D)$ and producing {\it compact routing tables} of size $\tilde{O}(n^{1/k})$. The node lables consist of $O(k\log n)$ bits. This improves on the approximation ratio of $Θ(k^2)$ for tables of that size achieved by the best previously known algorithm, which terminates faster, in $\tilde{O}(n^{1/2+1/k}+D)$ rounds.
Home Automation Using SSVEP & Eye-Blink Detection Based Brain-Computer Interface
Venue: arXiv cs.HC 2014
Year: 2014

In this paper, we present a novel brain computer interface based home automation system using two responses - Steady State Visually Evoked Potential (SSVEP) and the eye-blink artifact, which is augmented by a Bluetooth based indoor localization system, to greatly increase the number of controllable devices. The hardware implementation of this system to control a table lamp and table fan using brain signals has also been discussed and state-of-the-art results have been achieved.
Bitcoin Meets Strong Consistency
Venue: arXiv cs.DC 2014
Year: 2014

The Bitcoin system only provides eventual consistency. For everyday life, the time to confirm a Bitcoin transaction is prohibitively slow. In this paper we propose a new system, built on the Bitcoin blockchain, which enables strong consistency. Our system, PeerCensus, acts as a certification authority, manages peer identities in a peer-to-peer network, and ultimately enhances Bitcoin and similar systems with strong consistency. Our extensive analysis shows that PeerCensus is in a secure state with high probability. We also show how Discoin, a Bitcoin variant that decouples block creation and transaction confirmation, can be built on top of PeerCensus, enabling real-time payments. Unlike Bitcoin, once transactions in Discoin are committed, they stay committed.
Detect2Rank : Combining Object Detectors Using Learning to Rank
Venue: arXiv cs.CV 2014
Year: 2014

Object detection is an important research area in the field of computer vision. Many detection algorithms have been proposed. However, each object detector relies on specific assumptions of the object appearance and imaging conditions. As a consequence, no algorithm can be considered as universal. With the large variety of object detectors, the subsequent question is how to select and combine them. In this paper, we propose a framework to learn how to combine object detectors. The proposed method uses (single) detectors like DPM, CN and EES, and exploits their correlation by high level contextual features to yield a combined detection list. Experiments on the PASCAL VOC07 and VOC10 datasets show that the proposed method significantly outperforms single object detectors, DPM (8.4%), CN (6.8%) and EES (17.0%) on VOC07 and DPM (6.5%), CN (5.5%) and EES (16.2%) on VOC10.
Texture analysis by multi-resolution fractal descriptors
Venue: arXiv cs.CV 2014
Year: 2014

This work proposes a texture descriptor based on fractal theory. The method is based on the Bouligand-Minkowski descriptors. We decompose the original image recursively into 4 equal parts. In each recursion step, we estimate the average and the deviation of the Bouligand-Minkowski descriptors computed over each part. Thus, we extract entropy features from both average and deviation. The proposed descriptors are provided by the concatenation of such measures. The method is tested in a classification experiment under well known datasets, that is, Brodatz and Vistex. The results demonstrate that the proposed technique achieves better results than classical and state-of-the-art texture descriptors, such as Gabor-wavelets and co-occurrence matrix.
Adding Context to Knowledge and Action Bases
Venue: arXiv cs.AI 2014
Year: 2014

Knowledge and Action Bases (KABs) have been recently proposed as a formal framework to capture the dynamics of systems which manipulate Description Logic (DL) Knowledge Bases (KBs) through action execution. In this work, we enrich the KAB setting with contextual information, making use of different context dimensions. On the one hand, context is determined by the environment using context-changing actions that make use of the current state of the KB and the current context. On the other hand, it affects the set of TBox assertions that are relevant at each time point, and that have to be considered when processing queries posed over the KAB. Here we extend to our enriched setting the results on verification of rich temporal properties expressed in mu-calculus, which had been established for standard KABs. Specifically, we show that under a run-boundedness condition, verification stays decidable.
Impact of Wavelength and Modulation Conversion on Transluscent Elastic Optical Networks Using MILP
Venue: arXiv cs.NI 2014
Year: 2014

Compared to legacy wavelength division multiplexing networks, elastic optical networks (EON) have added flexibility to network deployment and management. EONs can include previously available technology, such as signal regeneration and wavelength conversion, as well as new features such as finer-granularity spectrum assignment and modulation conversion. Yet each added feature adds to the cost of the network. In order to quantify the potential benefit of each technology, we present a link-based mixed-integer linear programming (MILP) formulation to solve the optimal resource allocation problem. We then propose a recursive model in order to either augment existing network deployments or speed up the resource allocation computation time for larger networks with higher traffic demand requirements than can be solved using an MILP. We show through simulation that systems equipped with signal regenerators or wavelength converters require a notably smaller total bandwidth, depending on the topology of the network. We also show that the suboptimal recursive solution speeds up the calculation and makes the running-time more predictable, compared to the optimal MILP.
A Simulation Based Performance Comparison Study of Stability-Based Routing, Power-Aware Routing and Load-Balancing On-Demand Routing Protocols for Mobile Ad hoc Networks
Venue: arXiv cs.NI 2014
Year: 2014

The high-level contribution of this paper is a simulation-based detailed performance comparison of three different classes of on-demand routing protocols for mobile ad hoc networks: stability-based routing, power-aware routing and load-balanced routing. We choose the Flow-Oriented Routing protocol (FORP), Min-Max Battery Cost Routing (MMBCR) and the traffic interference based Load Balancing Routing (LBR) protocol as representatives of the stability-based routing, poweraware routing and load-balancing routing protocols respectively. FORP incurs the least number of route transitions; while LBR incurs the smallest hop count and lowest end-to-end delay per data packet. Energy consumed per data packet is the least for LBR, closely followed by MMBCR. FORP incurs the maximum energy consumed per data packet, both in the absence and presence of power control. Nevertheless, in the presence of power control, the end-to-end delay per data packet and energy consumed per data packet incurred by FORP are significantly reduced compared to the scenario without power control. MMBCR is the most fair in terms of node usage and incurs the largest time for first node failure. FORP tends to repeatedly use nodes lying on the stable path and hence is the most unfair of the three routing protocols. FORP also incurs the smallest value for the time of first node failure.
Complex support vector machines regression for robust channel estimation in LTE downlink system
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, the problem of channel estimation for LTE Downlink system in the environment of high mobility presenting non-Gaussian impulse noise interfering with reference signals is faced. The estimation of the frequency selective time varying multipath fading channel is performed by using a channel estimator based on a nonlinear complex Support Vector Machine Regression (SVR) which is applied to Long Term Evolution (LTE) downlink. The estimation algorithm makes use of the pilot signals to estimate the total frequency response of the highly selective fading multipath channel. Thus, the algorithm maps trained data into a high dimensional feature space and uses the structural risk minimization principle to carry out the regression estimation for the frequency response function of the fading channel. The obtained results show the effectiveness of the proposed method which has better performance than the conventional Least Squares (LS) and Decision Feedback methods to track the variations of the fading multipath channel.
Adapting Graph Application Performance via Alternate Data Structure Representation
Venue: arXiv cs.PL 2014
Year: 2014

Graph processing is used extensively in areas from social networking mining to web indexing. We demonstrate that the performance and dependability of such applications critically hinges on the graph data structure used, because a fixed, compile-time choice of data structure can lead to poor performance or applications unable to complete. To address this problem, we introduce an approach that helps programmers transform regular, off-the-shelf graph applications into adaptive, more dependable applications where adaptations are performed via runtime selection from alternate data structure representations. Using our approach, applications dynamically adapt to the input graph's characteristics and changes in available memory so they continue to run when faced with adverse conditions such as low memory. Experiments with graph algorithms on real-world (e.g., Wikipedia metadata, Gnutella topology) and synthetic graph datasets show that our adaptive applications run to completion with lower execution time and/or memory utilization in comparison to their non-adaptive versions.
Generalized quaternions and their relations with Grassmann-Clifford procedure of doubling
Venue: arXiv cs.NA 2014
Year: 2014

The class of non-commutative hypercomplex number systems (HNS) of 4-dimension, constructed by using of non-commutative Grassmann-Clifford procedure of doubling of 2-dimensional systems is investigated in the article and established here are their relationships with the generalized quaternions. Algorithms of performance of operations and methods of algebraic characteristics calculation in them, such as conjugation, normalization, a type of zero divisors are investigated. The considered arithmetic and algebraic operations and procedures in this class HNS allow to use these HNS in mathematical modeling.