OpenRaiser/Intern-Atlas huggingface dataset:
A Polynomial Time Algorithm for Spatio-Temporal Security Games
Venue: arXiv cs.GT 2017
Year: 2017

An ever-important issue is protecting infrastructure and other valuable targets from a range of threats from vandalism to theft to piracy to terrorism. The "defender" can rarely afford the needed resources for a 100% protection. Thus, the key question is, how to provide the best protection using the limited available resources. We study a practically important class of security games that is played out in space and time, with targets and "patrols" moving on a real line. A central open question here is whether the Nash equilibrium (i.e., the minimax strategy of the defender) can be computed in polynomial time. We resolve this question in the affirmative. Our algorithm runs in time polynomial in the input size, and only polylogarithmic in the number of possible patrol locations (M). Further, we provide a continuous extension in which patrol locations can take arbitrary real values. Prior work obtained polynomial-time algorithms only under a substantial assumption, e.g., a constant number of rounds. Further, all these algorithms have running times polynomial in M, which can be very large.
Evolutionary Data Systems
Venue: arXiv cs.DB 2017
Year: 2017

Anyone in need of a data system today is confronted with numerous complex options in terms of system architectures, such as traditional relational databases, NoSQL and NewSQL solutions as well as several sub-categories like column-stores, row-stores etc. This overwhelming array of choices makes bootstrapping data-driven applications difficult and time consuming, requiring expertise often not accessible due to cost issues (e.g., to scientific labs or small businesses). In this paper, we present the vision of evolutionary data systems that free systems architects and application designers from the complex, cumbersome and expensive process of designing and tuning specialized data system architectures that fit only a single, static application scenario. Setting up an evolutionary system is as simple as identifying the data. As new data and queries come in, the system automatically evolves so that its architecture matches the properties of the incoming workload at all times. Inspired by the theory of evolution, at any given point in time, an evolutionary system may employ multiple competing solutions down at the low level of database architectures -- characterized as combinations of data layouts, access methods and execution strategies. Over time, "the fittest wins" and becomes the dominant architecture until the environment (workload) changes. In our initial prototype, we demonstrate solutions that can seamlessly evolve (back and forth) between a key-value store and a column-store architecture in order to adapt to changing workloads.
CFI CaRE: Hardware-supported Call and Return Enforcement for Commercial Microcontrollers
Venue: arXiv cs.CR 2017
Year: 2017

With the increasing scale of deployment of Internet of Things (IoT), concerns about IoT security have become more urgent. In particular, memory corruption attacks play a predominant role as they allow remote compromise of IoT devices. Control-flow integrity (CFI) is a promising and generic defense technique against these attacks. However, given the nature of IoT deployments, existing protection mechanisms for traditional computing environments (including CFI) need to be adapted to the IoT setting. In this paper, we describe the challenges of enabling CFI on microcontroller (MCU) based IoT devices. We then present CaRE, the first interrupt-aware CFI scheme for low-end MCUs. CaRE uses a novel way of protecting the CFI metadata by leveraging TrustZone-M security extensions introduced in the ARMv8-M architecture. Its binary instrumentation approach preserves the memory layout of the target MCU software, allowing pre-built bare-metal binary code to be protected by CaRE. We describe our implementation on a Cortex-M Prototyping System and demonstrate that CaRE is secure while imposing acceptable performance and memory impact.
An exploration to visualize finite element data with a DSL
Venue: arXiv cs.HC 2017
Year: 2017

The scientific community use PDEs to model a range of problems. The people in this domain are interested in visualizing their results, but existing mechanisms for visualization can not handle the full richness of computations in the domain. We did an exploration to see how Diderot, a domain specific language for scientific visualization and image analysis, could be used to solve this problem. We demonstrate our first and modest approach of visualizing FE data with Diderot and provide examples. Using Diderot, we do a simple sampling and a volume rendering of a FE field. These examples showcase Diderot's ability to provide a visualization result for Firedrake. This paper describes the extension of the Diderot language to include FE data.
Families of Distributed Memory Parallel Graph Algorithms from Self-Stabilizing Kernels-An SSSP Case Study
Venue: arXiv cs.DC 2017
Year: 2017

Self-stabilizing algorithms are an important because of their robustness and guaranteed convergence. Starting from any arbitrary state, a self-stabilizing algorithm is guaranteed to converge to a legitimate state.Those algorithms are not directly amenable to solving distributed graph processing problems when performance and scalability are important. In this paper, we show the "Abstract Graph Machine" (AGM) model that can be used to convert self-stabilizing algorithms into forms suitable for distributed graph processing. An AGM is a mathematical model of parallel computation on graphs that adds work dependency and ordering to self-stabilizing algorithms. Using the AGM model we show that some of the existing distributed Single Source Shortest Path (SSSP) algorithms are actually specializations of self-stabilizing SSSP. We extend the AGM model to apply more fine-grained orderings at different spatial levels to derive additional scalable variants of SSSP algorithms, essentially enabling the algorithm to be generated for a specific target architecture. Experimental results show that this approach can generate new algorithmic variants that out-perform standard distributed algorithms for SSSP.
A Divide and Conquer Approach to Cooperative Distributed Model Predictive Control
Venue: arXiv cs.SY 2017
Year: 2017

This paper is concerned with the design of cooperative distributed Model Predictive Control (MPC) for linear systems. Motivated by the special structure of the distributed models in some existing literature, we propose to apply a state transformation to the original system and global cost function. This has major implications on the closed-loop stability analysis and the mechanism of the resultant cooperative framework. It turns out that the proposed framework can be implemented without cooperative iterations being performed in the local optimizations, thus allowing one to compute the local inputs in parallel and independently from each other while requiring only partial plant-wide state information. The proposed framework can also be realized with cooperative iterations, thereby keeping the advantages of the technique in the former reference. Under certain conditions, closed-loop stability for both implementation procedures can be guaranteed a priori by appropriate selections of the original local cost functions. The strengths and benefits of the proposed method are highlighted by means of two numerical examples.
Code Constructions based on Reed-Solomon Codes
Venue: arXiv cs.IT 2017
Year: 2017

Reed--Solomon codes are a well--studied code class which fulfill the Singleton bound with equality. However, their length is limited to the size $q$ of the underlying field $\mathbb{F}_q$. In this paper we present a code construction which yields codes with lengths of factors of the field size. Furthermore a decoding algorithm beyond half the minimum distance is given and analyzed.
Deadline-Aware Multipath Communication: An Optimization Problem
Venue: arXiv cs.NI 2017
Year: 2017

Multipath communication not only allows improved throughput but can also be used to leverage different path characteristics to best fulfill each application's objective. In particular, certain delay-sensitive applications, such as real time voice and video communications, can usually withstand packet loss and aim to maximize throughput while keeping latency at a reasonable level. In such a context, one hard problem is to determine along which path the data should be transmitted or retransmitted. In this paper, we formulate this problem as a linear optimization, show bounds on the performance that can be obtained in a multipath paradigm, and show that path diversity is a strong asset for improving network performance. We also discuss how these theoretical limits can be approached in practice and present simulation results.
LiDAR point clouds correction acquired from a moving car based on CAN-bus data
Venue: arXiv cs.RO 2017
Year: 2017

In this paper, we investigate the impact of different kind of car trajectories on LiDAR scans. In fact, LiDAR scanning speeds are considerably slower than car speeds introducing distortions. We propose a method to overcome this issue as well as new metrics based on CAN bus data. Our results suggest that the vehicle trajectory should be taken into account when building 3D large-scale maps from a LiDAR mounted on a moving vehicle.
Time Complexity of Constraint Satisfaction via Universal Algebra
Venue: arXiv cs.CC 2017
Year: 2017

The exponential-time hypothesis (ETH) states that 3-SAT is not solvable in subexponential time, i.e. not solvable in O(c^n) time for arbitrary c > 1, where n denotes the number of variables. Problems like k-SAT can be viewed as special cases of the constraint satisfaction problem (CSP), which is the problem of determining whether a set of constraints is satisfiable. In this paper we study thef worst-case time complexity of NP-complete CSPs. Our main interest is in the CSP problem parameterized by a constraint language Gamma (CSP(Gamma)), and how the choice of Gamma affects the time complexity. It is believed that CSP(Gamma) is either tractable or NP-complete, and the algebraic CSP dichotomy conjecture gives a sharp delineation of these two classes based on algebraic properties of constraint languages. Under this conjecture and the ETH, we first rule out the existence of subexponential algorithms for finite-domain NP-complete CSP(Gamma) problems. This result also extends to certain infinite-domain CSPs and structurally restricted CSP(Gamma) problems. We then begin a study of the complexity of NP-complete CSPs where one is allowed to arbitrarily restrict the values of individual variables, which is a very well-studied subclass of CSPs. For such CSPs with finite domain D, we identify a relation SD such that (1) CSP({SD}) is NP-complete and (2) if CSP(Gamma) over D is NP-complete and solvable in O(c^n) time, then CSP({SD}) is solvable in O(c^n) time, too. Hence, the time complexity of CSP({SD}) is a lower bound for all CSPs of this particular kind. We also prove that the complexity of CSP({SD}) is decreasing when |D| increases, unless the ETH is false. This implies, for instance, that for every c>1 there exists a finite-domain Gamma such that CSP(Gamma) is NP-complete and solvable in O(c^n) time.
Evidence Logics with Relational Evidence
Venue: arXiv cs.LO 2017
Year: 2017

Dynamic evidence logics are logics for reasoning about the evidence and evidence-based beliefs of agents in a dynamic environment. In this paper, we introduce a family of logics for reasoning about relational evidence: evidence that involves an orderings of states in terms of their relative plausibility. We provide sound and complete axiomatizations for the logics. We also present several evidential actions and prove soundness and completeness for the associated dynamic logics.
Data protection by means of fragmentation in various different distributed storage systems - a survey
Venue: arXiv cs.CR 2017
Year: 2017

This paper analyzes various distributed storage systems that use data fragmentation and dispersal as a way of protection.Existing solutions have been organized into two categories: bitwise and structurewise. Systems from the bitwise category are operating on unstructured data and in a uniform environment. Those having structured input data with predefined confidentiality level and disposing of a heterogeneous environment in terms of machine trustworthiness were classified as structurewise. Furthermore, we outline high-level requirements and desirable architecture traits of an eficient data fragmentation system, which will address performance (including latency), availability, resilience and scalability.
Complete Semantics to empower Touristic Service Providers
Venue: arXiv cs.IR 2017
Year: 2017

The tourism industry has a significant impact on the world's economy, contributes 10.2% of the world's gross domestic product in 2016. It becomes a very competitive industry, where having a strong online presence is an essential aspect for business success. To achieve this goal, the proper usage of latest Web technologies, particularly schema.org annotations is crucial. In this paper, we present our effort to improve the online visibility of touristic service providers in the region of Tyrol, Austria, by creating and deploying a substantial amount of semantic annotations according to schema.org, a widely used vocabulary for structured data on the Web. We started our work from Tourismusverband (TVB) Mayrhofen-Hippach and all touristic service providers in the Mayrhofen-Hippach region and applied the same approach to other TVBs and regions, as well as other use cases. The rationale for doing this is straightforward. Having schema.org annotations enables search engines to understand the content better, and provide better results for end users, as well as enables various intelligent applications to utilize them. As a direct consequence, the region of Tyrol and its touristic service increase their online visibility and decrease the dependency on intermediaries, i.e. Online Travel Agency (OTA).
Guided Depth Upsampling for Precise Mapping of Urban Environments
Venue: arXiv cs.CG 2017
Year: 2017

We present an improved model for MRF-based depth upsampling, guided by image- as well as 3D surface normal features. By exploiting the underlying camera model we define a novel regularization term that implicitly evaluates the planarity of arbitrary oriented surfaces. Our method improves upsampling quality in scenes composed of predominantly planar surfaces, such as urban areas. We use a synthetic dataset to demonstrate that our approach outperforms recent methods that implement distance-based regularization terms. Finally, we validate our approach for mapping applications on our experimental vehicle.
The $\mathcal{E}$-Average Common Submatrix: Approximate Searching in a Restricted Neighborhood
Venue: arXiv cs.CV 2017
Year: 2017

This paper introduces a new (dis)similarity measure for 2D arrays, extending the Average Common Submatrix measure. This is accomplished by: (i) considering the frequency of matching patterns, (ii) restricting the pattern matching to a fixed-size neighborhood, and (iii) computing a distance-based approximate matching. This will achieve better performances with low execution time and larger information retrieval.
Lessons Learnt from Field Trials of a Robotic Sweet Pepper Harvester
Venue: arXiv cs.RO 2017
Year: 2017

In this paper, we present the lessons learnt during the development of a new robotic harvester (Harvey) that can autonomously harvest sweet pepper (capsicum) in protected cropping environments. Robotic harvesting offers an attractive potential solution to reducing labour costs while enabling more regular and selective harvesting, optimising crop quality, scheduling and therefore profit. Our approach combines effective vision algorithms with a novel end-effector design to enable successful harvesting of sweet peppers. We demonstrate a simple and effective vision-based algorithm for crop detection, a grasp selection method, and a novel end-effector design for harvesting. To reduce the complexity of motion planning and to minimise occlusions we focus on picking sweet peppers in a protected cropping environment where plants are grown on planar trellis structures. Initial field trials in protected cropping environments, with two cultivars, demonstrate the efficacy of this approach. The results show that the robot harvester can successfully detect, grasp, and detach crop from the plant within a real protected cropping system. The novel contributions of this work have resulted in significant and encouraging improvements in sweet pepper picking success rates compared with the state-of-the-art. Future work will look at detecting sweet pepper peduncles and improving the total harvesting cycle time for each sweet pepper. The methods presented in this paper provide steps towards the goal of fully autonomous and reliable crop picking systems that will revolutionise the horticulture industry by reducing labour costs, maximising the quality of produce, and ultimately improving the sustainability of farming enterprises.
On the Optimality of Secure Communication Without Using Cooperative Jamming
Venue: arXiv cs.IT 2017
Year: 2017

We consider secure communication over a two-user Gaussian interference channel, where each transmitter sends a confidential message to its legitimate receiver. For this setting, we identify a regime where the simple scheme of using Gaussian wiretap codebook at each transmitter (without cooperative jamming) and treating interference as noise at each intended receiver (in short, GWC-TIN scheme) achieves the optimal secure sum capacity to within a constant gap. The results are proved by first considering the deterministic interference channel model and identifying a regime in which a simple scheme without using cooperative jamming is optimal in terms of secure sum capacity. For the symmetric case of the deterministic model, this simple scheme is optimal if and only if the interference-to-signal ratio (in channel strengths) is no more than 2/3.
Leveraging Sensory Data in Estimating Transformer Lifetime
Venue: arXiv cs.SY 2017
Year: 2017

Transformer lifetime assessments plays a vital role in reliable operation of power systems. In this paper, leveraging sensory data, an approach in estimating transformer lifetime is presented. The winding hottest-spot temperature, which is the pivotal driver that impacts transformer aging, is measured hourly via a temperature sensor, then transformer loss of life is calculated based on the IEEE Std. C57.91-2011. A Cumulative Moving Average (CMA) model is subsequently applied to the data stream of the transformer loss of life to provide hourly estimates until convergence. Numerical examples demonstrate the effectiveness of the proposed approach for the transformer lifetime estimation, and explores its efficiency and practical merits.
The well-separated pair decomposition for balls
Venue: arXiv cs.CG 2017
Year: 2017

Given a real number $t>1$, a geometric $t$-spanner is a geometric graph for a point set in $\mathbb{R}^d$ with straight lines between vertices such that the ratio of the shortest-path distance between every pair of vertices in the graph (with Euclidean edge lengths) to their actual Euclidean distance is at most $t$. An imprecise point set is modeled by a set $R$ of regions in $\mathbb{R}^d$. If one chooses a point in each region of $R$, then the resulting point set is called a precise instance of~$R$. An imprecise $t$-spanner for an imprecise point set $R$ is a graph $G=(R,E)$ such that for each precise instance $S$ of $R$, graph $G_S=(S,E_S)$, where $E_S$ is the set of edges corresponding to $E$, is a $t$-spanner. In this paper, we show that, given a real number $t>1$, there is an imprecise point set $R$ of $n$ straight-line segments in the plane such that any imprecise $t$-spanner for $R$ has $Ω(n^2)$ edges. Then, we propose an algorithm that computes a Well-Separated Pair Decomposition (WSPD) of size ${\cal O}(n)$ for a set of $n$ pairwise disjoint $d$-dimensional balls with arbitrary sizes. Given a real number $t>1$ and given a set of $n$ pairwise disjoint $d$-balls with arbitrary sizes, we use this WSPD to compute in ${\cal O}(n\log n+n/(t-1)^d)$ time an imprecise $t$-spanner with ${\cal O}(n/(t-1)^d)$ edges for balls.
pyRecLab: A Software Library for Quick Prototyping of Recommender Systems
Venue: arXiv cs.SE 2017
Year: 2017

This paper introduces pyRecLab, a software library written in C++ with Python bindings which allows to quickly train, test and develop recommender systems. Although there are several software libraries for this purpose, only a few let developers to get quickly started with the most traditional methods, permitting them to try different parameters and approach several tasks without a significant loss of performance. Among the few libraries that have all these features, they are available in languages such as Java, Scala or C#, what is a disadvantage for less experienced programmers more used to the popular Python programming language. In this article we introduce details of pyRecLab, showing as well performance analysis in terms of error metrics (MAE and RMSE) and train/test time. We benchmark it against the popular Java-based library LibRec, showing similar results. We expect programmers with little experience and people interested in quickly prototyping recommender systems to be benefited from pyRecLab.
Mining Significant Microblogs for Misinformation Identification: An Attention-based Approach
Venue: arXiv cs.IR 2017
Year: 2017

With the rapid growth of social media, massive misinformation is also spreading widely on social media, such as microblog, and bring negative effects to human life. Nowadays, automatic misinformation identification has drawn attention from academic and industrial communities. For an event on social media usually consists of multiple microblogs, current methods are mainly based on global statistical features. However, information on social media is full of noisy and outliers, which should be alleviated. Moreover, most of microblogs about an event have little contribution to the identification of misinformation, where useful information can be easily overwhelmed by useless information. Thus, it is important to mine significant microblogs for a reliable misinformation identification method. In this paper, we propose an Attention-based approach for Identification of Misinformation (AIM). Based on the attention mechanism, AIM can select microblogs with largest attention values for misinformation identification. The attention mechanism in AIM contains two parts: content attention and dynamic attention. Content attention is calculated based textual features of each microblog. Dynamic attention is related to the time interval between the posting time of a microblog and the beginning of the event. To evaluate AIM, we conduct a series of experiments on the Weibo dataset and the Twitter dataset, and the experimental results show that the proposed AIM model outperforms the state-of-the-art methods.
Session Analysis using Plan Recognition
Venue: arXiv cs.AI 2017
Year: 2017

This paper presents preliminary results of our work with a major financial company, where we try to use methods of plan recognition in order to investigate the interactions of a costumer with the company's online interface. In this paper, we present the first steps of integrating a plan recognition algorithm in a real-world application for detecting and analyzing the interactions of a costumer. It uses a novel approach for plan recognition from bare-bone UI data, which reasons about the plan library at the lowest recognition level in order to define the relevancy of actions in our domain, and then uses it to perform plan recognition. We present preliminary results of inference on three different use-cases modeled by domain experts from the company, and show that this approach manages to decrease the overload of information required from an analyst to evaluate a costumer's session - whether this is a malicious or benign session, whether the intended tasks were completed, and if not - what actions are expected next.