OpenRaiser/Intern-Atlas huggingface dataset:
Structured Connectivity Augmentation
Venue: arXiv cs.DS 2017
Year: 2017

We initiate the algorithmic study of the following "structured augmentation" question: is it possible to increase the connectivity of a given graph G by superposing it with another given graph H? More precisely, graph F is the superposition of G and H with respect to injective mapping ϕ: V(H)->V(G) if every edge uv of F is either an edge of G, or ϕ^{-1}(u)ϕ^{-1}(v) is an edge of H. We consider the following optimization problem. Given graphs G,H, and a weight function ωassigning non-negative weights to pairs of vertices of V(G), the task is to find φof minimum weight ω(ϕ)=\sum_{xy\in E(H)}ω(ϕ(x)φ(y)) such that the edge connectivity of the superposition F of G and H with respect to ϕis higher than the edge connectivity of G. Our main result is the following "dichotomy" complexity classification. We say that a class of graphs C has bounded vertex-cover number, if there is a constant t depending on C only such that the vertex-cover number of every graph from C does not exceed t. We show that for every class of graphs C with bounded vertex-cover number, the problems of superposing into a connected graph F and to 2-edge connected graph F, are solvable in polynomial time when H\in C. On the other hand, for any hereditary class C with unbounded vertex-cover number, both problems are NP-hard when H\in C. For the unweighted variants of structured augmentation problems, i.e. the problems where the task is to identify whether there is a superposition of graphs of required connectivity, we provide necessary and sufficient combinatorial conditions on the existence of such superpositions. These conditions imply polynomial time algorithms solving the unweighted variants of the problems.
Assessing Economic Outcomes in Simulated Reverse Clock Auctions for Radio Spectrum
Venue: arXiv cs.GT 2017
Year: 2017

We investigate the economic outcomes that result under simulated bidder behavior in a model of the FCC's reverse auction for radio spectrum. In our simulations, limiting our notion of efficiency to the reverse auction in isolation, the reverse clock auction achieves very efficient solutions, the FCC's scoring rule greatly reduces the total payments to TV broadcasters at the cost of some efficiency, and using a poor feasibility checker can have grave consequences both in terms of the auction's cost and efficiency.
From Relational Data to Graphs: Inferring Significant Links using Generalized Hypergeometric Ensembles
Venue: arXiv cs.SI 2017
Year: 2017

The inference of network topologies from relational data is an important problem in data analysis. Exemplary applications include the reconstruction of social ties from data on human interactions, the inference of gene co-expression networks from DNA microarray data, or the learning of semantic relationships based on co-occurrences of words in documents. Solving these problems requires techniques to infer significant links in noisy relational data. In this short paper, we propose a new statistical modeling framework to address this challenge. It builds on generalized hypergeometric ensembles, a class of generative stochastic models that give rise to analytically tractable probability spaces of directed, multi-edge graphs. We show how this framework can be used to assess the significance of links in noisy relational data. We illustrate our method in two data sets capturing spatio-temporal proximity relations between actors in a social system. The results show that our analytical framework provides a new approach to infer significant links from relational data, with interesting perspectives for the mining of data on social systems.
Runtime Verification for Business Processes Utilizing the Bitcoin Blockchain
Venue: arXiv cs.SE 2017
Year: 2017

The usage of process choreographies and decentralized Business Process Management Systems has been named as an alternative to centralized business process orchestration. In choreographies, control over a process instance is shared between independent parties, and no party has full control or knowledge during process runtime. Nevertheless, it is necessary to monitor and verify process instances during runtime for purposes of documentation, accounting, or compensation. To achieve business process runtime verification, this work explores the suitability of the Bitcoin blockchain to create a novel solution for choreographies. The resulting approach is realized in a fully-functional software prototype. This software solution is evaluated in a qualitative comparison. Findings show that our blockchain-based approach enables a seamless execution monitoring and verification of choreographies, while at the same time preserving anonymity and independence of the process participants. Furthermore, the prototype is evaluated in a performance analysis.
Is Natural Language a Perigraphic Process? The Theorem about Facts and Words Revisited
Venue: arXiv cs.IT 2017
Year: 2017

As we discuss, a stationary stochastic process is nonergodic when a random persistent topic can be detected in the infinite random text sampled from the process, whereas we call the process strongly nonergodic when an infinite sequence of independent random bits, called probabilistic facts, is needed to describe this topic completely. Replacing probabilistic facts with an algorithmically random sequence of bits, called algorithmic facts, we adapt this property back to ergodic processes. Subsequently, we call a process perigraphic if the number of algorithmic facts which can be inferred from a finite text sampled from the process grows like a power of the text length. We present a simple example of such a process. Moreover, we demonstrate an assertion which we call the theorem about facts and words. This proposition states that the number of probabilistic or algorithmic facts which can be inferred from a text drawn from a process must be roughly smaller than the number of distinct word-like strings detected in this text by means of the PPM compression algorithm. We also observe that the number of the word-like strings for a sample of plays by Shakespeare follows an empirical stepwise power law, in a stark contrast to Markov processes. Hence we suppose that natural language considered as a process is not only non-Markov but also perigraphic.
SalProp: Salient object proposals via aggregated edge cues
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we propose a novel object proposal generation scheme by formulating a graph-based salient edge classification framework that utilizes the edge context. In the proposed method, we construct a Bayesian probabilistic edge map to assign a saliency value to the edgelets by exploiting low level edge features. A Conditional Random Field is then learned to effectively combine these features for edge classification with object/non-object label. We propose an objectness score for the generated windows by analyzing the salient edge density inside the bounding box. Extensive experiments on PASCAL VOC 2007 dataset demonstrate that the proposed method gives competitive performance against 10 popular generic object detection techniques while using fewer number of proposals.
Learning Local Shape Descriptors from Part Correspondences With Multi-view Convolutional Networks
Venue: arXiv cs.CV 2017
Year: 2017

We present a new local descriptor for 3D shapes, directly applicable to a wide range of shape analysis problems such as point correspondences, semantic segmentation, affordance prediction, and shape-to-scan matching. The descriptor is produced by a convolutional network that is trained to embed geometrically and semantically similar points close to one another in descriptor space. The network processes surface neighborhoods around points on a shape that are captured at multiple scales by a succession of progressively zoomed out views, taken from carefully selected camera positions. We leverage two extremely large sources of data to train our network. First, since our network processes rendered views in the form of 2D images, we repurpose architectures pre-trained on massive image datasets. Second, we automatically generate a synthetic dense point correspondence dataset by non-rigid alignment of corresponding shape parts in a large collection of segmented 3D models. As a result of these design choices, our network effectively encodes multi-scale local context and fine-grained surface detail. Our network can be trained to produce either category-specific descriptors or more generic descriptors by learning from multiple shape categories. Once trained, at test time, the network extracts local descriptors for shapes without requiring any part segmentation as input. Our method can produce effective local descriptors even for shapes whose category is unknown or different from the ones used while training. We demonstrate through several experiments that our learned local descriptors are more discriminative compared to state of the art alternatives, and are effective in a variety of shape analysis applications.
Modeling Multimodal Clues in a Hybrid Deep Learning Framework for Video Classification
Venue: arXiv cs.MM 2017
Year: 2017

Videos are inherently multimodal. This paper studies the problem of how to fully exploit the abundant multimodal clues for improved video categorization. We introduce a hybrid deep learning framework that integrates useful clues from multiple modalities, including static spatial appearance information, motion patterns within a short time window, audio information as well as long-range temporal dynamics. More specifically, we utilize three Convolutional Neural Networks (CNNs) operating on appearance, motion and audio signals to extract their corresponding features. We then employ a feature fusion network to derive a unified representation with an aim to capture the relationships among features. Furthermore, to exploit the long-range temporal dynamics in videos, we apply two Long Short Term Memory networks with extracted appearance and motion features as inputs. Finally, we also propose to refine the prediction scores by leveraging contextual relationships among video semantics. The hybrid deep learning framework is able to exploit a comprehensive set of multimodal features for video classification. Through an extensive set of experiments, we demonstrate that (1) LSTM networks which model sequences in an explicitly recurrent manner are highly complementary with CNN models; (2) the feature fusion network which produces a fused representation through modeling feature relationships outperforms alternative fusion strategies; (3) the semantic context of video classes can help further refine the predictions for improved performance. Experimental results on two challenging benchmarks, the UCF-101 and the Columbia Consumer Videos (CCV), provide strong quantitative evidence that our framework achieves promising results: $93.1\%$ on the UCF-101 and $84.5\%$ on the CCV, outperforming competing methods with clear margins.
Evaluating Personal Assistants on Mobile devices
Venue: arXiv cs.HC 2017
Year: 2017

The iPhone was introduced only a decade ago in 2007 but has fundamentally changed the way we interact with online information. Mobile devices differ radically from classic command-based and point-and-click user interfaces, now allowing for gesture-based interaction using fine-grained touch and swipe signals. Due to the rapid growth in the use of voice-controlled intelligent personal assistants on mobile devices, such as Microsoft's Cortana, Google Now, and Apple's Siri, mobile devices have become personal, allowing us to be online all the time, and assist us in any task, both in work and in our daily lives, making context a crucial factor to consider. Mobile usage is now exceeding desktop usage, and is still growing at a rapid rate, yet our main ways of training and evaluating personal assistants are still based on (and framed in) classical desktop interactions, focusing on explicit queries, clicks, and dwell time spent. However, modern user interaction with mobile devices is radically different due to touch screens with a gesture- and voice-based control and the varying context of use, e.g., in a car, by bike, often invalidating the assumptions underlying today's user satisfaction evaluation. There is an urgent need to understand voice- and gesture-based interaction, taking all interaction signals and context into account in appropriate ways. We propose a research agenda for developing methods to evaluate and improve context-aware user satisfaction with mobile interactions using gesture-based signals at scale.
Block-space GPU Mapping for Embedded Sierpiński Gasket Fractals
Venue: arXiv cs.DC 2017
Year: 2017

This work studies the problem of GPU thread mapping for a Sierpiński gasket fractal embedded in a discrete Euclidean space of $n \times n$. A block-space map $λ: \mathbb{Z}_{\mathbb{E}}^{2} \mapsto \mathbb{Z}_{\mathbb{F}}^{2}$ is proposed, from Euclidean parallel space $\mathbb{E}$ to embedded fractal space $\mathbb{F}$, that maps in $\mathcal{O}(\log_2 \log_2(n))$ time and uses no more than $\mathcal{O}(n^\mathbb{H})$ threads with $\mathbb{H} \approx 1.58...$ being the Hausdorff dimension, making it parallel space efficient. When compared to a bounding-box map, $λ(ω)$ offers a sub-exponential improvement in parallel space and a monotonically increasing speedup once $n > n_0$. Experimental performance tests show that in practice $λ(ω)$ can produce performance improvement at any block-size once $n > n_0 = 2^8$, reaching approximately $10\times$ of speedup for $n=2^{16}$ under optimal block configurations.
SideEye: A Generative Neural Network Based Simulator of Human Peripheral Vision
Venue: arXiv cs.NE 2017
Year: 2017

Foveal vision makes up less than 1% of the visual field. The other 99% is peripheral vision. Precisely what human beings see in the periphery is both obvious and mysterious in that we see it with our own eyes but can't visualize what we see, except in controlled lab experiments. Degradation of information in the periphery is far more complex than what might be mimicked with a radial blur. Rather, behaviorally-validated models hypothesize that peripheral vision measures a large number of local texture statistics in pooling regions that overlap and grow with eccentricity. In this work, we develop a new method for peripheral vision simulation by training a generative neural network on a behaviorally-validated full-field synthesis model. By achieving a 21,000 fold reduction in running time, our approach is the first to combine realism and speed of peripheral vision simulation to a degree that provides a whole new way to approach visual design: through peripheral visualization.
PMU Assisted Power System Parameter Calibration at Jiangsu Electric Power Company
Venue: arXiv cs.SY 2017
Year: 2017

An online PMU-assisted Power System Parameter Calibration System (PSPCS) was recently developed and implemented at State Grid Jiangsu Electric Power Company (JEPC). PSPCS leverages high-resolution PMU data and data mining techniques to perform online screening of the EMS and Production Management System (PMS) databases for data cleaning, model validation, and parameter calibration. PSPCS calculates transmission line and generator parameters on a regular real-time basis and compares the results with databases to identify record(s) with significant discrepancy, if any. Once consistent discrepancy is observed, the system will raise a flag and further investigation will be initiated, including a novel density-based spatial clustering procedure for parameter/data calibration. A novel metric is proposed to quantify the credibility of PMU-based parameter identification. This paper discusses the proposed methodologies, challenges, as well as implementation issues identified during the development and deployment of PSPCS.
Learning a visuomotor controller for real world robotic grasping using simulated depth images
Venue: arXiv cs.RO 2017
Year: 2017

We want to build robots that are useful in unstructured real world applications, such as doing work in the household. Grasping in particular is an important skill in this domain, yet it remains a challenge. One of the key hurdles is handling unexpected changes or motion in the objects being grasped and kinematic noise or other errors in the robot. This paper proposes an approach to learning a closed-loop controller for robotic grasping that dynamically guides the gripper to the object. We use a wrist-mounted sensor to acquire depth images in front of the gripper and train a convolutional neural network to learn a distance function to true grasps for grasp configurations over an image. The training sensor data is generated in simulation, a major advantage over previous work that uses real robot experience, which is costly to obtain. Despite being trained in simulation, our approach works well on real noisy sensor images. We compare our controller in simulated and real robot experiments to a strong baseline for grasp pose detection, and find that our approach significantly outperforms the baseline in the presence of kinematic noise, perceptual errors and disturbances of the object during grasping.
Optimal Orchestration of Virtual Network Functions
Venue: arXiv cs.NI 2017
Year: 2017

-The emergence of Network Functions Virtualization (NFV) is bringing a set of novel algorithmic challenges in the operation of communication networks. NFV introduces volatility in the management of network functions, which can be dynamically orchestrated, i.e., placed, resized, etc. Virtual Network Functions (VNFs) can belong to VNF chains, where nodes in a chain can serve multiple demands coming from the network edges. In this paper, we formally define the VNF placement and routing (VNF-PR) problem, proposing a versatile linear programming formulation that is able to accommodate specific features and constraints of NFV infrastructures, and that is substantially different from existing virtual network embedding formulations in the state of the art. We also design a math-heuristic able to scale with multiple objectives and large instances. By extensive simulations, we draw conclusions on the trade-off achievable between classical traffic engineering (TE) and NFV infrastructure efficiency goals, evaluating both Internet access and Virtual Private Network (VPN) demands. We do also quantitatively compare the performance of our VNF-PR heuristic with the classical Virtual Network Embedding (VNE) approach proposed for NFV orchestration, showing the computational differences, and how our approach can provide a more stable and closer-to-optimum solution.
Foveated Video Streaming for Cloud Gaming
Venue: arXiv cs.MM 2017
Year: 2017

Good user experience with interactive cloud-based multimedia applications, such as cloud gaming and cloud-based VR, requires low end-to-end latency and large amounts of downstream network bandwidth at the same time. In this paper, we present a foveated video streaming system for cloud gaming. The system adapts video stream quality by adjusting the encoding parameters on the fly to match the player's gaze position. We conduct measurements with a prototype that we developed for a cloud gaming system in conjunction with eye tracker hardware. Evaluation results suggest that such foveated streaming can reduce bandwidth requirements by even more than 50% depending on parametrization of the foveated video coding and that it is feasible from the latency perspective.
Distributed Differential Privacy By Sampling
Venue: arXiv cs.CR 2017
Year: 2017

In this paper, we describe our approach to achieve distributed differential privacy by sampling alone. Our mechanism works in the semi-honest setting (honest-but-curious whereby aggregators attempt to peek at the data though follow the protocol). We show that the utility remains constant and does not degrade due to the variance as compared to the randomized response mechanism. In addition, we show smaller privacy leakage as compared to the randomized response mechanism.
A Novel Construction of Low-Complexity MDS Codes with Optimal Repair Capability for Distributed Storage Systems
Venue: arXiv cs.IT 2017
Year: 2017

Maximum-distance-separable (MDS) codes are a class of erasure codes that are widely adopted to enhance the reliability of distributed storage systems (DSS). In (n, k) MDS coded DSS, the original data are stored into n distributed nodes in an efficient manner such that each storage node only contains a small amount (i.e., 1/k) of the data and a data collector connected to any k nodes can retrieve the entire data. On the other hand, a node failure can be repaired (i.e., stored data at the failed node can be successfully recovered) by downloading data segments from other surviving nodes. In this paper, we develop a new approach to construction of simple (5, 3) MDS codes. With judiciously block-designed generator matrices, we show that the proposed MDS codes have a minimum stripe size α = 2 and can be constructed over a small (Galois) finite field F4 of only four elements, both facilitating low-complexity computations and implementations for data storage, retrieval and repair. In addition, with the proposed MDS codes, any single node failure can be repaired through interference alignment technique with a minimum data amount downloaded from the surviving nodes; i.e., the proposed codes ensure optimal exact-repair of any single node failure using the minimum bandwidth. The low-complexity and all-node-optimal-repair properties of the proposed MDS codes make them readily deployed for practical DSS.
DOTE: Dual cOnvolutional filTer lEarning for Super-Resolution and Cross-Modality Synthesis in MRI
Venue: arXiv cs.CV 2017
Year: 2017

Cross-modal image synthesis is a topical problem in medical image computing. Existing methods for image synthesis are either tailored to a specific application, require large scale training sets, or are based on partitioning images into overlapping patches. In this paper, we propose a novel Dual cOnvolutional filTer lEarning (DOTE) approach to overcome the drawbacks of these approaches. We construct a closed loop joint filter learning strategy that generates informative feedback for model self-optimization. Our method can leverage data more efficiently thus reducing the size of the required training set. We extensively evaluate DOTE in two challenging tasks: image super-resolution and cross-modality synthesis. The experimental results demonstrate superior performance of our method over other state-of-the-art methods.