OpenRaiser/Intern-Atlas huggingface dataset:
Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing
Venue: arXiv cs.DS 2016
Year: 2016

In this paper, we present a new data structure called the packed compact trie (packed c-trie) which stores a set $S$ of $k$ strings of total length $n$ in $n \logσ+ O(k \log n)$ bits of space and supports fast pattern matching queries and updates, where $σ$ is the size of an alphabet. Assume that $α= \log_σn$ letters are packed in a single machine word on the standard word RAM model, and let $f(k,n)$ denote the query and update times of the dynamic predecessor/successor data structure of our choice which stores $k$ integers from universe $[1,n]$ in $O(k \log n)$ bits of space. Then, given a string of length $m$, our packed c-tries support pattern matching queries and insert/delete operations in $O(\frac{m}α f(k,n))$ worst-case time and in $O(\frac{m}α + f(k,n))$ expected time. Our experiments show that our packed c-tries are faster than the standard compact tries (a.k.a. Patricia trees) on real data sets. As an application of our packed c-trie, we show that the sparse suffix tree for a string of length $n$ over prefix codes with $k$ sampled positions, such as evenly-spaced and word delimited sparse suffix trees, can be constructed online in $O((\frac{n}α + k) f(k,n))$ worst-case time and $O(\frac{n}α + k f(k,n))$ expected time with $n \log σ+ O(k \log n)$ bits of space. When $k = O(\frac{n}α)$, by using the state-of-the-art dynamic predecessor/successor data structures, we obtain sub-linear time construction algorithms using only $O(\frac{n}α)$ bits of space in both cases. We also discuss an application of our packed c-tries to online LZD factorization.
Reduction-Based Creative Telescoping for Algebraic Functions
Venue: arXiv cs.SC 2016
Year: 2016

Continuing a series of articles in the past few years on creative telescoping using reductions, we develop a new algorithm to construct minimal telescopers for algebraic functions. This algorithm is based on Trager's Hermite reduction and on polynomial reduction, which was originally designed for hyperexponential functions and extended to the algebraic case in this paper.
A Graph Representation for Two-Dimensional Finite Type Constrained Systems
Venue: arXiv cs.IT 2016
Year: 2016

The demand of two-dimensional source coding and constrained coding has been getting higher these days, but compared to the one-dimensional case, many problems have remained open as the analysis is cumbersome. A main reason for that would be because there are no graph representations discovered so far. In this paper, we focus on a two-dimensional finite type constrained system, a set of two-dimensional blocks characterized by a finite number of two-dimensional constraints, and propose its graph representation. We then show how to generate an element of the two-dimensional finite type constrained system from the graph representation.
Power Allocation and Scheduling for SWIPT Systems with Non-linear Energy Harvesting Model
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we design a resource allocation algorithm for multiuser simultaneous wireless information and power transfer systems for a realistic non-linear energy harvesting (EH) model. In particular, the algorithm design is formulated as a non-convex optimization problem for the maximization of the long-term average total harvested power at EH receivers subject to quality of service requirements for information decoding receivers. To obtain a tractable solution, we transform the corresponding non-convex sum-of-ratios objective function into an equivalent objective function in parametric subtractive form. This leads to a computationally efficient iterative resource allocation algorithm. Numerical results reveal a significant performance gain that can be achieved if the resource allocation algorithm design is based on the non-linear EH model instead of the traditional linear model.
I Know What You Saw Last Minute - Encrypted HTTP Adaptive Video Streaming Title Classification
Venue: arXiv cs.MM 2016
Year: 2016

Desktops and laptops can be maliciously exploited to violate privacy. There are two main types of attack scenarios: active and passive. In this paper, we consider the passive scenario where the adversary does not interact actively with the device, but he is able to eavesdrop on the network traffic of the device from the network side. Most of the Internet traffic is encrypted and thus passive attacks are challenging. Previous research has shown that information can be extracted from encrypted multimedia streams. This includes video title classification of non HTTP adaptive streams (non-HAS). This paper presents an algorithm for encrypted HTTP adaptive video streaming title classification. We show that an external attacker can identify the video title from video HTTP adaptive streams (HAS) sites such as YouTube. To the best of our knowledge, this is the first work that shows this. We provide a large data set of 10000 YouTube video streams of 100 popular video titles (each title downloaded 100 times) as examples for this task. The dataset was collected under real-world network conditions. We present several machine algorithms for the task and run a through set of experiments, which shows that our classification accuracy is more than 95%. We also show that our algorithms are able to classify video titles that are not in the training set as unknown and some of the algorithms are also able to eliminate false prediction of video titles and instead report unknown. Finally, we evaluate our algorithms robustness to delays and packet losses at test time and show that a solution that uses SVM is the most robust against these changes given enough training data. We provide the dataset and the crawler for future research.
GRAD: On Graph Database Modeling
Venue: arXiv cs.DB 2016
Year: 2016

Graph databases have emerged as the fundamental technology underpinning trendy application domains where traditional databases are not well-equipped to handle complex graph data. However, current graph databases support basic graph structures and integrity constraints with no standard algebra. In this paper, we introduce GRAD, a native and generic graph database model. GRAD goes beyond traditional graph database models, which support simple graph structures and constraints. Instead, GRAD presents a complete graph database model supporting advanced graph structures, a set of well-defined constraints over these structures and a powerful graph analysis-oriented algebra.
Functional Dependencies Unleashed for Scalable Data Exchange
Venue: arXiv cs.DB 2016
Year: 2016

We address the problem of efficiently evaluating target functional dependencies (fds) in the Data Exchange (DE) process. Target fds naturally occur in many DE scenarios, including the ones in Life Sciences in which multiple source relations need to be structured under a constrained target schema. However, despite their wide use, target fds' evaluation is still a bottleneck in the state-of-the-art DE engines. Systems relying on an all-SQL approach typically do not support target fds unless additional information is provided. Alternatively, DE engines that do include these dependencies typically pay the price of a significant drop in performance and scalability. In this paper, we present a novel chase-based algorithm that can efficiently handle arbitrary fds on the target. Our approach essentially relies on exploiting the interactions between source-to-target (s-t) tuple-generating dependencies (tgds) and target fds. This allows us to tame the size of the intermediate chase results, by playing on a careful ordering of chase steps interleaving fds and (chosen) tgds. As a direct consequence, we importantly diminish the fd application scope, often a central cause of the dramatic overhead induced by target fds. Moreover, reasoning on dependency interaction further leads us to interesting parallelization opportunities, yielding additional scalability gains. We provide a proof-of-concept implementation of our chase-based algorithm and an experimental study aiming at gauging its scalability with respect to a number of parameters, among which the size of source instances and the number of dependencies of each tested scenario. Finally, we empirically compare with the latest DE engines, and show that our algorithm outperforms them.
A Deep Learning Based Fast Image Saliency Detection Algorithm
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we propose a fast deep learning method for object saliency detection using convolutional neural networks. In our approach, we use a gradient descent method to iteratively modify the input images based on the pixel-wise gradients to reduce a pre-defined cost function, which is defined to measure the class-specific objectness and clamp the class-irrelevant outputs to maintain image background. The pixel-wise gradients can be efficiently computed using the back-propagation algorithm. We further apply SLIC superpixels and LAB color based low level saliency features to smooth and refine the gradients. Our methods are quite computationally efficient, much faster than other deep learning based saliency methods. Experimental results on two benchmark tasks, namely Pascal VOC 2012 and MSRA10k, have shown that our proposed methods can generate high-quality salience maps, at least comparable with many slow and complicated deep learning methods. Comparing with the pure low-level methods, our approach excels in handling many difficult images, which contain complex background, highly-variable salient objects, multiple objects, and/or very small salient objects.
Autonomous Agent Behaviour Modelled in PRISM -- A Case Study
Venue: arXiv cs.SY 2016
Year: 2016

Formal verification of agents representing robot behaviour is a growing area due to the demand that autonomous systems have to be proven safe. In this paper we present an abstract definition of autonomy which can be used to model autonomous scenarios and propose the use of small-scale simulation models representing abstract actions to infer quantitative data. To demonstrate the applicability of the approach we build and verify a model of an unmanned aerial vehicle (UAV) in an exemplary autonomous scenario, utilising this approach.
Combining ConvNets with Hand-Crafted Features for Action Recognition Based on an HMM-SVM Classifier
Venue: arXiv cs.CV 2016
Year: 2016

This paper proposes a new framework for RGB-D-based action recognition that takes advantages of hand-designed features from skeleton data and deeply learned features from depth maps, and exploits effectively both the local and global temporal information. Specifically, depth and skeleton data are firstly augmented for deep learning and making the recognition insensitive to view variance. Secondly, depth sequences are segmented using the hand-crafted features based on skeleton joints motion histogram to exploit the local temporal information. All training se gments are clustered using an Infinite Gaussian Mixture Model (IGMM) through Bayesian estimation and labelled for training Convolutional Neural Networks (ConvNets) on the depth maps. Thus, a depth sequence can be reliably encoded into a sequence of segment labels. Finally, the sequence of labels is fed into a joint Hidden Markov Model and Support Vector Machine (HMM-SVM) classifier to explore the global temporal information for final recognition.
User Access Mode Selection in Fog Computing Based Radio Access Networks
Venue: arXiv cs.IT 2016
Year: 2016

Fog computing based radio access network is a promising paradigm for the fifth generation wireless communication system to provide high spectral and energy efficiency. With the help of the new designed fog computing based access points (F-APs), the user-centric objectives can be achieved through the adaptive technique and will relieve the load of fronthaul and alleviate the burden of base band unit pool. In this paper, we derive the coverage probability and ergodic rate for both F-AP users and device-to-device users by taking into account the different nodes locations, cache sizes as well as user access modes. Particularly, the stochastic geometry tool is used to derive expressions for above performance metrics. Simulation results validate the accuracy of our analysis and we obtain interesting trade-offs that depend on the effect of the cache size, user node density, and the quality of service constrains on the different performance metrics.
Research on Information Security Enhancement Approaches and the Applications on HCI Systems
Venue: arXiv cs.HC 2016
Year: 2016

With rapid development of computer techniques, the human computer interaction scenarios are becoming more and more frequent. The development history of the human-computer interaction is from a person to adapt to the computer to the computer and continually adapt to the rapid development. Facing the process of human-computer interaction, information system daily operation to produce huge amounts of data, how to ensure human-computer interaction interface clear, generated data safe and reliable, has become a problem to be solved in the world of information. To deal with the challenging, we propose the information security enhancement approaches and the core applications on HCI systems. Through reviewing the other state-of-the-art methods, we propose the data encryption system to deal with the issues that uses mixed encryption system to make full use of the symmetric cipher algorithm encryption speed and encryption intensity is high while the encryption of large amounts of data efficiently. Our method could enhance the general safety of the HCI system, the experimental result verities the feasibility and general robustness of our approach.
On Physical Web models
Venue: arXiv cs.CY 2016
Year: 2016

The Physical Web is a generic term describes interconnection of physical objects and web. The Physical Web lets present physical objects in a web. There are different ways to do that and we will discuss them in our paper. Usually, the web presentation for a physical object could be implemented with the help of mobile devices. The basic idea behind the Physical Web is to navigate and control physical objects in the world surrounding mobile devices with the help of web technologies. Of course, there are different ways to identify and enumerate physical objects. In this paper, we describe the existing models as well as related challenges. In our analysis, we will target objects enumeration and navigation as well as data retrieving and programming for the Physical Web.
Partial Recovery Bounds for the Sparse Stochastic Block Model
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we study the information-theoretic limits of community detection in the symmetric two-community stochastic block model, with intra-community and inter-community edge probabilities $\frac{a}{n}$ and $\frac{b}{n}$ respectively. We consider the sparse setting, in which $a$ and $b$ do not scale with $n$, and provide upper and lower bounds on the proportion of community labels recovered on average. We provide a numerical example for which the bounds are near-matching for moderate values of $a - b$, and matching in the limit as $a-b$ grows large.
BANZKP: a Secure Authentication Scheme Using Zero Knowledge Proof for WBANs
Venue: arXiv cs.CR 2016
Year: 2016

-Wireless body area network(WBAN) has shown great potential in improving healthcare quality not only for patients but also for medical staff. However, security and privacy are still an important issue in WBANs especially in multi-hop architectures. In this paper, we propose and present the design and the evaluation of a secure lightweight and energy efficient authentication scheme BANZKP based on an efficient cryptographic protocol, Zero Knowledge Proof (ZKP) and a commitment scheme. ZKP is used to confirm the identify of the sensor nodes, with small computational requirement, which is favorable for body sensors given their limited resources, while the commitment scheme is used to deal with replay attacks and hence the injection attacks by committing a message and revealing the key later. Our scheme reduces the memory requirement by 56.13 % compared to TinyZKP [13], the comparable alternative so far for Body Area Networks, and uses 10 % less energy.
Algorithms and Heuristics for Scalable Betweenness Centrality Computation on Multi-GPU Systems
Venue: arXiv cs.DC 2016
Year: 2016

Betweenness Centrality (BC) is steadily growing in popularity as a metrics of the influence of a vertex in a graph. The BC score of a vertex is proportional to the number of all-pairs-shortest-paths passing through it. However, complete and exact BC computation for a large-scale graph is an extraordinary challenge that requires high performance computing techniques to provide results in a reasonable amount of time. Our approach combines bi-dimensional (2-D) decomposition of the graph and multi-level parallelism together with a suitable data-thread mapping that overcomes most of the difficulties caused by the irregularity of the computation on GPUs. Furthermore, we propose novel heuristics which exploit the topology information of the graph in order to reduce time and space requirements of BC computation. Experimental results on synthetic and real-world graphs show that the proposed techniques allow the BC computation of graphs which are too large to fit in the memory of a single computational node along with a significant reduction of the computing time.
CPL: A Core Language for Cloud Computing -- Technical Report
Venue: arXiv cs.PL 2016
Year: 2016

Running distributed applications in the cloud involves deployment. That is, distribution and configuration of application services and middleware infrastructure. The considerable complexity of these tasks resulted in the emergence of declarative JSON-based domain-specific deployment languages to develop deployment programs. However, existing deployment programs unsafely compose artifacts written in different languages, leading to bugs that are hard to detect before run time. Furthermore, deployment languages do not provide extension points for custom implementations of existing cloud services such as application-specific load balancing policies. To address these shortcomings, we propose CPL (Cloud Platform Language), a statically-typed core language for programming both distributed applications as well as their deployment on a cloud platform. In CPL, application services and deployment programs interact through statically typed, extensible interfaces, and an application can trigger further deployment at run time. We provide a formal semantics of CPL and demonstrate that it enables type-safe, composable and extensible libraries of service combinators, such as load balancing and fault tolerance.
Head Pose Estimation of Occluded Faces using Regularized Regression
Venue: arXiv cs.CV 2016
Year: 2016

This paper presents regression methods for estimation of head pose from occluded 2-D face images. The process primarily involves reconstructing a face from its occluded image, followed by classification. Typical methods for reconstruction assume that the pixel errors of the occluded regions are independent. However, such an assumption is not true in the case of occlusion, because of its inherent contiguous nature. Hence, we use nuclear norm as a metric that can describe well the structure of the error. We also use LASSO Regression based l1 - regularization to improve reconstruction. Next, we implement Nuclear Norm Regularized Regression (NR), and also our proposed method, for reconstruction and subsequent classification. Finally, we compare the performance of the methods in terms of accuracy of head pose estimation of occluded faces.
Network Clustering via Maximizing Modularity: Approximation Algorithms and Theoretical Limits
Venue: arXiv cs.SI 2016
Year: 2016

Many social networks and complex systems are found to be naturally divided into clusters of densely connected nodes, known as community structure (CS). Finding CS is one of fundamental yet challenging topics in network science. One of the most popular classes of methods for this problem is to maximize Newman's modularity. However, there is a little understood on how well we can approximate the maximum modularity as well as the implications of finding community structure with provable guarantees. In this paper, we settle definitely the approximability of modularity clustering, proving that approximating the problem within any (multiplicative) positive factor is intractable, unless P = NP. Yet we propose the first additive approximation algorithm for modularity clustering with a constant factor. Moreover, we provide a rigorous proof that a CS with modularity arbitrary close to maximum modularity QOPT might bear no similarity to the optimal CS of maximum modularity. Thus even when CS with near-optimal modularity are found, other verification methods are needed to confirm the significance of the structure.
On Deep Multi-View Representation Learning: Objectives and Optimization
Venue: arXiv cs.LG 2016
Year: 2016

We consider learning representations (features) in the setting in which we have access to multiple unlabeled views of the data for learning while only one view is available for downstream tasks. Previous work on this problem has proposed several techniques based on deep neural networks, typically involving either autoencoder-like networks with a reconstruction objective or paired feedforward networks with a batch-style correlation-based objective. We analyze several techniques based on prior work, as well as new variants, and compare them empirically on image, speech, and text tasks. We find an advantage for correlation-based representation learning, while the best results on most tasks are obtained with our new variant, deep canonically correlated autoencoders (DCCAE). We also explore a stochastic optimization procedure for minibatch correlation-based objectives and discuss the time/performance trade-offs for kernel-based and neural network-based implementations.
Scalable Ontological Query Processing over Semantically Integrated Life Science Datasets using MapReduce
Venue: arXiv cs.DB 2016
Year: 2016

To address the requirement of enabling a comprehensive perspective of life-sciences data, Semantic Web technologies have been adopted for standardized representations of data and linkages between data. This has resulted in data warehouses such as UniProt, Bio2RDF, and Chem2Bio2RDF, that integrate different kinds of biological and chemical data using ontologies. Unfortunately, the ability to process queries over ontologically-integrated collections remains a challenge, particularly when data is large. The reason is that besides the traditional challenges of processing graph-structured data, complete query answering requires inferencing to explicate implicitly represented facts. Since traditional inferencing techniques like forward chaining are difficult to scale up, and need to be repeated each time data is updated, recent focus has been on inferencing that can be supported using database technologies via query rewriting. However, due to the richness of most biomedical ontologies relative to other domain ontologies, the queries resulting from the query rewriting technique are often more complex than existing query optimization techniques can cope with. This is particularly so when using the emerging class of cloud data processing platforms for big data processing due to some additional overhead which they introduce. In this paper, we present an approach for dealing such complex queries on big data using MapReduce, along with an evaluation on existing real-world datasets and benchmark queries.