OpenRaiser/Intern-Atlas huggingface dataset:
Cluster Lifecycle Analysis: Challenges, Techniques, and Framework
Venue: arXiv cs.CY 2018
Year: 2018

Novel forms of data analysis methods have emerged as a significant research direction in the transportation domain. These methods can potentially help to improve our understanding of the dynamic flows of vehicles, people, and goods. Understanding these dynamics has economic and social consequences, which can improve the quality of life locally or worldwide. Aiming at this objective, a significant amount of research has focused on clustering moving objects to address problems in many domains, including the transportation, health, and environment. However, previous research has not investigated the lifecycle of a cluster, including cluster genesis, existence, and disappearance. The representation and analysis of cluster lifecycles can create novel avenues for research, result in new insights for analyses, and allow unique forms of prediction. This technical report focuses on studying the lifecycle of clusters by investigating the relations that a cluster has with moving elements and other clusters. This technical report also proposes a big data framework that manages the identification and processing of a cluster lifecycle. The ongoing research approach will lead to new ways to perform cluster analysis and advance the state of the art by leading to new insights related to cluster lifecycle. These results can have a significant impact on transport industry data science applications in a wide variety of areas, including congestion management, resource optimization, and hotspot management.
Dynamic Loop Scheduling Using MPI Passive-Target Remote Memory Access
Venue: arXiv cs.DC 2018
Year: 2018

Scientific applications often contain large computationally-intensive parallel loops. Loop scheduling techniques aim to achieve load balanced executions of such applications. For distributed-memory systems, existing dynamic loop scheduling (DLS) libraries are typically MPI-based, and employ a master-worker execution model to assign variably-sized chunks of loop iterations. The master-worker execution model may adversely impact performance due to the master-level contention. This work proposes a distributed chunk-calculation approach that does not require the master-worker execution scheme. Moreover, it considers the novel features in the latest MPI standards, such as passive-target remote memory access, shared-memory window creation, and atomic read-modify-write operations. To evaluate the proposed approach, five well-known DLS techniques, two applications, and two heterogeneous hardware setups have been considered. The DLS techniques implemented using the proposed approach outperformed their counterparts implemented using the traditional master-worker execution model.
RoboCup Junior in the Hunter Region: Driving the Future of Robotic STEM Education
Venue: arXiv cs.OH 2018
Year: 2018

RoboCup Junior is a project-oriented educational initiative that sponsors regional, national and international robotic events for young students in primary and secondary school. It leads children to the fundamentals of teamwork and complex problem solving through step-by-step logical thinking using computers and robots. The Faculty of Engineering and Built Environment at the University of Newcastle in Australia has hosted and organized the Hunter regional tournament since 2012. This paper presents an analysis of data collected from RoboCup Junior in the Hunter Region, New South Wales, Australia, for a period of six years 2012-2017 inclusive. Our study evaluates the effectiveness of the competition in terms of geographical spread, participation numbers, and gender balance. We also present a case study about current university students who have previously participated in RoboCup Junior.
Ethical Implications: The ACM/IEEE-CS Software Engineering Code applied to Tesla's "Autopilot" System
Venue: arXiv cs.CY 2018
Year: 2018

On October 14, 2015, Tesla Inc. an American electric car company, released the initial version of the Autopilot system. This system promised to provide semi-autonomous driving using the existing hardware already installed on Tesla vehicles. On March 23rd, 2018, a Tesla vehicle ran into a divider at highway speed, killing the driver. This occurred under the control of the Autopilot system with no driver intervention. Critics argue that though Tesla gives drivers warnings in its owner's manual, it is ultimately unethical to release a system that is marketed as an Autopilot yet still makes grave mistakes that any human driver would not make. Others defend Tesla by stating that their advisories are suitable and that drivers should ultimately be at fault for any mistakes of the Autopilot. This paper will scrutinize the ethical implications of Tesla's choice to develop, market, and ship a beta product that requires extensive testing. It will further analyze the implications of Tesla's aggressive advertisement of the product under the name Autopilot along with associated marketing materials. By applying the joint ACM/IEEE-CS Software Engineering Code of Ethics, this paper will show that Tesla's choices and actions during this event are inconsistent with the code and are unethical since they are responsible for adequately testing and honestly marketing their product.
Identifying influential nodes based on fuzzy local dimension in complex networks
Venue: arXiv cs.SI 2018
Year: 2018

How to identify influential nodes in complex networks is an important aspect in the study of complex network. In this paper, a novel fuzzy local dimension (FLD) is proposed to rank the influential nodes in complex networks, where a node with high fuzzy local dimension has high influential ability. This proposed method focuses on the influence of the distance from the center node on the local dimension of center node by fuzzy set, resulting in a change in influential ability. In order to show this proposed method's effectiveness and accuracy, four real-world networks are applied in this paper. Meanwhile, Susceptible-Infected (SI) is used to simulate the spreading process by FLD and other centrality measures, and Kendall's tau coefficient is used to describe the correlation between the influential nodes obtained by centrality and the results measured by SI model. Observing from the ranking lists and simulated results, this method is effective and accurate to rank the influential nodes.
Boundary Evolution Algorithm for SAT-NP
Venue: arXiv cs.NE 2018
Year: 2018

A boundary evolution Algorithm (BEA) is proposed by simultaneously taking into account the bottom and the high-level crossover and mutation, ie., the boundary of the hierarchical genetic algorithm. Operators and optimal individuals based on optional annealing are designed. Based on the numerous versions of genetic algorithm, the boundary evolution approach with crossover and mutation has been tested on the SAT problem and compared with two competing methods: a traditional genetic algorithm and another traditional hierarchical genetic algorithm, and among some others. The results of the comparative experiments in solving SAT problem have proved that the new hierarchical genetic algorithm based on simulated annealing and optimal individuals (BEA) can improve the success rate and convergence speed considerably for SAT problem due to its avoidance of both divergence and loss of optimal individuals, and by coronary, conducive to NP problem. Though more extensive comparisons are to be made on more algorithms, the consideration of the boundary elasticity of hierarchical genetic algorithm is an implication of evolutionary algorithm.
Timed Context-Free Temporal Logics
Venue: arXiv cs.LO 2018
Year: 2018

The paper is focused on temporal logics for the description of the behaviour of real-time pushdown reactive systems. The paper is motivated to bridge tractable logics specialized for expressing separately dense-time real-time properties and context-free properties by ensuring decidability and tractability in the combined setting. To this end we introduce two real-time linear temporal logics for specifying quantitative timing context-free requirements in a pointwise semantics setting: Event-Clock Nested Temporal Logic (EC_NTL) and Nested Metric Temporal Logic (NMTL). The logic EC_NTL is an extension of both the logic CaRet (a context-free extension of standard LTL) and Event-Clock Temporal Logic (a tractable real-time logical framework related to the class of Event-Clock automata). We prove that satisfiability of EC_NTL and visibly model-checking of Visibly Pushdown Timed Automata (VPTA) against EC_NTL are decidable and EXPTIME-complete. The other proposed logic NMTL is a context-free extension of standard Metric Temporal Logic (MTL). It is well known that satisfiability of future MTL is undecidable when interpreted over infinite timed words but decidable over finite timed words. On the other hand, we show that by augmenting future MTL with future context-free temporal operators, the satisfiability problem turns out to be undecidable also for finite timed words. On the positive side, we devise a meaningful and decidable fragment of the logic NMTL which is expressively equivalent to EC_NTL and for which satisfiability and visibly model-checking of VPTA are EXPTIME-complete.
Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
Venue: arXiv cs.AI 2019
Year: 2019

Message passing algorithms have proved surprisingly successful in solving hard constraint satisfaction problems on sparse random graphs. In such applications, variables are fixed sequentially to satisfy the constraints. Message passing is run after each step. Its outcome provides an heuristic to make choices at next step. This approach has been referred to as `decimation,' with reference to analogous procedures in statistical physics. The behavior of decimation procedures is poorly understood. Here we consider a simple randomized decimation algorithm based on belief propagation (BP), and analyze its behavior on random k-satisfiability formulae. In particular, we propose a tree model for its analysis and we conjecture that it provides asymptotically exact predictions in the limit of large instances. This conjecture is confirmed by numerical simulations.
ALLSAT compressed with wildcards: All, or all maximum independent sets
Venue: arXiv cs.DS 2019
Year: 2019

An odd cycle cover is a vertex set whose removal makes a graph bipartite. We show that if a $k$-element odd cycle cover of a graph with w vertices is known then all $N$ maximum anticliques (= independent sets) can be generated in time $O(2^k w^3 + N w^2))$. Generating ${\it all}\ N'$ anticliques (maximum or not) is easier and works for arbitrary graphs in time $O(N'w^2)$. In fact the use of wildcards allows to compactly generate the anticliques in clusters.
JBotSim, a Tool for Fast Prototyping of Distributed Algorithms in Dynamic Networks
Venue: arXiv cs.MS 2019
Year: 2019

JBotSim is a java library that offers basic primitives for prototyping, running, and visualizing distributed algorithms in dynamic networks. With JBotSim, one can implement an idea in minutes and interact with it ({\it e.g. }, add, move, or delete nodes) while it is running. JBotSim is well suited to prepare live demonstrations of your algorithms to colleagues or students; it can also be used to evaluate performance at the algorithmic level (number of messages, number of rounds, etc.). Unlike most tools, JBotSim is not an integrated environment. It is a lightweight library to be used in your program. In this paper, we present an overview of its distinctive features and architecture.
Maximizing Sequence-Submodular Functions and its Application to Online Advertising
Venue: arXiv cs.DM 2019
Year: 2019

Motivated by applications in online advertising, we consider a class of maximization problems where the objective is a function of the sequence of actions as well as the running duration of each action. For these problems, we introduce the concepts of \emph{sequence-submodularity} and \emph{sequence-monotonicity} which extend the notions of submodularity and monotonicity from functions defined over sets to functions defined over sequences. We establish that if the objective function is sequence-submodular and sequence-non-decreasing, then there exists a greedy algorithm that achieves $1-1/e$ of the optimal solution. We apply our algorithm and analysis to two applications in online advertising: online ad allocation and query rewriting. We first show that both problems can be formulated as maximizing non-decreasing sequence-submodular functions. We then apply our framework to these two problems, leading to simple greedy approaches with guaranteed performances. In particular, for online ad allocation problem the performance of our algorithm is $1-1/e$, which matches the best known existing performance, and for query rewriting problem the performance of our algorithm is $1- 1/e^{1-1/e}$ which improves upon the best known existing performance in the literature.
Complexity Classification in Infinite-Domain Constraint Satisfaction
Venue: arXiv cs.CC 2019
Year: 2019

A constraint satisfaction problem (CSP) is a computational problem where the input consists of a finite set of variables and a finite set of constraints, and where the task is to decide whether there exists a satisfying assignment of values to the variables. Depending on the type of constraints that we allow in the input, a CSP might be tractable, or computationally hard. In recent years, general criteria have been discovered that imply that a CSP is polynomial-time tractable, or that it is NP-hard. Finite-domain CSPs have become a major common research focus of graph theory, artificial intelligence, and finite model theory. It turned out that the key questions for complexity classification of CSPs are closely linked to central questions in universal algebra. This thesis studies CSPs where the variables can take values from an infinite domain. This generalization enhances dramatically the range of computational problems that can be modeled as a CSP. Many problems from areas that have so far seen no interaction with constraint satisfaction theory can be formulated using infinite domains, e.g. problems from temporal and spatial reasoning, phylogenetic reconstruction, and operations research. It turns out that the universal-algebraic approach can also be applied to study large classes of infinite-domain CSPs, yielding elegant complexity classification results. A new tool in this thesis that becomes relevant particularly for infinite domains is Ramsey theory. We demonstrate the feasibility of our approach with two complete complexity classification results: one on CSPs in temporal reasoning, the other on a generalization of Schaefer's theorem for propositional logic to logic over graphs. We also study the limits of complexity classification, and present classes of computational problems provably do not exhibit a complexity dichotomy into hard and easy problems.
Constructions of transitive latin hypercubes
Venue: arXiv cs.IT 2019
Year: 2019

A function $f:\{0,...,q-1\}^n\to\{0,...,q-1\}$ invertible in each argument is called a latin hypercube. A collection $(π_0,π_1,...,π_n)$ of permutations of $\{0,...,q-1\}$ is called an autotopism of a latin hypercube $f$ if $π_0f(x_1,...,x_n)=f(π_1x_1,...,π_n x_n)$ for all $x_1$, ..., $x_n$. We call a latin hypercube isotopically transitive (topolinear) if its group of autotopisms acts transitively (regularly) on all $q^n$ collections of argument values. We prove that the number of nonequivalent topolinear latin hypercubes grows exponentially with respect to $\sqrt{n}$ if $q$ is even and exponentially with respect to $n^2$ if $q$ is divisible by a square. We show a connection of the class of isotopically transitive latin squares with the class of G-loops, known in noncommutative algebra, and establish the existence of a topolinear latin square that is not a group isotope. We characterize the class of isotopically transitive latin hypercubes of orders $q=4$ and $q=5$. Keywords: transitive code, propelinear code, latin square, latin hypercube, autotopism, G-loop.
Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence
Venue: arXiv cs.LO 2019
Year: 2019

The problem if a given configuration of a pushdown automaton (PDA) is bisimilar with some (unspecified) finite-state process is shown to be decidable. The decidability is proven in the framework of first-order grammars, which are given by finite sets of labelled rules that rewrite roots of first-order terms. The framework is equivalent to PDA where also deterministic (i.e. alternative-free) epsilon-steps are allowed, i.e. to the model for which Sénizergues showed an involved procedure deciding bisimilarity (1998, 2005). Such a procedure is here used as a black-box part of the algorithm. The result extends the decidability of the regularity problem for deterministic PDA that was shown by Stearns (1967), and later improved by Valiant (1975) regarding the complexity. The decidability question for nondeterministic PDA, answered positively here, had been open (as indicated, e.g., by Broadbent and Göller, 2012).
New and Improved Spanning Ratios for Yao Graphs
Venue: arXiv cs.CG 2019
Year: 2019

For a set of points in the plane and a fixed integer $k > 0$, the Yao graph $Y_k$ partitions the space around each point into $k$ equiangular cones of angle $θ=2π/k$, and connects each point to a nearest neighbor in each cone. It is known for all Yao graphs, with the sole exception of $Y_5$, whether or not they are geometric spanners. In this paper we close this gap by showing that for odd $k \geq 5$, the spanning ratio of $Y_k$ is at most $1/(1-2\sin(3θ/8))$, which gives the first constant upper bound for $Y_5$, and is an improvement over the previous bound of $1/(1-2\sin(θ/2))$ for odd $k \geq 7$. We further reduce the upper bound on the spanning ratio for $Y_5$ from $10.9$ to $2+\sqrt{3} \approx 3.74$, which falls slightly below the lower bound of $3.79$ established for the spanning ratio of $Θ_5$ ($Θ$-graphs differ from Yao graphs only in the way they select the closest neighbor in each cone). This is the first such separation between a Yao and $Θ$-graph with the same number of cones. We also give a lower bound of $2.87$ on the spanning ratio of $Y_5$. Finally, we revisit the $Y_6$ graph, which plays a particularly important role as the transition between the graphs ($k > 6$) for which simple inductive proofs are known, and the graphs ($k \le 6$) whose best spanning ratios have been established by complex arguments. Here we reduce the known spanning ratio of $Y_6$ from $17.6$ to $5.8$, getting closer to the spanning ratio of 2 established for $Θ_6$.
Fully Abstract Game Semantics for Actors
Venue: arXiv cs.LO 2019
Year: 2019

Based on the work on the algebraic theory of actors and game semantics for asynchronous $π$ calculus, we give the full abstraction proof of game semantics for actors.
Alternating, private alternating, and quantum alternating realtime automata
Venue: arXiv cs.FL 2019
Year: 2019

We present new results on realtime alternating, private alternating, and quantum alternating automaton models. Firstly, we show that the emptiness problem for alternating one-counter automata on unary alphabets is undecidable. Then, we present two equivalent definitions of realtime private alternating finite automata (PAFAs). We show that the emptiness problem is undecidable for PAFAs. Furthermore, PAFAs can recognize some nonregular unary languages, including the unary squares language, which seems to be difficult even for some classical counter automata with two-way input. Regarding quantum finite automata (QFAs), we show that the emptiness problem is undecidable both for universal QFAs on general alphabets, and for alternating QFAs with two alternations on unary alphabets. On the other hand, the same problem is decidable for nondeterministic QFAs on general alphabets. We also show that the unary squares language is recognized by alternating QFAs with two alternations.
Autonomous Surveying Boat
Venue: arXiv cs.RO 2019
Year: 2019

The fresh water reservoirs are one of the main power resources of Pakistan.These water reservoirs are in the form of Tarbela Dam, Mangla Dam, Bhasha Dam,and Warsak Dam. To estimate the current power capability of the Dams, the statistical information about the water in the dam has to be clear and precise. For the purpose of water management monthly or yearly survey of the dams required. One of the important parameter is to find the water level of water, which can help us in finding the pressure and flow of water in dams. The existing surveying systems have some problems, i.e., risky, errors in measurement and sometimes expensive. Our project has tried a lot to overcome these flaws and to develop more economical, safe and accurate system for finding depth values of dams and ponds. The key purpose of Our Project Autonomous Surveying Boat is to have it log water depths along a predefined set of points. The Autonomous Surveying Boat floats in water according to predefined path, getting the coordinates from GPS Sensor and direction is controlled by using Magnetometer Sensor. It stores its data on SD card as a text file for later readings. The boat can also be used to find the average capacity of the dam. The average depth is calculated from the measured depth values at different set points of the dam. The actual length of the dam is determined by the magnetometer. The numbers of surveys over the time can help us in finding the silting ratio in dams.For square dams the length and width of the dam are measured and the average depth, then using these three parameters we can estimate the average capacity of the dam.The boat is scalable for furthered modification if needed.
Perfect Bayesian Equilibria in Repeated Sales
Venue: arXiv cs.GT 2019
Year: 2019

A special case of Myerson's classic result describes the revenue-optimal equilibrium when a seller offers a single item to a buyer. We study a repeated sales extension of this model: a seller offers to sell a single fresh copy of an item to the same buyer every day via a posted price. The buyer's private value for the item is drawn initially from a publicly known distribution $F$ and remains the same throughout. A key aspect of this game is that the seller might try to learn the buyer's private value to extract more revenue, while the buyer is motivated to hide it. We study the Perfect Bayesian Equilibria (PBE) in this setting with varying levels of commitment power to the seller. We find that the seller having the commitment power to not raise prices subsequent to a purchase significantly improves revenue in a PBE.
Dense 3D Face Correspondence
Venue: arXiv cs.CV 2019
Year: 2019

We present an algorithm that automatically establishes dense correspondences between a large number of 3D faces. Starting from automatically detected sparse correspondences on the outer boundary of 3D faces, the algorithm triangulates existing correspondences and expands them iteratively by matching points of distinctive surface curvature along the triangle edges. After exhausting keypoint matches, further correspondences are established by generating evenly distributed points within triangles by evolving level set geodesic curves from the centroids of large triangles. A deformable model (K3DM) is constructed from the dense corresponded faces and an algorithm is proposed for morphing the K3DM to fit unseen faces. This algorithm iterates between rigid alignment of an unseen face followed by regularized morphing of the deformable model. We have extensively evaluated the proposed algorithms on synthetic data and real 3D faces from the FRGCv2, Bosphorus, BU3DFE and UND Ear databases using quantitative and qualitative benchmarks. Our algorithm achieved dense correspondences with a mean localisation error of 1.28mm on synthetic faces and detected $14$ anthropometric landmarks on unseen real faces from the FRGCv2 database with 3mm precision. Furthermore, our deformable model fitting algorithm achieved 98.5% face recognition accuracy on the FRGCv2 and 98.6% on Bosphorus database. Our dense model is also able to generalize to unseen datasets.