OpenRaiser/Intern-Atlas huggingface dataset:
Lower Bounds for Multiplication via Network Coding
Venue: arXiv cs.DS 2019
Year: 2019

Multiplication is one of the most fundamental computational problems, yet its true complexity remains elusive. The best known upper bound, by Fürer, shows that two $n$-bit numbers can be multiplied via a boolean circuit of size $O(n \lg n \cdot 4^{\lg^*n})$, where $\lg^*n$ is the very slowly growing iterated logarithm. In this work, we prove that if a central conjecture in the area of network coding is true, then any constant degree boolean circuit for multiplication must have size $Ω(n \lg n)$, thus almost completely settling the complexity of multiplication circuits. We additionally revisit classic conjectures in circuit complexity, due to Valiant, and show that the network coding conjecture also implies one of Valiant's conjectures.
High dynamic range image forensics using cnn
Venue: arXiv cs.CV 2019
Year: 2019

High dynamic range (HDR) imaging has recently drawn much attention in multimedia community. In this paper, we proposed a HDR image forensics method based on convolutional neural network (CNN).To our best knowledge, this is the first time to apply deep learning method on HDR image forensics. The proposed algorithm uses CNN to distinguish HDR images generated by multiple low dynamic range (LDR) images from that expanded by single LDR image using inverse tone mapping (iTM). To do this, we learn the change of statistical characteristics extracted by the proposed CNN architectures and classify two kinds of HDR images. Comparision results with some traditional statistical characteristics shows efficiency of the proposed method in HDR image source identification.
Dynamic Multi-path Neural Network
Venue: arXiv cs.CV 2019
Year: 2019

Although deeper and larger neural networks have achieved better performance, the complex network structure and increasing computational cost cannot meet the demands of many resource-constrained applications. Existing methods usually choose to execute or skip an entire specific layer, which can only alter the depth of the network. In this paper, we propose a novel method called Dynamic Multi-path Neural Network (DMNN), which provides more path selection choices in terms of network width and depth during inference. The inference path of the network is determined by a controller, which takes into account both previous state and object category information. The proposed method can be easily incorporated into most modern network architectures. Experimental results on ImageNet and CIFAR-100 demonstrate the superiority of our method on both efficiency and overall classification accuracy. To be specific, DMNN-101 significantly outperforms ResNet-101 with an encouraging 45.1% FLOPs reduction, and DMNN-50 performs comparably to ResNet-101 while saving 42.1% parameters.
System Outage Performance for Three-Step Two-Way Energy Harvesting DF Relaying
Venue: arXiv cs.IT 2019
Year: 2019

Wireless energy harvesting (WEH) has been recognized as a promising technique to prolong the lifetime of energy constrained relay nodes in wireless sensor networks. Its application and related performance study in three-step two-way decode-and-forward (DF) relay networks are of high interest but still lack sufficient study. In this paper we propose a dynamic power splitting (PS) scheme to minimize the system outage probability in a three-step two-way energy harvesting DF relay network and derive an analytical expression for the system outage probability with respect to the optimal dynamic PS ratios. In order to further improve the system outage performance, we propose an improved dynamic scheme where both the PS ratios and the power allocation ratio at the relay are dynamically adjusted according to instantaneous channel gains. The corresponding system performance with the improved dynamic scheme is also investigated. Simulation results show that our proposed schemes outperform the existing scheme in terms of the system outage performance and the improved dynamic scheme is superior to the dynamic PS scheme.
Evaluation of Frequent Itemset Mining Platforms using Apriori and FP-Growth Algorithm
Venue: arXiv cs.DB 2019
Year: 2019

With the overwhelming amount of complex and heterogeneous data pouring from any-where, any-time, and any-device, there is undeniably an era of Big Data. The emergence of the Big Data as a disruptive technology for next generation of intelligent systems, has brought many issues of how to extract and make use of the knowledge obtained from the data within short times, limited budget and under high rates of data generation. Companies are recognizing that big data can be used to make more accurate predictions, and can be used to enhance the business with the help of appropriate association rule mining algorithm. To help these organizations, with which software and algorithm is more appropriate for them depending on their dataset, we compared the most famous three MapReduce based software Hadoop, Spark, Flink on two widely used algorithms Apriori and Fp-Growth on different scales of dataset.
3D High-Resolution Cardiac Segmentation Reconstruction from 2D Views using Conditional Variational Autoencoders
Venue: arXiv cs.CV 2019
Year: 2019

Accurate segmentation of heart structures imaged by cardiac MR is key for the quantitative analysis of pathology. High-resolution 3D MR sequences enable whole-heart structural imaging but are time-consuming, expensive to acquire and they often require long breath holds that are not suitable for patients. Consequently, multiplanar breath-hold 2D cine sequences are standard practice but are disadvantaged by lack of whole-heart coverage and low through-plane resolution. To address this, we propose a conditional variational autoencoder architecture able to learn a generative model of 3D high-resolution left ventricular (LV) segmentations which is conditioned on three 2D LV segmentations of one short-axis and two long-axis images. By only employing these three 2D segmentations, our model can efficiently reconstruct the 3D high-resolution LV segmentation of a subject. When evaluated on 400 unseen healthy volunteers, our model yielded an average Dice score of $87.92 \pm 0.15$ and outperformed competing architectures.
Mobile Formation Coordination and Tracking Control for Multiple Non-holonomic Vehicles
Venue: arXiv cs.SY 2019
Year: 2019

This paper addresses forward motion control for trajectory tracking and mobile formation coordination for a group of non-holonomic vehicles on SE(2). Firstly, by constructing an intermediate attitude variable which involves vehicles' position information and desired attitude, the translational and rotational control inputs are designed in two stages to solve the trajectory tracking problem. Secondly, the coordination relationships of relative positions and headings are explored thoroughly for a group of non-holonomic vehicles to maintain a mobile formation with rigid body motion constraints. We prove that, except for the cases of parallel formation and translational straight line formation, a mobile formation with strict rigid-body motion can be achieved if and only if the ratios of linear speed to angular speed for each individual vehicle are constants. Motion properties for mobile formation with weak rigid-body motion are also demonstrated. Thereafter, based on the proposed trajectory tracking approach, a distributed mobile formation control law is designed under a directed tree graph. The performance of the proposed controllers is validated by both numerical simulations and experiments.
Static Stability of Robotic Fabric Strip Folding
Venue: arXiv cs.RO 2019
Year: 2019

Planning accurate manipulation for deformable objects requires prediction of their state. The prediction is often complicated by a loss of stability that may result in collapse of the deformable object. In this work, stability of a fabric strip folding performed by a robot is studied. We show that there is a static instability in the folding process. This instability is detected in a physics-based simulation and the position of the instability is verified experimentally by real robotic manipulation. Three state-of-the-art methods for folding are assessed in the presence of static instability. It is shown that one of the existing folding paths is suitable for folding of materials with internal friction such as fabrics. Another folding path that utilizes dynamic motion exists for ideal elastic materials without internal friction. Our results show that instability needs to be considered in planning to obtain accurate manipulation of deformable objects.
A Valgrind Tool to Compute the Working Set of a Software Process
Venue: arXiv cs.PF 2019
Year: 2019

This paper introduces a new open-source tool for the dynamic analyzer Valgrind. The tool measures the amount of memory that is actively being used by a process at any given point in time. While there exist numerous tools to measure the memory requirements of a process, the vast majority only focuses on metrics like resident or proportional set sizes, which include memory that was once claimed, but is momentarily disused. Consequently, such tools do not permit drawing conclusions about how much cache or RAM a process actually requires at each point in time, and thus cannot be used for performance debugging. The few tools which do measure only actively used memory, however, have limitations in temporal resolution and introspection. In contrast, our tool offers an easy way to compute the memory that has recently been accessed at any point in time, reflecting how cache and RAM requirements change over time. In particular, this tool computes the set of memory references made within a fixed time interval before any point in time, known as the working set, and captures call stacks for interesting peaks in the working set size. We first introduce the tool, then we run some examples comparing the output from our tool with similar memory tools, and we close with a discussion of limitations
Generative Models for Low-Rank Video Representation and Reconstruction
Venue: arXiv cs.CV 2019
Year: 2019

Finding compact representation of videos is an essential component in almost every problem related to video processing or understanding. In this paper, we propose a generative model to learn compact latent codes that can efficiently represent and reconstruct a video sequence from its missing or under-sampled measurements. We use a generative network that is trained to map a compact code into an image. We first demonstrate that if a video sequence belongs to the range of the pretrained generative network, then we can recover it by estimating the underlying compact latent codes. Then we demonstrate that even if the video sequence does not belong to the range of a pretrained network, we can still recover the true video sequence by jointly updating the latent codes and the weights of the generative network. To avoid overfitting in our model, we regularize the recovery problem by imposing low-rank and similarity constraints on the latent codes of the neighboring frames in the video sequence. We use our methods to recover a variety of videos from compressive measurements at different compression rates. We also demonstrate that we can generate missing frames in a video sequence by interpolating the latent codes of the observed frames in the low-dimensional space.
Algorithm and Hardness results on Liar's Dominating Set and $k$-tuple Dominating Set
Venue: arXiv cs.CG 2019
Year: 2019

Given a graph $G=(V,E)$, the dominating set problem asks for a minimum subset of vertices $D\subseteq V$ such that every vertex $u\in V\setminus D$ is adjacent to at least one vertex $v\in D$. That is, the set $D$ satisfies the condition that $|N[v]\cap D|\geq 1$ for each $v\in V$, where $N[v]$ is the closed neighborhood of $v$. In this paper, we study two variants of the classical dominating set problem: $\boldmath{k}$-tuple dominating set ($k$-DS) problem and Liar's dominating set (LDS) problem, and obtain several algorithmic and hardness results. On the algorithmic side, we present a constant factor ($\frac{11}{2}$)-approximation algorithm for the Liar's dominating set problem on unit disk graphs. Then, we obtain a PTAS for the $\boldmath{k}$-tuple dominating set problem on unit disk graphs. On the hardness side, we show a $Ω(n^2)$ bits lower bound for the space complexity of any (randomized) streaming algorithm for Liar's dominating set problem as well as for the $\boldmath{k}$-tuple dominating set problem. Furthermore, we prove that the Liar's dominating set problem on bipartite graphs is W[2]-hard.
Enabling efficient application monitoring in cloud data centers using SDN
Venue: arXiv cs.NI 2019
Year: 2019

Software Defined Networking (SDN) not only enables agility through the realization of part of the network functionality in software but also facilitates offering advanced features at the network layer. Hence, SDN can support a wide range of middleware services; network performance monitoring is an example of these services that are already deployed in practice. In this paper, we exploit the use of SDNs to efficiently provide application monitoring functionality. The recent rise of complex cloud applications has made performance monitoring a major issue. We show that many performance indicators can be inferred from messages exchanged among application components. By analyzing these messages, we argue that the overhead of performance monitoring could be effectively moved from the end hosts into the SDN middleware of the cloud infrastructure which enables more flexible placement of logging functionality. This paper explores several approaches for supporting application monitoring through SDN. In particular, we combine selective forwarding in SDN to enable message filtering and reformatting, and propose a customized port sniffing technique. We describe the implementation of the approach within the standard SDN software, namely OVS. We further provide a comprehensive performance evaluation to analyze advantages and disadvantages of our approach, and highlight the trade-offs.
EyeDoc: Documentation Navigation with Eye Tracking
Venue: arXiv cs.SE 2019
Year: 2019

We demonstrate EyeDoc, a tool for navigating software documentation with the use of the eyes. When programming, developers often have many windows open such as an IDE, consoles and GUIs for third-party utilities, the application under development, and a web browser for navigating documentation. Several studies have shown that the navigation among these different tasks imposes a small mental load which, over time, adds to a significant decrease in productivity. One solution to this problem is to increase "screen real estate" with larger monitors and higher resolutions, so that more information can be presented to the programmer at one time. But this solution has limits: the complexity and size of software is also increasing rapidly. In this paper, we use eye-tracking technology to build a tool for navigating documentation. All a programmer needs to do to use EyeDoc is look at the monitor containing the documentation. The tool detects when the eyes glance at different components of the documentation, and allows the programmer to navigate to those components by gazes and blinking. The programmer does not need to move his or her hands, or risk losing the context of other tasks on the desktop. We built EyeDoc as a research prototype and proof-of-concept using low-cost consumer eye-tracking hardware and our own software built as a JavaScript addition to JavaDocs. This paper describes the tool's design, use, and strategy for evaluation and future development.
Speeding up Deep Learning with Transient Servers
Venue: arXiv cs.PF 2019
Year: 2019

Distributed training frameworks, like TensorFlow, have been proposed as a means to reduce the training time of deep learning models by using a cluster of GPU servers. While such speedups are often desirable---e.g., for rapidly evaluating new model designs---they often come with significantly higher monetary costs due to sublinear scalability. In this paper, we investigate the feasibility of using training clusters composed of cheaper transient GPU servers to get the benefits of distributed training without the high costs. We conduct the first large-scale empirical analysis, launching more than a thousand GPU servers of various capacities, aimed at understanding the characteristics of transient GPU servers and their impact on distributed training performance. Our study demonstrates the potential of transient servers with a speedup of 7.7X with more than 62.9% monetary savings for some cluster configurations. We also identify a number of important challenges and opportunities for redesigning distributed training frameworks to be transient-aware. For example, the dynamic cost and availability characteristics of transient servers suggest the need for frameworks to dynamically change cluster configurations to best take advantage of current conditions.
A Long-Short Demands-Aware Model for Next-Item Recommendation
Venue: arXiv cs.IR 2019
Year: 2019

Recommending the right products is the central problem in recommender systems, but the right products should also be recommended at the right time to meet the demands of users, so as to maximize their values. Users' demands, implying strong purchase intents, can be the most useful way to promote products sales if well utilized. Previous recommendation models mainly focused on user's general interests to find the right products. However, the aspect of meeting users' demands at the right time has been much less explored. To address this problem, we propose a novel Long-Short Demands-aware Model (LSDM), in which both user's interests towards items and user's demands over time are incorporated. We summarize two aspects: termed as long-time demands (e.g., purchasing the same product repetitively showing a long-time persistent interest) and short-time demands (e.g., co-purchase like buying paintbrushes after pigments). To utilize such long-short demands of users, we create different clusters to group the successive product purchases together according to different time spans, and use recurrent neural networks to model each sequence of clusters at a time scale. The long-short purchase demands with multi-time scales are finally aggregated by joint learning strategies. Experimental results on three real-world commerce datasets demonstrate the effectiveness of our model for next-item recommendation, showing the usefulness of modeling users' long-short purchase demands of items with multi-time scales.
A block-random algorithm for learning on distributed, heterogeneous data
Venue: arXiv cs.LG 2019
Year: 2019

Most deep learning models are based on deep neural networks with multiple layers between input and output. The parameters defining these layers are initialized using random values and are "learned" from data, typically using stochastic gradient descent based algorithms. These algorithms rely on data being randomly shuffled before optimization. The randomization of the data prior to processing in batches that is formally required for stochastic gradient descent algorithm to effectively derive a useful deep learning model is expected to be prohibitively expensive for in situ model training because of the resulting data communications across the processor nodes. We show that the stochastic gradient descent (SGD) algorithm can still make useful progress if the batches are defined on a per-processor basis and processed in random order even though (i) the batches are constructed from data samples from a single class or specific flow region, and (ii) the overall data samples are heterogeneous. We present block-random gradient descent, a new algorithm that works on distributed, heterogeneous data without having to pre-shuffle. This algorithm enables in situ learning for exascale simulations. The performance of this algorithm is demonstrated on a set of benchmark classification models and the construction of a subgrid scale large eddy simulations (LES) model for turbulent channel flow using a data model similar to that which will be encountered in exascale simulation.
Appearance-based Gesture recognition in the compressed domain
Venue: arXiv cs.CV 2019
Year: 2019

We propose a novel appearance-based gesture recognition algorithm using compressed domain signal processing techniques. Gesture features are extracted directly from the compressed measurements, which are the block averages and the coded linear combinations of the image sensor's pixel values. We also improve both the computational efficiency and the memory requirement of the previous DTW-based K-NN gesture classifiers. Both simulation testing and hardware implementation strongly support the proposed algorithm.
Lung CT Imaging Sign Classification through Deep Learning on Small Data
Venue: arXiv cs.CV 2019
Year: 2019

The annotated medical images are usually expensive to be collected. This paper proposes a deep learning method on small data to classify Common Imaging Signs of Lung diseases (CISL) in computed tomography (CT) images. We explore both the real data and the data generated by Generative Adversarial Network (GAN) to improve the reliability and the generalization of learning. First, we use GAN to generate a large number of CISLs from small annotated data, which are difficult to be distinguished from real counterparts. These generated samples are used to pre-train a Convolutional Neural Network (CNN) for classifying CISLs. Second, we fine-tune the CNN classification model with real data. Experiments were conducted on the LISS database of CISLs. We successfully convinced radiologists that our generated CISLs samples were real for 56.7% of our experiments. The pre-trained CNN model achieves 88.4% of mean accuracy of binary classification, and after fine-tuning, the mean accuracy is significantly increased to 95.0%. For multi-classification of all types of CISLs and normal tissues, through the two stages of training, the mean accuracy, sensitivity and specificity are up to about 91.83%, 92.73% and 99.0%, respectively. To our knowledge, this is the best result achieved on the LISS database, which demonstrates that the proposed method is effective and promising for fulfilling deep learning on small data.
Volumetric Instance-Aware Semantic Mapping and 3D Object Discovery
Venue: arXiv cs.RO 2019
Year: 2019

To autonomously navigate and plan interactions in real-world environments, robots require the ability to robustly perceive and map complex, unstructured surrounding scenes. Besides building an internal representation of the observed scene geometry, the key insight toward a truly functional understanding of the environment is the usage of higher-level entities during mapping, such as individual object instances. We propose an approach to incrementally build volumetric object-centric maps during online scanning with a localized RGB-D camera. First, a per-frame segmentation scheme combines an unsupervised geometric approach with instance-aware semantic object predictions. This allows us to detect and segment elements both from the set of known classes and from other, previously unseen categories. Next, a data association step tracks the predicted instances across the different frames. Finally, a map integration strategy fuses information about their 3D shape, location, and, if available, semantic class into a global volume. Evaluation on a publicly available dataset shows that the proposed approach for building instance-level semantic maps is competitive with state-of-the-art methods, while additionally able to discover objects of unseen categories. The system is further evaluated within a real-world robotic mapping setup, for which qualitative results highlight the online nature of the method.