OpenRaiser/Intern-Atlas huggingface dataset:
Width, depth and space
Venue: arXiv cs.CC 2016
Year: 2016

The width measure treedepth, also known as vertex ranking, centered coloring and elimination tree height, is a well-established notion which has recently seen a resurgence of interest. Since graphs of bounded treedepth are more restricted than graphs of bounded tree- or pathwidth, we are interested in the algorithmic utility of this additional structure. On the negative side, we show that every dynamic programming algorithm on treedepth decompositions of depth~$t$ cannot solve Dominating Set with $O((3-ε)^t \cdot \log n)$ space for any $ε> 0$. This result implies the same space lower bound for dynamic programming algorithms on tree and path decompositions. We supplement this result by showing a space lower bound of $O((3-ε)^t \cdot \log n)$ for 3-Coloring and $O((2-ε)^t \cdot \log n)$ for Vertex Cover. This formalizes the common intuition that dynamic programming algorithms on graph decompositions necessarily consume a lot of space and complements known results of the time-complexity of problems restricted to low-treewidth classes. We then show that treedepth lends itself to the design of branching algorithms. This class of algorithms has in general distinct advantages over dynamic programming algorithms: a) They use less space than algorithms based on dynamic programming, b) they are easy to parallelize and c) they provide possible solutions before terminating. Specifically, we design for Dominating Set a pure branching algorithm that runs in time $t^{O(t^2)}\cdot n$ and uses space $O(t^3 \log t + t \log n)$ and a hybrid of branching and dynamic programming that achieves a running time of $O(3^t \log t \cdot n)$ while using $O(2^t t \log t + t \log n)$ space. Algorithms for 3-Coloring and Vertex Cover with space complexity $O(t \cdot \log n)$ and time complexity $O(3^t \cdot n)$ and $O(2^t\cdot n)$, respectively, are included for completeness.
Walking without a Map: Optimizing Response Times of Traversal-Based Linked Data Queries (Extended Version)
Venue: arXiv cs.DB 2016
Year: 2016

The emergence of Linked Data on the WWW has spawned research interest in an online execution of declarative queries over this data. A particularly interesting approach is traversal-based query execution which fetches data by traversing data links and, thus, is able to make use of up-to-date data from initially unknown data sources. The downside of this approach is the delay before the query engine completes a query execution. In this paper, we address this problem by proposing an approach to return as many elements of the result set as soon as possible. The basis of this approach is a traversal strategy that aims to fetch result-relevant data as early as possible. The challenge for such a strategy is that the query engine does not know a priori which of the data sources that will be discovered during the query execution contain result-relevant data. We introduce 16 different traversal approaches and experimentally study their impact on response times. Our experiments show that some of the approaches can achieve significant improvements over the baseline of looking up URIs on a first-come, first-served basis. Additionally, we verify the importance of these approaches by showing that typical query optimization techniques that focus solely on the process of constructing the query result cannot have any significant impact on the response times of traversal-based query executions.
Application of Statistical Relational Learning to Hybrid Recommendation Systems
Venue: arXiv cs.AI 2016
Year: 2016

Recommendation systems usually involve exploiting the relations among known features and content that describe items (content-based filtering) or the overlap of similar users who interacted with or rated the target item (collaborative filtering). To combine these two filtering approaches, current model-based hybrid recommendation systems typically require extensive feature engineering to construct a user profile. Statistical Relational Learning (SRL) provides a straightforward way to combine the two approaches. However, due to the large scale of the data used in real world recommendation systems, little research exists on applying SRL models to hybrid recommendation systems, and essentially none of that research has been applied on real big-data-scale systems. In this paper, we proposed a way to adapt the state-of-the-art in SRL learning approaches to construct a real hybrid recommendation system. Furthermore, in order to satisfy a common requirement in recommendation systems (i.e. that false positives are more undesirable and therefore penalized more harshly than false negatives), our approach can also allow tuning the trade-off between the precision and recall of the system in a principled way. Our experimental results demonstrate the efficiency of our proposed approach as well as its improved performance on recommendation precision.
Minimalist Regression Network with Reinforced Gradients and Weighted Estimates: a Case Study on Parameters Estimation in Automated Welding
Venue: arXiv cs.LG 2016
Year: 2016

This paper presents a minimalist neural regression network as an aggregate of independent identical regression blocks that are trained simultaneously. Moreover, it introduces a new multiplicative parameter, shared by all the neural units of a given layer, to maintain the quality of its gradients. Furthermore, it increases its estimation accuracy via learning a weight factor whose quantity captures the redundancy between the estimated and actual values at each training iteration. We choose the estimation of the direct weld parameters of different welding techniques to show a significant improvement in calculation of these parameters by our model in contrast to state-of-the-arts techniques in the literature. Furthermore, we demonstrate the ability of our model to retain its performance when presented with combined data of different welding techniques. This is a nontrivial result in attaining an scalable model whose quality of estimation is independent of adopted welding techniques.
Towards Network-Failure-Tolerant Content Delivery for Web Content
Venue: arXiv cs.MM 2016
Year: 2016

Popularly used to distribute a variety of multimedia content items in today Internet, HTTP-based web content delivery still suffers from various content delivery failures. Hindered by the expensive deployment cost, the conventional CDN can not deploy as many edge servers as possible to successfully deliver content items to all users under these delivery failures. In this paper, we propose a joint CDN and peer-assisted web content delivery framework to address the delivery failure problem. Different from conventional peer-assisted approaches for web content delivery, which mainly focus on alleviating the CDN servers bandwidth load, we study how to use a browser-based peer-assisted scheme, namely WebRTC, to resolve content delivery failures. To this end, we carry out large-scale measurement studies on how users access and view webpages. Our measurement results demonstrate the challenges (e.g., peers stay on a webpage extremely short) that can not be directly solved by conventional P2P strategies, and some important webpage viewing patterns. Due to these unique characteristics, WebRTC peers open up new possibilities for helping the web content delivery, coming with the problem of how to utilize the dynamic resources efficiently. We formulate the peer selection that is the critical strategy in our framework, as an optimization problem, and design a heuristic algorithm based on the measurement insights to solve it. Our simulation experiments driven by the traces from Tencent QZone demonstrate the effectiveness of our design: compared with non-peer-assisted strategy and random peer selection strategy, our design significantly improves the successful relay ratio of web content items under network failures, e.g., our design improves the content download ratio up to 60% even when users located in a particular region (e.g., city) where none can connect to the regional CDN server.
Unit Interval Vertex Deletion: Fewer Vertices are Relevant
Venue: arXiv cs.DS 2016
Year: 2016

The unit interval vertex deletion problem asks for a set of at most $k$ vertices whose deletion from an $n$-vertex graph makes it a unit interval graph. We develop an $O(k^4)$-vertex kernel for the problem, significantly improving the $O(k^{53})$-vertex kernel of Fomin, Saurabh, and Villanger [ESA'12; SIAM J. Discrete Math 27(2013)]. We introduce a novel way of organizing cliques of a unit interval graph. Our constructive proof for the correctness of our algorithm, using interval models, greatly simplifies the destructive proofs, based on forbidden induced subgraphs, for similar problems in literature.
A Measurement Study of TCP Performance for Chunk Delivery in DASH
Venue: arXiv cs.MM 2016
Year: 2016

Dynamic Adaptive Streaming over HTTP (DASH) has emerged as an increasingly popular paradigm for video streaming [13], in which a video is segmented into many chunks delivered to users by HTTP request/response over Transmission Control Protocol (TCP) con- nections. Therefore, it is intriguing to study the performance of strategies implemented in conventional TCPs, which are not dedicated for video streaming, e.g., whether chunks are efficiently delivered when users per- form interactions with the video players. In this paper, we conduct mea- surement studies on users chunk requesting traces in DASH from a rep- resentative video streaming provider, to investigate users behaviors in DASH, and TCP-connection-level traces from CDN servers, to investi- gate the performance of TCP for DASH. By studying how video chunks are delivered in both the slow start and congestion avoidance phases, our observations have revealed the performance characteristics of TCP for DASH as follows: (1) Request patterns in DASH have a great impact on the performance of TCP variations including cubic; (2) Strategies in conventional TCPs may cause user perceived quality degradation in DASH streaming; (3) Potential improvement to TCP strategies for better delivery in DASH can be further explored.
Calculation of mutual information for nonlinear communication channel at large SNR
Venue: arXiv cs.IT 2016
Year: 2016

Using the path-integral technique we examine the mutual information for the communication channel modelled by the nonlinear Schrödinger equation with additive Gaussian noise. The nonlinear Schrödinger equation is one of the fundamental models in nonlinear physics, and it has a broad range of applications, including fiber optical communications --- the backbone of the Internet. At large signal-to-noise ratio ($\mathrm{SNR}$) we present the mutual information through the path-integral which is convenient for the perturbative expansion in nonlinearity. In the limit of small noise and small nonlinearity we derive analytically the first nonzero nonlinear correction to the mutual information for the channel.
TTC: A Tensor Transposition Compiler for Multiple Architectures
Venue: arXiv cs.MS 2016
Year: 2016

We consider the problem of transposing tensors of arbitrary dimension and describe TTC, an open source domain-specific parallel compiler. TTC generates optimized parallel C++/CUDA C code that achieves a significant fraction of the system's peak memory bandwidth. TTC exhibits high performance across multiple architectures, including modern AVX-based systems (e.g.,~Intel Haswell, AMD Steamroller), Intel's Knights Corner as well as different CUDA-based GPUs such as NVIDIA's Kepler and Maxwell architectures. We report speedups of TTC over a meaningful baseline implementation generated by external C++ compilers; the results suggest that a domain-specific compiler can outperform its general purpose counterpart significantly: For instance, comparing with Intel's latest C++ compiler on the Haswell and Knights Corner architecture, TTC yields speedups of up to $8\times$ and $32\times$, respectively. We also showcase TTC's support for multiple leading dimensions, making it a suitable candidate for the generation of performance-critical packing functions that are at the core of the ubiquitous BLAS 3 routines.
Unifying notions of generalized weights for universal security on wire-tap networks
Venue: arXiv cs.IT 2016
Year: 2016

Universal security over a network with linear network coding has been intensively studied. However, previous linear codes used for this purpose were linear over a larger field than that used on the network. In this work, we introduce new parameters (relative dimension/rank support profile and relative generalized matrix weights) for linear codes that are linear over the field used in the network, measuring the universal security performance of these codes. The proposed new parameters enable us to use optimally universal secure linear codes on noiseless networks for all possible parameters, as opposed to previous works, and also enable us to add universal security to the recently proposed list-decodable rank-metric codes by Guruswami et al. We give several properties of the new parameters: monotonicity, Singleton-type lower and upper bounds, a duality theorem, and definitions and characterizations of equivalences of linear codes. Finally, we show that our parameters strictly extend relative dimension/length profile and relative generalized Hamming weights, respectively, and relative dimension/intersection profile and relative generalized rank weights, respectively. Moreover, we show that generalized matrix weights are larger than Delsarte generalized weights.
Randomly Generated Subgroups of the Symmetric Group and Random Lifts of Graphs
Venue: arXiv cs.DM 2016
Year: 2016

Amit and Linial showed that a random lift of a graph with minimum degree $δ\ge3$ is asymptotically almost surely $δ$-connected, and mentioned the problem of estimating this probability as a function of the degree of the lift. We relate a randomly generated subgroup of the symmetric group on $n$ elements to random $n$-lifts of a graph and use it to provide such an estimate along with related results. We also improve their later result showing a lower bound on the edge expansion on random lifts. Our proofs rely on new ideas from group theory which make several improvements possible. We exactly calculate the probability that a random lift of a connected graph with first Betti number $l$ is connected by showing that it is equal to the probability that a subgroup of the symmetric group generated by $l$ random elements is transitive. We also calculate the probability that a subgroup of a wreath product of symmetric groups generated by $l$ random generators is transitive. We show the existence of homotopy invariants in random covering graphs which reduces some of their properties to those of random regular multigraphs, and in particular makes it possible to compute the exact probability with which random regular multigraphs are connected. All our results about random lifts easily extend to iterated random lifts.
Matrix Factorization at Scale: a Comparison of Scientific Data Analytics in Spark and C+MPI Using Three Case Studies
Venue: arXiv cs.DC 2016
Year: 2016

We explore the trade-offs of performing linear algebra using Apache Spark, compared to traditional C and MPI implementations on HPC platforms. Spark is designed for data analytics on cluster computing platforms with access to local disks and is optimized for data-parallel tasks. We examine three widely-used and important matrix factorizations: NMF (for physical plausability), PCA (for its ubiquity) and CX (for data interpretability). We apply these methods to TB-sized problems in particle physics, climate modeling and bioimaging. The data matrices are tall-and-skinny which enable the algorithms to map conveniently into Spark's data-parallel model. We perform scaling experiments on up to 1600 Cray XC40 nodes, describe the sources of slowdowns, and provide tuning guidance to obtain high performance.
Extended LTLvis Motion Planning interface (Extended Technical Report)
Venue: arXiv cs.RO 2016
Year: 2016

This paper introduces an extended version of the Linear Temporal Logic (LTL) graphical interface. It is a sketch based interface built on the Android platform which makes the LTL control interface more straightforward and friendly to nonexpert users. By predefining a set of areas of interest, this interface can quickly and efficiently create plans that satisfy extended plan goals in LTL. The interface can also allow users to customize the paths for this plan by sketching a set of reference trajectories. Given the custom paths by the user, the LTL specification and the environment, the interface generates a plan balancing the customized paths and the LTL specifications. We also show experimental results with the implemented interface.
A Generalized Framework on Beamformer Design and CSI Acquisition for Single-Carrier Massive MIMO Systems in Millimeter Wave Channels
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we establish a general framework on the reduced dimensional channel state information (CSI) estimation and pre-beamformer design for frequency-selective massive multiple-input multiple-output MIMO systems employing single-carrier (SC) modulation in time division duplex (TDD) mode by exploiting the joint angle-delay domain channel sparsity in millimeter (mm) wave frequencies. First, based on a generic subspace projection taking the joint angle-delay power profile and user-grouping into account, the reduced rank minimum mean square error (RR-MMSE) instantaneous CSI estimator is derived for spatially correlated wideband MIMO channels. Second, the statistical pre-beamformer design is considered for frequency-selective SC massive MIMO channels. We examine the dimension reduction problem and subspace (beamspace) construction on which the RR-MMSE estimation can be realized as accurately as possible. Finally, a spatio-temporal domain correlator type reduced rank channel estimator, as an approximation of the RR-MMSE estimate, is obtained by carrying out least square (LS) estimation in a proper reduced dimensional beamspace. It is observed that the proposed techniques show remarkable robustness to the pilot interference (or contamination) with a significant reduction in pilot overhead.
Effectiveness of Rapid Rail Transit System in Beijing
Venue: arXiv cs.SI 2016
Year: 2016

The effectiveness of rapid rail transit system is analyzed using tools of complex network for the first time. We evaluated the effectiveness of the system in Beijing quantitatively from different perspectives, including descriptive statistics analysis, bridging property, centrality property, ability of connecting different part of the system and ability of disease spreading. The results showed that the public transport of Beijing does benefit from the rapid rail transit lines, but there is still room to improve. The paper concluded with some policy suggestions regarding how to promote the system. This study offered significant insight that can help understand the public transportation better. The methodology can be easily applied to analyze other urban public systems, such as electricity grid, water system, to develop more livable cities.
Mixed Strategy for Constrained Stochastic Optimal Control
Venue: arXiv cs.RO 2016
Year: 2016

Choosing control inputs randomly can result in a reduced expected cost in optimal control problems with stochastic constraints, such as stochastic model predictive control (SMPC). We consider a controller with initial randomization, meaning that the controller randomly chooses from K+1 control sequences at the beginning (called K-randimization).It is known that, for a finite-state, finite-action Markov Decision Process (MDP) with K constraints, K-randimization is sufficient to achieve the minimum cost. We found that the same result holds for stochastic optimal control problems with continuous state and action spaces.Furthermore, we show the randomization of control input can result in reduced cost when the optimization problem is nonconvex, and the cost reduction is equal to the duality gap. We then provide the necessary and sufficient conditions for the optimality of a randomized solution, and develop an efficient solution method based on dual optimization. Furthermore, in a special case with K=1 such as a joint chance-constrained problem, the dual optimization can be solved even more efficiently by root finding. Finally, we test the theories and demonstrate the solution method on multiple practical problems ranging from path planning to the planning of entry, descent, and landing (EDL) for future Mars missions.
Extracting Formal Models from Normative Texts
Venue: arXiv cs.CL 2016
Year: 2016

Normative texts are documents based on the deontic notions of obligation, permission, and prohibition. Our goal is to model such texts using the C-O Diagram formalism, making them amenable to formal analysis, in particular verifying that a text satisfies properties concerning causality of actions and timing constraints. We present an experimental, semi-automatic aid to bridge the gap between a normative text and its formal representation. Our approach uses dependency trees combined with our own rules and heuristics for extracting the relevant components. The resulting tabular data can then be converted into a C-O Diagram.
Towards Self-explanatory Ontology Visualization with Contextual Verbalization
Venue: arXiv cs.AI 2016
Year: 2016

Ontologies are one of the core foundations of the Semantic Web. To participate in Semantic Web projects, domain experts need to be able to understand the ontologies involved. Visual notations can provide an overview of the ontology and help users to understand the connections among entities. However, the users first need to learn the visual notation before they can interpret it correctly. Controlled natural language representation would be readable right away and might be preferred in case of complex axioms, however, the structure of the ontology would remain less apparent. We propose to combine ontology visualizations with contextual ontology verbalizations of selected ontology (diagram) elements, displaying controlled natural language (CNL) explanations of OWL axioms corresponding to the selected visual notation elements. Thus, the domain experts will benefit from both the high-level overview provided by the graphical notation and the detailed textual explanations of particular elements in the diagram.
Message Importance Measure and Its Application to Minority Subset Detection in Big Data
Venue: arXiv cs.IT 2016
Year: 2016

Message importance measure (MIM) is an important index to describe the message importance in the scenario of big data. Similar to the Shannon Entropy and Renyi Entropy, MIM is required to characterize the uncertainty of a random process and some related statistical characteristics. Moreover, MIM also need to highlight the importance of those events with relatively small occurring probabilities, thereby is especially applicable to big data. In this paper, we first define a parametric MIM measure from the viewpoint of information theory and then investigate its properties. We also present a parameter selection principle that provides answers to the minority subsets detection problem in the statistical processing of big data.