OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Dynamic Multicast Scheduling for Cache-Enabled Content-Centric Wireless Networks
Venue: arXiv cs.IT 2016
Year: 2016

Caching and multicasting at base stations are two promising approaches to support massive content delivery over wireless networks. However, existing scheduling designs do not make full use of the advantages of the two approaches. In this paper, we consider the optimal dynamic multicast scheduling to jointly minimize the average delay, power, and fetching costs for cache-enabled content-centric wireless networks. We formulate this stochastic optimization problem as an infinite horizon average cost Markov decision process (MDP). It is well-known to be a difficult problem due to the curse of dimensionality, and there generally only exist numerical solutions. By using relative value iteration algorithm and the special structures of the request queue dynamics, we analyze the properties of the value function and the state-action cost function of the MDP for both the uniform and nonuniform channel cases. Based on these properties, we show that the optimal policy, which is adaptive to the request queue state, has a switch structure in the uniform case and a partial switch structure in the nonuniform case. Moreover, in the uniform case with two contents, we show that the switch curve is monotonically non-decreasing. Then, by exploiting these structural properties of the optimal policy, we propose two low-complexity optimal algorithms. Motivated by the switch structures of the optimal policy, to further reduce the complexity, we also propose a low-complexity suboptimal policy, which possesses similar structural properties to the optimal policy, and develop a low-complexity algorithm to compute this policy.
Negatively Correlated Search
Venue: arXiv cs.NE 2016
Year: 2016

Evolutionary Algorithms (EAs) have been shown to be powerful tools for complex optimization problems, which are ubiquitous in both communication and big data analytics. This paper presents a new EA, namely Negatively Correlated Search (NCS), which maintains multiple individual search processes in parallel and models the search behaviors of individual search processes as probability distributions. NCS explicitly promotes negatively correlated search behaviors by encouraging differences among the probability distributions (search behaviors). By this means, individual search processes share information and cooperate with each other to search diverse regions of a search space, which makes NCS a promising method for non-convex optimization. The cooperation scheme of NCS could also be regarded as a novel diversity preservation scheme that, different from other existing schemes, directly promotes diversity at the level of search behaviors rather than merely trying to maintain diversity among candidate solutions. Empirical studies showed that NCS is competitive to well-established search methods in the sense that NCS achieved the best overall performance on 20 multimodal (non-convex) continuous optimization problems. The advantages of NCS over state-of-the-art approaches are also demonstrated with a case study on the synthesis of unequally spaced linear antenna arrays.
Online Social Network Analysis: A Survey of Research Applications in Computer Science
Venue: arXiv cs.SI 2016
Year: 2016

The emergence and popularization of online social networks suddenly made available a large amount of data from social organization, interaction and human behavior. All this information opens new perspectives and challenges to the study of social systems, being of interest to many fields. Although most online social networks are recent (less than fifteen years old), a vast amount of scientific papers was already published on this topic, dealing with a broad range of analytical methods and applications. This work describes how computational researches have approached this subject and the methods used to analyze such systems. Founded on a wide though non-exaustive review of the literature, a taxonomy is proposed to classify and describe different categories of research. Each research category is described and the main works, discoveries and perspectives are highlighted.
An FPT algorithm and a polynomial kernel for Linear Rankwidth-1 Vertex Deletion
Venue: arXiv cs.DS 2016
Year: 2016

Linear rankwidth is a linearized variant of rankwidth, introduced by Oum and Seymour [Approximating clique-width and branch-width. J. Combin. Theory Ser. B, 96(4):514--528, 2006]. Motivated from recent development on graph modification problems regarding classes of graphs of bounded treewidth or pathwidth, we study the Linear Rankwidth-1 Vertex Deletion problem (shortly, LRW1-Vertex Deletion). In the LRW1-Vertex Deletion problem, given an $n$-vertex graph $G$ and a positive integer $k$, we want to decide whether there is a set of at most $k$ vertices whose removal turns $G$ into a graph of linear rankwidth at most $1$ and find such a vertex set if one exists. While the meta-theorem of Courcelle, Makowsky, and Rotics implies that LRW1-Vertex Deletion can be solved in time $f(k)\cdot n^3$ for some function $f$, it is not clear whether this problem allows a running time with a modest exponential function. We first establish that LRW1-Vertex Deletion can be solved in time $8^k\cdot n^{\mathcal{O}(1)}$. The major obstacle to this end is how to handle a long induced cycle as an obstruction. To fix this issue, we define necklace graphs and investigate their structural properties. Later, we reduce the polynomial factor by refining the trivial branching step based on a cliquewidth expression of a graph, and obtain an algorithm that runs in time $2^{\mathcal{O}(k)}\cdot n^4$. We also prove that the running time cannot be improved to $2^{o(k)}\cdot n^{\mathcal{O}(1)}$ under the Exponential Time Hypothesis assumption. Lastly, we show that the LRW1-Vertex Deletion problem admits a polynomial kernel.
Deterministically Deterring Timing Attacks in Deterland
Venue: arXiv cs.OS 2016
Year: 2016

The massive parallelism and resource sharing embodying today's cloud business model not only exacerbate the security challenge of timing channels, but also undermine the viability of defenses based on resource partitioning. We propose hypervisor-enforced timing mitigation to control timing channels in cloud environments. This approach closes "reference clocks" internal to the cloud by imposing a deterministic view of time on guest code, and uses timing mitigators to pace I/O and rate-limit potential information leakage to external observers. Our prototype hypervisor is the first system to mitigate timing-channel leakage across full-scale existing operating systems such as Linux and applications in arbitrary languages. Mitigation incurs a varying performance cost, depending on workload and tunable leakage-limiting parameters, but this cost may be justified for security-critical cloud applications and data.
Surrogate regret bounds for generalized classification performance metrics
Venue: arXiv cs.LG 2016
Year: 2016

We consider optimization of generalized performance metrics for binary classification by means of surrogate losses. We focus on a class of metrics, which are linear-fractional functions of the false positive and false negative rates (examples of which include $F_β$-measure, Jaccard similarity coefficient, AM measure, and many others). Our analysis concerns the following two-step procedure. First, a real-valued function $f$ is learned by minimizing a surrogate loss for binary classification on the training sample. It is assumed that the surrogate loss is a strongly proper composite loss function (examples of which include logistic loss, squared-error loss, exponential loss, etc.). Then, given $f$, a threshold $\widehatθ$ is tuned on a separate validation sample, by direct optimization of the target performance metric. We show that the regret of the resulting classifier (obtained from thresholding $f$ on $\widehatθ$) measured with respect to the target metric is upperbounded by the regret of $f$ measured with respect to the surrogate loss. We also extend our results to cover multilabel classification and provide regret bounds for micro- and macro-averaging measures. Our findings are further analyzed in a computational study on both synthetic and real data sets.
Nonlinear Markov Processes in Big Networks
Venue: arXiv cs.SY 2016
Year: 2016

Big networks express various large-scale networks in many practical areas such as computer networks, internet of things, cloud computation, manufacturing systems, transportation networks, and healthcare systems. This paper analyzes such big networks, and applies the mean-field theory and the nonlinear Markov processes to set up a broad class of nonlinear continuous-time block-structured Markov processes, which can be applied to deal with many practical stochastic systems. Firstly, a nonlinear Markov process is derived from a large number of interacting big networks with symmetric interactions, each of which is described as a continuous-time block-structured Markov process. Secondly, some effective algorithms are given for computing the fixed points of the nonlinear Markov process by means of the UL-type RG-factorization. Finally, the Birkhoff center, the Lyapunov functions and the relative entropy are used to analyze stability or metastability of the big network, and several interesting open problems are proposed with detailed interpretation. We believe that the results given in this paper can be useful and effective in the study of big networks.
Note on Equivalence Between Recurrent Neural Network Time Series Models and Variational Bayesian Models
Venue: arXiv cs.LG 2016
Year: 2016

We observe that the standard log likelihood training objective for a Recurrent Neural Network (RNN) model of time series data is equivalent to a variational Bayesian training objective, given the proper choice of generative and inference models. This perspective may motivate extensions to both RNNs and variational Bayesian models. We propose one such extension, where multiple particles are used for the hidden state of an RNN, allowing a natural representation of uncertainty or multimodality.
Information-theoretic Interestingness Measures for Cross-Ontology Data Mining
Venue: arXiv cs.AI 2016
Year: 2016

Community annotation of biological entities with concepts from multiple bio-ontologies has created large and growing repositories of ontology-based annotation data with embedded implicit relationships among orthogonal ontologies. Development of efficient data mining methods and metrics to mine and assess the quality of the mined relationships has not kept pace with the growth of annotation data. In this study, we present a data mining method that uses ontology-guided generalization to discover relationships across ontologies along with a new interestingness metric based on information theory. We apply our data mining algorithm and interestingness measures to datasets from the Gene Expression Database at the Mouse Genome Informatics as a preliminary proof of concept to mine relationships between developmental stages in the mouse anatomy ontology and Gene Ontology concepts (biological process, molecular function and cellular component). In addition, we present a comparison of our interestingness metric to four existing metrics. Ontology-based annotation datasets provide a valuable resource for discovery of relationships across ontologies. The use of efficient data mining methods and appropriate interestingness metrics enables the identification of high quality relationships.
On the estimation of initial conditions in kernel-based system identification
Venue: arXiv cs.SY 2016
Year: 2016

Recent developments in system identification have brought attention to regularized kernel-based methods, where, adopting the recently introduced stable spline kernel, prior information on the unknown process is enforced. This reduces the variance of the estimates and thus makes kernel-based methods particularly attractive when few input-output data samples are available. In such cases however, the influence of the system initial conditions may have a significant impact on the output dynamics. In this paper, we specifically address this point. We propose three methods that deal with the estimation of initial conditions using different types of information. The methods consist in various mixed maximum likelihood--a posteriori estimators which estimate the initial conditions and tune the hyperparameters characterizing the stable spline kernel. To solve the related optimization problems, we resort to the expectation-maximization method, showing that the solutions can be attained by iterating among simple update steps. Numerical experiments show the advantages, in terms of accuracy in reconstructing the system impulse response, of the proposed strategies, compared to other kernel-based schemes not accounting for the effect initial conditions.
The Shannon Lower Bound is Asymptotically Tight
Venue: arXiv cs.IT 2016
Year: 2016

The Shannon lower bound is one of the few lower bounds on the rate-distortion function that holds for a large class of sources. In this paper, it is demonstrated that its gap to the rate-distortion function vanishes as the allowed distortion tends to zero for all sources having a finite differential entropy and whose integer part is finite. Conversely, it is demonstrated that if the integer part of the source has an infinite entropy, then its rate-distortion function is infinite for every finite distortion. Consequently, the Shannon lower bound provides an asymptotically tight bound on the rate-distortion function if, and only if, the integer part of the source has a finite entropy.
Cracking a hierarchical chaotic image encryption algorithm based on permutation
Venue: arXiv cs.CR 2016
Year: 2016

In year 2000, an efficient hierarchical chaotic image encryption (HCIE) algorithm was proposed, which divides a plain-image of size $M\times N$ with $T$ possible value levels into $K$ blocks of the same size and then operates position permutation on two levels: intra-block and inter-block. As a typical position permutation-only encryption algorithm, it has received intensive attention. The present paper analyzes specific security performance of HCIE against ciphertext-only attack and known/chosen-plaintext attack. It is found that only $O(\lceil\log_T(M\cdot N/K) \rceil)$ known/chosen plain-images are sufficient to achieve a good performance, and the computational complexity is $O(M\cdot N\cdot \lceil\log_T(M\cdot N/K) \rceil)$, which effectively demonstrates that hierarchical permutation-only image encryption algorithms are less secure than normal (i.e., non-hierarchical) ones. Detailed experiment results are given to verify the feasibility of the known-plaintext attack. In addition, it is pointed out that the security of HCIE against ciphertext-only attack was much overestimated.
Making Sense of Hidden Layer Information in Deep Networks by Learning Hierarchical Targets
Venue: arXiv cs.NE 2016
Year: 2016

This paper proposes an architecture for deep neural networks with hidden layer branches that learn targets of lower hierarchy than final layer targets. The branches provide a channel for enforcing useful information in hidden layer which helps in attaining better accuracy, both for the final layer and hidden layers. The shared layers modify their weights using the gradients of all cost functions higher than the branching layer. This model provides a flexible inference system with many levels of targets which is modular and can be used efficiently in situations requiring different levels of results according to complexity. This paper applies the idea to a text classification task on 20 Newsgroups data set with two level of hierarchical targets and a comparison is made with training without the use of hidden layer branches.
Specular sets
Venue: arXiv cs.DM 2016
Year: 2016

We introduce the notion of specular sets which are subsets of groups called here specular and which form a natural generalization of free groups. These sets are an abstract generalization of the natural codings of linear involutions. We prove several results concerning the subgroups generated by return words and by maximal bifix codes in these sets.
Constructions of High-Rate MSR Codes over Small Fields
Venue: arXiv cs.IT 2016
Year: 2016

A novel technique for construction of minimum storage regenerating (MSR) codes is presented. Based on this technique, three explicit constructions of MSR codes are given. The first two constructions provide access-optimal MSR codes, with two and three parities, respectively, which attain the sub-packetization bound for access-optimal codes. The third construction provides longer MSR codes with three parities, which are not access-optimal, and do not necessarily attain the sub-packetization bound. In addition to a minimum storage in a node, all three constructions allow the entire data to be recovered from a minimal number of storage nodes. That is, given storage $\ell$ in each node, the entire stored data can be recovered from any $2\log_2 \ell$ for 2 parity nodes, and either $3\log_3\ell$ or $4\log_3\ell$ for 3 parity nodes. Second, in the first two constructions, a helper node accesses the minimum number of its symbols for repair of a failed node (access-optimality). The generator matrix of these codes is based on perfect matchings of complete graphs and hypergraphs, and on a rational canonical form of matrices. The goal of this paper is to provide a construction of such optimal codes over the smallest possible finite fields. For two parities, the field size is reduced by a factor of two for access-optimal codes compared to previous constructions. For three parities, in the first construction the field size is $6\log_3 \ell+1$ (or $3\log_3 \ell+1$ for fields with characteristic 2), and in the second construction the field size is larger, yet linear in $\log_3\ell$. Both constructions with 3 parities provide a significant improvement over existing previous works, since only non-explicit constructions with exponential field size (in $\log_3\ell$) were known so far.
The Configurable SAT Solver Challenge (CSSC)
Venue: arXiv cs.AI 2016
Year: 2016

It is well known that different solution strategies work well for different types of instances of hard combinatorial problems. As a consequence, most solvers for the propositional satisfiability problem (SAT) expose parameters that allow them to be customized to a particular family of instances. In the international SAT competition series, these parameters are ignored: solvers are run using a single default parameter setting (supplied by the authors) for all benchmark instances in a given track. While this competition format rewards solvers with robust default settings, it does not reflect the situation faced by a practitioner who only cares about performance on one particular application and can invest some time into tuning solver parameters for this application. The new Configurable SAT Solver Competition (CSSC) compares solvers in this latter setting, scoring each solver by the performance it achieved after a fully automated configuration step. This article describes the CSSC in more detail, and reports the results obtained in its two instantiations so far, CSSC 2013 and 2014.
Strong Typed Böhm Theorem and Functional Completeness on the Linear Lambda Calculus
Venue: arXiv cs.LO 2016
Year: 2016

In this paper, we prove a version of the typed Böhm theorem on the linear lambda calculus, which says, for any given types A and B, when two different closed terms s1 and s2 of A and any closed terms u1 and u2 of B are given, there is a term t such that t s1 is convertible to u1 and t s2 is convertible to u2. Several years ago, a weaker version of this theorem was proved, but the stronger version was open. As a corollary of this theorem, we prove that if A has two different closed terms s1 and s2, then A is functionally complete with regard to s1 and s2. So far, it was only known that a few types are functionally complete.
Geometry-Aware Neighborhood Search for Learning Local Models for Image Reconstruction
Venue: arXiv cs.CV 2016
Year: 2016

Local learning of sparse image models has proven to be very effective to solve inverse problems in many computer vision applications. To learn such models, the data samples are often clustered using the K-means algorithm with the Euclidean distance as a dissimilarity metric. However, the Euclidean distance may not always be a good dissimilarity measure for comparing data samples lying on a manifold. In this paper, we propose two algorithms for determining a local subset of training samples from which a good local model can be computed for reconstructing a given input test sample, where we take into account the underlying geometry of the data. The first algorithm, called Adaptive Geometry-driven Nearest Neighbor search (AGNN), is an adaptive scheme which can be seen as an out-of-sample extension of the replicator graph clustering method for local model learning. The second method, called Geometry-driven Overlapping Clusters (GOC), is a less complex nonadaptive alternative for training subset selection. The proposed AGNN and GOC methods are evaluated in image super-resolution, deblurring and denoising applications and shown to outperform spectral clustering, soft clustering, and geodesic distance based subset selection in most settings.
On Secrecy Capacity of Minimum Storage Regenerating Codes
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we revisit the problem of characterizing the secrecy capacity of minimum storage regenerating (MSR) codes under the passive $(l_1,l_2)$-eavesdropper model, where the eavesdropper has access to data stored on $l_1$ nodes and the repair data for an additional $l_2$ nodes. We study it from the information-theoretic perspective. First, some general properties of MSR codes as well as a simple and generally applicable upper bound on secrecy capacity are given. Second, a new concept of \emph{stable} MSR codes is introduced, where the stable property is shown to be closely linked with secrecy capacity. Finally, a comprehensive and explicit result on secrecy capacity in the linear MSR scenario is present, which generalizes all related works in the literature and also predicts certain results for some unexplored linear MSR codes.
Evaluate and Compare Two Utilization-Based Schedulability-Test Frameworks for Real-Time Systems
Venue: arXiv cs.DS 2016
Year: 2016

This report summarizes two general frameworks, namely k2Q and k2U, that have been recently developed by us. The purpose of this report is to provide detailed evaluations and comparisons of these two frameworks. These two frameworks share some similar characteristics, but they are useful for different application cases. These two frameworks together provide comprehensive means for the users to automatically convert the pseudo polynomial-time tests (or even exponential-time tests) into polynomial-time tests with closed mathematical forms. With the quadratic and hyperbolic forms, k2Q and k2U frameworks can be used to provide many quantitive features to be measured and evaluated, like the total utilization bounds, speed-up factors, etc., not only for uniprocessor scheduling but also for multiprocessor scheduling. These frameworks can be viewed as "blackbox" interfaces for providing polynomial-time schedulability tests and response time analysis for real-time applications. We have already presented their advantages for being applied in some models in the previous papers. However, it was not possible to present a more comprehensive comparison between these two frameworks. We hope this report can help the readers and users clearly understand the difference of these two frameworks, their unique characteristics, and their advantages. We demonstrate their differences and properties by using the traditional sporadic realtime task models in uniprocessor scheduling and multiprocessor global scheduling.