OpenRaiser/Intern-Atlas huggingface dataset:
Lossy kernels for connected distance-$r$ domination on nowhere dense graph classes
Venue: arXiv cs.DM 2017
Year: 2017

For $α\colon\mathbb{N}\rightarrow\mathbb{R}$, an $α$-approximate bi-kernel is a polynomial-time algorithm that takes as input an instance $(I, k)$ of a problem $Q$ and outputs an instance $(I',k')$ of a problem $Q'$ of size bounded by a function of $k$ such that, for every $c\geq 1$, a $c$-approximate solution for the new instance can be turned into a $c\cdotα(k)$-approximate solution of the original instance in polynomial time. This framework of \emph{lossy kernelization} was recently introduced by Lokshtanov et al. We prove that for every nowhere dense class of graphs, every $α>1$ and $r\in\mathbb{N}$ there exists a polynomial $p$ (whose degree depends only on $r$ while its coefficients depend on $α$) such that the connected distance-$r$ dominating set problem with parameter $k$ admits an $α$-approximate bi-kernel of size $p(k)$. Furthermore, we show that this result cannot be extended to more general classes of graphs which are closed under taking subgraphs by showing that if a class $C$ is somewhere dense and closed under taking subgraphs, then for some value of $r\in\mathbb{N}$ there cannot exist an $α$-approximate bi-kernel for the (connected) distance-$r$ dominating set problem on $C$ for any function $α\colon\mathbb{N}\rightarrow\mathbb{R}$ (assuming the Gap Exponential Time Hypothesis).
Bias Estimation for Decentralized Sensor Fusion -- Multi-Agent Based Bias Estimation Method
Venue: arXiv cs.SY 2017
Year: 2017

In multi-sensor data fusion (or sensor fusion), sensor biases (or offsets) often affect the accuracy of the correlation and integration results of the tracking targets. Therefore, to estimate and compensate the bias, several methods are proposed. However, most methods involve bias estimation and sensor fusion simultaneously by using Kalman filter after collecting the plot data together. Hence, these methods cannot support to fuse the track data prepared by tracking filter at each sensor node. This report proposes the new bias estimation method based on multi-agent model, in order to estimate and compensate the bias for decentralized sensor fusion.
Spatially variant PSF modeling in confocal macroscopy
Venue: arXiv cs.CV 2017
Year: 2017

Point spread function (PSF) plays an essential role in image reconstruction. In the context of confocal microscopy, optical performance degrades towards the edge of the field of view as astigmatism, coma and vignetting. Thus, one should expect the related artifacts to be even stronger in macroscopy, where the field of view is much larger. The field aberrations in macroscopy fluorescence imaging system was observed to be symmetrical and to increase with the distance from the center of the field of view. In this paper we propose an experiment and an optimization method for assessing the center of the field of view. The obtained results constitute a step towards reducing the number of parameters in macroscopy PSF model.
Unmixing dynamic PET images with variable specific binding kinetics
Venue: arXiv cs.CV 2017
Year: 2017

To analyze dynamic positron emission tomography (PET) images, various generic multivariate data analysis techniques have been considered in the literature, such as principal component analysis (PCA), independent component analysis (ICA), factor analysis and nonnegative matrix factorization (NMF). Nevertheless, these conventional approaches neglect any possible nonlinear variations in the time activity curves describing the kinetic behavior of tissues with specific binding, which limits their ability to recover a reliable, understandable and interpretable description of the data. This paper proposes an alternative analysis paradigm that accounts for spatial fluctuations in the exchange rate of the tracer between a free compartment and a specifically bound ligand compartment. The method relies on the concept of linear unmixing, usually applied on the hyperspectral domain, which combines NMF with a sum-to-one constraint that ensures an exhaustive description of the mixtures. The spatial variability of the signature corresponding to the specific binding tissue is explicitly modeled through a perturbed component. The performance of the method is assessed on both synthetic and real data and is shown to compete favorably when compared to other conventional analysis methods. The proposed method improved both factor estimation and proportions extraction for specific binding. Modeling the variability of the specific binding factor has a strong potential impact for dynamic PET image analysis.
Debugging Transactions and Tracking their Provenance with Reenactment
Venue: arXiv cs.DB 2017
Year: 2017

Debugging transactions and understanding their execution are of immense importance for developing OLAP applications, to trace causes of errors in production systems, and to audit the operations of a database. However, debugging transactions is hard for several reasons: 1) after the execution of a transaction, its input is no longer available for debugging, 2) internal states of a transaction are typically not accessible, and 3) the execution of a transaction may be affected by concurrently running transactions. We present a debugger for transactions that enables non-invasive, post-mortem debugging of transactions with provenance tracking and supports what-if scenarios (changes to transaction code or data). Using reenactment, a declarative replay technique we have developed, a transaction is replayed over the state of the DB seen by its original execution including all its interactions with concurrently executed transactions from the history. Importantly, our approach uses the temporal database and audit logging capabilities available in many DBMS and does not require any modifications to the underlying database system nor transactional workload.
Formal Analysis of Continuous-time Systems using Fourier Transform
Venue: arXiv cs.LO 2017
Year: 2017

To study the dynamical behaviour of the engineering and physical systems, we often need to capture their continuous behaviour, which is modeled using differential equations, and perform the frequency-domain analysis of these systems. Traditionally, Fourier transform methods are used to perform this frequency domain analysis using paper-and-pencil based analytical techniques or computer simulations. However, both of these methods are error prone and thus are not suitable for analyzing systems used in safety-critical domains, like medicine and transportation. In order to provide an accurate alternative, we propose to use higher-order-logic theorem proving to conduct the frequency domain analysis of these systems. For this purpose, the paper presents a higher-order-logic formalization of Fourier transform using the HOL-Light theorem prover. In particular, we use the higher-order-logic based formalizations of differential, integral, transcendental and topological theories of multivariable calculus to formally define Fourier transform and reason about the correctness of its classical properties, such as existence, linearity, time shifting, frequency shifting, modulation, time scaling, time reversal and differentiation in time domain, and its relationships with Fourier Cosine, Fourier Sine and Laplace transforms. We use our proposed formalization for the formal verification of the frequency response of a generic n-order linear system, an audio equalizer and a MEMs accelerometer, using the HOL-Light theorem prover.
Which Distribution Distances are Sublinearly Testable?
Venue: arXiv cs.DS 2017
Year: 2017

Given samples from an unknown distribution $p$ and a description of a distribution $q$, are $p$ and $q$ close or far? This question of "identity testing" has received significant attention in the case of testing whether $p$ and $q$ are equal or far in total variation distance. However, in recent work, the following questions have been been critical to solving problems at the frontiers of distribution testing: -Alternative Distances: Can we test whether $p$ and $q$ are far in other distances, say Hellinger? -Tolerance: Can we test when $p$ and $q$ are close, rather than equal? And if so, close in which distances? Motivated by these questions, we characterize the complexity of distribution testing under a variety of distances, including total variation, $\ell_2$, Hellinger, Kullback-Leibler, and $χ^2$. For each pair of distances $d_1$ and $d_2$, we study the complexity of testing if $p$ and $q$ are close in $d_1$ versus far in $d_2$, with a focus on identifying which problems allow strongly sublinear testers (i.e., those with complexity $O(n^{1 - γ})$ for some $γ> 0$ where $n$ is the size of the support of the distributions $p$ and $q$). We provide matching upper and lower bounds for each case. We also study these questions in the case where we only have samples from $q$ (equivalence testing), showing qualitative differences from identity testing in terms of when tolerance can be achieved. Our algorithms fall into the classical paradigm of $χ^2$-statistics, but require crucial changes to handle the challenges introduced by each distance we consider. Finally, we survey other recent results in an attempt to serve as a reference for the complexity of various distribution testing problems.
An efficient MPI/OpenMP parallelization of the Hartree-Fock method for the second generation of Intel Xeon Phi processor
Venue: arXiv cs.DC 2017
Year: 2017

Modern OpenMP threading techniques are used to convert the MPI-only Hartree-Fock code in the GAMESS program to a hybrid MPI/OpenMP algorithm. Two separate implementations that differ by the sharing or replication of key data structures among threads are considered, density and Fock matrices. All implementations are benchmarked on a super-computer of 3,000 Intel Xeon Phi processors. With 64 cores per processor, scaling numbers are reported on up to 192,000 cores. The hybrid MPI/OpenMP implementation reduces the memory footprint by approximately 200 times compared to the legacy code. The MPI/OpenMP code was shown to run up to six times faster than the original for a range of molecular system sizes.
SemEval-2017 Task 1: Semantic Textual Similarity - Multilingual and Cross-lingual Focused Evaluation
Venue: arXiv cs.CL 2017
Year: 2017

Semantic Textual Similarity (STS) measures the meaning similarity of sentences. Applications include machine translation (MT), summarization, generation, question answering (QA), short answer grading, semantic search, dialog and conversational systems. The STS shared task is a venue for assessing the current state-of-the-art. The 2017 task focuses on multilingual and cross-lingual pairs with one sub-track exploring MT quality estimation (MTQE) data. The task obtained strong participation from 31 teams, with 17 participating in all language tracks. We summarize performance and review a selection of well performing methods. Analysis highlights common errors, providing insight into the limitations of existing models. To support ongoing work on semantic representations, the STS Benchmark is introduced as a new shared training and evaluation set carefully selected from the corpus of English STS shared task data (2012-2017).
Computing the Margin of Victory in Preferential Parliamentary Elections
Venue: arXiv cs.DS 2017
Year: 2017

We show how to use automated computation of election margins to assess the number of votes that would need to change in order to alter a parliamentary outcome for single-member preferential electorates. In the context of increasing automation of Australian electoral processes, and accusations of deliberate interference in elections in Europe and the USA, this work forms the basis of a rigorous statistical audit of the parliamentary election outcome. Our example is the New South Wales Legislative Council election of 2015, but the same process could be used for any similar parliament for which data was available, such as the Australian House of Representatives given the proposed automatic scanning of ballots.
A Stable Coin with Pro-rated Rebasement and Price Manipulation Protection
Venue: arXiv cs.CR 2017
Year: 2017

An existing pseudo-commodity and a smart contracts framework allow the creation of a purely automatic and self-sufficient price-stable cryptocurrency, without human intervention. This new currency, we denominated Toroid or TRD, can be used more extensively for commerce than pseudo commodity cryptocurrencies due to its lower volatility. Also, is suitable for investment, as the tokens in each account multiply, return interest, when the market grows. Like the controlled fiat money of a central bank plus the benefits of an inflation-adjusted perpetuity bond. Collateral in base coin, for example BTC or ETH, can be added to bootstrap your own Toroid investment or withdrawed after a very small investment period. So, the Toroids are not created from nothing nor have a limited monetary base. The minimum investment period can be very small, for example one day, and you keep the interest but you can return the Toroids and refund your collateral. That is a one-side only peg to a deflationary crypto-commodity. The stability is guaranteed by endogenous measurements of number of transactions and wallet pro-rated rebasement of balance to reduce volatility of price. Each account has its own rebasement due to the account creation timestamp. Rebasement control mechanism is progressive during initial bootstrap period because price manipulation protection is more severe when the capital involved is smaller. Rebasement has a quick positive start to incentivize early adopters that see only big growth in their TRD account during bootstrap period. Finally, the new rebasement control makes it economically infeasible for an attacker targeting the coin with manipulated transaction volume if we set the minimum rebasement greater than profits from massive currency manipulation.
On outer-connected domination for graph products
Venue: arXiv cs.DM 2017
Year: 2017

An outer-connected dominating set for an arbitrary graph $G$ is a set $\tilde{D} \subseteq V$ such that $\tilde{D}$ is a dominating set and the induced subgraph $G [V \setminus \tilde{D}]$ be connected. In this paper, we focus on the outer-connected domination number of the product of graphs. We investigate the existence of outer-connected dominating set in lexicographic product and Corona of two arbitrary graphs, and we present upper bounds for outer-connected domination number in lexicographic and Cartesian product of graphs. Also, we establish an equivalent form of the Vizing's conjecture for outer-connected domination number in lexicographic and Cartesian product as $\tilde{γ_c}(G \circ K)\tilde{γ_c}(H \circ K) \leq \tilde{γ_c}(G\Box H)\circ K$. Furthermore, we study the outer-connected domination number of the direct product of finitely many complete graphs.
Energy-Efficient Data Collection in UAV Enabled Wireless Sensor Network
Venue: arXiv cs.IT 2017
Year: 2017

In wireless sensor networks (WSNs), utilizing the unmanned aerial vehicle (UAV) as a mobile data collector for the ground sensor nodes (SNs) is an energy-efficient technique to prolong the network lifetime. Specifically, since the UAV can sequentially move close to each of the SNs when collecting data from them and thus reduce the link distance for saving the SNs' transmission energy. In this letter, considering a general fading channel model for the SN-UAV links, we jointly optimize the SNs' wake-up schedule and UAV's trajectory to minimize the maximum energy consumption of all SNs, while ensuring that the required amount of data is collected reliably from each SN. We formulate our design as a mixed-integer non-convex optimization problem. By applying the successive convex optimization technique, an efficient iterative algorithm is proposed to find a sub-optimal solution. Numerical results show that the proposed scheme achieves significant network energy saving as compared to benchmark schemes.
Exact Approaches for the Travelling Thief Problem
Venue: arXiv cs.DS 2017
Year: 2017

Many evolutionary and constructive heuristic approaches have been introduced in order to solve the Traveling Thief Problem (TTP). However, the accuracy of such approaches is unknown due to their inability to find global optima. In this paper, we propose three exact algorithms and a hybrid approach to the TTP. We compare these with state-of-the-art approaches to gather a comprehensive overview on the accuracy of heuristic methods for solving small TTP instances.
Implementing an Edge-Fog-Cloud architecture for stream data management
Venue: arXiv cs.DC 2017
Year: 2017

The Internet of Moving Things (IoMT) requires support for a data life cycle process ranging from sorting, cleaning and monitoring data streams to more complex tasks such as querying, aggregation, and analytics. Current solutions for stream data management in IoMT have been focused on partial aspects of a data life cycle process, with special emphasis on sensor networks. This paper aims to address this problem by developing streaming data life cycle process that incorporates an edge/fog/cloud architecture that is needed for handling heterogeneous, streaming and geographically-dispersed IoMT devices. We propose a 3-tier architecture to support an instant intra-layer communication that establishes a stream data flow in real-time to respond to immediate data life cycle tasks in the system. Communication and process are thus the defining factors in the design of our stream data management solution for IoMT. We describe and evaluate our prototype implementation using real-time transit data feeds. Preliminary results are showing the advantages of running data life cycle tasks for reducing the volume of data streams that are redundant and should not be transported to the cloud.
A Watershed Delineation Algorithm for 2D Flow Direction Grids
Venue: arXiv cs.DS 2017
Year: 2017

In this paper we propose an algorithm and associated data model for creating a watershed boundary using a 2D Flow Direction Grid. Flow Direction Grids (FDGs) are common abstractions for hydrodynamic models and are utilized for delineating physical systems (e.g. watersheds, fluvial, and non-fluvial flow paths). The proposed algorithm and associated data model provides geometric speed increases in watershed boundary retrieval while keeping storage constraints linear in comparison to existing techniques. The algorithm called Haag Shokoufandehs' March (HSM) relies on an existing data structure, the modified nested set model, originally described by Celko and applied to hydrodynamic models by Haag and Shokoufandeh in 2017. The proposed algorithm creates watershed boundaries by marching around the edges of its' corresponding region, never entering the internal area. In contrast to existing algorithms that scales in proportional to the area of the underlying region, the complexity of the HSM algorithm is proportional to the boundary length. Results for a group of tested watersheds (n = 14,718) in the approximately 36,000 km^2 Delaware River Watershed show a reduction of between 0 and 99% in computational complexity using a 30 m DEM vs. existing techniques. Larger watersheds have a consistent reduction in the number of (read) operation complexity, with the largest watershed resulting in approximately 35 million reads using traditional techniques compared to approximately 45 thousand using the HSM algorithm, respectively. Modelled estimates of the complexity for the approximately 6.1 million km^2 Amazon River basin show a reduction from 6.7 billion to 1.4 million reads.
An Analytical Study of Large SPARQL Query Logs
Venue: arXiv cs.DB 2017
Year: 2017

With the adoption of RDF as the data model for Linked Data and the Semantic Web, query specification from end- users has become more and more common in SPARQL end- points. In this paper, we conduct an in-depth analytical study of the queries formulated by end-users and harvested from large and up-to-date query logs from a wide variety of RDF data sources. As opposed to previous studies, ours is the first assessment on a voluminous query corpus, span- ning over several years and covering many representative SPARQL endpoints. Apart from the syntactical structure of the queries, that exhibits already interesting results on this generalized corpus, we drill deeper in the structural char- acteristics related to the graph- and hypergraph represen- tation of queries. We outline the most common shapes of queries when visually displayed as pseudographs, and char- acterize their (hyper-)tree width. Moreover, we analyze the evolution of queries over time, by introducing the novel con- cept of a streak, i.e., a sequence of queries that appear as subsequent modifications of a seed query. Our study offers several fresh insights on the already rich query features of real SPARQL queries formulated by real users, and brings us to draw a number of conclusions and pinpoint future di- rections for SPARQL query evaluation, query optimization, tuning, and benchmarking.
Using Program Induction to Interpret Transition System Dynamics
Venue: arXiv cs.AI 2017
Year: 2017

Explaining and reasoning about processes which underlie observed black-box phenomena enables the discovery of causal mechanisms, derivation of suitable abstract representations and the formulation of more robust predictions. We propose to learn high level functional programs in order to represent abstract models which capture the invariant structure in the observed data. We introduce the $π$-machine (program-induction machine) -- an architecture able to induce interpretable LISP-like programs from observed data traces. We propose an optimisation procedure for program learning based on backpropagation, gradient descent and A* search. We apply the proposed method to two problems: system identification of dynamical systems and explaining the behaviour of a DQN agent. Our results show that the $π$-machine can efficiently induce interpretable programs from individual data traces.
Exponentially Twisted Sampling: a Unified Approach for Centrality Analysis in Attributed Networks
Venue: arXiv cs.SI 2017
Year: 2017

In our recent works, we developed a probabilistic framework for structural analysis in undirected networks and directed networks. The key idea of that framework is to sample a network by a symmetric and asymmetric bivariate distribution and then use that bivariate distribution to formerly defining various notions, including centrality, relative centrality, community, and modularity. The main objective of this paper is to extend the probabilistic definition to attributed networks, where sampling bivariate distributions by exponentially twisted sampling. Our main finding is that we find a way to deal with the sampling of the attributed network including signed network. By using the sampling method, we define the various centralities in attributed networks. The influence centralities and trust centralities correctly show that how to identify centralities in signed network. The advertisement-specific influence centralities also perfectly define centralities when the attributed networks that have node attribute. Experimental results on real-world dataset demonstrate the different centralities with changing the temperature. Further experiments are conducted to gain a deeper understanding of the importance of the temperature.