OpenRaiser/Intern-Atlas huggingface dataset:
BigRoots: An Effective Approach for Root-cause Analysis of Stragglers in Big Data System
Venue: arXiv cs.DC 2018
Year: 2018

Stragglers are commonly believed to have a great impact on the performance of big data system. However, the reason to cause straggler is complicated. Previous works mostly focus on straggler detection, schedule level optimization and coarse-grained cause analysis. These methods cannot provide valuable insights to help users optimize their programs. In this paper, we propose BigRoots, a general method incorporating both framework and system features for root-cause analysis of stragglers in big data system. BigRoots considers features from big data framework such as shuffle read/write bytes and JVM garbage collection time, as well as system resource utilization such as CPU, I/O and network, which is able to detect both internal and external root causes of stragglers. We verify BigRoots by injecting high resource utilization across different system components and perform case studies to analyze different workloads in Hibench. The experimental results demonstrate that BigRoots is effective to identify the root cause of stragglers and provide useful guidance for performance optimization.
Unsupervised Despeckling
Venue: arXiv cs.CV 2018
Year: 2018

Contrast and quality of ultrasound images are adversely affected by the excessive presence of speckle. However, being an inherent imaging property, speckle helps in tissue characterization and tracking. Thus, despeckling of the ultrasound images requires the reduction of speckle extent without any oversmoothing. In this letter, we aim to address the despeckling problem using an unsupervised deep adversarial approach. A despeckling residual neural network (DRNN) is trained with an adversarial loss imposed by a discriminator. The discriminator tries to differentiate between the despeckled images generated by the DRNN and the set of high-quality images. Further to prevent the developed DRNN from oversmoothing, a structural loss term is used along with the adversarial loss. Experimental evaluations show that the proposed DRNN is able to outperform the state-of-the-art despeckling approaches.
MilkQA: a Dataset of Consumer Questions for the Task of Answer Selection
Venue: arXiv cs.CL 2018
Year: 2018

We introduce MilkQA, a question answering dataset from the dairy domain dedicated to the study of consumer questions. The dataset contains 2,657 pairs of questions and answers, written in the Portuguese language and originally collected by the Brazilian Agricultural Research Corporation (Embrapa). All questions were motivated by real situations and written by thousands of authors with very different backgrounds and levels of literacy, while answers were elaborated by specialists from Embrapa's customer service. Our dataset was filtered and anonymized by three human annotators. Consumer questions are a challenging kind of question that is usually employed as a form of seeking information. Although several question answering datasets are available, most of such resources are not suitable for research on answer selection models for consumer questions. We aim to fill this gap by making MilkQA publicly available. We study the behavior of four answer selection models on MilkQA: two baseline models and two convolutional neural network archictetures. Our results show that MilkQA poses real challenges to computational models, particularly due to linguistic characteristics of its questions and to their unusually longer lengths. Only one of the experimented models gives reasonable results, at the cost of high computational requirements.
Neural Program Synthesis with Priority Queue Training
Venue: arXiv cs.AI 2018
Year: 2018

We consider the task of program synthesis in the presence of a reward function over the output of programs, where the goal is to find programs with maximal rewards. We employ an iterative optimization scheme, where we train an RNN on a dataset of K best programs from a priority queue of the generated programs so far. Then, we synthesize new programs and add them to the priority queue by sampling from the RNN. We benchmark our algorithm, called priority queue training (or PQT), against genetic algorithm and reinforcement learning baselines on a simple but expressive Turing complete programming language called BF. Our experimental results show that our simple PQT algorithm significantly outperforms the baselines. By adding a program length penalty to the reward function, we are able to synthesize short, human readable programs.
On the Noise-Information Separation of a Private Principal Component Analysis Scheme
Venue: arXiv cs.IT 2018
Year: 2018

In a survey disclosure model, we consider an additive noise privacy mechanism and study the trade-off between privacy guarantees and statistical utility. Privacy is approached from two different but complementary viewpoints: information and estimation theoretic. Motivated by the performance of principal component analysis, statistical utility is measured via the spectral gap of a certain covariance matrix. This formulation and its motivation rely on classical results from random matrix theory. We prove some properties of this statistical utility function and discuss a simple numerical method to evaluate it.
Deterministic search for CNF satisfying assignments in almost polynomial time
Venue: arXiv cs.CC 2018
Year: 2018

We consider the fundamental derandomization problem of deterministically finding a satisfying assignment to a CNF formula that has many satisfying assignments. We give a deterministic algorithm which, given an $n$-variable $\mathrm{poly}(n)$-clause CNF formula $F$ that has at least $\varepsilon 2^n$ satisfying assignments, runs in time \[ n^{\tilde{O}(\log\log n)^2} \] for $\varepsilon \ge 1/\mathrm{polylog}(n)$ and outputs a satisfying assignment of $F$. Prior to our work the fastest known algorithm for this problem was simply to enumerate over all seeds of a pseudorandom generator for CNFs; using the best known PRGs for CNFs [DETT10], this takes time $n^{\tildeΩ(\log n)}$ even for constant $\varepsilon$. Our approach is based on a new general framework relating deterministic search and deterministic approximate counting, which we believe may find further applications.
Quadrature compressive sampling SAR imaging
Venue: arXiv cs.IT 2018
Year: 2018

This paper presents a quadrature compressive sampling (QuadCS) and associated fast imaging scheme for synthetic aperture radar (SAR). Different from other analog-to-information conversions (AIC), QuadCS AICs using independent spreading signals sample the SAR echoes due to different transmitted pulses. Then the resulting sensing matrix has lower correlation between any two columns than that by a fixed spreading signal, and better SAR image can be reconstructed. With proper setting of the spreading signals in QuadCS, the sensing matrix has the structures suitable for fast computation of matrix-vector multiplication operations, which leads to the fast image reconstruction. The performance of the proposed scheme is assessed using real SAR image. The reconstructed SAR images with only one-fourth of the Nyquist data achieve the image quality similar to that of the classical SAR images with Nyquist samples.
On approximate equivalence of modularity, D and non-negative matrix factorization
Venue: arXiv cs.SI 2018
Year: 2018

Community structures detection is one of the fundamental problems in complex network analysis towards understanding the topology structures of the network and the functions of it. Nonnegative matrix factorization (NMF) is a widely used method for community detection, and modularity Q and modularity density D are criteria to evaluate the quality of community structures. In this paper, we establish the connections between Q, D and NMF for the first time. Q maximization can be approximately reformulated under the framework of NMF with Frobenius norm, especially when $n$ is large, and D maximization can also be reformulated under the framework of NMF. Q minimization can be reformulated under the framework of NMF with Kullback-Leibler divergence. We propose new methods for community structures detection based on the above findings, and the experimental results on synthetic networks demonstrate their effectiveness.
A tool framework for tweaking features in synthetic datasets
Venue: arXiv cs.DB 2018
Year: 2018

Researchers and developers use benchmarks to compare their algorithms and products. A database benchmark must have a dataset D. To be application-specific, this dataset D should be empirical. However, D may be too small, or too large, for the benchmarking experiments. D must, therefore, be scaled to the desired size. To ensure the scaled D' is similar to D, previous work typically specifies or extracts a fixed set of features F = {F_1, F_2, . . . , F_n} from D, then uses F to generate synthetic data for D'. However, this approach (D -> F -> D') becomes increasingly intractable as F gets larger, so a new solution is necessary. Different from existing approaches, this paper proposes ASPECT to scale D to enforce similarity. ASPECT first uses a size-scaler (S0) to scale D to D'. Then the user selects a set of desired features F'_1, . . . , F'_n. For each desired feature F'_k, there is a tweaking tool T_k that tweaks D' to make sure D' has the required feature F'_k. ASPECT coordinates the tweaking of T_1,...,T_n to D', so T_n(...(T_1(D'))...) has the required features F'_1,...,F'_n. By shifting from D -> F -> D' to D -> D' -> F', data scaling becomes flexible. The user can customise the scaled dataset with their own interested features. Extensive experiments on real datasets show that ASPECT can enforce similarity in the dataset effectively and efficiently.
Asynchronous Mobile-Edge Computation Offloading: Energy-Efficient Resource Management
Venue: arXiv cs.IT 2018
Year: 2018

Mobile-edge computation offloading (MECO) is an emerging technology for enhancing mobiles' computation capabilities and prolonging their battery lives, by offloading intensive computation from mobiles to nearby servers such as base stations. In this paper, we study the energy-efficient resource-management policy for the asynchronous MECO system, where the mobiles have heterogeneous input-data arrival time instants and computation deadlines. First, we consider the general case with arbitrary arrival-deadline orders. Based on the monomial energy-consumption model for data transmission, an optimization problem is formulated to minimize the total mobile-energy consumption under the time-sharing and computation-deadline constraints. The optimal resource-management policy for data partitioning (for offloading and local computing) and time division (for transmissions) is shown to be computed by using the block coordinate decent method. To gain further insights, we study the optimal resource-management design for two special cases. First, consider the case of identical arrival-deadline orders, i.e., a mobile with input data arriving earlier also needs to complete computation earlier. The optimization problem is reduced to two sequential problems corresponding to the optimal scheduling order and joint data-partitioning and time-division given the optimal order. It is found that the optimal time-division policy tends to balance the defined effective computing power among offloading mobiles via time sharing. Furthermore, this solution approach is extended to the case of reverse arrival-deadline orders. The corresponding time-division policy is derived by a proposed transformation-and-scheduling approach, which first determines the total offloading duration and data size for each mobile in the transformation phase and then specifies the offloading intervals for each mobile in the scheduling phase.
Repairing the Faure-Loidreau Public-Key Cryptosystem
Venue: arXiv cs.CR 2018
Year: 2018

A repair of the Faure-Loidreau (FL) public-key code-based cryptosystem is proposed. The FL cryptosystem is based on the hardness of list decoding Gabidulin codes which are special rank-metric codes. We prove that the recent structural attack on the system by Gaborit et al. is equivalent to decoding an interleaved Gabidulin code. Since all known polynomial-time decoders for these codes fail for a large constructive class of error patterns, we are able to construct public keys that resist the attack. It is also shown that all other known attacks fail for our repair and parameter choices. Compared to other code-based cryptosystems, we obtain significantly smaller key sizes for the same security level.
A Software-defined SoC Memory Bus Bridge Architecture for Disaggregated Computing
Venue: arXiv cs.AR 2018
Year: 2018

Disaggregation and rack-scale systems have the potential of drastically decreasing TCO and increasing utilization of cloud datacenters, while maintaining performance. While the concept of organising resources in separate pools and interconnecting them together on demand is straightforward, its materialisation can be radically different in terms of performance and scale potential. In this paper, we present a memory bus bridge architecture which enables communication between 100s of masters and slaves in todays complex multiprocessor SoCs, that are physically intregrated in different chips and even different mainboards. The bridge tightly couples serial transceivers and a circuit network for chip-to-chip transfers. A key property of the proposed bridge architecture is that it is software-defined and thus can be configured at runtime, via a software control plane, to prepare and steer memory access transactions to remote slaves. This is particularly important because it enables datacenter orchestration tools to manage the disaggregated resource allocation. Moreover, we evaluate a bridge prototype we have build for ARM AXI4 memory bus interconnect and we discuss application-level observed performance.
Performance Evaluation of Advanced Relaying Protocols in Large Wireless Networks
Venue: arXiv cs.IT 2018
Year: 2018

This paper studies the performance of some state-of-the-art cooperative full-duplex relaying protocols in the context of a large wireless network modelled using stochastic geometry tools. We investigate the outage behaviour for different cooperative schemes, namely, decode-and-forward, noisy-network coding and mixed noisy-network coding, considering fading, path loss and interference from other sources and relays. Due to the high complexity of the network topology and the protocols considered, a closed-form analysis is not possible, so our study is performed through extensive but careful numerical simulations, sweeping a large number of relevant parameters. Several scenarios of particular interest are investigated. In this way, insightful conclusions are drawn regarding the network regimes in which relay-assisted cooperation is most beneficial and the potential gains that could be achieved through it.
EARL: Joint Entity and Relation Linking for Question Answering over Knowledge Graphs
Venue: arXiv cs.AI 2018
Year: 2018

Many question answering systems over knowledge graphs rely on entity and relation linking components in order to connect the natural language input to the underlying knowledge graph. Traditionally, entity linking and relation linking have been performed either as dependent sequential tasks or as independent parallel tasks. In this paper, we propose a framework called EARL, which performs entity linking and relation linking as a joint task. EARL implements two different solution strategies for which we provide a comparative analysis in this paper: The first strategy is a formalisation of the joint entity and relation linking tasks as an instance of the Generalised Travelling Salesman Problem (GTSP). In order to be computationally feasible, we employ approximate GTSP solvers. The second strategy uses machine learning in order to exploit the connection density between nodes in the knowledge graph. It relies on three base features and re-ranking steps in order to predict entities and relations. We compare the strategies and evaluate them on a dataset with 5000 questions. Both strategies significantly outperform the current state-of-the-art approaches for entity and relation linking.
Terahertz Dielectric Resonator Antenna Coupled to Graphene Plasmonic Dipole
Venue: arXiv cs.ET 2018
Year: 2018

This paper presents an efficient approach for exciting a dielectric resonator antenna (DRA) in the terahertz frequencies by means of a graphene plasmonic dipole. Design and analysis are performed in two steps. First, the propagation properties of hybrid plasmonic onedimensional and two-dimensional structures are obtained by using transfer matrix theory and the finite-element method. The coupling amount between the plasmonic graphene mode and the dielectric wave mode is explored based on different parameters. These results, together with DRA and plasmonic antenna theory, are then used to design a DRA antenna that supports the $TE_{y}^{112}$ mode at 2.4 THz and achieves a gain (IEEE) of up to 7 dBi and a radiation efficiency of up 70%. This gain is 6.5 dB higher than that of the graphene dipole alone and achieved with a moderate area overhead, demonstrating the value of the proposed structure.
A Monetary Mechanism for Stabilizing Cooperative Data Exchange with Selfish Users
Venue: arXiv cs.IT 2018
Year: 2018

This paper considers the problem of stabilizing cooperative data exchange with selfish users. In this setting, each user has a subset of packets in the ground set $X$, and wants all other packets in $X$. The users can exchange their packets by broadcasting coded or uncoded packets over a lossless broadcast channel, and monetary transactions are allowed between any pair of users. We define the utility of each user as the sum of two sub-utility functions: (i) the difference between the total payment received by the user and the total transmission rate of the user, and (ii) the difference between the total number of required packets by the user and the total payment made by the user. A rate-vector and payment-matrix pair $(r,p)$ is said to stabilize the grand coalition (i.e., the set of all users) if $(r,p)$ is Pareto optimal over all minor coalitions (i.e., all proper subsets of users who collectively know all packets in $X$). Our goal is to design a stabilizing rate-payment pair with minimum total sum-rate and minimum total sum-payment for any given instance of the problem. In this work, we propose two algorithms that find such a solution. Moreover, we show that both algorithms maximize the sum of utility of all users (over all solutions), and one of the algorithms also maximizes the minimum utility among all users (over all solutions).
An entropy inequality for symmetric random variables
Venue: arXiv cs.IT 2018
Year: 2018

We establish a lower bound on the entropy of weighted sums of (possibly dependent) random variables $(X_1, X_2, \dots, X_n)$ possessing a symmetric joint distribution. Our lower bound is in terms of the joint entropy of $(X_1, X_2, \dots, X_n)$. We show that for $n \geq 3$, the lower bound is tight if and only if $X_i$'s are i.i.d.\ Gaussian random variables. For $n=2$ there are numerous other cases of equality apart from i.i.d.\ Gaussians, which we completely characterize. Going beyond sums, we also present an inequality for certain linear transformations of $(X_1, \dots, X_n)$. Our primary technical contribution lies in the analysis of the equality cases, and our approach relies on the geometry and the symmetry of the problem.
Parameterized (Approximate) Defective Coloring
Venue: arXiv cs.DS 2018
Year: 2018

In Defective Coloring we are given a graph $G = (V, E)$ and two integers $χ_d, Δ^*$ and are asked if we can partition $V$ into $χ_d$ color classes, so that each class induces a graph of maximum degree $Δ^*$. We investigate the complexity of this generalization of Coloring with respect to several well-studied graph parameters, and show that the problem is W-hard parameterized by treewidth, pathwidth, tree-depth, or feedback vertex set, if $χ_d = 2$. As expected, this hardness can be extended to larger values of $χ_d$ for most of these parameters, with one surprising exception: we show that the problem is FPT parameterized by feedback vertex set for any $χ_d \ge 2$, and hence 2-coloring is the only hard case for this parameter. In addition to the above, we give an ETH-based lower bound for treewidth and pathwidth, showing that no algorithm can solve the problem in $n^{o(pw)}$, essentially matching the complexity of an algorithm obtained with standard techniques. We complement these results by considering the problem's approximability and show that, with respect to $Δ^*$, the problem admits an algorithm which for any $ε> 0$ runs in time $(tw/ε)^{O(tw)}$ and returns a solution with exactly the desired number of colors that approximates the optimal $Δ^*$ within $(1 + ε)$. We also give a $(tw)^{O(tw)}$ algorithm which achieves the desired $Δ^*$ exactly while 2-approximating the minimum value of $χ_d$. We show that this is close to optimal, by establishing that no FPT algorithm can (under standard assumptions) achieve a better than $3/2$-approximation to $χ_d$, even when an extra constant additive error is also allowed.
Privacy in Index Coding: Improved Bounds and Coding Schemes
Venue: arXiv cs.IT 2018
Year: 2018

It was recently observed in [1], that in index coding, learning the coding matrix used by the server can pose privacy concerns: curious clients can extract information about the requests and side information of other clients. One approach to mitigate such concerns is the use of $k$-limited-access schemes [1], that restrict each client to learn only part of the index coding matrix, and in particular, at most $k$ rows. These schemes transform a linear index coding matrix of rank $T$ to an alternate one, such that each client needs to learn at most $k$ of the coding matrix rows to decode its requested message. This paper analyzes $k$-limited-access schemes. First, a worst-case scenario, where the total number of clients $n$ is $2^T-1$ is studied. For this case, a novel construction of the coding matrix is provided and shown to be order-optimal in the number of transmissions. Then, the case of a general $n$ is considered and two different schemes are designed and analytically and numerically assessed in their performance. It is shown that these schemes perform better than the one designed for the case $n=2^T-1$.
On Locally Decodable Index Codes
Venue: arXiv cs.IT 2018
Year: 2018

Index coding achieves bandwidth savings by jointly encoding the messages demanded by all the clients in a broadcast channel. The encoding is performed in such a way that each client can retrieve its demanded message from its side information and the broadcast codeword. In general, in order to decode its demanded message symbol, a receiver may have to observe the entire transmitted codeword. Querying or downloading the codeword symbols might involve costs to a client -- such as network utilization costs and storage requirements for the queried symbols to perform decoding. In traditional index coding solutions, this 'client aware' perspective is not considered during code design. As a result, for these codes, the number of codeword symbols queried by a client per decoded message symbol, which we refer to as 'locality', could be large. In this paper, considering locality as a cost parameter, we view index coding as a trade-off between the achievable broadcast rate (codeword length normalized by the message length) and locality, where the objective is to minimize the broadcast rate for a given value of locality and vice versa. We show that the smallest possible locality for any index coding problem is 1, and that the optimal index coding solution with locality 1 is the coding scheme based on fractional coloring of the interference graph. We propose index coding schemes with small locality by covering the side information graph using acyclic subgraphs and subgraphs with small minrank. We also show how locality can be accounted for in conventional partition multicast and cycle covering solutions to index coding. Finally, applying these new techniques, we characterize the locality-broadcast rate trade-off of the index coding problem whose side information graph is the directed 3-cycle.