OpenRaiser/Intern-Atlas huggingface dataset:
Cloud K-SVD: A Collaborative Dictionary Learning Algorithm for Big, Distributed Data
Venue: arXiv cs.LG 2015
Year: 2015

This paper studies the problem of data-adaptive representations for big, distributed data. It is assumed that a number of geographically-distributed, interconnected sites have massive local data and they are interested in collaboratively learning a low-dimensional geometric structure underlying these data. In contrast to previous works on subspace-based data representations, this paper focuses on the geometric structure of a union of subspaces (UoS). In this regard, it proposes a distributed algorithm---termed cloud K-SVD---for collaborative learning of a UoS structure underlying distributed data of interest. The goal of cloud K-SVD is to learn a common overcomplete dictionary at each individual site such that every sample in the distributed data can be represented through a small number of atoms of the learned dictionary. Cloud K-SVD accomplishes this goal without requiring exchange of individual samples between sites. This makes it suitable for applications where sharing of raw data is discouraged due to either privacy concerns or large volumes of data. This paper also provides an analysis of cloud K-SVD that gives insights into its properties as well as deviations of the dictionaries learned at individual sites from a centralized solution in terms of different measures of local/global data and topology of interconnections. Finally, the paper numerically illustrates the efficacy of cloud K-SVD on real and synthetic distributed data.
Adjusting Leverage Scores by Row Weighting: A Practical Approach to Coherent Matrix Completion
Venue: arXiv cs.LG 2015
Year: 2015

Low-rank matrix completion is an important problem with extensive real-world applications. When observations are uniformly sampled from the underlying matrix entries, existing methods all require the matrix to be incoherent. This paper provides the first working method for coherent matrix completion under the standard uniform sampling model. Our approach is based on the weighted nuclear norm minimization idea proposed in several recent work, and our key contribution is a practical method to compute the weighting matrices so that the leverage scores become more uniform after weighting. Under suitable conditions, we are able to derive theoretical results, showing the effectiveness of our approach. Experiments on synthetic data show that our approach recovers highly coherent matrices with high precision, whereas the standard unweighted method fails even on noise-free data.
An Effective Approach for Mobile ad hoc Network via I-Watchdog Protocol
Venue: arXiv cs.NI 2015
Year: 2015

Mobile ad hoc network (MANET) is now days become very famous due to their fixed infrastructure-less quality and dynamic nature. They contain a large number of nodes which are connected and communicated to each other in wireless nature. Mobile ad hoc network is a wireless technology that contains high mobility of nodes and does not depend on the background administrator for central authority, because they do not contain any infrastructure. Nodes of the MANET use radio wave for communication and having limited resources and limited computational power. The Topology of this network is changing very frequently because they are distributed in nature and self-configurable. Due to its wireless nature and lack of any central authority in the background, Mobile ad hoc networks are always vulnerable to some security issues and performance issues. The security imposes a huge impact on the performance of any network. Some of the security issues are black hole attack, flooding, wormhole attack etc. In this paper, we will discuss issues regarding low performance of Watchdog protocol used in the MANET and proposed an improved Watchdog mechanism, which is called by I-Watchdog protocol that overcomes the limitations of Watchdog protocol and gives high performance in terms of throughput, delay.
Pattern Matching and Local Alignment for RNA Structures
Venue: arXiv cs.DS 2015
Year: 2015

The primary structure of a ribonucleic acid (RNA) molecule can be represented as a sequence of nucleotides (bases) over the alphabet {A, C, G, U}. The secondary or tertiary structure of an RNA is a set of base pairs which form bonds between A-U and G-C. For secondary structures, these bonds have been traditionally assumed to be one-to-one and non-crossing. This paper considers pattern matching as well as local alignment between two RNA structures. For pattern matching, we present two algorithms, one for obtaining an exact match, the other for approximate match. We then present an algorithm for RNA local structural alignment.
Full Duplex Operation for Small Cells
Venue: arXiv cs.NI 2015
Year: 2015

Full duplex (FD) communications has the potential to double the capacity of a half duplex (HD) system at the link level. However, FD operation increases the aggregate interference on each communication link, which limits the capacity improvement. In this paper, we investigate how much of the potential doubling can be practically achieved in the resource-managed, small multi-cellular system, similar to the TDD variant of LTE, both in indoor and outdoor environments, assuming FD base stations (BSs) and HD user equipment (UEs). We focus on low-powered small cellular systems, because they are more suitable for FD operation given practical self-interference cancellation limits. A joint UE selection and power allocation method for a multi-cell scenario is presented, where a hybrid scheduling policy assigns FD timeslots when it provides a throughput advantage by pairing UEs with appropriate power levels to mitigate the mutual interference, but otherwise defaults to HD operation. Due to the complexity of finding the globally optimum solution of the proposed algorithm, a sub-optimal method based on a heuristic greedy algorithm for UE selection, and a novel solution using geometric programming for power allocation, is proposed. With practical self-interference cancellation, antennas and circuits, it is shown that the proposed hybrid FD system achieves as much as 94% throughput improvement in the downlink, and 92% in the uplink, compared to a HD system in an indoor multi-cell scenario and 54% in downlink and 61% in uplink in an outdoor multi-cell scenario. Further, we also compare the energy efficiency of FD operation.
Characterizing Propositional Proofs as Non-Commutative Formulas
Venue: arXiv cs.CC 2015
Year: 2015

Does every Boolean tautology have a short propositional-calculus proof? Here, a propositional calculus (i.e. Frege) proof is a proof starting from a set of axioms and deriving new Boolean formulas using a set of fixed sound derivation rules. Establishing any super-polynomial size lower bound on Frege proofs (in terms of the size of the formula proved) is a major open problem in proof complexity, and among a handful of fundamental hardness questions in complexity theory by and large. Non-commutative arithmetic formulas, on the other hand, constitute a quite weak computational model, for which exponential-size lower bounds were shown already back in 1991 by Nisan [Nis91] who used a particularly transparent argument. In this work we show that Frege lower bounds in fact follow from corresponding size lower bounds on non-commutative formulas computing certain polynomials (and that such lower bounds on non-commutative formulas must exist, unless NP=coNP). More precisely, we demonstrate a natural association between tautologies $T$ to non-commutative polynomials $p$, such that: if $T$ has a polynomial-size Frege proof then $p$ has a polynomial-size non-commutative arithmetic formula; and conversely, when $T$ is a DNF, if $p$ has a polynomial-size non-commutative arithmetic formula over $GF(2)$ then $T$ has a Frege proof of quasi-polynomial size.
Image Super-Resolution Using Deep Convolutional Networks
Venue: arXiv cs.CV 2015
Year: 2015

We propose a deep learning method for single image super-resolution (SR). Our method directly learns an end-to-end mapping between the low/high-resolution images. The mapping is represented as a deep convolutional neural network (CNN) that takes the low-resolution image as the input and outputs the high-resolution one. We further show that traditional sparse-coding-based SR methods can also be viewed as a deep convolutional network. But unlike traditional methods that handle each component separately, our method jointly optimizes all layers. Our deep CNN has a lightweight structure, yet demonstrates state-of-the-art restoration quality, and achieves fast speed for practical on-line usage. We explore different network structures and parameter settings to achieve trade-offs between performance and speed. Moreover, we extend our network to cope with three color channels simultaneously, and show better overall reconstruction quality.
On the anonymizability of mobile traffic datasets
Venue: arXiv cs.CY 2015
Year: 2015

Preserving user privacy is paramount when it comes to publicly disclosed datasets that contain fine-grained data about large populations. The problem is especially critical in the case of mobile traffic datasets collected by cellular operators, as they feature elevate subscriber trajectory uniqueness and they are resistant to anonymization through spatiotemporal generalization. In this work, we investigate the $k$-anonymizability of trajectories in two large-scale mobile traffic datasets, by means of a novel dedicated measure. Our results are in agreement with those of previous analyses, however they also provide additional insights on the reasons behind the poor anonimizability of mobile traffic datasets. As such, our study is a step forward in the direction of a more robust dataset anonymization.
A persistence landscapes toolbox for topological statistics
Venue: arXiv cs.CG 2015
Year: 2015

Topological data analysis provides a multiscale description of the geometry and topology of quantitative data. The persistence landscape is a topological summary that can be easily combined with tools from statistics and machine learning. We give efficient algorithms for calculating persistence landscapes, their averages, and distances between such averages. We discuss an implementation of these algorithms and some related procedures. These are intended to facilitate the combination of statistics and machine learning with topological data analysis. We present an experiment showing that the low-dimensional persistence landscapes of points sampled from spheres (and boxes) of varying dimensions differ.
An information services algorithm to heuristically summarize IP addresses for a distributed, hierarchical directory service
Venue: arXiv cs.DC 2015
Year: 2015

A distributed, hierarchical information service for computer networks might rely in several instances, located in different layers. A distributed directory service, for example, might be comprised of upper level listings, and local directories. The upper level listings contain a compact version of the local directories. Clients desiring to access the information contained in local directories might first access the high-level listings, in order to locate the appropriate local instance. One of the keys for the competent operation of such service is the ability of properly summarizing the information, which will be maintained in the upper level directories. We analyze the case of the Lookup Service in the Information Services plane of perfSONAR performance monitoring distributed architecture, which implements IPv4 summarization in its functions. We propose an empirical method, or heuristic, to achieve the summarizations, based on the PATRICIA tree. We further apply the heuristic on a simulated distributed test bed and contemplate the results.
Comparison of Accuracy for Methods to Approximate Fisher Information in the Scalar Case
Venue: arXiv cs.IT 2015
Year: 2015

The Fisher information matrix (FIM) has long been of interest in statistics and other areas. It is widely used to measure the amount of information and calculate the lower bound for the variance for maximum likelihood estimation (MLE). In practice, we do not always know the actual FIM. This is often because obtaining the first or second-order derivatives of the log-likelihood function is difficult, or simply because the calculation of FIM is too formidable. In such cases, we need to utilize the approximation of FIM. In general, there are two ways to estimate FIM. One is to use the product of gradient and the transpose of itself, and the other is to calculate the Hessian matrix and then take negative sign. Mostly people use the latter method in practice. However, this is not necessarily the optimal way. To find out which of the two methods is better, we need to conduct a theoretical study to compare their efficiency. In this paper we mainly focus on the case where the unknown parameter that needs to be estimated by MLE is scalar and the random variables we have are independent. In this scenario, Fisher information matrix is virtually Fisher information number (FIN). Using the Central Limit Theorem (CLT), we get asymptotic variances for the two methods, by which we compare their accuracy. Taylor expansion assists in estimating the two asymptotic variances. A numerical study is provided as an illustration of the conclusion. The next is a summary of limitations of this paper. We also enumerate several fields of interest for future study in the end of this paper. Key words: Fisher information matrix, Fisher information number, the Central Limit Theorem, Taylor expansion, asymptotic variance.
Contact Representations of Graphs in 3D
Venue: arXiv cs.CG 2015
Year: 2015

We study contact representations of graphs in which vertices are represented by axis-aligned polyhedra in 3D and edges are realized by non-zero area common boundaries between corresponding polyhedra. We show that for every 3-connected planar graph, there exists a simultaneous representation of the graph and its dual with 3D boxes. We give a linear-time algorithm for constructing such a representation. This result extends the existing primal-dual contact representations of planar graphs in 2D using circles and triangles. While contact graphs in 2D directly correspond to planar graphs, we next study representations of non-planar graphs in 3D. In particular we consider representations of optimal 1-planar graphs. A graph is 1-planar if there exists a drawing in the plane where each edge is crossed at most once, and an optimal n-vertex 1-planar graph has the maximum (4n - 8) number of edges. We describe a linear-time algorithm for representing optimal 1-planar graphs without separating 4-cycles with 3D boxes. However, not every optimal 1-planar graph admits a representation with boxes. Hence, we consider contact representations with the next simplest axis-aligned 3D object, L-shaped polyhedra. We provide a quadratic-time algorithm for representing optimal 1-planar graph with L-shaped polyhedra.
Efficient 2-Step Protocol and Its Discriminative Feature Selections in Secure Similar Document Detection
Venue: arXiv cs.CR 2015
Year: 2015

Secure similar document detection (SSDD) identifies similar documents of two parties while each party does not disclose its own sensitive documents to another party. In this paper, we propose an efficient 2-step protocol that exploits a feature selection as the lower-dimensional transformation and presents discriminative feature selections to maximize the performance of the protocol. For this, we first analyze that the existing 1-step protocol causes serious computation and communication overhead for high dimensional document vectors. To alleviate the overhead, we next present the feature selection-based 2-step protocol and formally prove its correctness. The proposed 2-step protocol works as follows: (1) in the filtering step, it uses low dimensional vectors obtained by the feature selection to filter out non-similar documents; (2) in the post-processing step, it identifies similar documents only from the non-filtered documents by using the 1-step protocol. As the feature selection, we first consider the simplest one, random projection (RP), and propose its 2-step solution SSDD-RP. We then present two discriminative feature selections and their solutions: SSDD-LF (local frequency) which selects a few dimensions locally frequent in the current querying vector and SSDD-GF (global frequency) which selects ones globally frequent in the set of all document vectors. We finally propose a hybrid one, SSDD-HF (hybrid frequency), that takes advantage of both SSDD-LF and SSDD-GF. We empirically show that the proposed 2-step protocol outperforms the 1-step protocol by three or four orders of magnitude.
Comprehend DeepWalk as Matrix Factorization
Venue: arXiv cs.LG 2015
Year: 2015

Word2vec, as an efficient tool for learning vector representation of words has shown its effectiveness in many natural language processing tasks. Mikolov et al. issued Skip-Gram and Negative Sampling model for developing this toolbox. Perozzi et al. introduced the Skip-Gram model into the study of social network for the first time, and designed an algorithm named DeepWalk for learning node embedding on a graph. We prove that the DeepWalk algorithm is actually factoring a matrix M where each entry M_{ij} is logarithm of the average probability that node i randomly walks to node j in fix steps.
Efficiently Discovering Frequent Motifs in Large-scale Sensor Data
Venue: arXiv cs.DB 2015
Year: 2015

While analyzing vehicular sensor data, we found that frequently occurring waveforms could serve as features for further analysis, such as rule mining, classification, and anomaly detection. The discovery of waveform patterns, also known as time-series motifs, has been studied extensively; however, available techniques for discovering frequently occurring time-series motifs were found lacking in either efficiency or quality: Standard subsequence clustering results in poor quality, to the extent that it has even been termed 'meaningless'. Variants of hierarchical clustering using techniques for efficient discovery of 'exact pair motifs' find high-quality frequent motifs, but at the cost of high computational complexity, making such techniques unusable for our voluminous vehicular sensor data. We show that good quality frequent motifs can be discovered using bounded spherical clustering of time-series subsequences, which we refer to as COIN clustering, with near linear complexity in time-series size. COIN clustering addresses many of the challenges that previously led to subsequence clustering being viewed as meaningless. We describe an end-to-end motif-discovery procedure using a sequence of pre and post-processing techniques that remove trivial-matches and shifted-motifs, which also plagued previous subsequence-clustering approaches. We demonstrate that our technique efficiently discovers frequent motifs in voluminous vehicular sensor data as well as in publicly available data sets.
An Experimental Analysis of the Echo State Network Initialization Using the Particle Swarm Optimization
Venue: arXiv cs.NE 2015
Year: 2015

This article introduces a robust hybrid method for solving supervised learning tasks, which uses the Echo State Network (ESN) model and the Particle Swarm Optimization (PSO) algorithm. An ESN is a Recurrent Neural Network with the hidden-hidden weights fixed in the learning process. The recurrent part of the network stores the input information in internal states of the network. Another structure forms a free-memory method used as supervised learning tool. The setting procedure for initializing the recurrent structure of the ESN model can impact on the model performance. On the other hand, the PSO has been shown to be a successful technique for finding optimal points in complex spaces. Here, we present an approach to use the PSO for finding some initial hidden-hidden weights of the ESN model. We present empirical results that compare the canonical ESN model with this hybrid method on a wide range of benchmark problems.
Mapping and Matching Algorithms: Data Mining by Adaptive Graphs
Venue: arXiv cs.OH 2015
Year: 2015

Assume we have two bijective functions $U(x)$ and $M(x)$ with $M(x)\neq U(x)$ for all $x$ and $M,N: \N \rightarrow \N$ . Every day and in different locations, we see the different results of $U$ and $M$ without seeing $x$. We are not assured about the time stamp nor the order within the day but at least the location is fully defined. We want to find the matching between $U(x)$ and $M(x)$ (i.e., we will not know $x$). We formulate this problem as an adaptive graph mining: we develop the theory, the solution, and the implementation. This work stems from a practical problem thus our definitions. The solution is simple, clear, and the implementation parallel and efficient. In our experience, the problem and the solution are novel and we want to share our finding.
Function of Forgetfulness for the Tedium of Oblivion on Liquidity of Ontology Matching
Venue: arXiv cs.CY 2015
Year: 2015

The shallow and fragile knowledge on the Web does not examine in depth the things: it behaves lightly. The conditions created by the Web makes our attention labile and especially fickle, it's unable to concentrate for long as we are trained to "surf" without going though never in depth. The Web also brings with it the added advantage of a nearly availability infinite knowledge but leads to a loss of the ability to retain and evaluate that knowledge within us increasing forgetfulness of knowledge. In this paper we show how the "function of forgetfulness" appears linked to tedium and oblivion of knowledge through the liquidity of ontology matching.
Effective Use of Human Computer Interaction in Digital Academic Supportive Devices
Venue: arXiv cs.HC 2015
Year: 2015

In this research, a literature in human-computer interaction is reviewed and the technology aspect of human computer interaction related with digital academic supportive devices is also analyzed. According to all these concerns, recommendations to design good human-computer digital academic supportive devices are analyzed and proposed. Due to improvements in both hardware and software, digital devices have unveiled continuous advances in efficiency and processing capacity. However, many of these systems are also becoming larger and increasingly more complex. Although such complexity usually poses no difficulties for many users, it often creates barriers for academic users while using digital devices. Usually, in designing those digital devices, the human-computer interaction is left behind without consideration. To achieve dependable, usable, and well-engineered interactive digital academic supportive devices requires applied human computer interaction research and awareness of its issues.
Adaptive Dispatching of Tasks in the Cloud
Venue: arXiv cs.DC 2015
Year: 2015

The increasingly wide application of Cloud Computing enables the consolidation of tens of thousands of applications in shared infrastructures. Thus, meeting the quality of service requirements of so many diverse applications in such shared resource environments has become a real challenge, especially since the characteristics and workload of applications differ widely and may change over time. This paper presents an experimental system that can exploit a variety of online quality of service aware adaptive task allocation schemes, and three such schemes are designed and compared. These are a measurement driven algorithm that uses reinforcement learning, secondly a "sensible" allocation algorithm that assigns jobs to sub-systems that are observed to provide a lower response time, and then an algorithm that splits the job arrival stream into sub-streams at rates computed from the hosts' processing capabilities. All of these schemes are compared via measurements among themselves and with a simple round-robin scheduler, on two experimental test-beds with homogeneous and heterogeneous hosts having different processing capacities.