OpenRaiser/Intern-Atlas huggingface dataset:
Mathematical models and search algorithms for the capacitated $p$-center problem
Venue: arXiv cs.DS 2018
Year: 2018

The capacitated p-center problem requires to select p facilities from a set of candidates to service a number of customers, subject to facility capacity constraints, with the aim of minimizing the maximum distance between a customer and its associated facility. The problem is well known in the field of facility location, because of the many applications that it can model. In this paper, we solve it by means of search algorithms that iteratively seek the optimal distance by solving tailored subproblems. We present different mathematical formulations for the subproblems and improve them by means of several valid inequalities, including an effective one based on a 0-1 disjunction and the solution of subset sum problems. We also develop an alternative search strategy that finds a balance between the traditional sequential search and binary search. This strategy limits the number of feasible subproblems to be solved and, at the same time, avoids large overestimates of the solution value, which are detrimental for the search. We evaluate the proposed techniques by means of extensive computational experiments on benchmark instances from the literature and new larger test sets. All instances from the literature with up to 402 vertices and integer distances are solved to proven optimality, including 13 open cases, and feasible solutions are found in 10 minutes for instances with up to 3038 vertices.
Lazy Receding Horizon A* for Efficient Path Planning in Graphs with Expensive-to-Evaluate Edges
Venue: arXiv cs.RO 2018
Year: 2018

Motion-planning problems, such as manipulation in cluttered environments, often require a collision-free shortest path to be computed quickly given a roadmap graph. Typically, the computational cost of evaluating whether an edge of the roadmap graph is collision-free dominates the running time of search algorithms. Algorithms such as Lazy Weighted A* (LWA*) and LazySP have been proposed to reduce the number of edge evaluations by employing a lazy lookahead (one-step lookahead and infinite-step lookahead, respectively). However, this comes at the expense of additional graph operations: the larger the lookahead, the more the graph operations that are typically required. We propose Lazy Receding-Horizon A* (LRA*) to minimize the total planning time by balancing edge evaluations and graph operations. Endowed with a lazy lookahead, LRA* represents a family of lazy shortest-path graph-search algorithms that generalizes LWA* and LazySP. We analyze the theoretic properties of LRA* and demonstrate empirically that, in many cases, to minimize the total planning time, the algorithm requires an intermediate lazy lookahead. Namely, using an intermediate lazy lookahead, our algorithm outperforms both LWA* and LazySP. These experiments span simulated random worlds in $\mathbb{R}^2$ and $\mathbb{R}^4$, and manipulation problems using a 7-DOF manipulator.
Caveat Emptor, Computational Social Science: Large-Scale Missing Data in a Widely-Published Reddit Corpus
Venue: arXiv cs.SI 2018
Year: 2018

As researchers use computational methods to study complex social behaviors at scale, the validity of this computational social science depends on the integrity of the data. On July 2, 2015, Jason Baumgartner published a dataset advertised to include ``every publicly available Reddit comment'' which was quickly shared on Bittorrent and the Internet Archive. This data quickly became the basis of many academic papers on topics including machine learning, social behavior, politics, breaking news, and hate speech. We have discovered substantial gaps and limitations in this dataset which may contribute to bias in the findings of that research. In this paper, we document the dataset, substantial missing observations in the dataset, and the risks to research validity from those gaps. In summary, we identify strong risks to research that considers user histories or network analysis, moderate risks to research that compares counts of participation, and lesser risk to machine learning research that avoids making representative claims about behavior and participation on Reddit.
AURORA: Auditing PageRank on Large Graphs
Venue: arXiv cs.SI 2018
Year: 2018

Ranking on large-scale graphs plays a fundamental role in many high-impact application domains, ranging from information retrieval, recommender systems, sports team management, biology to neuroscience and many more. PageRank, together with many of its random walk based variants, has become one of the most well-known and widely used algorithms, due to its mathematical elegance and the superior performance across a variety of application domains. Important as it might be, state-of-the-art lacks an intuitive way to explain the ranking results by PageRank (or its variants), e.g., why it thinks the returned top-k webpages are most important ones in the entire graph; why it gives a higher rank to actor John than actor Smith in terms of their relevance w.r.t. a particular movie? In order to answer these questions, this paper proposes a paradigm shift for PageRank, from identifying which nodes are most important to understanding why the ranking algorithm gives a particular ranking result. We formally define the PageRank auditing problem, whose central idea is to identify a set of key graph elements (e.g., edges, nodes, subgraphs) with the highest influence on the ranking results. We formulate it as an optimization problem and propose a family of effective and scalable algorithms (AURORA) to solve it. Our algorithms measure the influence of graph elements and incrementally select influential elements w.r.t. their gradients over the ranking results. We perform extensive empirical evaluations on real-world datasets, which demonstrate that the proposed methods (AURORA) provide intuitive explanations with a linear scalability.
Network Coding for Real-time Wireless Communication for Automation
Venue: arXiv cs.IT 2018
Year: 2018

Real-time applications require latencies on the order of a millisecond with very high reliabilities, paralleling the requirements for high-performance industrial control. Current wireless technologies like WiFi, Bluetooth, LTE, etc. are unable to meet these stringent latency and reliability requirements, forcing the use of wired systems. This paper introduces a wireless communication protocol based on network coding that in conjunction with cooperative communication techniques builds the necessary diversity to achieve the target reliability. The proposed protocol is analyzed using a communication theoretic delay-limited-capacity framework and compared to proposed protocols without network coding. The results show that for larger network sizes or payloads employing network coding lowers the minimum SNR required to achieve the target reliability. For a scenario inspired by an industrial printing application with $30$ nodes in the control loop, aggregate throughput of $4.8$ Mb/s, $20$MHz of bandwidth and cycle time under $2$ ms, the protocol can robustly achieve a system probability of error better than $10^{-9}$ with a nominal SNR less than $2$ dB under ideal channel conditions.
How to evaluate sentiment classifiers for Twitter time-ordered data?
Venue: arXiv cs.CL 2018
Year: 2018

Social media are becoming an increasingly important source of information about the public mood regarding issues such as elections, Brexit, stock market, etc. In this paper we focus on sentiment classification of Twitter data. Construction of sentiment classifiers is a standard text mining task, but here we address the question of how to properly evaluate them as there is no settled way to do so. Sentiment classes are ordered and unbalanced, and Twitter produces a stream of time-ordered data. The problem we address concerns the procedures used to obtain reliable estimates of performance measures, and whether the temporal ordering of the training and test data matters. We collected a large set of 1.5 million tweets in 13 European languages. We created 138 sentiment models and out-of-sample datasets, which are used as a gold standard for evaluations. The corresponding 138 in-sample datasets are used to empirically compare six different estimation procedures: three variants of cross-validation, and three variants of sequential validation (where test set always follows the training set). We find no significant difference between the best cross-validation and sequential validation. However, we observe that all cross-validation variants tend to overestimate the performance, while the sequential methods tend to underestimate it. Standard cross-validation with random selection of examples is significantly worse than the blocked cross-validation, and should not be used to evaluate classifiers in time-ordered data scenarios.
A unified approach to fixed-wing aircraft path following guidance and control
Venue: arXiv cs.SY 2018
Year: 2018

This paper addresses the path following control problem for scale-model fixed-wing aircraft. Kinematic guidance and dynamic control laws are developed within a single coherent framework that exploits a simple generic model of aerodynamics forces acting on the aircraft and applies to almost all regular 3D paths. The proposed control solutions are derived on the basis of theoretical stability and convergence analyses. They are complemented by addressing several practical issues, and validated via realistic hardware-in-the-loop simulations.
Identifying KDM Model of JSP Pages
Venue: arXiv cs.SE 2018
Year: 2018

In this report, we propose our approach that identifies a KDM model of JSP pages. Our approach is based on two main steps. The first one aims to reduce the problem space by translating JSP pages into Java Servlets where we can use existing tools to identify a KDM model. The second step aims to complete the resulting KDM model by identifying dependencies of JSP tags that are not codified by the translation step.
What Should You Know Before Developing a Service Identification Approach
Venue: arXiv cs.SE 2018
Year: 2018

In this paper, we answer a set of research questions that are required to develop service identification approach based on the analysis of object- oriented software. Such research questions are: (1) what is a service, (2) how are services different from software components, (3) what are types of services, (4) what are existing service identification approaches that consider service types into account, and (5) how to identify services based on the object-oriented source code with respect to their types. Our methodology is based on performing a literature review to identify the answers of these research questions. Also, we propose a taxonomy of service types.
On the Security of Some Compact Keys for McEliece Scheme
Venue: arXiv cs.IT 2018
Year: 2018

In this paper we study the security of the key of compact McEliece schemes based on alternant/Goppa codes with a non-trivial permutation group, in particular quasi-cyclic alternant codes. We show that it is possible to reduce the key-recovery problem on the original quasi-cyclic code to the same problem on a smaller code derived from the public key. This result is obtained thanks to the invariant code operation which gives the subcode whose elements are fixed by a permutation in Perm(C). The fundamental advantage is that the invariant subcode of an alternant code is an alternant code. This approach improves the technique of Faugere, Otmani, Tillich, Perret and Portzamparc which uses folded codes of alternant codes obtained by using supports globally stable by an affine map. We use a simpler approach with a unified view on quasi-cyclic alternant codes and we treat the case of automorphisms arising from a non affine homography. In addition, we provide an efficient algorithm to recover the full structure of the alternant code from the structure of the invariant code.
Efficient Realization of Givens Rotation through Algorithm-Architecture Co-design for Acceleration of QR Factorization
Venue: arXiv cs.DC 2018
Year: 2018

We present efficient realization of Generalized Givens Rotation (GGR) based QR factorization that achieves 3-100x better performance in terms of Gflops/watt over state-of-the-art realizations on multicore, and General Purpose Graphics Processing Units (GPGPUs). GGR is an improvement over classical Givens Rotation (GR) operation that can annihilate multiple elements of rows and columns of an input matrix simultaneously. GGR takes 33% lesser multiplications compared to GR. For custom implementation of GGR, we identify macro operations in GGR and realize them on a Reconfigurable Data-path (RDP) tightly coupled to pipeline of a Processing Element (PE). In PE, GGR attains speed-up of 1.1x over Modified Householder Transform (MHT) presented in the literature. For parallel realization of GGR, we use REDEFINE, a scalable massively parallel Coarse-grained Reconfigurable Architecture, and show that the speed-up attained is commensurate with the hardware resources in REDEFINE. GGR also outperforms General Matrix Multiplication (gemm) by 10% in-terms of Gflops/watt which is counter-intuitive.
Capturing the influence of geopolitical ties from Wikipedia with reduced Google matrix
Venue: arXiv cs.SI 2018
Year: 2018

Interactions between countries originate from diverse aspects such as geographic proximity, trade, socio-cultural habits, language, religions, etc. Geopolitics studies the influence of a country's geographic space on its political power and its relationships with other countries. This work reveals the potential of Wikipedia mining for geopolitical study. Actually, Wikipedia offers solid knowledge and strong correlations among countries by linking web pages together for different types of information (e.g. economical, historical, political, and many others). The major finding of this paper is to show that meaningful results on the influence of country ties can be extracted from the hyperlinked structure of Wikipedia. We leverage a novel stochastic matrix representation of Markov chains of complex directed networks called the reduced Google matrix theory. For a selected small size set of nodes, the reduced Google matrix concentrates direct and indirect links of the million-node sized Wikipedia network into a small Perron-Frobenius matrix keeping the PageRank probabilities of the global Wikipedia network. We perform a novel sensitivity analysis that leverages this reduced Google matrix to characterize the influence of relationships between countries from the global network. We apply this analysis to two chosen sets of countries (i.e. the set of 27 European Union countries and a set of 40 top worldwide countries). We show that with our sensitivity analysis we can exhibit easily very meaningful information on geopolitics from five different Wikipedia editions (English, Arabic, Russian, French and German).
Learning to Recognize Musical Genre from Audio
Venue: arXiv cs.SD 2018
Year: 2018

We here summarize our experience running a challenge with open data for musical genre recognition. Those notes motivate the task and the challenge design, show some statistics about the submissions, and present the results.
The Hsu-Harn-Mu-Zhang-Zhu group key establishment protocol is insecure
Venue: arXiv cs.CR 2018
Year: 2018

A significant security vulnerability in a recently published group key establishment protocol is described. This vulnerability allows a malicious insider to fraudulently establish a group key with an innocent victim, with the key chosen by the attacker. This shortcoming is sufficiently serious that the protocol should not be used.
An Analysis of Home IoT Network Traffic and Behaviour
Venue: arXiv cs.NI 2018
Year: 2018

Internet-connected devices are increasingly present in our homes, and privacy breaches, data thefts, and security threats are becoming commonplace. In order to avoid these, we must first understand the behaviour of these devices. In this work, we analyse network traces from a testbed of common IoT devices, and describe general methods for fingerprinting their behavior. We then use the information and insights derived from this data to assess where privacy and security risks manifest themselves, as well as how device behavior affects bandwidth. We demonstrate simple measures that circumvent attempts at securing devices and protecting privacy.
Approximate Query Matching for Image Retrieval
Venue: arXiv cs.CV 2018
Year: 2018

Traditional image recognition involves identifying the key object in a portrait-type image with a single object focus (ILSVRC, AlexNet, and VGG). More recent approaches consider dense image recognition - segmenting an image with appropriate bounding boxes and performing image recognition within these bounding boxes (Semantic segmentation). The Visual Genome dataset [5] is an attempt to bridge these various approaches to a cohesive dataset for each subtask - bounding box generation, image recognition, captioning, and a new operation: scene graph generation. Our focus is on using such scene graphs to perform graph search on image databases to holistically retrieve images based on a search criteria. We develop a method to store scene graphs and metadata in graph databases (using Neo4J) and to perform fast approximate retrieval of images based on a graph search query. We process more complex queries than single object search, e.g. "girl eating cake" retrieves images that contain the specified relation as well as variations.
SentEval: An Evaluation Toolkit for Universal Sentence Representations
Venue: arXiv cs.CL 2018
Year: 2018

We introduce SentEval, a toolkit for evaluating the quality of universal sentence representations. SentEval encompasses a variety of tasks, including binary and multi-class classification, natural language inference and sentence similarity. The set of tasks was selected based on what appears to be the community consensus regarding the appropriate evaluations for universal sentence representations. The toolkit comes with scripts to download and preprocess datasets, and an easy interface to evaluate sentence encoders. The aim is to provide a fairer, less cumbersome and more centralized way for evaluating sentence representations.
Subexponential-Time and FPT Algorithms for Embedded Flat Clustered Planarity
Venue: arXiv cs.DS 2018
Year: 2018

The C-Planarity problem asks for a drawing of a $\textit{clustered graph}$, i.e., a graph whose vertices belong to properly nested clusters, in which each cluster is represented by a simple closed region with no edge-edge crossings, no region-region crossings, and no unnecessary edge-region crossings. We study C-Planarity for $\textit{embedded flat clustered graphs}$, graphs with a fixed combinatorial embedding whose clusters partition the vertex set. Our main result is a subexponential-time algorithm to test C-Planarity for these graphs when their face size is bounded. Furthermore, we consider a variation of the notion of $\textit{embedded tree decomposition}$ in which, for each face, including the outer face, there is a bag that contains every vertex of the face. We show that C-Planarity is fixed-parameter tractable with the embedded-width of the underlying graph and the number of disconnected clusters as parameters.
On the Approximation of Constrained Linear Quadratic Regulator Problems and their Application to Model Predictive Control - Supplementary Notes
Venue: arXiv cs.SY 2018
Year: 2018

By parametrizing input and state trajectories with basis functions different approximations to the constrained linear quadratic regulator problem are obtained. These notes present and discuss technical results that are intended to supplement a corresponding journal article. The results can be applied in a model predictive control context.
Self-Supervised Monocular Image Depth Learning and Confidence Estimation
Venue: arXiv cs.CV 2018
Year: 2018

Convolutional Neural Networks (CNNs) need large amounts of data with ground truth annotation, which is a challenging problem that has limited the development and fast deployment of CNNs for many computer vision tasks. We propose a novel framework for depth estimation from monocular images with corresponding confidence in a self-supervised manner. A fully differential patch-based cost function is proposed by using the Zero-Mean Normalized Cross Correlation (ZNCC) that takes multi-scale patches as a matching strategy. This approach greatly increases the accuracy and robustness of the depth learning. In addition, the proposed patch-based cost function can provide a 0 to 1 confidence, which is then used to supervise the training of a parallel network for confidence map learning and estimation. Evaluation on KITTI dataset shows that our method outperforms the state-of-the-art results.
Micky: A Cheaper Alternative for Selecting Cloud Instances
Venue: arXiv cs.DC 2018
Year: 2018

Most cloud computing optimizers explore and improve one workload at a time. When optimizing many workloads, the single-optimizer approach can be prohibitively expensive. Accordingly, we examine "collective optimizer" that concurrently explore and improve a set of workloads significantly reducing the measurement costs. Our large-scale empirical study shows that there is often a single cloud configuration which is surprisingly near-optimal for most workloads. Consequently, we create a collective-optimizer, MICKY, that reformulates the task of finding the near-optimal cloud configuration as a multi-armed bandit problem. MICKY efficiently balances exploration (of new cloud configurations) and exploitation (of known good cloud configuration). Our experiments show that MICKY can achieve on average 8.6 times reduction in measurement cost as compared to the state-of-the-art method while finding near-optimal solutions. Hence we propose MICKY as the basis of a practical collective optimization method for finding good cloud configurations (based on various constraints such as budget and tolerance to near-optimal configurations).
Information Security in Health Care Centre Using Cryptography and Steganography
Venue: arXiv cs.CR 2018
Year: 2018

As the volume of medicinal information stored electronically increase, so do the need to enhance how it is secured. The inaccessibility to patient record at the ideal time can prompt death toll and also well degrade the level of health care services rendered by the medicinal professionals. Criminal assaults in social insurance have expanded by 125% since 2010 and are now the leading cause of medical data breaches. This study therefore presents the combination of 3DES and LSB to improve security measure applied on medical data. Java programming language was used to develop a simulation program for the experiment. The result shows medical data can be stored, shared, and managed in a reliable and secure manner using the combined model.
A nonlinear transform based analog video transmission framework
Venue: arXiv cs.MM 2018
Year: 2018

Soft-cast, a cross-layer design for wireless video transmission, is proposed to solve the drawbacks of digital video transmission: threshold transmission framework achieving the same effect. Specifically, in encoder, we carry out power allocation on the transformed coefficients and encode the coefficients based on the new formulation of power distortion. In decoder, the process of LLSE estimator is also improved. Accompanied with the inverse nonlinear transform, DCT coefficients can be recovered depending on the scaling factors , LLSE estimator coefficients and metadata. Experiment results show that our proposed framework outperforms the Soft-cast in PSNR 1.08 dB and the MSSIM gain reaches to 2.35% when transmitting under the same bandwidth and total power.