OpenRaiser/Intern-Atlas huggingface dataset:
Leveraging Friendship Networks for Dynamic Link Prediction in Social Interaction Networks
Venue: arXiv cs.SI 2018
Year: 2018

On-line social networks (OSNs) often contain many different types of relationships between users. When studying the structure of OSNs such as Facebook, two of the most commonly studied networks are friendship and interaction networks. The link prediction problem in friendship networks has been heavily studied. There has also been prior work on link prediction in interaction networks, independent of friendship networks. In this paper, we study the predictive power of combining friendship and interaction networks. We hypothesize that, by leveraging friendship networks, we can improve the accuracy of link prediction in interaction networks. We augment several interaction link prediction algorithms to incorporate friendships and predicted friendships. From experiments on Facebook data, we find that incorporating friendships into interaction link prediction algorithms results in higher accuracy, but incorporating predicted friendships does not when compared to incorporating current friendships.
On capacities of the two-user union channel with complete feedback
Venue: arXiv cs.IT 2018
Year: 2018

The exact values of the optimal symmetric rate point in the Cover--Leung capacity region of the two-user union channel with complete feedback were determined by Willems when the size of the input alphabet is 2, and by Vinck, Hoeks and Post when the size is at least 6. We complete this line of research when the size of the input alphabet is 3, 4 or 5. The proof hinges on the technical lemma that concerns the maximal joint entropy of two independent random variables in terms of their probability of equality. For the zero-error capacity region, using superposition coding, we provide a practical near-optimal communication scheme which improves all the previous explicit constructions.
Gesture based Human-Swarm Interactions for Formation Control using interpreters
Venue: arXiv cs.RO 2018
Year: 2018

We propose a novel Human-Swarm Interaction (HSI) framework which enables the user to control a swarm shape and formation. The user commands the swarm utilizing just arm gestures and motions which are recorded by an off-the-shelf wearable armband. We propose a novel interpreter system, which acts as an intermediary between the user and the swarm to simplify the user's role in the interaction. The interpreter takes in a high level input drawn using gestures by the user, and translates it into low level swarm control commands. This interpreter employs machine learning, Kalman filtering and optimal control techniques to translate the user input into swarm control parameters. A notion of Human Interpretable dynamics is introduced, which is used by the interpreter for planning as well as to provide feedback to the user. The dynamics of the swarm are controlled using a novel decentralized formation controller based on distributed linear iterations and dynamic average consensus. The framework is demonstrated theoretically as well as experimentally in a 2D environment, with a human controlling a swarm of simulated robots in real time.
goSLP: Globally Optimized Superword Level Parallelism Framework
Venue: arXiv cs.PL 2018
Year: 2018

Modern microprocessors are equipped with single instruction multiple data (SIMD) or vector instruction sets which allow compilers to exploit superword level parallelism (SLP), a type of fine-grained parallelism. Current SLP auto-vectorization techniques use heuristics to discover vectorization opportunities in high-level language code. These heuristics are fragile, local and typically only present one vectorization strategy that is either accepted or rejected by a cost model. We present goSLP, a novel SLP auto-vectorization framework which solves the statement packing problem in a pairwise optimal manner. Using an integer linear programming (ILP) solver, goSLP searches the entire space of statement packing opportunities for a whole function at a time, while limiting total compilation time to a few minutes. Furthermore, goSLP optimally solves the vector permutation selection problem using dynamic programming. We implemented goSLP in the LLVM compiler infrastructure, achieving a geometric mean speedup of 7.58% on SPEC2017fp, 2.42% on SPEC2006fp and 4.07% on NAS benchmarks compared to LLVM's existing SLP auto-vectorizer.
Data-driven Summarization of Scientific Articles
Venue: arXiv cs.CL 2018
Year: 2018

Data-driven approaches to sequence-to-sequence modelling have been successfully applied to short text summarization of news articles. Such models are typically trained on input-summary pairs consisting of only a single or a few sentences, partially due to limited availability of multi-sentence training data. Here, we propose to use scientific articles as a new milestone for text summarization: large-scale training data come almost for free with two types of high-quality summaries at different levels - the title and the abstract. We generate two novel multi-sentence summarization datasets from scientific articles and test the suitability of a wide range of existing extractive and abstractive neural network-based summarization approaches. Our analysis demonstrates that scientific papers are suitable for data-driven text summarization. Our results could serve as valuable benchmarks for scaling sequence-to-sequence models to very long sequences.
Accurate 3-D Reconstruction with RGB-D Cameras using Depth Map Fusion and Pose Refinement
Venue: arXiv cs.CV 2018
Year: 2018

Depth map fusion is an essential part in both stereo and RGB-D based 3-D reconstruction pipelines. Whether produced with a passive stereo reconstruction or using an active depth sensor, such as Microsoft Kinect, the depth maps have noise and may have poor initial registration. In this paper, we introduce a method which is capable of handling outliers, and especially, even significant registration errors. The proposed method first fuses a sequence of depth maps into a single non-redundant point cloud so that the redundant points are merged together by giving more weight to more certain measurements. Then, the original depth maps are re-registered to the fused point cloud to refine the original camera extrinsic parameters. The fusion is then performed again with the refined extrinsic parameters. This procedure is repeated until the result is satisfying or no significant changes happen between iterations. The method is robust to outliers and erroneous depth measurements as well as even significant depth map registration errors due to inaccurate initial camera poses.
Developing Theoretical Foundations for Runtime Enforcement
Venue: arXiv cs.LO 2018
Year: 2018

The ubiquitous reliance on software systems increases the need for ensuring that systems behave correctly and are well protected against security risks. Runtime enforcement is a dynamic analysis technique that utilizes software monitors to check the runtime behaviour of a software system with respect to a correctness specification. Whenever the runtime behaviour of the monitored system is about to deviate from the specification (either due to a programming bug or a security hijack attack), the monitors apply enforcement techniques to prevent this deviation. Current Runtime Enforcement techniques require that the correctness specification defines the behaviour of the enforcement monitor itself. This burdens the specifier with not only having to define property that needs to be enforced, but also with having to specify how this should be enforced at runtime; we thus relieve the specifier from this burden by resorting to a highly expressive logic. Using a logic we allow the specifier to define the correctness specification as a logic formula from which we can automatically synthesise the appropriate enforcement monitor. Highly expressive logics can, however, permit for defining a wide variety of formulae, some of which cannot actually be enforced correctly at runtime. We thus study the enforceability of Hennessy Milner Logic with Recursion for which we identify a subset that allows for defining enforceable formulae. This allows us to define a synthesis function that translates enforceable formulae into enforcement monitors. As our monitors are meant to ensure the correct behaviour of the monitored system, it is imperative that they work correctly themselves. We thus study formal definitions that allow us to ensure that our enforcement monitors behave correctly.
A new class of convolutional codes and its use in the McEliece Cryptosystem
Venue: arXiv cs.IT 2018
Year: 2018

In this paper we present a new class of convolutional codes that admits an efficient al- gebraic decoding algorithm. We study some of its properties and show that it can decode interesting sequences of errors patterns. The second part of the paper is devoted to in- vestigate its use in a variant of the McEliece cryptosystem. In contrast to the classical McEliece cryptosystems, where block codes are used, we propose the use of a convolu- tional encoder to be part of the public key. In this setting the message is a sequence of messages instead of a single block message and the errors are added randomly throughout the sequence. We conclude the paper providing some comments on the security. Although there is no obvious security threats to this new scheme, we point out several possible adaptations of existing attacks and discuss the difficulties of such attacks to succeed in breaking this cryptosystem.
Tighter Connections Between Formula-SAT and Shaving Logs
Venue: arXiv cs.CC 2018
Year: 2018

A noticeable fraction of Algorithms papers in the last few decades improve the running time of well-known algorithms for fundamental problems by logarithmic factors. For example, the $O(n^2)$ dynamic programming solution to the Longest Common Subsequence problem (LCS) was improved to $O(n^2/\log^2 n)$ in several ways and using a variety of ingenious tricks. This line of research, also known as "the art of shaving log factors", lacks a tool for proving negative results. Specifically, how can we show that it is unlikely that LCS can be solved in time $O(n^2/\log^3 n)$? Perhaps the only approach for such results was suggested in a recent paper of Abboud, Hansen, Vassilevska W. and Williams (STOC'16). The authors blame the hardness of shaving logs on the hardness of solving satisfiability on Boolean formulas (Formula-SAT) faster than exhaustive search. They show that an $O(n^2/\log^{1000} n)$ algorithm for LCS would imply a major advance in circuit lower bounds. Whether this approach can lead to tighter barriers was unclear. In this paper, we push this approach to its limit and, in particular, prove that a well-known barrier from complexity theory stands in the way for shaving five additional log factors for fundamental combinatorial problems. For LCS, regular expression pattern matching, as well as the Fréchet distance problem from Computational Geometry, we show that an $O(n^2/\log^{7+\varepsilon} n)$ runtime would imply new Formula-SAT algorithms. Our main result is a reduction from SAT on formulas of size $s$ over $n$ variables to LCS on sequences of length $N=2^{n/2} \cdot s^{1+o(1)}$. Our reduction is essentially as efficient as possible, and it greatly improves the previously known reduction for LCS with $N=2^{n/2} \cdot s^c$, for some $c \geq 100$.
Optimal User Scheduling in Energy Harvesting Wireless Networks
Venue: arXiv cs.IT 2018
Year: 2018

We consider a wireless network where multiple energy harvesting transmitters communicate with the common receiver in a time sharing manner. In each slot, a transmitter can either harvest energy or send its data to the receiver. Given a time deadline, the goal is to maximize the sum-rate of transmitters under random energy arrivals with both perfect and imperfect channel state information (CSI) at the receiver. The original sumrate maximization (SRM) problem is a non-convex mixed integer non-linear program (MINLP). To obtain the optimal scheduling policy, we first reduce the original optimization problem to a convex MINLP and solve it using the generalized Benders decomposition algorithm. We observe that the SRM problem results in an unfair rate allocation among transmitters, i.e., the transmitter closer to the receiver achieves a higher rate than that by the transmitter farther from the receiver. Hence, to induce fairness among transmitters, we consider the minimumrate maximization (MRM) problem. For the bounded channel estimation error, we obtain a robust scheduling policy by solving the worst-case SRM and MRM problems. Finally, we compare the proposed policies with myopic policies studied in the literature and show that the former outperform the latter in terms of achievable rates.
Developing a machine learning framework for estimating soil moisture with VNIR hyperspectral data
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we investigate the potential of estimating the soil-moisture content based on VNIR hyperspectral data combined with LWIR data. Measurements from a multi-sensor field campaign represent the benchmark dataset which contains measured hyperspectral, LWIR, and soil-moisture data conducted on grassland site. We introduce a regression framework with three steps consisting of feature selection, preprocessing, and well-chosen regression models. The latter are mainly supervised machine learning models. An exception are the self-organizing maps which combine unsupervised and supervised learning. We analyze the impact of the distinct preprocessing methods on the regression results. Of all regression models, the extremely randomized trees model without preprocessing provides the best estimation performance. Our results reveal the potential of the respective regression framework combined with the VNIR hyperspectral data to estimate soil moisture measured under real-world conditions. In conclusion, the results of this paper provide a basis for further improvements in different research directions.
Sparse Power Factorization: Balancing peakiness and sample complexity
Venue: arXiv cs.IT 2018
Year: 2018

In many applications, one is faced with an inverse problem, where the known signal depends in a bilinear way on two unknown input vectors. Often at least one of the input vectors is assumed to be sparse, i.e., to have only few non-zero entries. Sparse Power Factorization (SPF), proposed by Lee, Wu, and Bresler, aims to tackle this problem. They have established recovery guarantees for a somewhat restrictive class of signals under the assumption that the measurements are random. We generalize these recovery guarantees to a significantly enlarged and more realistic signal class at the expense of a moderately increased number of measurements.
dockChain: A Solution for Electric Vehicles Charge Point Anxiety
Venue: arXiv cs.SY 2018
Year: 2018

This paper addresses Charge Point Anxiety surrounding electric vehicles (EVs), an issue preventing the mass adoption of this greener mode of transport. We discuss the design and implementation of a charge point adapter called \textit{dockChain} that will help mitigate Charge Point Anxiety. The key feature of the dockChain is that it allows multiple EVs to connect simultaneously to a single charge by connecting the adapters together in a chain resulting in additional charging opportunities - without the need for infrastructural changes. We describe the operation of the network of adapters, the hardware components and charging policies for the adapter. A distributed algorithm that can detect the length of the chain in a dockChain network is also presented.
On the construction of sparse matrices from expander graphs
Venue: arXiv cs.IT 2018
Year: 2018

We revisit the asymptotic analysis of probabilistic construction of adjacency matrices of expander graphs proposed in [4]. With better bounds we derived a new reduced sample complexity for the number of nonzeros per column of these matrices, precisely $d = \mathcal{O}\left(\log_s(N/s) \right)$; as opposed to the standard $d = \mathcal{O}\left(\log(N/s) \right)$. This gives insights into why using small $d$ performed well in numerical experiments involving such matrices. Furthermore, we derive quantitative sampling theorems for our constructions which show our construction outperforming the existing state-of-the-art. We also used our results to compare performance of sparse recovery algorithms where these matrices are used for linear sketching.
Unified approaches based effective capacity analysis over composite $α-η-μ$/gamma fading channels
Venue: arXiv cs.IT 2018
Year: 2018

This letter analyses the effective capacity of communications system using unified models. In order to obtain a simple closed-form mathematically tractable expression, two different unified approximate models have been used. The mixture gamma (MG) distribution which is highly accurate approximation approach has been firstly employed to represent the signal-to-noise-ratio (SNR) of fading channel. In the second approach, the mixture of Gaussian (MoG) distribution which is another unified representation approach has been utilised. A comparison between the simulated and numerical results using both distributions over composite $α-η-μ$/gamma fading channels has been provided.
How Diverse Users and Activities Trigger Connective Action via Social Media: Lessons from the Twitter Hashtag Campaign #ILookLikeAnEngineer
Venue: arXiv cs.SI 2018
Year: 2018

We present a study that examines how a social media activism campaign aimed at improving gender diversity within engineering gained and maintained momentum in its early period. We examined over 50,000 Tweets posted over the first ~75 days of the #ILookLikeAnEngineer campaign and found that diverse participation - of types of users - increased activity at crucial moments. We categorize these triggers into four types: 1) Event-Driven: Alignment of the campaign with offline events related to the issue (Diversity SFO, Disrupt, etc.); 2) Media-Driven: News coverage of the events in the media (TechCrunch, CNN, BBC, etc.); 3) Industry-Driven: Web participation in the campaign by large organizations (Microsoft, Tesla, GE, Cisco, etc.); and 4) Personality-Driven: Alignment of the events with popular and/or known personalities (e.g. Isis Anchalee; Michelle Sun; Ada Lovelace.) This study illustrates how one mechanism - triggering - supports connective action in social media campaign.
Ambient Backscatter Systems: Exact Average Bit Error Rate under Fading Channels
Venue: arXiv cs.IT 2018
Year: 2018

The success of Internet-of-Things (IoT) paradigm relies on, among other things, developing energy-efficient communication techniques that can enable information exchange among billions of battery-operated IoT devices. With its technological capability of simultaneous information and energy transfer, ambient backscatter is quickly emerging as an appealing solution for this communication paradigm, especially for the links with low data rate requirement. In this paper, we study signal detection and characterize exact bit error rate for the ambient backscatter system. In particular, we formulate a binary hypothesis testing problem at the receiver and analyze system performance under three detection techniques: a) mean threshold (MT), b) maximum likelihood threshold (MLT), and c) approximate MLT. Motivated by the energy-constrained nature of IoT devices, we perform the above analyses for two receiver types: i) the ones that can accurately track channel state information (CSI), and ii) the ones that cannot. Two main features of the analysis that distinguish this work from the prior art are the characterization of the exact conditional density functions of the average received signal energy, and the characterization of exact average bit error rate (BER) for this setup. The key challenge lies in the handling of correlation between channel gains of two hypotheses for the derivation of joint probability distribution of magnitude squared channel gains that is needed for the BER analysis.
Robust Anomaly-Based Ship Proposals Detection from Pan-sharpened High-Resolution Satellite Image
Venue: arXiv cs.CV 2018
Year: 2018

Pre-screening of ship proposals is now employed by top ship detectors to avoid exhaustive search across image. In very high resolution (VHR) optical image, ships appeared as a cluster of abnormal bright pixels in open sea clutter (noise-like background). Anomaly-based detector utilizing Panchromatic (PAN) data has been widely used in many researches to detect ships, however, still facing two main drawbacks: 1) detection rate tend to be low particularly when a ship is low contrast and 2) these models require a high manual configuration to select a threshold value best separate ships from sea surface background. This paper aims at further investigation of anomaly-based model to solve those issues. First, pan-sharpened Multi Spectral (MS) data is incorporated together with PAN to enhance ship discrimination. Second, we propose an improved anomaly-based model combining both global intensity anomaly and local texture anomaly map. Regarding noise appeared due to the present of sea clutter and because of pan-sharpen process, texture abnormality suppression term based on quantization theory is introduced. Experimental results on VNREDSat-1 VHR optical satellite images suggest that the pan-sharpened near-infrared (P-NIR) band can improve discrimination of ships from surrounding waters. Compared to state-of-the-art anomaly-based detectors, our proposed anomaly-based model on the combination of PAN and P-NIR data cannot only achieved highest ship detection's recall rate (91.14% and 45.9% on high-contrast and low-contrast dataset respectively) but also robust to different automatic threshold selection techniques.
Processing Database Joins over a Shared-Nothing System of Multicore Machines
Venue: arXiv cs.DB 2018
Year: 2018

To process a large volume of data, modern data management systems use a collection of machines connected through a network. This paper looks into the feasibility of scaling up such a shared-nothing system while processing a compute- and communication-intensive workload---processing distributed joins. By exploiting multiple processing cores within the individual machines, we implement a system to process database joins that parallelizes computation within each node, pipelines the computation with communication, parallelizes the communication by allowing multiple simultaneous data transfers (send/receive), and removes synchronization barriers (a scalability bottleneck in a distributed data processing system). Our experimental results show that using only four threads per node the framework achieves a 3.5x gains in intra-node performance while compared with a single-threaded counterpart. Moreover, with the join processing workload the cluster-wide performance (and speedup) is observed to be dictated by the intra-node computational loads; this property brings a near-linear speedup with increasing nodes in the system, a feature much desired in modern large-scale data processing system.