OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Processing of Very Large Graphs in a Small Cluster
Venue: arXiv cs.DC 2016
Year: 2016

Inspired by the success of Google's Pregel, many systems have been developed recently for iterative computation over big graphs. These systems provide a user-friendly vertex-centric programming interface, where a programmer only needs to specify the behavior of one generic vertex when developing a parallel graph algorithm. However, most existing systems require the input graph to reside in memories of the machines in a cluster, and the few out-of-core systems suffer from problems such as poor efficiency for sparse computation workload, high demand on network bandwidth, and expensive cost incurred by external-memory join and group-by. In this paper, we introduce the GraphD system for a user to process very large graphs with ordinary computing resources. GraphD fully overlaps computation with communication, by streaming edges and messages on local disks, while transmitting messages in parallel. For a broad class of Pregel algorithms where message combiner is applicable, GraphD eliminates the need of any expensive external-memory join or group-by. These key techniques allow GraphD to achieve comparable performance to in-memory Pregel-like systems without keeping edges and messages in memories. We prove that to process a graph G=(V, E) with n machines using GraphD, each machine only requires O(|V|/n) memory space, allowing GraphD to scale to very large graphs with a small cluster. Extensive experiments show that GraphD beats existing out-of-core systems by orders of magnitude, and achieves comparable performance to in-memory systems running with enough memories.
Reading Car License Plates Using Deep Convolutional Neural Networks and LSTMs
Venue: arXiv cs.CV 2016
Year: 2016

In this work, we tackle the problem of car license plate detection and recognition in natural scene images. Inspired by the success of deep neural networks (DNNs) in various vision applications, here we leverage DNNs to learn high-level features in a cascade framework, which lead to improved performance on both detection and recognition. Firstly, we train a $37$-class convolutional neural network (CNN) to detect all characters in an image, which results in a high recall, compared with conventional approaches such as training a binary text/non-text classifier. False positives are then eliminated by the second plate/non-plate CNN classifier. Bounding box refinement is then carried out based on the edge information of the license plates, in order to improve the intersection-over-union (IoU) ratio. The proposed cascade framework extracts license plates effectively with both high recall and precision. Last, we propose to recognize the license characters as a {sequence labelling} problem. A recurrent neural network (RNN) with long short-term memory (LSTM) is trained to recognize the sequential features extracted from the whole license plate via CNNs. The main advantage of this approach is that it is segmentation free. By exploring context information and avoiding errors caused by segmentation, the RNN method performs better than a baseline method of combining segmentation and deep CNN classification; and achieves state-of-the-art recognition accuracy.
Proving Craig and Lyndon Interpolation Using Labelled Sequent Calculi
Venue: arXiv cs.LO 2016
Year: 2016

We have recently presented a general method of proving the fundamental logical properties of Craig and Lyndon Interpolation (IPs) by induction on derivations in a wide class of internal sequent calculi, including sequents, hypersequents, and nested sequents. Here we adapt the method to a more general external formalism of labelled sequents and provide sufficient criteria on the Kripke-frame characterization of a logic that guarantee the IPs. In particular, we show that classes of frames definable by quantifier-free Horn formulas correspond to logics with the IPs. These criteria capture the modal cube and the infinite family of transitive Geach logics.
Basker: A Threaded Sparse LU Factorization Utilizing Hierarchical Parallelism and Data Layouts
Venue: arXiv cs.DC 2016
Year: 2016

Scalable sparse LU factorization is critical for efficient numerical simulation of circuits and electrical power grids. In this work, we present a new scalable sparse direct solver called Basker. Basker introduces a new algorithm to parallelize the Gilbert-Peierls algorithm for sparse LU factorization. As architectures evolve, there exists a need for algorithms that are hierarchical in nature to match the hierarchy in thread teams, individual threads, and vector level parallelism. Basker is designed to map well to this hierarchy in architectures. There is also a need for data layouts to match multiple levels of hierarchy in memory. Basker uses a two-dimensional hierarchical structure of sparse matrices that maps to the hierarchy in the memory architectures and to the hierarchy in parallelism. We present performance evaluations of Basker on the Intel SandyBridge and Xeon Phi platforms using circuit and power grid matrices taken from the University of Florida sparse matrix collection and from Xyce circuit simulations. Basker achieves a geometric mean speedup of 5.91x on CPU (16 cores) and 7.4x on Xeon Phi (32 cores) relative to KLU. Basker outperforms Intel MKL Pardiso (PMKL) by as much as 53x on CPU (16 cores) and 13.3x on Xeon Phi (32 cores) for low fill-in circuit matrices. Furthermore, Basker provides 5.4x speedup on a challenging matrix sequence taken from an actual Xyce simulation.
Folding Flat Crease Patterns with Thick Materials
Venue: arXiv cs.CG 2016
Year: 2016

Modeling folding surfaces with nonzero thickness is of practical interest for mechanical engineering. There are many existing approaches that account for material thickness in folding applications. We propose a new systematic and broadly applicable algorithm to transform certain flat-foldable crease patterns into new crease patterns with similar folded structure but with a facet-separated folded state. We provide conditions on input crease patterns for the algorithm to produce a thickened crease pattern avoiding local self intersection, and provide bounds for the maximum thickness that the algorithm can produce for a given input. We demonstrate these results in parameterized numerical simulations and physical models.
A New Pivot Selection Algorithm for Symmetric Indefinite Factorization Arising in Quadratic Programming with Block Constraint Matrices
Venue: arXiv cs.NA 2016
Year: 2016

Quadratic programmingis a class of constrained optimization problem with quadratic objective functions and linear constraints. It has applications in many areas and is also used to solve nonlinear optimization problems. This article focuses on the equality constrained quadratic programs whose constraint matrices are block diagonal. Using the direct solution method, we propose a new pivot selection algorithm for the factorization of the Karush-Kuhn-Tucker(KKT) matrix for this problem that maintains the sparsity and stability of the problem. Our experiments show that our pivot selection algorithm appears to produce no fill-ins in the factorizationof such matrices. In addition, we compare our method with MA57 and find that the factors produced by our algorithm are sparser.
A Note on Antenna Selection in Gaussian MIMO Channels: Capacity Guarantees and Bounds
Venue: arXiv cs.IT 2016
Year: 2016

We consider the problem of selecting $k_t \times k_r$ antennas from a Gaussian MIMO channel with $n_t \times n_r$ antennas, where $k_t \leq n_t$ and $k_r \leq n_r$. We prove the following two results that hold universally, in the sense that they do not depend on the channel coefficients: (i) The capacity of the best $k_t \times k_r$ subchannel is always lower bounded by a fraction $\frac{k_t k_r}{n_t n_r}$ of the full capacity (with $n_t \times n_r$ antennas). This bound is tight as the channel coefficients diminish in magnitude. (ii) There always exists a selection of $k_t \times k_r$ antennas (including the best) that achieves a fraction greater than $\frac{\min(k_t ,k_r)}{\min(n_t,n_r)}$ of the full capacity within an additive constant that is independent of the coefficients in the channel matrix. The key mathematical idea that allows us to derive these universal bounds is to directly relate the determinants of principle sub-matrices of a Hermitian matrix to the determinant of the entire matrix.
Executing Arbitrary Code in the Context of the Smartcard System Service
Venue: arXiv cs.CR 2016
Year: 2016

This report summarizes our findings regarding a severe weakness in implementations of the Open Mobile API deployed on several Android devices. The vulnerability allows arbitrary code coming from a specially crafted Android application package (APK) to be injected into and executed by the smartcard system service component (the middleware component of the Open Mobile API implementation). This can be exploited to gain elevated capabilities, such as privileges protected by signature- and system-level permissions assigned to this service. The affected source code seems to originate from the SEEK-for-Android open-source project and was adopted by various vendor-specific implementations of the Open Mobile API, including the one that is used on the Nexus 6 (as of Android version 5.1).
Regression Testing of Virtual Prototypes Using Symbolic Execution
Venue: arXiv cs.SE 2016
Year: 2016

Recently virtual platforms and virtual prototyping techniques have been widely applied for accelerating software development in electronics companies. It has been proved that these techniques can greatly shorten time-to-market and improve product quality. One challenge is how to test and validate a virtual prototype. In this paper, we present how to conduct regression testing of virtual prototypes in different versions using symbolic execution. Suppose we have old and new versions of a virtual prototype, we first apply symbolic execution to the new version and collect all path constraints. Then the collected path constraints are used for guiding the symbolic execution of the old version. For each path explored, we compare the device states between two versions to check if they behave the same. We have applied this approach to a widely-used virtual prototype and detected numerous differences. The experimental results show that our approach is useful and efficient.
Speech vocoding for laboratory phonology
Venue: arXiv cs.CL 2016
Year: 2016

Using phonological speech vocoding, we propose a platform for exploring relations between phonology and speech processing, and in broader terms, for exploring relations between the abstract and physical structures of a speech signal. Our goal is to make a step towards bridging phonology and speech processing and to contribute to the program of Laboratory Phonology. We show three application examples for laboratory phonology: compositional phonological speech modelling, a comparison of phonological systems and an experimental phonological parametric text-to-speech (TTS) system. The featural representations of the following three phonological systems are considered in this work: (i) Government Phonology (GP), (ii) the Sound Pattern of English (SPE), and (iii) the extended SPE (eSPE). Comparing GP- and eSPE-based vocoded speech, we conclude that the latter achieves slightly better results than the former. However, GP - the most compact phonological speech representation - performs comparably to the systems with a higher number of phonological features. The parametric TTS based on phonological speech representation, and trained from an unlabelled audiobook in an unsupervised manner, achieves intelligibility of 85% of the state-of-the-art parametric speech synthesis. We envision that the presented approach paves the way for researchers in both fields to form meaningful hypotheses that are explicitly testable using the concepts developed and exemplified in this paper. On the one hand, laboratory phonologists might test the applied concepts of their theoretical models, and on the other hand, the speech processing community may utilize the concepts developed for the theoretical phonological models for improvements of the current state-of-the-art applications.
Learning Support Correlation Filters for Visual Tracking
Venue: arXiv cs.CV 2016
Year: 2016

Sampling and budgeting training examples are two essential factors in tracking algorithms based on support vector machines (SVMs) as a trade-off between accuracy and efficiency. Recently, the circulant matrix formed by dense sampling of translated image patches has been utilized in correlation filters for fast tracking. In this paper, we derive an equivalent formulation of a SVM model with circulant matrix expression and present an efficient alternating optimization method for visual tracking. We incorporate the discrete Fourier transform with the proposed alternating optimization process, and pose the tracking problem as an iterative learning of support correlation filters (SCFs) which find the global optimal solution with real-time performance. For a given circulant data matrix with n^2 samples of size n*n, the computational complexity of the proposed algorithm is O(n^2*logn) whereas that of the standard SVM-based approaches is at least O(n^4). In addition, we extend the SCF-based tracking algorithm with multi-channel features, kernel functions, and scale-adaptive approaches to further improve the tracking performance. Experimental results on a large benchmark dataset show that the proposed SCF-based algorithms perform favorably against the state-of-the-art tracking methods in terms of accuracy and speed.
Greedy Algorithms for Optimal Distribution Approximation
Venue: arXiv cs.IT 2016
Year: 2016

The approximation of a discrete probability distribution $\mathbf{t}$ by an $M$-type distribution $\mathbf{p}$ is considered. The approximation error is measured by the informational divergence $\mathbb{D}(\mathbf{t}\Vert\mathbf{p})$, which is an appropriate measure, e.g., in the context of data compression. Properties of the optimal approximation are derived and bounds on the approximation error are presented, which are asymptotically tight. It is shown that $M$-type approximations that minimize either $\mathbb{D}(\mathbf{t}\Vert\mathbf{p})$, or $\mathbb{D}(\mathbf{p}\Vert\mathbf{t})$, or the variational distance $\Vert\mathbf{p}-\mathbf{t}\Vert_1$ can all be found by using specific instances of the same general greedy algorithm.
Optimal Resource Allocation Over Time and Degree Classes for Maximizing Information Dissemination in Social Networks
Venue: arXiv cs.SI 2016
Year: 2016

We study the optimal control problem of allocating campaigning resources over the campaign duration and degree classes in a social network. Information diffusion is modeled as a Susceptible-Infected epidemic and direct recruitment of susceptible nodes to the infected (informed) class is used as a strategy to accelerate the spread of information. We formulate an optimal control problem for optimizing a net reward function, a linear combination of the reward due to information spread and cost due to application of controls. The time varying resource allocation and seeds for the epidemic are jointly optimized. A problem variation includes a fixed budget constraint. We prove the existence of a solution for the optimal control problem, provide conditions for uniqueness of the solution, and prove some structural results for the controls (e.g. controls are non-increasing functions of time). The solution technique uses Pontryagin's Maximum Principle and the forward-backward sweep algorithm (and its modifications) for numerical computations. Our formulations lead to large optimality systems with up to about 200 differential equations and allow us to study the effect of network topology (Erdos-Renyi/scale-free) on the controls. Results reveal that the allocation of campaigning resources to various degree classes depends not only on the network topology but also on system parameters such as cost/abundance of resources. The optimal strategies lead to significant gains over heuristic strategies for various model parameters. Our modeling approach assumes uncorrelated network, however, we find the approach useful for real networks as well. This work is useful in product advertising, political and crowdfunding campaigns in social networks.
Paraphrase Generation from Latent-Variable PCFGs for Semantic Parsing
Venue: arXiv cs.CL 2016
Year: 2016

One of the limitations of semantic parsing approaches to open-domain question answering is the lexicosyntactic gap between natural language questions and knowledge base entries -- there are many ways to ask a question, all with the same answer. In this paper we propose to bridge this gap by generating paraphrases of the input question with the goal that at least one of them will be correctly mapped to a knowledge-base query. We introduce a novel grammar model for paraphrase generation that does not require any sentence-aligned paraphrase corpus. Our key idea is to leverage the flexibility and scalability of latent-variable probabilistic context-free grammars to sample paraphrases. We do an extrinsic evaluation of our paraphrases by plugging them into a semantic parser for Freebase. Our evaluation experiments on the WebQuestions benchmark dataset show that the performance of the semantic parser significantly improves over strong baselines.
VOUTE-Virtual Overlays Using Tree Embeddings
Venue: arXiv cs.CR 2016
Year: 2016

Friend-to-friend (F2F) overlays, which restrict direct communication to mutually trusted parties, are a promising substrate for privacy-preserving communication due to their inherent membership-concealment and Sybil-resistance. Yet, existing F2F overlays suffer from a low performance, are vulnerable to denial-of-service attacks, or fail to provide anonymity. In particular, greedy embeddings allow highly efficient communication in arbitrary connectivity-restricted overlays but require communicating parties to reveal their identity. In this paper, we present a privacy-preserving routing scheme for greedy embeddings based on anonymous return addresses rather than identifying node coordinates. We prove that the presented algorithm are highly scalalbe, with regard to the complexity of both the routing and the stabilization protocols. Furthermore, we show that the return addresses provide plausible deniability for both sender and receiver. We further enhance the routing's resilience by using multiple embeddings and propose a method for efficient content addressing. Our simulation study on real-world data indicates that our approach is highly efficient and effectively mitigates failures as well as powerful denial-of-service attacks.
Codes with Unequal Locality
Venue: arXiv cs.IT 2016
Year: 2016

For a code $\code$, its $i$-th symbol is said to have locality $r$ if its value can be recovered by accessing some other $r$ symbols of $\code$. Locally repairable codes (LRCs) are the family of codes such that every symbol has locality $r$. In this paper, we focus on (linear) codes whose individual symbols can be partitioned into disjoint subsets such that the symbols in one subset have different locality than the symbols in other. We call such codes as "codes with unequal locality". For codes with "unequal information locality", we compute a tight upper bound on the minimum distance as a function of number of information symbols of each locality. We demonstrate that the construction of Pyramid codes can be adapted to design codes with unequal information locality that achieve the minimum distance bound. This result generalizes the classical result of Gopalan et al. for codes with unequal locality. Next, we consider codes with "unequal all symbol locality", and establish an upper bound on the minimum distance as a function of number of symbols of each locality. We show that the construction based on rank-metric codes by Silberstein et al. can be adapted to obtain codes with unequal all symbol locality that achieve the minimum distance bound. Finally, we introduce the concept of "locality requirement" on a code, which can be viewed as a recoverability requirement on symbols. Information locality requirement on a code essentially specifies the minimum number of information symbols of different localities that must be present in the code. We present a greedy algorithm that assigns localities to information symbols so as to maximize the minimum distance among all codes that satisfy a given locality requirement.
Universal Collaboration Strategies for Signal Detection: A Sparse Learning Approach
Venue: arXiv cs.LG 2016
Year: 2016

This paper considers the problem of high dimensional signal detection in a large distributed network whose nodes can collaborate with their one-hop neighboring nodes (spatial collaboration). We assume that only a small subset of nodes communicate with the Fusion Center (FC). We design optimal collaboration strategies which are universal for a class of deterministic signals. By establishing the equivalence between the collaboration strategy design problem and sparse PCA, we solve the problem efficiently and evaluate the impact of collaboration on detection performance.
Intelligent Management and Efficient Operation of Big Data
Venue: arXiv cs.NI 2016
Year: 2016

This chapter details how Big Data can be used and implemented in networking and computing infrastructures. Specifically, it addresses three main aspects: the timely extraction of relevant knowledge from heterogeneous, and very often unstructured large data sources, the enhancement on the performance of processing and networking (cloud) infrastructures that are the most important foundational pillars of Big Data applications or services, and novel ways to efficiently manage network infrastructures with high-level composed policies for supporting the transmission of large amounts of data with distinct requisites (video vs. non-video). A case study involving an intelligent management solution to route data traffic with diverse requirements in a wide area Internet Exchange Point is presented, discussed in the context of Big Data, and evaluated.
Security and Privacy Issues of Big Data
Venue: arXiv cs.CR 2016
Year: 2016

This chapter revises the most important aspects in how computing infrastructures should be configured and intelligently managed to fulfill the most notably security aspects required by Big Data applications. One of them is privacy. It is a pertinent aspect to be addressed because users share more and more personal data and content through their devices and computers to social networks and public clouds. So, a secure framework to social networks is a very hot topic research. This last topic is addressed in one of the two sections of the current chapter with case studies. In addition, the traditional mechanisms to support security such as firewalls and demilitarized zones are not suitable to be applied in computing systems to support Big Data. SDN is an emergent management solution that could become a convenient mechanism to implement security in Big Data systems, as we show through a second case study at the end of the chapter. This also discusses current relevant work and identifies open issues.