OpenRaiser/Intern-Atlas huggingface dataset:
Generalized Paxos Made Byzantine (and Less Complex)
Venue: arXiv cs.DC 2017
Year: 2017

One of the most recent members of the Paxos family of protocols is Generalized Paxos. This variant of Paxos has the characteristic that it departs from the original specification of consensus, allowing for a weaker safety condition where different processes can have a different views on a sequence being agreed upon. However, much like the original Paxos counterpart, Generalized Paxos does not have a simple implementation. Furthermore, with the recent practical adoption of Byzantine fault tolerant protocols, it is timely and important to understand how Generalized Paxos can be implemented in the Byzantine model. In this paper, we make two main contributions. First, we provide a description of Generalized Paxos that is easier to understand, based on a simpler specification and the pseudocode for a solution that can be readily implemented. Second, we extend the protocol to the Byzantine fault model.
Learning to Blame: Localizing Novice Type Errors with Data-Driven Diagnosis
Venue: arXiv cs.PL 2017
Year: 2017

Localizing type errors is challenging in languages with global type inference, as the type checker must make assumptions about what the programmer intended to do. We introduce Nate, a data-driven approach to error localization based on supervised learning. Nate analyzes a large corpus of training data -- pairs of ill-typed programs and their "fixed" versions -- to automatically learn a model of where the error is most likely to be found. Given a new ill-typed program, Nate executes the model to generate a list of potential blame assignments ranked by likelihood. We evaluate Nate by comparing its precision to the state of the art on a set of over 5,000 ill-typed OCaml programs drawn from two instances of an introductory programming course. We show that when the top-ranked blame assignment is considered, Nate's data-driven model is able to correctly predict the exact sub-expression that should be changed 72% of the time, 28 points higher than OCaml and 16 points higher than the state-of-the-art SHErrLoc tool. Furthermore, Nate's accuracy surpasses 85% when we consider the top two locations and reaches 91% if we consider the top three.
Comments on Truncation Errors for Polynomial Chaos Expansions
Venue: arXiv cs.SY 2017
Year: 2017

Methods based on polynomial chaos expansion allow to approximate the behavior of systems with uncertain parameters by deterministic dynamics. These methods are used in a wide range of applications, spanning from simulation of uncertain systems to estimation and control. For practical purposes the exploited spectral series expansion is typically truncated to allow for efficient computation, which leads to approximation errors. Despite the Hilbert space nature of polynomial chaos, there are only a few results in the literature that explicitly discuss and quantify these approximation errors. This work derives error bounds for polynomial chaos approximations of polynomial and non-polynomial mappings. Sufficient conditions are established, which allow investigating the question whether zero truncation errors can be achieved and which series order is required to achieve this. Furthermore, convex quadratic programs, whose argmin operator is a special case of a piecewise polynomial mapping, are studied due to their relevance in predictive control. Several simulation examples illustrate our findings.
Recover the lost Phasor Measurement Unit Data Using Alternating Direction Multipliers Method
Venue: arXiv cs.NA 2017
Year: 2017

This paper presents a novel algorithm for recovering missing data of phasor measurement units (PMUs). Due to the low-rank property of PMU data, missing measurement recovery can be formulated as a low-rank matrix-completion problem. Based on maximum-margin matrix factorization, we propose an efficient algorithm based on alternating direction method of multipliers (ADMM) for solving the matrix completion problem. Comparing to existing approaches, the proposed ADMM based algorithm does not need to estimate the rank of the target data matrix and provides better performance in computation complexity. In addition, we consider the case of measurements missing from all PMU channels and provide a strategy of reshaping the matrix which contains the received PMU data for recovery. Numerical results using PMU measurements from IEEE 68-bus power system model illustrate the effectiveness and efficiency of the proposed approaches.
Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
Venue: arXiv cs.LG 2017
Year: 2017

We present Fashion-MNIST, a new dataset comprising of 28x28 grayscale images of 70,000 fashion products from 10 categories, with 7,000 images per category. The training set has 60,000 images and the test set has 10,000 images. Fashion-MNIST is intended to serve as a direct drop-in replacement for the original MNIST dataset for benchmarking machine learning algorithms, as it shares the same image size, data format and the structure of training and testing splits. The dataset is freely available at https://github.com/zalandoresearch/fashion-mnist
Algorithms for Big Data: Graphs and PageRank
Venue: arXiv cs.DS 2017
Year: 2017

This work consists of a study of a set of techniques and strategies related with algorithm's design, whose purpose is the resolution of problems on massive data sets, in an efficient way. This field is known as Algorithms for Big Data. In particular, this work has studied the Streaming Algorithms, which represents the basis of the data structures of sublinear order $o(n)$ in space, known as Sketches. In addition, it has deepened in the study of problems applied to Graphs on the Semi-Streaming model. Next, the PageRank algorithm was analyzed as a concrete case study. Finally, the development of a library for the resolution of graph problems, implemented on the top of the intensive mathematical computation platform known as TensorFlow has been started.
Wireless Access for Ultra-Reliable Low-Latency Communication (URLLC): Principles and Building Blocks
Venue: arXiv cs.IT 2017
Year: 2017

Ultra-reliable low latency communication (URLLC) is an important new feature brought by 5G, with a potential to support a vast set of applications that rely on mission-critical links. In this article, we first discuss the principles for supporting URLLC from the perspective of the traditional assumptions and models applied in communication/information theory. We then discuss how these principles are applied in various elements of the system design, such as use of various diversity sources, design of packets and access protocols. The important messages are that there is a need to optimize the transmission of signaling information, as well as a need for a lean use of various sources of diversity.
A European research roadmap for optimizing societal impact of big data on environment and energy efficiency
Venue: arXiv cs.CY 2017
Year: 2017

We present a roadmap to guide European research efforts towards a socially responsible big data economy that maximizes the positive impact of big data in environment and energy efficiency. The goal of the roadmap is to allow stakeholders and the big data community to identify and meet big data challenges, and to proceed with a shared understanding of the societal impact, positive and negative externalities, and concrete problems worth investigating. It builds upon a case study focused on the impact of big data practices in the context of Earth Observation that reveals both positive and negative effects in the areas of economy, society and ethics, legal frameworks and political issues. The roadmap identifies European technical and non-technical priorities in research and innovation to be addressed in the upcoming five years in order to deliver societal impact, develop skills and contribute to standardization.
Critical Peaks Redefined - $Φ\sqcup Ψ= \top$
Venue: arXiv cs.LO 2017
Year: 2017

Let a cluster be a term with a number of patterns occurring in it. We give two accounts of clusters, a geometric one as sets of (node and edge) positions, and an inductive one as pairs of terms with gaps (2nd order variables) and pattern-substitutions for the gaps. We show both notions of cluster and the corresponding refinement/coarsening orders on them, to be isomorphic. This equips clusters with a lattice structure which we lift to (parallel/multi) steps to yield an alternative account of the notion of critical peak.
An Algorithm of Parking Planning for Smart Parking System
Venue: arXiv cs.DS 2017
Year: 2017

There are so many vehicles in the world and the number of vehicles is increasing rapidly. To alleviate the parking problems caused by that, the smart parking system has been developed. The parking planning is one of the most important parts of it. An effective parking planning strategy makes the better use of parking resources possible. In this paper, we present a feasible method to do parking planning. We transform the parking planning problem into a kind of linear assignment problem. We take vehicles as jobs and parking spaces as agents. We take distances between vehicles and parking spaces as costs for agents doing jobs. Then we design an algorithm for this particular assignment problem and solve the parking planning problem. The method proposed can give timely and efficient guide information to vehicles for a real time smart parking system. Finally, we show the effectiveness of the method with experiments over some data, which can simulate the situation of doing parking planning in the real world.
3D Binary Signatures
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we propose a novel binary descriptor for 3D point clouds. The proposed descriptor termed as 3D Binary Signature (3DBS) is motivated from the matching efficiency of the binary descriptors for 2D images. 3DBS describes keypoints from point clouds with a binary vector resulting in extremely fast matching. The method uses keypoints from standard keypoint detectors. The descriptor is built by constructing a Local Reference Frame and aligning a local surface patch accordingly. The local surface patch constitutes of identifying nearest neighbours based upon an angular constraint among them. The points are ordered with respect to the distance from the keypoints. The normals of the ordered pairs of these keypoints are projected on the axes and the relative magnitude is used to assign a binary digit. The vector thus constituted is used as a signature for representing the keypoints. The matching is done by using hamming distance. We show that 3DBS outperforms state of the art descriptors on various evaluation metrics.
LERC: Coordinated Cache Management for Data-Parallel Systems
Venue: arXiv cs.DC 2017
Year: 2017

Memory caches are being aggressively used in today's data-parallel frameworks such as Spark, Tez and Storm. By caching input and intermediate data in memory, compute tasks can witness speedup by orders of magnitude. To maximize the chance of in-memory data access, existing cache algorithms, be it recency- or frequency-based, settle on cache hit ratio as the optimization objective. However, unlike the conventional belief, we show in this paper that simply pursuing a higher cache hit ratio of individual data blocks does not necessarily translate into faster task completion in data-parallel environments. A data-parallel task typically depends on multiple input data blocks. Unless all of these blocks are cached in memory, no speedup will result. To capture this all-or-nothing property, we propose a more relevant metric, called effective cache hit ratio. Specifically, a cache hit of a data block is said to be effective if it can speed up a compute task. In order to optimize the effective cache hit ratio, we propose the Least Effective Reference Count (LERC) policy that persists the dependent blocks of a compute task as a whole in memory. We have implemented the LERC policy as a memory manager in Spark and evaluated its performance through Amazon EC2 deployment. Evaluation results demonstrate that LERC helps speed up data-parallel jobs by up to 37% compared with the widely employed least-recently-used (LRU) policy.
3D Object Reconstruction from a Single Depth View with Adversarial Learning
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we propose a novel 3D-RecGAN approach, which reconstructs the complete 3D structure of a given object from a single arbitrary depth view using generative adversarial networks. Unlike the existing work which typically requires multiple views of the same object or class labels to recover the full 3D geometry, the proposed 3D-RecGAN only takes the voxel grid representation of a depth view of the object as input, and is able to generate the complete 3D occupancy grid by filling in the occluded/missing regions. The key idea is to combine the generative capabilities of autoencoders and the conditional Generative Adversarial Networks (GAN) framework, to infer accurate and fine-grained 3D structures of objects in high-dimensional voxel space. Extensive experiments on large synthetic datasets show that the proposed 3D-RecGAN significantly outperforms the state of the art in single view 3D object reconstruction, and is able to reconstruct unseen types of objects. Our code and data are available at: https://github.com/Yang7879/3D-RecGAN.
Limited Feedback Scheme for Device to Device Communications in 5G Cellular Networks with Reliability and Cellular Secrecy Outage Constraints
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we propose a device to device (D2D) communication scenario underlaying a cellular network where both D2D and cellular users (CUs) are discrete power-rate systems with limited feedback from the receivers. It is assumed that there exists an adversary which wants to eavesdrop on the information transmission from the base station (BS) to CUs. Since D2D communication shares the same spectrum with cellular network, cross interference must be considered. However, when secrecy capacity is considered, the interference caused by D2D communication can help to improve the secrecy communications by confusing the eavesdroppers. Since both systems share the same spectrum, cross interference must be considered. We formulate the proposed resource allocation into an optimization problem whose objective is to maximize the average transmission rate of D2D pair in the presence of the cellular communications under average transmission power constraint. For the cellular network, we require a minimum average achievable secrecy rate in the absence of D2D communication as well as a maximum secrecy outage probability in the presence of D2D communication which should be satisfied. Due to high complexity convex optimization methods, to solve the proposed optimization problem, we apply Particle Swarm Optimization (PSO) which is an evolutionary approach. Moreover, we model and study the error in the feedback channel and the imperfectness of channel distribution information (CDI) using parametric and nonparametric methods. Finally, the impact of different system parameters on the performance of the proposed scheme is investigated through simulations. The performance of the proposed scheme is evaluated using numerical results for different scenarios.
GiViP: A Visual Profiler for Distributed Graph Processing Systems
Venue: arXiv cs.DC 2017
Year: 2017

Analyzing large-scale graphs provides valuable insights in different application scenarios. While many graph processing systems working on top of distributed infrastructures have been proposed to deal with big graphs, the tasks of profiling and debugging their massive computations remain time consuming and error-prone. This paper presents GiViP, a visual profiler for distributed graph processing systems based on a Pregel-like computation model. GiViP captures the huge amount of messages exchanged throughout a computation and provides an interactive user interface for the visual analysis of the collected data. We show how to take advantage of GiViP to detect anomalies related to the computation and to the infrastructure, such as slow computing units and anomalous message patterns.
On Secure Communication using RF Energy Harvesting Two-Way Untrusted Relay
Venue: arXiv cs.IT 2017
Year: 2017

We focus on a scenario where two wireless source nodes wish to exchange confidential information via an RF energy harvesting untrusted two-way relay. Despite its cooperation in forwarding the information, the relay is considered untrusted out of the concern that it might attempt to decode the confidential information that is being relayed. To discourage the eavesdropping intention of the relay, we use a friendly jammer. Under the total power constraint, to maximize the sum-secrecy rate, we allocate the power among the sources and the jammer optimally and calculate the optimal power splitting ratio to balance between the energy harvesting and the information processing at the relay. We further examine the effect of imperfect channel state information at both sources on the sum-secrecy rate. Numerical results highlight the role of the jammer in achieving the secure communication under channel estimation errors. We have shown that, as the channel estimation error on any of the channels increases, the power allocated to the jammer decreases to abate the interference caused to the confidential information reception due to the imperfect cancellation of jammer's signal.
Fast and Precise Type Checking for JavaScript
Venue: arXiv cs.PL 2017
Year: 2017

In this paper we present the design and implementation of Flow, a fast and precise type checker for JavaScript that is used by thousands of developers on millions of lines of code at Facebook every day. Flow uses sophisticated type inference to understand common JavaScript idioms precisely. This helps it find non-trivial bugs in code and provide code intelligence to editors without requiring significant rewriting or annotations from the developer. We formalize an important fragment of Flow's analysis and prove its soundness. Furthermore, Flow uses aggressive parallelization and incrementalization to deliver near-instantaneous response times. This helps it avoid introducing any latency in the usual edit-refresh cycle of rapid JavaScript development. We describe the algorithms and systems infrastructure that we built to scale Flow's analysis.
Local Gaussian Processes for Efficient Fine-Grained Traffic Speed Prediction
Venue: arXiv cs.AI 2017
Year: 2017

Traffic speed is a key indicator for the efficiency of an urban transportation system. Accurate modeling of the spatiotemporally varying traffic speed thus plays a crucial role in urban planning and development. This paper addresses the problem of efficient fine-grained traffic speed prediction using big traffic data obtained from static sensors. Gaussian processes (GPs) have been previously used to model various traffic phenomena, including flow and speed. However, GPs do not scale with big traffic data due to their cubic time complexity. In this work, we address their efficiency issues by proposing local GPs to learn from and make predictions for correlated subsets of data. The main idea is to quickly group speed variables in both spatial and temporal dimensions into a finite number of clusters, so that future and unobserved traffic speed queries can be heuristically mapped to one of such clusters. A local GP corresponding to that cluster can then be trained on the fly to make predictions in real-time. We call this method localization. We use non-negative matrix factorization for localization and propose simple heuristics for cluster mapping. We additionally leverage on the expressiveness of GP kernel functions to model road network topology and incorporate side information. Extensive experiments using real-world traffic data collected in the two U.S. cities of Pittsburgh and Washington, D.C., show that our proposed local GPs significantly improve both runtime performances and prediction accuracies compared to the baseline global and local GPs.
Learning MSO-definable hypotheses on string
Venue: arXiv cs.LG 2017
Year: 2017

We study the classification problems over string data for hypotheses specified by formulas of monadic second-order logic MSO. The goal is to design learning algorithms that run in time polynomial in the size of the training set, independently of or at least sublinear in the size of the whole data set. We prove negative as well as positive results. If the data set is an unprocessed string to which our algorithms have local access, then learning in sublinear time is impossible even for hypotheses definable in a small fragment of first-order logic. If we allow for a linear time pre-processing of the string data to build an index data structure, then learning of MSO-definable hypotheses is possible in time polynomial in the size of the training set, independently of the size of the whole data set.
LocalCoin: An Ad-hoc Payment Scheme for Areas with High Connectivity
Venue: arXiv cs.CR 2017
Year: 2017

The popularity of digital currencies, especially cryptocurrencies, has been continuously growing since the appearance of Bitcoin. Bitcoin's security lies in a proof-of-work scheme, which requires high computational resources at the miners. Despite advances in mobile technology, existing cryptocurrencies cannot be maintained by mobile devices due to their low processing capabilities. Mobile devices can only accommodate mobile applications (wallets) that allow users to exchange credits of cryptocurrencies. In this work, we propose LocalCoin, an alternative cryptocurrency that requires minimal computational resources, produces low data traffic and works with off-the-shelf mobile devices. LocalCoin replaces the computational hardness that is at the root of Bitcoin's security with the social hardness of ensuring that all witnesses to a transaction are colluders. Localcoin features (i) a lightweight proof-of-work scheme and (ii) a distributed blockchain. We analyze LocalCoin for double spending for passive and active attacks and prove that under the assumption of sufficient number of users and properly selected tuning parameters the probability of double spending is close to zero. Extensive simulations on real mobility traces, realistic urban settings, and random geometric graphs show that the probability of success of one transaction converges to 1 and the probability of the success of a double spending attempt converges to 0.
ChainerCV: a Library for Deep Learning in Computer Vision
Venue: arXiv cs.CV 2017
Year: 2017

Despite significant progress of deep learning in the field of computer vision, there has not been a software library that covers these methods in a unifying manner. We introduce ChainerCV, a software library that is intended to fill this gap. ChainerCV supports numerous neural network models as well as software components needed to conduct research in computer vision. These implementations emphasize simplicity, flexibility and good software engineering practices. The library is designed to perform on par with the results reported in published papers and its tools can be used as a baseline for future research in computer vision. Our implementation includes sophisticated models like Faster R-CNN and SSD, and covers tasks such as object detection and semantic segmentation.