OpenRaiser/Intern-Atlas huggingface dataset:
Near-Optimal Distributed Band-Joins through Recursive Partitioning
Venue: arXiv cs.DB 2020
Year: 2020

We consider running-time optimization for band-joins in a distributed system, e.g., the cloud. To balance load across worker machines, input has to be partitioned, which causes duplication. We explore how to resolve this tension between maximum load per worker and input duplication for band-joins between two relations. Previous work suffered from high optimization cost or considered partitionings that were too restricted (resulting in suboptimal join performance). Our main insight is that recursive partitioning of the join-attribute space with the appropriate split scoring measure can achieve both low optimization cost and low join cost. It is the first approach that is not only effective for one-dimensional band-joins but also for joins on multiple attributes. Experiments indicate that our method is able to find partitionings that are within 10% of the lower bound for both maximum load per worker and input duplication for a broad range of settings, significantly improving over previous work.
An Efficient UAV-based Artificial Intelligence Framework for Real-Time Visual Tasks
Venue: arXiv cs.CV 2020
Year: 2020

Modern Unmanned Aerial Vehicles equipped with state of the art artificial intelligence (AI) technologies are opening to a wide plethora of novel and interesting applications. While this field received a strong impact from the recent AI breakthroughs, most of the provided solutions either entirely rely on commercial software or provide a weak integration interface which denies the development of additional techniques. This leads us to propose a novel and efficient framework for the UAV-AI joint technology. Intelligent UAV systems encounter complex challenges to be tackled without human control. One of these complex challenges is to be able to carry out computer vision tasks in real-time use cases. In this paper we focus on this challenge and introduce a multi-layer AI (MLAI) framework to allow easy integration of ad-hoc visual-based AI applications. To show its features and its advantages, we implemented and evaluated different modern visual-based deep learning models for object detection, target tracking and target handover.
Distributed Learning: Sequential Decision Making in Resource-Constrained Environments
Venue: arXiv cs.LG 2020
Year: 2020

We study cost-effective communication strategies that can be used to improve the performance of distributed learning systems in resource-constrained environments. For distributed learning in sequential decision making, we propose a new cost-effective partial communication protocol. We illustrate that with this protocol the group obtains the same order of performance that it obtains with full communication. Moreover, we prove that under the proposed partial communication protocol the communication cost is $O(\log T)$, where $T$ is the time horizon of the decision-making process. This improves significantly on protocols with full communication, which incur a communication cost that is $O(T)$. We validate our theoretical results using numerical simulations.
PoKi: A Large Dataset of Poems by Children
Venue: arXiv cs.CL 2020
Year: 2020

Child language studies are crucial in improving our understanding of child well-being; especially in determining the factors that impact happiness, the sources of anxiety, techniques of emotion regulation, and the mechanisms to cope with stress. However, much of this research is stymied by the lack of availability of large child-written texts. We present a new corpus of child-written text, PoKi, which includes about 62 thousand poems written by children from grades 1 to 12. PoKi is especially useful in studying child language because it comes with information about the age of the child authors (their grade). We analyze the words in PoKi along several emotion dimensions (valence, arousal, dominance) and discrete emotions (anger, fear, sadness, joy). We use non-parametric regressions to model developmental differences from early childhood to late-adolescence. Results show decreases in valence that are especially pronounced during mid-adolescence, while arousal and dominance peaked during adolescence. Gender differences in the developmental trajectory of emotions are also observed. Our results support and extend the current state of emotion development research.
A Hierarchical Model for Fast Distributed Consensus in Dynamic Networks
Venue: arXiv cs.DC 2020
Year: 2020

We present two new consensus algorithms for dynamic networks. The first, Fast Raft, is a variation on the Raft consensus algorithm that reduces the number of message rounds in typical operation. Fast Raft is ideal for fast-paced distributed systems where membership changes over time and where sites must reach consensus quickly. The second, C-Raft, is targeted for distributed systems where sites are grouped into clusters, with fast communication within clusters and slower communication between clusters. C-Raft uses Fast Raft as a building block and defines a hierarchical model of consensus to improve upon throughput in globally distributed systems. We prove the safety and liveness properties of each algorithm. Finally, we present an experimental evaluation of both algorithms in AWS.
A Robust Reputation-based Group Ranking System and its Resistance to Bribery
Venue: arXiv cs.IR 2020
Year: 2020

The spread of online reviews and opinions and its growing influence on people's behavior and decisions, boosted the interest to extract meaningful information from this data deluge. Hence, crowdsourced ratings of products and services gained a critical role in business and governments. Current state-of-the-art solutions rank the items with an average of the ratings expressed for an item, with a consequent lack of personalization for the users, and the exposure to attacks and spamming/spurious users. Using these ratings to group users with similar preferences might be useful to present users with items that reflect their preferences and overcome those vulnerabilities. In this paper, we propose a new reputation-based ranking system, utilizing multipartite rating subnetworks, which clusters users by their similarities using three measures, two of them based on Kolmogorov complexity. We also study its resistance to bribery and how to design optimal bribing strategies. Our system is novel in that it reflects the diversity of preferences by (possibly) assigning distinct rankings to the same item, for different groups of users. We prove the convergence and efficiency of the system. By testing it on synthetic and real data, we see that it copes better with spamming/spurious users, being more robust to attacks than state-of-the-art approaches. Also, by clustering users, the effect of bribery in the proposed multipartite ranking system is dimmed, comparing to the bipartite case.
Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal
Venue: arXiv cs.CG 2020
Year: 2020

Given a collection of $n$ points in $\mathbb{R}^d$, the goal of the $(k,z)$-clustering problem is to find a subset of $k$ "centers" that minimizes the sum of the $z$-th powers of the Euclidean distance of each point to the closest center. Special cases of the $(k,z)$-clustering problem include the $k$-median and $k$-means problems. Our main result is a unified two-stage importance sampling framework that constructs an $\varepsilon$-coreset for the $(k,z)$-clustering problem. Compared to the results for $(k,z)$-clustering in [Feldman and Langberg, STOC 2011], our framework saves a $\varepsilon^2 d$ factor in the coreset size. Compared to the results for $(k,z)$-clustering in [Sohler and Woodruff, FOCS 2018], our framework saves a $\operatorname{poly}(k)$ factor in the coreset size and avoids the $\exp(k/\varepsilon)$ term in the construction time. Specifically, our coreset for $k$-median ($z=1$) has size $\tilde{O}(\varepsilon^{-4} k)$ which, when compared to the result in [Sohler and Woodruff, STOC 2018], saves a $k$ factor in the coreset size. Our algorithmic results rely on a new dimensionality reduction technique that connects two well-known shape fitting problems: subspace approximation and clustering, and may be of independent interest. We also provide a size lower bound of $Ω\left(k\cdot \min \left\{2^{z/20},d \right\}\right)$ for a $0.01$-coreset for $(k,z)$-clustering, which has a linear dependence of size on $k$ and an exponential dependence on $z$ that matches our algorithmic results.
A Demonstration of Issues with Value-Based Multiobjective Reinforcement Learning Under Stochastic State Transitions
Venue: arXiv cs.LG 2020
Year: 2020

We report a previously unidentified issue with model-free, value-based approaches to multiobjective reinforcement learning in the context of environments with stochastic state transitions. An example multiobjective Markov Decision Process (MOMDP) is used to demonstrate that under such conditions these approaches may be unable to discover the policy which maximises the Scalarised Expected Return, and in fact may converge to a Pareto-dominated solution. We discuss several alternative methods which may be more suitable for maximising SER in MOMDPs with stochastic transitions.
Gelato: Feedback-driven and Guided Security Analysis of Client-side Web Applications
Venue: arXiv cs.SE 2020
Year: 2020

Even though a lot of effort has been invested in analyzing client-side web applications during the past decade, the existing tools often fail to deal with the complexity of modern JavaScript applications. However, from an attacker point of view, the client side of such web applications can reveal invaluable information about the server side. In this paper, first we study the existing tools and enumerate the most crucial features a security-aware client-side analysis should be supporting. Next, we propose GELATO to detect vulnerabilities in modern client-side JavaScript applications that are built upon complex libraries and frameworks. In particular, we take the first step in closing the gap between state-aware crawling and client-side security analysis by proposing a feedback-driven security-aware guided crawler that is able to analyze complex frameworks automatically, and increase the coverage of security-sensitive parts of the program efficiently. Moreover, we propose a new lightweight client-side taint analysis that outperforms the start-of-the-art tools, requires no modification to browsers, and reports non-trivial taint flows on modern JavaScript applications.
Budget Learning via Bracketing
Venue: arXiv cs.LG 2020
Year: 2020

Conventional machine learning applications in the mobile/IoT setting transmit data to a cloud-server for predictions. Due to cost considerations (power, latency, monetary), it is desirable to minimise device-to-server transmissions. The budget learning (BL) problem poses the learner's goal as minimising use of the cloud while suffering no discernible loss in accuracy, under the constraint that the methods employed be edge-implementable. We propose a new formulation for the BL problem via the concept of bracketings. Concretely, we propose to sandwich the cloud's prediction, $g,$ via functions $h^-, h^+$ from a `simple' class so that $h^- \le g \le h^+$ nearly always. On an instance $x$, if $h^+(x)=h^-(x)$, we leverage local processing, and bypass the cloud. We explore theoretical aspects of this formulation, providing PAC-style learnability definitions; associating the notion of budget learnability to approximability via brackets; and giving VC-theoretic analyses of their properties. We empirically validate our theory on real-world datasets, demonstrating improved performance over prior gating based methods.
Addressing Packet Dropping Misbehavior using Metaheuristic Approach: A Survey
Venue: arXiv cs.NI 2020
Year: 2020

A Mobile Ad hoc Network can be said as a collection of mobile nodes, which builds a dynamic topology and a resource constrained network. Due to dynamic nature routing is challenging in MANET. In Mobile Ad hoc Networks different type of attack is possible. By manipulation in routing and attacks against data are reasoned by malicious nodes. MANETs are susceptible to various attacks from selfish nodes. To defeat those problems security is demanded for preventing node from various attacks. Metaheuristic techniques are used for addressing a problem found in ad hoc networks such as routing, security and optimization. A lot of research has been carried out for secure routing process with metaheuristic approaches. In this paper, we present survey of metaheuristic approach to improve routing process by enhancing the security and optimization among different nodes in mobile ad hoc networks.
Test Automation Process Improvement in a DevOpsTeam: Experience Report
Venue: arXiv cs.SE 2020
Year: 2020

How to successfully conduct test automation process improvement (TAPI) for continuous development, consisting of iterative software development, continuous testing, and delivery, is the challenge faced by many software organizations. In this paper, we present an experience report on TAPI in one DevOps team in F-Secure (a Finnish software company). The team builds Windows application software and exists in F-Secure's TAPI culture. The team self-reports high satisfaction and maturity in test automation for continuous development. To study their TAPI, we reviewed a collection of experience notes, team reflection reports and telemetry result reports. Then several meetings were held to discuss the details. We found that based on the understanding of the team, test automation maturity for continuous development is defined as a set of indicators, e.g., the increasing speed to release, improving the productivity of the team, high test efficiency. Second, the team indicated that a set of critical success factors have a major impact on successfully carrying out its TAPI, e.g., incremental approach, the whole team effort, test tool choice and architecture, telemetry. Third, we compare the TAPI practices in the observed team with the practices described in prior literature. The team believes that the existing test automation maturity approaches should include the identified practices like the whole team effort to build a more comprehensive test automation improvement model for the software industry.
PASTRAMI: Privacy-preserving, Auditable, Scalable & Trustworthy Auctions for Multiple Items
Venue: arXiv cs.CR 2020
Year: 2020

Decentralised cloud computing platforms enable individuals to offer and rent resources in a peer-to-peer fashion. They must assign resources from multiple sellers to multiple buyers and derive prices that match the interests and capacities of both parties. The assignment process must be decentralised, fair and transparent, but also protect the privacy of buyers. We present PASTRAMI, a decentralised platform enabling trustworthy assignments of items and prices between a large number of sellers and bidders, through the support of multi-item auctions. PASTRAMI uses threshold blind signatures and commitment schemes to provide strong privacy guarantees while making bidders accountable. It leverages the Ethereum blockchain for auditability, combining efficient off-chain computations with novel, on-chain proofs of misbehaviour. Our evaluation of PASTRAMI using Filecoin workloads show its ability to efficiently produce trustworthy assignments between thousands of buyers and sellers.
Efficient Approximation Algorithms for Adaptive Influence Maximization
Venue: arXiv cs.SI 2020
Year: 2020

Given a social network $G$ and an integer $k$, the influence maximization (IM) problem asks for a seed set $S$ of $k$ nodes from $G$ to maximize the expected number of nodes influenced via a propagation model. The majority of the existing algorithms for the IM problem are developed only under the non-adaptive setting, i.e., where all $k$ seed nodes are selected in one batch without observing how they influence other users in real world. In this paper, we study the adaptive IM problem where the $k$ seed nodes are selected in batches of equal size $b$, such that the $i$-th batch is identified after the actual influence results of the former $i-1$ batches are observed. In this paper, we propose the first practical algorithm for the adaptive IM problem that could provide the worst-case approximation guarantee of $1-\mathrm{e}^{ρ_b(\varepsilon-1)}$, where $ρ_b=1-(1-1/b)^b$ and $\varepsilon \in (0, 1)$ is a user-specified parameter. In particular, we propose a general framework AdaptGreedy that could be instantiated by any existing non-adaptive IM algorithms with expected approximation guarantee. Our approach is based on a novel randomized policy that is applicable to the general adaptive stochastic maximization problem, which may be of independent interest. In addition, we propose a novel non-adaptive IM algorithm called EPIC which not only provides strong expected approximation guarantee, but also presents superior performance compared with the existing IM algorithms. Meanwhile, we clarify some existing misunderstandings in recent work and shed light on further study of the adaptive IM problem. We conduct experiments on real social networks to evaluate our proposed algorithms comprehensively, and the experimental results strongly corroborate the superiorities and effectiveness of our approach.
BugDoc: Algorithms to Debug Computational Processes
Venue: arXiv cs.DB 2020
Year: 2020

Data analysis for scientific experiments and enterprises, large-scale simulations, and machine learning tasks all entail the use of complex computational pipelines to reach quantitative and qualitative conclusions. If some of the activities in a pipeline produce erroneous outputs, the pipeline may fail to execute or produce incorrect results. Inferring the root cause(s) of such failures is challenging, usually requiring time and much human thought, while still being error-prone. We propose a new approach that makes use of iteration and provenance to automatically infer the root causes and derive succinct explanations of failures. Through a detailed experimental evaluation, we assess the cost, precision, and recall of our approach compared to the state of the art. Our experimental data and processing software is available for use, reproducibility, and enhancement.
FAST-Hex -- A Morphing Hexarotor: Design, Mechanical Implementation, Control and Experimental Validation
Venue: arXiv cs.RO 2020
Year: 2020

We present FAST-Hex, a micro aerial hexarotor platform that allows to seamlessly transit from an under-actuated to a fully-actuated configuration with only one additional control input, a motor that synchronously tilts all propellers. The FAST-Hex adapts its configuration between the more efficient but under-actuated, collinear multi-rotors and the less efficient, but full-pose-tracking, which is attained by non-collinear multi-rotors. On the basis of prior work on minimal input configurable micro aerial vehicle we mainly stress three aspects: mechanical design, motion control and experimental validation. Specifically, we present the lightweight mechanical structure of the FAST-Hex that allows it to only use one additional input to achieve configurability and full actuation in a vast state space. The motion controller receives as input any reference pose in $\mathbb{R}^3\times \mathrm{SO}(3)$ (3D position + 3D orientation). Full pose tracking is achieved if the reference pose is feasible with respect to actuator constraints. In case of unfeasibility a new feasible desired trajectory is generated online giving priority to the position tracking over the orientation tracking. Finally we present a large set of experimental results shading light on all aspects of the control and pose tracking of FAST-Hex.
Reduction Methods on Probabilistic Control-flow Programs for Reliability Analysis
Venue: arXiv cs.LO 2020
Year: 2020

Modern safety-critical systems are heterogeneous, complex, and highly dynamic. They require reliability evaluation methods that go beyond the classical static methods such as fault trees, event trees, or reliability block diagrams. Promising dynamic reliability analysis methods employ probabilistic model checking on various probabilistic state-based models. However, such methods have to tackle the well-known state-space explosion problem. To compete with this problem, reduction methods such as symmetry reduction and partial-order reduction have been successfully applied to probabilistic models by means of discrete Markov chains or Markov decision processes. Such models are usually specified using probabilistic programs provided in guarded command language. In this paper, we propose two automated reduction methods for probabilistic programs that operate on a purely syntactic level: reset value optimization and register allocation optimization. The presented techniques rely on concepts well known from compiler construction such as live range analysis and register allocation through interference graph coloring. Applied on a redundancy system model for an aircraft velocity control loop modeled in SIMULINK, we show effectiveness of our implementation of the reduction methods. We demonstrate that model-size reductions in three orders of magnitude are possible and show that we can achieve significant speedups for a reliability analysis.
Software-Based Monitoring and Analysis of a USB Host Controller Subject to Electrostatic Discharge
Venue: arXiv cs.OH 2020
Year: 2020

Observing, understanding, and mitigating the effects of failure in embedded systems is essential for building dependable control systems. We develop a software-based monitoring methodology to further this goal. This methodology can be applied to any embedded system peripheral and allows the system to operate normally while the monitoring software is running. We use software to instrument the operating system kernel and record indicators of system behavior. By comparing those indicators against baseline indicators of normal system operation, faults can be detected and appropriate action can be taken. We implement this methodology to detect faults caused by electrostatic discharge in a USB host controller. As indicators, we select specific control registers that provide a manifestation of the internal execution of the host controller. Analysis of the recorded register values reveals differences in system execution when the system is subject to interference. %We also develop a classifier capable of predicting whether or not the system's behavior is being affected by such shocks. This improved understanding of system behavior may lead to better hardware and software mitigation of electrostatic discharge and assist in root-cause analysis and repair of failures.