OpenRaiser/Intern-Atlas huggingface dataset:
PCN: Point Completion Network
Venue: arXiv cs.CV 2019
Year: 2019

Shape completion, the problem of estimating the complete geometry of objects from partial observations, lies at the core of many vision and robotics applications. In this work, we propose Point Completion Network (PCN), a novel learning-based approach for shape completion. Unlike existing shape completion methods, PCN directly operates on raw point clouds without any structural assumption (e.g. symmetry) or annotation (e.g. semantic class) about the underlying shape. It features a decoder design that enables the generation of fine-grained completions while maintaining a small number of parameters. Our experiments show that PCN produces dense, complete point clouds with realistic structures in the missing regions on inputs with various levels of incompleteness and noise, including cars from LiDAR scans in the KITTI dataset.
A Systematic Comparison of Dynamic Load Balancing Algorithms for Massively Parallel Rigid Particle Dynamics
Venue: arXiv cs.DC 2019
Year: 2019

As compute power increases with time, more involved and larger simulations become possible. However, it gets increasingly difficult to efficiently use the provided computational resources. Especially in particle-based simulations with a spatial domain partitioning large load imbalances can occur due to the simulation being dynamic. Then a static domain partitioning may not be suitable. This can deteriorate the overall runtime of the simulation significantly. Sophisticated load balancing strategies must be designed to alleviate this problem. In this paper we conduct a systematic evaluation of the performance of six different load balancing algorithms. Our tests cover a wide range of simulation sizes, and employ one of the largest supercomputers available. In particular we study the runtime and memory complexity of all components of the simulation carefully. When progressing to extreme scale simulations it is essential to identify bottlenecks and to predict the scaling behaviour. Scaling experiments are shown for up to over one million processes. The performance of each algorithm is analyzed with respect to the quality of the load balancing and its runtime costs. For all tests, the waLBerla multiphysics framework is employed.
Hallucinating Agnostic Images to Generalize Across Domains
Venue: arXiv cs.CV 2019
Year: 2019

The ability to generalize across visual domains is crucial for the robustness of artificial recognition systems. Although many training sources may be available in real contexts, the access to even unlabeled target samples cannot be taken for granted, which makes standard unsupervised domain adaptation methods inapplicable in the wild. In this work we investigate how to exploit multiple sources by hallucinating a deep visual domain composed of images, possibly unrealistic, able to maintain categorical knowledge while discarding specific source styles. The produced agnostic images are the result of a deep architecture that applies pixel adaptation on the original source data guided by two adversarial domain classifier branches at image and feature level. Our approach is conceived to learn only from source data, but it seamlessly extends to the use of unlabeled target samples. Remarkable results for both multi-source domain adaptation and domain generalization support the power of hallucinating agnostic images in this framework.
CornerNet: Detecting Objects as Paired Keypoints
Venue: arXiv cs.CV 2019
Year: 2019

We propose CornerNet, a new approach to object detection where we detect an object bounding box as a pair of keypoints, the top-left corner and the bottom-right corner, using a single convolution neural network. By detecting objects as paired keypoints, we eliminate the need for designing a set of anchor boxes commonly used in prior single-stage detectors. In addition to our novel formulation, we introduce corner pooling, a new type of pooling layer that helps the network better localize corners. Experiments show that CornerNet achieves a 42.2% AP on MS COCO, outperforming all existing one-stage detectors.
Distributed Differential Privacy via Shuffling
Venue: arXiv cs.CR 2019
Year: 2019

We consider the problem of designing scalable, robust protocols for computing statistics about sensitive data. Specifically, we look at how best to design differentially private protocols in a distributed setting, where each user holds a private datum. The literature has mostly considered two models: the "central" model, in which a trusted server collects users' data in the clear, which allows greater accuracy; and the "local" model, in which users individually randomize their data, and need not trust the server, but accuracy is limited. Attempts to achieve the accuracy of the central model without a trusted server have so far focused on variants of cryptographic MPC, which limits scalability. In this paper, we initiate the analytic study of a shuffled model for distributed differentially private algorithms, which lies between the local and central models. This simple-to-implement model, a special case of the ESA framework of [Bittau et al., '17], augments the local model with an anonymous channel that randomly permutes a set of user-supplied messages. For sum queries, we show that this model provides the power of the central model while avoiding the need to trust a central server and the complexity of cryptographic secure function evaluation. More generally, we give evidence that the power of the shuffled model lies strictly between those of the central and local models: for a natural restriction of the model, we show that shuffled protocols for a widely studied selection problem require exponentially higher sample complexity than do central-model protocols.
A survey on Deep Learning Advances on Different 3D Data Representations
Venue: arXiv cs.CV 2019
Year: 2019

3D data is a valuable asset the computer vision filed as it provides rich information about the full geometry of sensed objects and scenes. Recently, with the availability of both large 3D datasets and computational power, it is today possible to consider applying deep learning to learn specific tasks on 3D data such as segmentation, recognition and correspondence. Depending on the considered 3D data representation, different challenges may be foreseen in using existent deep learning architectures. In this work, we provide a comprehensive overview about various 3D data representations highlighting the difference between Euclidean and non-Euclidean ones. We also discuss how Deep Learning methods are applied on each representation, analyzing the challenges to overcome.
Towards Closing the Gap in Weakly Supervised Semantic Segmentation with DCNNs: Combining Local and Global Models
Venue: arXiv cs.CV 2019
Year: 2019

Generating training sets for deep convolutional neural networks (DCNNs) is a bottleneck for modern real-world applications. This is a demanding task for applications where annotating training data is costly, such as in semantic segmentation. In the literature, there is still a gap between the performance achieved by a network trained on full and on weak annotations. In this paper, we establish a strategy to measure this gap and to identify the ingredients necessary to reduce it. On scribbles, we establish new state-of-the-art results: we obtain a mIoU of 75.6% without, and 75.7% with CRF post-processing. We reduce the gap by 64.2% whereas the current state-of-the-art reduces it only by 57.5%. Thanks to a systematic study of the different ingredients involved in the weakly supervised scenario and an original experimental strategy, we unravel a counter-intuitive mechanism that is simple and amenable to generalisations to other weakly-supervised scenarios: averaging poor local predicted annotations with the baseline ones and reuse them for training a DCNN yields new state-of-the-art results.
Size-Change Termination as a Contract
Venue: arXiv cs.PL 2019
Year: 2019

Termination is an important but undecidable program property, which has led to a large body of work on static methods for conservatively predicting or enforcing termination. One such method is the size-change termination approach of Lee, Jones, and Ben-Amram, which operates in two phases: (1) abstract programs into "size-change graphs," and (2) check these graphs for the size-change property: the existence of paths that lead to infinite decreasing sequences. We transpose these two phases with an operational semantics that accounts for the run-time enforcement of the size-change property, postponing (or entirely avoiding) program abstraction. This choice has two key consequences: (1) size-change termination can be checked at run-time and (2) termination can be rephrased as a safety property analyzed using existing methods for systematic abstraction. We formulate run-time size-change checks as contracts in the style of Findler and Felleisen. The result compliments existing contracts that enforce partial correctness specifications to obtain contracts for total correctness. Our approach combines the robustness of the size-change principle for termination with the precise information available at run-time. It has tunable overhead and can check for nontermination without the conservativeness necessary in static checking. To obtain a sound and computable termination analysis, we apply existing abstract interpretation techniques directly to the operational semantics, avoiding the need for custom abstractions for termination. The resulting analyzer is competitive with with existing, purpose-built analyzers.
Deep Stacked Stochastic Configuration Networks for Lifelong Learning of Non-Stationary Data Streams
Venue: arXiv cs.LG 2019
Year: 2019

The concept of SCN offers a fast framework with universal approximation guarantee for lifelong learning of non-stationary data streams. Its adaptive scope selection property enables for proper random generation of hidden unit parameters advancing conventional randomized approaches constrained with a fixed scope of random parameters. This paper proposes deep stacked stochastic configuration network (DSSCN) for continual learning of non-stationary data streams which contributes two major aspects: 1) DSSCN features a self-constructing methodology of deep stacked network structure where hidden unit and hidden layer are extracted automatically from continuously generated data streams; 2) the concept of SCN is developed to randomly assign inverse covariance matrix of multivariate Gaussian function in the hidden node addition step bypassing its computationally prohibitive tuning phase. Numerical evaluation and comparison with prominent data stream algorithms under two procedures: periodic hold-out and prequential test-then-train processes demonstrate the advantage of proposed methodology.
MaRe: a MapReduce-Oriented Framework for Processing Big Data with Application Containers
Venue: arXiv cs.DC 2019
Year: 2019

Background. Life science is increasingly driven by Big Data analytics, and the MapReduce programming model has been proven successful for data-intensive analyses. However, current MapReduce frameworks offer poor support for reusing existing processing tools in bioinformatics pipelines. Further, these frameworks do not have native support for application containers, which are becoming popular in scientific data processing. Results. Here we present MaRe, a programming model with an associated open-source implementation, which introduces support for application containers in MapReduce. MaRe is based on Apache Spark and Docker, the MapReduce framework and container engine that have collected the largest open source community, thus providing interoperability with the cutting-edge software ecosystem. We demonstrate MaRe on two data-intensive applications in life science, showing ease of use and scalability. Conclusions. MaRe enables scalable data-intensive processing in life science with MapReduce and application containers. When compared with current best practices, that involve the use of workflow systems, MaRe has the advantage of providing data locality, ingestion from heterogeneous storage systems and interactive processing. MaRe is generally-applicable and available as open source software.
Persistent Monitoring of Dynamically Changing Environments Using an Unmanned Vehicle
Venue: arXiv cs.DS 2019
Year: 2019

We consider the problem of planning a closed walk $\mathcal W$ for a UAV to persistently monitor a finite number of stationary targets with equal priorities and dynamically changing properties. A UAV must physically visit the targets in order to monitor them and collect information therein. The frequency of monitoring any given target is specified by a target revisit time, $i.e.$, the maximum allowable time between any two successive visits to the target. The problem considered in this paper is the following: Given $n$ targets and $k \geq n$ allowed visits to them, find an optimal closed walk $\mathcal W^*(k)$ so that every target is visited at least once and the maximum revisit time over all the targets, $\mathcal R(\mathcal W(k))$, is minimized. We prove the following: If $k \geq n^2-n$, $\mathcal R(\mathcal W^*(k))$ (or simply, $\mathcal R^*(k)$) takes only two values: $\mathcal R^*(n)$ when $k$ is an integral multiple of $n$, and $\mathcal R^*(n+1)$ otherwise. This result suggests significant computational savings - one only needs to determine $\mathcal W^*(n)$ and $\mathcal W^*(n+1)$ to construct an optimal solution $\mathcal W^*(k)$. We provide MILP formulations for computing $\mathcal W^*(n)$ and $\mathcal W^*(n+1)$. Furthermore, for {\it any} given $k$, we prove that $\mathcal R^*(k) \geq \mathcal R^*(k+n)$.
An Effective Framework for Constructing Exponent Lattice Basis of Nonzero Algebraic Numbers
Venue: arXiv cs.SC 2019
Year: 2019

Computing a basis for the exponent lattice of algebraic numbers is a basic problem in the field of computational number theory with applications to many other areas. The main cost of a well-known algorithm \cite{ge1993algorithms,kauers2005algorithms} solving the problem is on computing the primitive element of the extended field generated by the given algebraic numbers. When the extended field is of large degree, the problem seems intractable by the tool implementing the algorithm. In this paper, a special kind of exponent lattice basis is introduced. An important feature of the basis is that it can be inductively constructed, which allows us to deal with the given algebraic numbers one by one when computing the basis. Based on this, an effective framework for constructing exponent lattice basis is proposed. Through computing a so-called pre-basis first and then solving some linear Diophantine equations, the basis can be efficiently constructed. A new certificate for multiplicative independence and some techniques for decreasing degrees of algebraic numbers are provided to speed up the computation. The new algorithm has been implemented with Mathematica and its effectiveness is verified by testing various examples. Moreover, the algorithm is applied to program verification for finding invariants of linear loops.
Learning to Optimize Join Queries With Deep Reinforcement Learning
Venue: arXiv cs.DB 2019
Year: 2019

Exhaustive enumeration of all possible join orders is often avoided, and most optimizers leverage heuristics to prune the search space. The design and implementation of heuristics are well-understood when the cost model is roughly linear, and we find that these heuristics can be significantly suboptimal when there are non-linearities in cost. Ideally, instead of a fixed heuristic, we would want a strategy to guide the search space in a more data-driven way---tailoring the search to a specific dataset and query workload. Recognizing the link between classical Dynamic Programming enumeration methods and recent results in Reinforcement Learning (RL), we propose a new method for learning optimized join search strategies. We present our RL-based DQ optimizer, which currently optimizes select-project-join blocks. We implement three versions of DQ to illustrate the ease of integration into existing DBMSes: (1) A version built on top of Apache Calcite, (2) a version integrated into PostgreSQL, and (3) a version integrated into SparkSQL. Our extensive evaluation shows that DQ achieves plans with optimization costs and query execution times competitive with the native query optimizer in each system, but can execute significantly faster after learning (often by orders of magnitude).
Testing Implementation of FAMTAR: Adaptive Multipath Routing
Venue: arXiv cs.NI 2019
Year: 2019

Flow-Aware Multi-Topology Adaptive Routing (FAMTAR) is a new approach to multipath and adaptive routing in IP networks which enables automatic use of alternative paths when the primary one becomes congested. It provides more efficient network resource utilization and higher quality of transmission compared to standard IP routing. However, thus far it has only been evaluated through simulations. In this paper we share our experiences from building a real-time FAMTAR router and present results of its tests in a physical network. The results are in line with those obtained previously through simulations and they open the way to implementation of a production grade FAMTAR router.
Systematic analysis of agreement between metrics and peer review in the UK REF
Venue: arXiv cs.DL 2019
Year: 2019

When performing a national research assessment, some countries rely on citation metrics whereas others, such as the UK, primarily use peer review. In the influential Metric Tide report, a low agreement between metrics and peer review in the UK Research Excellence Framework (REF) was found. However, earlier studies observed much higher agreement between metrics and peer review in the REF and argued in favour of using metrics. This shows that there is considerable ambiguity in the discussion on agreement between metrics and peer review. We provide clarity in this discussion by considering four important points: (1) the level of aggregation of the analysis; (2) the use of either a size-dependent or a size-independent perspective; (3) the suitability of different measures of agreement; and (4) the uncertainty in peer review. In the context of the REF, we argue that agreement between metrics and peer review should be assessed at the institutional level rather than at the publication level. Both a size-dependent and a size-independent perspective are relevant in the REF. The interpretation of correlations may be problematic and as an alternative we therefore use measures of agreement that are based on the absolute or relative differences between metrics and peer review. To get an idea of the uncertainty in peer review, we rely on a model to bootstrap peer review outcomes. We conclude that particularly in Physics, Clinical Medicine, and Public Health, metrics agree quite well with peer review and may offer an alternative to peer review.
Unsupervised Learning of Sentence Representations Using Sequence Consistency
Venue: arXiv cs.CL 2019
Year: 2019

Computing universal distributed representations of sentences is a fundamental task in natural language processing. We propose ConsSent, a simple yet surprisingly powerful unsupervised method to learn such representations by enforcing consistency constraints on sequences of tokens. We consider two classes of such constraints -- sequences that form a sentence and between two sequences that form a sentence when merged. We learn sentence encoders by training them to distinguish between consistent and inconsistent examples, the latter being generated by randomly perturbing consistent examples in six different ways. Extensive evaluation on several transfer learning and linguistic probing tasks shows improved performance over strong unsupervised and supervised baselines, substantially surpassing them in several cases. Our best results are achieved by training sentence encoders in a multitask setting and by an ensemble of encoders trained on the individual tasks.
Power-Aware Allocation of Graph Jobs in Geo-Distributed Cloud Networks
Venue: arXiv cs.DC 2019
Year: 2019

In the era of big-data, the jobs submitted to the clouds exhibit complicated structures represented by graphs, where the nodes denote the sub-tasks each of which can be accommodated at a slot in a server, while the edges indicate the communication constraints among the sub-tasks. We develop a framework for efficient allocation of graph jobs in geo-distributed cloud networks (GDCNs), explicitly considering the power consumption of the datacenters (DCs). We address the following two challenges arising in graph job allocation: i) the allocation problem belongs to NP-hard nonlinear integer programming; ii) the allocation requires solving the NP-complete sub-graph isomorphism problem, which is particularly cumbersome in large-scale GDCNs. We develop a suite of efficient solutions for GDCNs of various scales. For small-scale GDCNs, we propose an analytical approach based on convex programming. For medium-scale GDCNs, we develop a distributed allocation algorithm exploiting the processing power of DCs in parallel. Afterward, we provide a novel low-complexity (decentralized) sub-graph extraction method, based on which we introduce cloud crawlers aiming to extract allocations of good potentials for large-scale GDCNs. Given these suggested strategies, we further investigate strategy selection under both fixed and adaptive DC pricing schemes, and propose an online learning algorithm for each.
On the approximability of the stable matching problem with ties of size two
Venue: arXiv cs.GT 2019
Year: 2019

The stable matching problem is one of the central problems of algorithmic game theory. If participants are allowed to have ties, the problem of finding a stable matching of maximum cardinality is an NP-hard problem, even when the ties are of size two. Moreover, in this setting it is UGC-hard to provide an approximation for the maximum cardinality stable matching problem with a constant factor smaller than 4/3. In this paper, we give a tight analysis of an approximation algorithm given by Huang and Kavitha for the maximum cardinality stable matching problem with ties of size two, demonstrating an improved 4/3-approximation factor.
Time-Multiplexed Parsing in Marking-based Network Telemetry
Venue: arXiv cs.NI 2019
Year: 2019

Network telemetry is a key capability for managing the health and efficiency of a large-scale network. Alternate Marking Performance Measurement (AM-PM) is a recently introduced approach that accurately measures the packet loss and delay in a network using a small overhead of one or two bits per data packet. This paper introduces a novel time-multiplexed parsing approach that enables a practical and accurate implementation of AM-PM in network devices, while requiring just a single bit per packet. Experimental results are presented, based on a hardware implementation, and a software P4-based implementation.
Evaluating Datalog via Tree Automata and Cycluits
Venue: arXiv cs.DB 2019
Year: 2019

We investigate parameterizations of both database instances and queries that make query evaluation fixed-parameter tractable in combined complexity. We show that clique-frontier-guarded Datalog with stratified negation (CFG-Datalog) enjoys bilinear-time evaluation on structures of bounded treewidth for programs of bounded rule size. Such programs capture in particular conjunctive queries with simplicial decompositions of bounded width, guarded negation fragment queries of bounded CQ-rank, or two-way regular path queries. Our result is shown by translating to alternating two-way automata, whose semantics is defined via cyclic provenance circuits (cycluits) that can be tractably evaluated.