OpenRaiser/Intern-Atlas huggingface dataset:
Application Component Placement in NFV-based Hybrid Cloud/Fog Systems with Mobile Fog Nodes
Venue: arXiv cs.DC 2019
Year: 2019

Fog computing reduces the latency induced by distant clouds by enabling the deployment of some application components at the edge of the network, on fog nodes, while keeping others in the cloud. Application components can be implemented as Virtual Network Functions (VNFs) and their execution sequences can be modeled by a combination of sub-structures like sequence, parallel, selection, and loops. Efficient placement algorithms are required to map the application components onto the infrastructure nodes. Current solutions do not consider the mobility of fog nodes, a phenomenon which may happen in real systems. In this paper, we use the random waypoint mobility model for fog nodes to calculate the expected makespan and application execution cost. We then model the problem as an Integer Linear Programming (ILP) formulation which minimizes an aggregated weighted function of the makespan and cost. We propose a Tabu Search-based Component Placement (TSCP) algorithm to find sub-optimal placements. The results show that the proposed algorithm improves the makespan and the application execution cost.
A Survey on Parallel Genetic Algorithms for Shop Scheduling Problems
Venue: arXiv cs.DC 2019
Year: 2019

There have been extensive works dealing with genetic algorithms (GAs) for seeking optimal solutions of shop scheduling problems. Due to the NP hardness, the time cost is always heavy. With the development of high performance computing (HPC) in last decades, the interest has been focused on parallel GAs for shop scheduling problems. In this paper, we present the state of the art with respect to the recent works on solving shop scheduling problems using parallel GAs. It showcases the most representative publications in this field by the categorization of parallel GAs and analyzes their designs based on the frameworks.
Evaluating KGR10 Polish word embeddings in the recognition of temporal expressions using BiLSTM-CRF
Venue: arXiv cs.CL 2019
Year: 2019

The article introduces a new set of Polish word embeddings, built using KGR10 corpus, which contains more than 4 billion words. These embeddings are evaluated in the problem of recognition of temporal expressions (timexes) for the Polish language. We described the process of KGR10 corpus creation and a new approach to the recognition problem using Bidirectional Long-Short Term Memory (BiLSTM) network with additional CRF layer, where specific embeddings are essential. We presented experiments and conclusions drawn from them.
Deep Learning Sentiment Analysis of Amazon.com Reviews and Ratings
Venue: arXiv cs.IR 2019
Year: 2019

Our study employs sentiment analysis to evaluate the compatibility of Amazon.com reviews with their corresponding ratings. Sentiment analysis is the task of identifying and classifying the sentiment expressed in a piece of text as being positive or negative. On e-commerce websites such as Amazon.com, consumers can submit their reviews along with a specific polarity rating. In some instances, there is a mismatch between the review and the rating. To identify the reviews with mismatched ratings we performed sentiment analysis using deep learning on Amazon.com product review data. Product reviews were converted to vectors using paragraph vector, which then was used to train a recurrent neural network with gated recurrent unit. Our model incorporated both semantic relationship of review text and product information. We also developed a web service application that predicts the rating score for a submitted review using the trained model and if there is a mismatch between predicted rating score and submitted rating score, it provides feedback to the reviewer.
Smart, Responsible, and Upper Caste Only: Measuring Caste Attitudes through Large-Scale Analysis of Matrimonial Profiles
Venue: arXiv cs.SI 2019
Year: 2019

Discriminatory caste attitudes currently stigmatize millions of Indians, subjecting individuals to prejudice in all aspects of life. Governmental incentives and societal movements have attempted to counter these attitudes, yet accurate measurements of public opinions on caste are not yet available for understanding whether progress is being made. Here, we introduce a novel approach to measure public attitudes of caste through an indicator variable: openness to intercaste marriage. Using a massive dataset of over 313K profiles from a major Indian matrimonial site, we precisely quantify public attitudes, along with differences between generations and between Indian residents and diaspora. We show that younger generations are more open to intercaste marriage, yet attitudes are based on a complex function of social status beyond their own caste. In examining the desired qualities in a spouse, we find that individuals open to intercaste marriage are more individualistic in the qualities they desire, rather than favoring family-related qualities, which mirrors larger societal trends away from collectivism. Finally, we show that attitudes in diaspora are significantly less open, suggesting a bi-cultural model of integration. Our research provides the first empirical evidence identifying how various intersections of identity shape attitudes toward intercaste marriage in India and among the Indian diaspora in the US.
Mode-Suppression: A Simple, Stable and Scalable Chunk-Sharing Algorithm for P2P Networks
Venue: arXiv cs.NI 2019
Year: 2019

The ability of a P2P network to scale its throughput up in proportion to the arrival rate of peers has recently been shown to be crucially dependent on the chunk sharing policy employed. Some policies can result in low frequencies of a particular chunk, known as the missing chunk syndrome, which can dramatically reduce throughput and lead to instability of the system. For instance, commonly used policies that nominally "boost" the sharing of infrequent chunks such as the well known rarest-first algorithm have been shown to be unstable. Recent efforts have largely focused on the careful design of boosting policies to mitigate this issue. We take a complementary viewpoint, and instead consider a policy that simply prevents the sharing of the most frequent chunk(s). Following terminology from statistics wherein the most frequent value in a data set is called the mode, we refer to this policy as mode-suppression. We also consider a more general version that suppresses the mode only if the mode frequency is larger than the lowest frequency by a fixed threshold. We prove the stability of mode-suppression using Lyapunov techniques, and use a Kingman bound argument to show that the total download time does not increase with peer arrival rate. We then design versions of mode-suppression that sample a small number of peers at each time, and construct noisy mode estimates by aggregating these samples over time. We show numerically that the variants of mode-suppression yield near-optimal download times, and outperform all other recently proposed chunk sharing algorithms.
Deep-Sentiment: Sentiment Analysis Using Ensemble of CNN and Bi-LSTM Models
Venue: arXiv cs.CL 2019
Year: 2019

With the popularity of social networks, and e-commerce websites, sentiment analysis has become a more active area of research in the past few years. On a high level, sentiment analysis tries to understand the public opinion about a specific product or topic, or trends from reviews or tweets. Sentiment analysis plays an important role in better understanding customer/user opinion, and also extracting social/political trends. There has been a lot of previous works for sentiment analysis, some based on hand-engineering relevant textual features, and others based on different neural network architectures. In this work, we present a model based on an ensemble of long-short-term-memory (LSTM), and convolutional neural network (CNN), one to capture the temporal information of the data, and the other one to extract the local structure thereof. Through experimental results, we show that using this ensemble model we can outperform both individual models. We are also able to achieve a very high accuracy rate compared to the previous works.
Least-squares registration of point sets over SE (d) using closed-form projections
Venue: arXiv cs.CV 2019
Year: 2019

Consider the problem of registering multiple point sets in some $d$-dimensional space using rotations and translations. Assume that there are sets with common points, and moreover the pairwise correspondences are known for such sets. We consider a least-squares formulation of this problem, where the variables are the transforms associated with the point sets. The present novelty is that we reduce this nonconvex problem to an optimization over the positive semidefinite cone, where the objective is linear but the constraints are nevertheless nonconvex. We propose to solve this using variable splitting and the alternating directions method of multipliers (ADMM). Due to the linearity of the objective and the structure of constraints, the ADMM subproblems are given by projections with closed-form solutions. In particular, for $m$ point sets, the dominant cost per iteration is the partial eigendecomposition of an $md \times md$ matrix, and $m-1$ singular value decompositions of $d \times d$ matrices. We empirically show that for appropriate parameter settings, the proposed solver has a large convergence basin and is stable under perturbations. As applications, we use our method for $2$D shape matching and $3$D multiview registration. In either application, we model the shapes/scans as point sets and determine the pairwise correspondences using ICP. In particular, our algorithm compares favorably with existing methods for multiview reconstruction in terms of timing and accuracy.
String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure
Venue: arXiv cs.DS 2019
Year: 2019

Burrows-Wheeler transform (BWT) is an invertible text transformation that, given a text $T$ of length $n$, permutes its symbols according to the lexicographic order of suffixes of $T$. BWT is one of the most heavily studied algorithms in data compression with numerous applications in indexing, sequence analysis, and bioinformatics. Its construction is a bottleneck in many scenarios, and settling the complexity of this task is one of the most important unsolved problems in sequence analysis that has remained open for 25 years. Given a binary string of length $n$, occupying $O(n/\log n)$ machine words, the BWT construction algorithm due to Hon et al. (SIAM J. Comput., 2009) runs in $O(n)$ time and $O(n/\log n)$ space. Recent advancements (Belazzougui, STOC 2014, and Munro et al., SODA 2017) focus on removing the alphabet-size dependency in the time complexity, but they still require $Ω(n)$ time. In this paper, we propose the first algorithm that breaks the $O(n)$-time barrier for BWT construction. Given a binary string of length $n$, our procedure builds the Burrows-Wheeler transform in $O(n/\sqrt{\log n})$ time and $O(n/\log n)$ space. We complement this result with a conditional lower bound proving that any further progress in the time complexity of BWT construction would yield faster algorithms for the very well studied problem of counting inversions: it would improve the state-of-the-art $O(m\sqrt{\log m})$-time solution by Chan and Pǎtraşcu (SODA 2010). Our algorithm is based on a novel concept of string synchronizing sets, which is of independent interest. As one of the applications, we show that this technique lets us design a data structure of the optimal size $O(n/\log n)$ that answers Longest Common Extension queries (LCE queries) in $O(1)$ time and, furthermore, can be deterministically constructed in the optimal $O(n/\log n)$ time.
Towards Traceability in Data Ecosystems using a Bill of Materials Model
Venue: arXiv cs.CY 2019
Year: 2019

Researchers and scientists use aggregations of data from a diverse combination of sources, including partners, open data providers and commercial data suppliers. As the complexity of such data ecosystems increases, and in turn leads to the generation of new reusable assets, it becomes ever more difficult to track data usage, and to maintain a clear view on where data in a system has originated and makes onward contributions. Reliable traceability on data usage is needed for accountability, both in demonstrating the right to use data, and having assurance that the data is as it is claimed to be. Society is demanding more accountability in data-driven and artificial intelligence systems deployed and used commercially and in the public sector. This paper introduces the conceptual design of a model for data traceability based on a Bill of Materials scheme, widely used for supply chain traceability in manufacturing industries, and presents details of the architecture and implementation of a gateway built upon the model. Use of the gateway is illustrated through a case study, which demonstrates how data and artifacts used in an experiment would be defined and instantiated to achieve the desired traceability goals, and how blockchain technology can facilitate accurate recordings of transactions between contributors.
CoRT: A Communication Robustness Testbed for Industrial Control System Components
Venue: arXiv cs.CR 2019
Year: 2019

The number of interconnected devices is growing constantly due to rapid digitalization, thus providing attackers with a larger attack surface. Particularly in critical infrastructures and manufacturing, where processes can be observed and controlled remotely, successful attacks could lead to high costs and damage. Therefore, it is necessary to investigate Industrial Control System (ICS) devices like Programmable Logic Controllers (PLCs) to make these sectors more secure. One possible attack vector is the exploitation of the network communication of devices. Thus, a robust communication system is essential to ensure security. Unfortunately, the high demand for real-world ICSs makes it difficult to assess component security during its runtime. However, this is possible in a research testbed where tests could be done and analyzed in a safe environment. In this paper, we introduce our testbed and measurement methods for communication robustness test research of ICS components.
Learned 3D Shape Representations Using Fused Geometrically Augmented Images: Application to Facial Expression and Action Unit Detection
Venue: arXiv cs.CV 2019
Year: 2019

This paper proposes an approach to learn generic multi-modal mesh surface representations using a novel scheme for fusing texture and geometric data. Our approach defines an inverse mapping between different geometric descriptors computed on the mesh surface or its down-sampled version, and the corresponding 2D texture image of the mesh, allowing the construction of fused geometrically augmented images (FGAI). This new fused modality enables us to learn feature representations from 3D data in a highly efficient manner by simply employing standard convolutional neural networks in a transfer-learning mode. In contrast to existing methods, the proposed approach is both computationally and memory efficient, preserves intrinsic geometric information and learns highly discriminative feature representation by effectively fusing shape and texture information at data level. The efficacy of our approach is demonstrated for the tasks of facial action unit detection and expression classification. The extensive experiments conducted on the Bosphorus and BU-4DFE datasets, show that our method produces a significant boost in the performance when compared to state-of-the-art solutions
Word Similarity Datasets for Thai: Construction and Evaluation
Venue: arXiv cs.CL 2019
Year: 2019

Distributional semantics in the form of word embeddings are an essential ingredient to many modern natural language processing systems. The quantification of semantic similarity between words can be used to evaluate the ability of a system to perform semantic interpretation. To this end, a number of word similarity datasets have been created for the English language over the last decades. For Thai language few such resources are available. In this work, we create three Thai word similarity datasets by translating and re-rating the popular WordSim-353, SimLex-999 and SemEval-2017-Task-2 datasets. The three datasets contain 1852 word pairs in total and have different characteristics in terms of difficulty, domain coverage, and notion of similarity (relatedness vs.~similarity). These features help to gain a broader picture of the properties of an evaluated word embedding model. We include baseline evaluations with existing Thai embedding models, and identify the high ratio of out-of-vocabulary words as one of the biggest challenges. All datasets, evaluation results, and a tool for easy evaluation of new Thai embedding models are available to the NLP community online.
Data-driven discovery of partial differential equation models with latent variables
Venue: arXiv cs.NA 2019
Year: 2019

In spatially extended systems, it is common to find latent variables that are hard, or even impossible, to measure with acceptable precision, but are crucially important for the proper description of the dynamics. This substantially complicates construction of an accurate model for such systems using data-driven approaches. The present paper illustrates how physical constraints can be employed to overcome this limitation using the example of a weakly turbulent quasi-two-dimensional Kolmogorov flow driven by a steady Lorenz force with an unknown spatial profile. Specifically, the terms involving latent variables in the partial differential equations governing the dynamics can be eliminated at the expense of raising the order of that equation. We show that local polynomial interpolation combined with symbolic regression can handle sparse data on grids that are representative of typical experimental measurement techniques such as particle image velocimetry. However, we also find that the reconstructed model is sensitive to measurement noise and trace this sensitivity to the presence of high order spatial and/or temporal derivatives.
Study of Decoherence in Quantum Computers: A Circuit-Design Perspective
Venue: arXiv cs.ET 2019
Year: 2019

Decoherence of quantum states is a major hurdle towards scalable and reliable quantum computing. Lower decoherence (i.e., higher fidelity) can alleviate the error correction overhead and obviate the need for energy-intensive noise reduction techniques e.g., cryogenic cooling. In this paper, we performed a noise-induced decoherence analysis of single and multi-qubit quantum gates using physics-based simulations. The analysis indicates that (i) decoherence depends on the input state and the gate type. Larger number of $|1\rangle$ states worsen the decoherence; (ii) amplitude damping is more detrimental than phase damping; (iii) shorter depth implementation of a quantum function can achieve lower decoherence. Simulations indicate 20\% improvement in the fidelity of a quantum adder when realized using lower depth topology. The insights developed in this paper can be exploited by the circuit designer to choose the right gates and logic implementation to optimize the system-level fidelity.
Quantifying the presence of graffiti in urban environments
Venue: arXiv cs.CV 2019
Year: 2019

Graffiti is a common phenomenon in urban scenarios. Differently from urban art, graffiti tagging is a vandalism act and many local governments are putting great effort to combat it. The graffiti map of a region can be a very useful resource because it may allow one to potentially combat vandalism in locations with high level of graffiti and also to cleanup saturated regions to discourage future acts. There is currently no automatic way of obtaining a graffiti map of a region and it is obtained by manual inspection by the police or by popular participation. In this sense, we describe an ongoing work where we propose an automatic way of obtaining a graffiti map of a neighbourhood. It consists of the systematic collection of street view images followed by the identification of graffiti tags in the collected dataset and finally, in the calculation of the proposed graffiti level of that location. We validate the proposed method by evaluating the geographical distribution of graffiti in a city known to have high concentration of graffiti -- Sao Paulo, Brazil.
Distributed Edge Connectivity in Sublinear Time
Venue: arXiv cs.DS 2019
Year: 2019

We present the first sublinear-time algorithm for a distributed message-passing network sto compute its edge connectivity $λ$ exactly in the CONGEST model, as long as there are no parallel edges. Our algorithm takes $\tilde O(n^{1-1/353}D^{1/353}+n^{1-1/706})$ time to compute $λ$ and a cut of cardinality $λ$ with high probability, where $n$ and $D$ are the number of nodes and the diameter of the network, respectively, and $\tilde O$ hides polylogarithmic factors. This running time is sublinear in $n$ (i.e. $\tilde O(n^{1-ε})$) whenever $D$ is. Previous sublinear-time distributed algorithms can solve this problem either (i) exactly only when $λ=O(n^{1/8-ε})$ [Thurimella PODC'95; Pritchard, Thurimella, ACM Trans. Algorithms'11; Nanongkai, Su, DISC'14] or (ii) approximately [Ghaffari, Kuhn, DISC'13; Nanongkai, Su, DISC'14]. To achieve this we develop and combine several new techniques. First, we design the first distributed algorithm that can compute a $k$-edge connectivity certificate for any $k=O(n^{1-ε})$ in time $\tilde O(\sqrt{nk}+D)$. Second, we show that by combining the recent distributed expander decomposition technique of [Chang, Pettie, Zhang, SODA'19] with techniques from the sequential deterministic edge connectivity algorithm of [Kawarabayashi, Thorup, STOC'15], we can decompose the network into a sublinear number of clusters with small average diameter and without any mincut separating a cluster (except the `trivial' ones). Finally, by extending the tree packing technique from [Karger STOC'96], we can find the minimum cut in time proportional to the number of components. As a byproduct of this technique, we obtain an $\tilde O(n)$-time algorithm for computing exact minimum cut for weighted graphs.
Hypersparse Neural Network Analysis of Large-Scale Internet Traffic
Venue: arXiv cs.NI 2019
Year: 2019

The Internet is transforming our society, necessitating a quantitative understanding of Internet traffic. Our team collects and curates the largest publicly available Internet traffic data containing 50 billion packets. Utilizing a novel hypersparse neural network analysis of "video" streams of this traffic using 10,000 processors in the MIT SuperCloud reveals a new phenomena: the importance of otherwise unseen leaf nodes and isolated links in Internet traffic. Our neural network approach further shows that a two-parameter modified Zipf-Mandelbrot distribution accurately describes a wide variety of source/destination statistics on moving sample windows ranging from 100,000 to 100,000,000 packets over collections that span years and continents. The inferred model parameters distinguish different network streams and the model leaf parameter strongly correlates with the fraction of the traffic in different underlying network topologies. The hypersparse neural network pipeline is highly adaptable and different network statistics and training models can be incorporated with simple changes to the image filter functions.