OpenRaiser/Intern-Atlas huggingface dataset:
Scalable Task-Based Algorithm for Multiplication of Block-Rank-Sparse Matrices
Venue: arXiv cs.DC 2015
Year: 2015

A task-based formulation of Scalable Universal Matrix Multiplication Algorithm (SUMMA), a popular algorithm for matrix multiplication (MM), is applied to the multiplication of hierarchy-free, rank-structured matrices that appear in the domain of quantum chemistry (QC). The novel features of our formulation are: (1) concurrent scheduling of multiple SUMMA iterations, and (2) fine-grained task-based composition. These features make it tolerant of the load imbalance due to the irregular matrix structure and eliminate all artifactual sources of global synchronization.Scalability of iterative computation of square-root inverse of block-rank-sparse QC matrices is demonstrated; for full-rank (dense) matrices the performance of our SUMMA formulation usually exceeds that of the state-of-the-art dense MM implementations (ScaLAPACK and Cyclops Tensor Framework).
On the Readability of Boundary Labeling
Venue: arXiv cs.CG 2015
Year: 2015

Boundary labeling deals with annotating features in images such that labels are placed outside of the image and are connected by curves (so-called leaders) to the corresponding features. While boundary labeling has been extensively investigated from an algorithmic perspective, the research on its readability has been neglected. In this paper we present the first formal user study on the readability of boundary labeling. We consider the four most studied leader types with respect to their performance, i.e., whether and how fast a viewer can assign a feature to its label and vice versa. We give a detailed analysis of the results regarding the readability of the four models and discuss their aesthetic qualities based on the users' preference judgments and interviews.
Visualizing signatures of human activity in cities across the globe
Venue: arXiv cs.SI 2015
Year: 2015

The availability of big data on human activity is currently changing the way we look at our surroundings. With the high penetration of mobile phones, nearly everyone is already carrying a high-precision sensor providing an opportunity to monitor and analyze the dynamics of human movement on unprecedented scales. In this article, we present a technique and visualization tool which uses aggregated activity measures of mobile networks to gain information about human activity shaping the structure of the cities. Based on ten months of mobile network data, activity patterns can be compared through time and space to unravel the "city's pulse" as seen through the specific signatures of different locations. Furthermore, the tool allows classifying the neighborhoods into functional clusters based on the timeline of human activity, providing valuable insights on the actual land use patterns within the city. This way, the approach and the tool provide new ways of looking at the city structure from historical perspective and potentially also in real-time based on dynamic up-to-date records of human behavior. The online tool presents results for four global cities: New York, London, Hong Kong and Los Angeles.
Stabilization of continuous-time switched linear systems with quantized output feedback
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we study the problem of stabilizing continuous-time switched linear systems with quantized output feedback. We assume that the observer and the control gain are given for each mode. Also, the plant mode is known to the controller and the quantizer. Extending the result in the non-switched case, we develop an update rule of the quantizer to achieve asymptotic stability of the closed-loop system under the average dwell-time assumption. To avoid quantizer saturation, we adjust the quantizer at every switching time.
Evaluating user reputation in online rating systems via an iterative group-based ranking method
Venue: arXiv cs.IR 2015
Year: 2015

Reputation is a valuable asset in online social lives and it has drawn increased attention. How to evaluate user reputation in online rating systems is especially significant due to the existence of spamming attacks. To address this issue, so far, a variety of methods have been proposed, including network-based methods, quality-based methods and group-based ranking method. In this paper, we propose an iterative group-based ranking (IGR) method by introducing an iterative reputation-allocation process into the original group-based ranking (GR) method. More specifically, users with higher reputation have higher weights in dominating the corresponding group sizes. The reputation of users and the corresponding group sizes are iteratively updated until they become stable. Results on two real data sets suggest that the proposed IGR method has better performance and its robustness is considerably improved comparing with the original GR method. Our work highlights the positive role of users' grouping behavior towards a better reputation evaluation.
Toward an effort estimation model for software projects integrating risk
Venue: arXiv cs.SE 2015
Year: 2015

According to a study of The Standish Group International, 44% of software projects cost more and last longer than expected. More accurate the effort estimation is; the better the enterprise gets organized and the more the software project respects the commitments on budget, time and quality. Enhancing the accuracy of effort estimation remains an ongoing challenge to software professionals. Several factors can influence the accuracy of effort estimation, namely the immaterial aspect of information system projects, new technologies and the lack of return on experience. However, the most important factor of cost and delay increase is software risks. A software risk is an uncertain event with a negative consequence on the software project. In this article, we propose a methodology to take into account risk exposure analysis in the effort estimation model. In the literature, this issue is little addressed and few approaches are investigated. In this research work, we first present an overview of these approaches and their limits. Then, we propose an effort estimation model that improves the accuracy of estimation by integrating software risks. We finally apply this model to a case study and compare its results to the results of a classic model.
Testing k-binomial equivalence
Venue: arXiv cs.FL 2015
Year: 2015

Two words $w_1$ and $w_2$ are said to be $k$-binomial equivalent if every non-empty word $x$ of length at most $k$ over the alphabet of $w_1$ and $w_2$ appears as a scattered factor of $w_1$ exactly as many times as it appears as a scattered factor of $w_2$. We give two different polynomial-time algorithms testing the $k$-binomial equivalence of two words. The first one is deterministic (but the degree of the corresponding polynomial is too high) and the second one is randomised (it is more direct and more efficient). These are the first known algorithms for the problem which run in polynomial time.
A Multilayer Model of Computer Networks
Venue: arXiv cs.NI 2015
Year: 2015

The fundamental concept of applying the system methodology to network analysis declares that network architecture should take into account services and applications which this network provides and supports. This work introduces a formal model of computer networks on the basis of the hierarchical multilayer networks. In turn, individual layers are represented as multiplex networks. The concept of layered networks provides conditions of top-down consistency of the model. Next, we determined the necessary set of layers for network architecture representation with regard to applying the system methodology to network analysis.
Heavy-tailed Independent Component Analysis
Venue: arXiv cs.LG 2015
Year: 2015

Independent component analysis (ICA) is the problem of efficiently recovering a matrix $A \in \mathbb{R}^{n\times n}$ from i.i.d. observations of $X=AS$ where $S \in \mathbb{R}^n$ is a random vector with mutually independent coordinates. This problem has been intensively studied, but all existing efficient algorithms with provable guarantees require that the coordinates $S_i$ have finite fourth moments. We consider the heavy-tailed ICA problem where we do not make this assumption, about the second moment. This problem also has received considerable attention in the applied literature. In the present work, we first give a provably efficient algorithm that works under the assumption that for constant $γ> 0$, each $S_i$ has finite $(1+γ)$-moment, thus substantially weakening the moment requirement condition for the ICA problem to be solvable. We then give an algorithm that works under the assumption that matrix $A$ has orthogonal columns but requires no moment assumptions. Our techniques draw ideas from convex geometry and exploit standard properties of the multivariate spherical Gaussian distribution in a novel way.
A Note on the Convexity of $\log \det ( I + KX^{-1} )$ and its Constrained Optimization Representation
Venue: arXiv cs.IT 2015
Year: 2015

This note provides another proof for the {\em convexity} ({\em strict convexity}) of $\log \det ( I + KX^{-1} )$ over the positive definite cone for any given positive semidefinite matrix $K \succeq 0$ (positive definite matrix $K \succ 0$) and the {\em strictly convexity} of $\log \det (K + X^{-1})$ over the positive definite cone for any given $K \succeq 0$. Equivalent optimization representation with linear matrix inequalities (LMIs) for the functions $\log \det ( I + KX^{-1} )$ and $\log \det (K + X^{-1})$ are presented. Their optimization representations with LMI constraints can be particularly useful for some related synthetic design problems.
Effective Spatial Data Partitioning for Scalable Query Processing
Venue: arXiv cs.DB 2015
Year: 2015

Recently, MapReduce based spatial query systems have emerged as a cost effective and scalable solution to large scale spatial data processing and analytics. MapReduce based systems achieve massive scalability by partitioning the data and running query tasks on those partitions in parallel. Therefore, effective data partitioning is critical for task parallelization, load balancing, and directly affects system performance. However, several pitfalls of spatial data partitioning make this task particularly challenging. First, data skew is very common in spatial applications. To achieve best query performance, data skew need to be reduced. Second, spatial partitioning approaches generate boundary objects that cross multiple partitions, and add extra query processing overhead. Consequently, boundary objects need to be minimized. Third, the high computational complexity of spatial partitioning algorithms combined with massive amounts of data require an efficient approach for partitioning to achieve overall fast query response. In this paper, we provide a systematic evaluation of multiple spatial partitioning methods with a set of different partitioning strategies, and study their implications on the performance of MapReduce based spatial queries. We also study sampling based partitioning methods and their impact on queries, and propose several MapReduce based high performance spatial partitioning methods. The main objective of our work is to provide a comprehensive guidance for optimal spatial data partitioning to support scalable and fast spatial data processing in massively parallel data processing frameworks such as MapReduce. The algorithms developed in this work are open source and can be easily integrated into different high performance spatial data processing systems.
Pulse Shaping Methods for OQAM/OFDM and WCP-COQAM
Venue: arXiv cs.IT 2015
Year: 2015

GFDM is a new modulation format whose advantages compared to OFDM reportedly make it a preferable modulation format for 5G. However, the non-orthogonal nature of GFDM with matched filtering (MF) receiver for pulses with good time-frequency localization is one of its disadvantages, leading to the proposal of WCP-COQAM, employing offset quadrature amplitude modulation (OQAM). In this paper, we prove that a pulse satisfying orthogonality conditions for OQAM-OFDM will also satisfy orthogonality with WCP-COQAM, thus the pulse design methods developed for OQAM-OFDM can also be used with WCP-COQAM. This statement is also verified by the simulation based results.
Training of CC4 Neural Network with Spread Unary Coding
Venue: arXiv cs.NE 2015
Year: 2015

This paper adapts the corner classification algorithm (CC4) to train the neural networks using spread unary inputs. This is an important problem as spread unary appears to be at the basis of data representation in biological learning. The modified CC4 algorithm is tested using the pattern classification experiment and the results are found to be good. Specifically, we show that the number of misclassified points is not particularly sensitive to the chosen radius of generalization.
Model Based Reinforcement Learning with Final Time Horizon Optimization
Venue: arXiv cs.SY 2015
Year: 2015

We present one of the first algorithms on model based reinforcement learning and trajectory optimization with free final time horizon. Grounded on the optimal control theory and Dynamic Programming, we derive a set of backward differential equations that propagate the value function and provide the optimal control policy and the optimal time horizon. The resulting policy generalizes previous results in model based trajectory optimization. Our analysis shows that the proposed algorithm recovers the theoretical optimal solution on linear low dimensional problem. Finally we provide application results on nonlinear systems.
The influence of Chunking on Dependency Crossing and Distance
Venue: arXiv cs.CL 2015
Year: 2015

This paper hypothesizes that chunking plays important role in reducing dependency distance and dependency crossings. Computer simulations, when compared with natural languages,show that chunking reduces mean dependency distance (MDD) of a linear sequence of nodes (constrained by continuity or projectivity) to that of natural languages. More interestingly, chunking alone brings about less dependency crossings as well, though having failed to reduce them, to such rarity as found in human languages. These results suggest that chunking may play a vital role in the minimization of dependency distance, and a somewhat contributing role in the rarity of dependency crossing. In addition, the results point to a possibility that the rarity of dependency crossings is not a mere side-effect of minimization of dependency distance, but a linguistic phenomenon with its own motivations.
Deep Broad Learning - Big Models for Big Data
Venue: arXiv cs.LG 2015
Year: 2015

Deep learning has demonstrated the power of detailed modeling of complex high-order (multivariate) interactions in data. For some learning tasks there is power in learning models that are not only Deep but also Broad. By Broad, we mean models that incorporate evidence from large numbers of features. This is of especial value in applications where many different features and combinations of features all carry small amounts of information about the class. The most accurate models will integrate all that information. In this paper, we propose an algorithm for Deep Broad Learning called DBL. The proposed algorithm has a tunable parameter $n$, that specifies the depth of the model. It provides straightforward paths towards out-of-core learning for large data. We demonstrate that DBL learns models from large quantities of data with accuracy that is highly competitive with the state-of-the-art.
Predicting SLA Violations in Real Time using Online Machine Learning
Venue: arXiv cs.NI 2015
Year: 2015

Detecting faults and SLA violations in a timely manner is critical for telecom providers, in order to avoid loss in business, revenue and reputation. At the same time predicting SLA violations for user services in telecom environments is difficult, due to time-varying user demands and infrastructure load conditions. In this paper, we propose a service-agnostic online learning approach, whereby the behavior of the system is learned on the fly, in order to predict client-side SLA violations. The approach uses device-level metrics, which are collected in a streaming fashion on the server side. Our results show that the approach can produce highly accurate predictions (>90% classification accuracy and < 10% false alarm rate) in scenarios where SLA violations are predicted for a video-on-demand service under changing load patterns. The paper also highlight the limitations of traditional offline learning methods, which perform significantly worse in many of the considered scenarios.
Insecure primitive elements in an ElGamal signature protocol
Venue: arXiv cs.CR 2015
Year: 2015

Consider the classical ElGamal digital signature scheme based on the modular relation $α^m\equiv y^r\, r^s\ [p]$. In this work, we prove that if we can compute a natural integer $i$ such that $α^i\ mod\ p$ is smooth and divides $p-1$, then it is possible to sign any given document without knowing the secret key. Therefore we extend and reinforce Bleichenbacher's attack presented at Eurocrypt'96.
Research of the Robot's Learning Effectiveness in the Changing Environment
Venue: arXiv cs.RO 2015
Year: 2015

The object of the research is the adaptive algorithms that are used by the operator when educating the robotic systems. Operator, being the target-setting subject, is interested in the goal that robotic systems, being the conductor of his targets (criteria), would provide a maximum effectiveness of these targets' (criteria's) achievement. Thus, the adaptive algorithms provide the adequate reflection of the operator's goals, found in the robotic systems' actions. This work considers potential possibilities of such target adaption of the robotic systems used for the class of the allocation problems.
Linear kernels for outbranching problems in sparse digraphs
Venue: arXiv cs.DS 2015
Year: 2015

In the $k$-Leaf Out-Branching and $k$-Internal Out-Branching problems we are given a directed graph $D$ with a designated root $r$ and a nonnegative integer $k$. The question is to determine the existence of an outbranching rooted at $r$ that has at least $k$ leaves, or at least $k$ internal vertices, respectively. Both these problems were intensively studied from the points of view of parameterized complexity and kernelization, and in particular for both of them kernels with $O(k^2)$ vertices are known on general graphs. In this work we show that $k$-Leaf Out-Branching admits a kernel with $O(k)$ vertices on $\mathcal{H}$-minor-free graphs, for any fixed family of graphs $\mathcal{H}$, whereas $k$-Internal Out-Branching admits a kernel with $O(k)$ vertices on any graph class of bounded expansion.
Bounded Model Checking of C++ Programs Based on the Qt Framework (extended version)
Venue: arXiv cs.LO 2015
Year: 2015

The software development process for embedded systems is getting faster and faster, which generally incurs an increase in the associated complexity. As a consequence, consumer electronics companies usually invest a lot of resources in fast and automatic verification processes, in order to create robust systems and reduce product recall rates. Because of that, the present paper proposes a simplified version of the Qt framework, which is integrated into the Efficient SMT-Based Bounded Model Checking tool to verify actual applications that use the mentioned framework. The method proposed in this paper presents a success rate of 94.45%, for the developed test suite.
Sampled Weighted Min-Hashing for Large-Scale Topic Mining
Venue: arXiv cs.LG 2015
Year: 2015

We present Sampled Weighted Min-Hashing (SWMH), a randomized approach to automatically mine topics from large-scale corpora. SWMH generates multiple random partitions of the corpus vocabulary based on term co-occurrence and agglomerates highly overlapping inter-partition cells to produce the mined topics. While other approaches define a topic as a probabilistic distribution over a vocabulary, SWMH topics are ordered subsets of such vocabulary. Interestingly, the topics mined by SWMH underlie themes from the corpus at different levels of granularity. We extensively evaluate the meaningfulness of the mined topics both qualitatively and quantitatively on the NIPS (1.7 K documents), 20 Newsgroups (20 K), Reuters (800 K) and Wikipedia (4 M) corpora. Additionally, we compare the quality of SWMH with Online LDA topics for document representation in classification.
On Hardness of the Joint Crossing Number
Venue: arXiv cs.DM 2015
Year: 2015

The Joint Crossing Number problem asks for a simultaneous embedding of two disjoint graphs into one surface such that the number of edge crossings (between the two graphs) is minimized. It was introduced by Negami in 2001 in connection with diagonal flips in triangulations of surfaces, and subsequently investigated in a general form for small-genus surfaces. We prove that all of the commonly considered variants of this problem are NP-hard already in the orientable surface of genus 6, by a reduction from a special variant of the anchored crossing number problem of Cabello and Mohar.
Channel Detection in Coded Communication
Venue: arXiv cs.IT 2015
Year: 2015

We consider the problem of block-coded communication, where in each block, the channel law belongs to one of two disjoint sets. The decoder is aimed to decode only messages that have undergone a channel from one of the sets, and thus has to detect the set which contains the prevailing channel. We begin with the simplified case where each of the sets is a singleton. For any given code, we derive the optimum detection/decoding rule in the sense of the best trade-off among the probabilities of decoding error, false alarm, and misdetection, and also introduce sub-optimal detection/decoding rules which are simpler to implement. Then, various achievable bounds on the error exponents are derived, including the exact single-letter characterization of the random coding exponents for the optimal detector/decoder. We then extend the random coding analysis to general sets of channels, and show that there exists a universal detector/decoder which performs asymptotically as well as the optimal detector/decoder, when tuned to detect a channel from a specific pair of channels. The case of a pair of binary symmetric channels is discussed in detail.