OpenRaiser/Intern-Atlas huggingface dataset:
KDD-SC: Subspace Clustering Extensions for Knowledge Discovery Frameworks
Venue: arXiv cs.DB 2014
Year: 2014

Analyzing high dimensional data is a challenging task. For these data it is known that traditional clustering algorithms fail to detect meaningful patterns. As a solution, subspace clustering techniques have been introduced. They analyze arbitrary subspace projections of the data to detect clustering structures. In this paper, we present our subspace clustering extension for KDD frameworks, termed KDD-SC. In contrast to existing subspace clustering toolkits, our solution neither is a standalone product nor is it tightly coupled to a specific KDD framework. Our extension is realized by a common codebase and easy-to-use plugins for three of the most popular KDD frameworks, namely KNIME, RapidMiner, and WEKA. KDD-SC extends these frameworks such that they offer a wide range of different subspace clustering functionalities. It provides a multitude of algorithms, data generators, evaluation measures, and visualization techniques specifically designed for subspace clustering. These functionalities integrate seamlessly with the frameworks' existing features such that they can be flexibly combined. KDD-SC is publicly available on our website.
Scheduling in Grid Computing Environment
Venue: arXiv cs.DC 2014
Year: 2014

Scheduling in Grid computing has been active area of research since its beginning. However, beginners find very difficult to understand related concepts due to a large learning curve of Grid computing. Thus, there is a need of concise understanding of scheduling in Grid computing area. This paper strives to present concise understanding of scheduling and related understanding of Grid computing system. The paper describes overall picture of Grid computing and discusses important sub-systems that enable Grid computing possible. Moreover, the paper also discusses concepts of resource scheduling and application scheduling and also presents classification of scheduling algorithms. Furthermore, the paper also presents methodology used for evaluating scheduling algorithms including both real system and simulation based approaches. The presented work on scheduling in Grid containing concise understandings of scheduling system, scheduling algorithm, and scheduling methodology would be very useful to users and researchers
Comparative performance analysis of AntHocNet and DSR in optimal path route determination
Venue: arXiv cs.NI 2014
Year: 2014

One of the key challenges in current Internet routing is the application of improved bio-inspired algorithms in deriving the path towards the destination. Current routing trends determine the optimal path based on throughput, delay or combination of these two metric. Here in this paper, we compare the performance of the two algorithms, AntHocNet (AHN) and Dynamic Source Routing (DSR) for determining the routing path. We introduce the goodput factor as one of the metric for determining the path. Goodput is the number of useful information bits, delivered by the network to a certain destination per unit time .The results show that AHN outperformed DSR in terms of end-to-end delay and overhead. Also the simulation results showed that overhead of AHN was 20.67% lesser than DSR.
A Comparison of Methods for Player Clustering via Behavioral Telemetry
Venue: arXiv cs.HC 2014
Year: 2014

The analysis of user behavior in digital games has been aided by the introduction of user telemetry in game development, which provides unprecedented access to quantitative data on user behavior from the installed game clients of the entire population of players. Player behavior telemetry datasets can be exceptionally complex, with features recorded for a varying population of users over a temporal segment that can reach years in duration. Categorization of behaviors, whether through descriptive methods (e.g. segmention) or unsupervised/supervised learning techniques, is valuable for finding patterns in the behavioral data, and developing profiles that are actionable to game developers. There are numerous methods for unsupervised clustering of user behavior, e.g. k-means/c-means, Non-negative Matrix Factorization, or Principal Component Analysis. Although all yield behavior categorizations, interpretation of the resulting categories in terms of actual play behavior can be difficult if not impossible. In this paper, a range of unsupervised techniques are applied together with Archetypal Analysis to develop behavioral clusters from playtime data of 70,014 World of Warcraft players, covering a five year interval. The techniques are evaluated with respect to their ability to develop actionable behavioral profiles from the dataset.
The friendship paradox in scale-free networks
Venue: arXiv cs.SI 2014
Year: 2014

Our friends have more friends than we do. That is the basis of the friendship paradox. In mathematical terms, the mean number of friends of friends is higher than the mean number of friends. In the present study, we analyzed the relationship between the mean degree of vertices (individuals), <k>, and the mean number of friends of friends, <k_FF>, in scale-free networks with degrees ranging from a minimum degree (k_min) to a maximum degree (k_max). We deduced an expression for <k_FF> - <k> for scale-free networks following a power-law distribution with a given scaling parameter (alpha). Based on this expression, we can quantify how the degree distribution of a scale-free network affects the mean number of friends of friends.
Privacy-Preserving Population-Enhanced Biometric Key Generation from Free-Text Keystroke Dynamics
Venue: arXiv cs.CR 2014
Year: 2014

Biometric key generation techniques are used to reliably generate cryptographic material from biometric signals. Existing constructions require users to perform a particular activity (e.g., type or say a password, or provide a handwritten signature), and are therefore not suitable for generating keys continuously. In this paper we present a new technique for biometric key generation from free-text keystroke dynamics. This is the first technique suitable for continuous key generation. Our approach is based on a scaled parity code for key generation (and subsequent key reconstruction), and can be augmented with the use of population data to improve security and reduce key reconstruction error. In particular, we rely on linear discriminant analysis (LDA) to obtain a better representation of discriminable biometric signals. To update the LDA matrix without disclosing user's biometric information, we design a provably secure privacy-preserving protocol (PP-LDA) based on homomorphic encryption. Our biometric key generation with PP-LDA was evaluated on a dataset of 486 users. We report equal error rate around 5% when using LDA, and below 7% without LDA.
Security of OS-level virtualization technologies: Technical report
Venue: arXiv cs.CR 2014
Year: 2014

The need for flexible, low-overhead virtualization is evident on many fronts ranging from high-density cloud servers to mobile devices. During the past decade OS-level virtualization has emerged as a new, efficient approach for virtualization, with implementations in multiple different Unix-based systems. Despite its popularity, there has been no systematic study of OS-level virtualization from the point of view of security. In this report, we conduct a comparative study of several OS-level virtualization systems, discuss their security and identify some gaps in current solutions.
Subspace Restricted Boltzmann Machine
Venue: arXiv cs.LG 2014
Year: 2014

The subspace Restricted Boltzmann Machine (subspaceRBM) is a third-order Boltzmann machine where multiplicative interactions are between one visible and two hidden units. There are two kinds of hidden units, namely, gate units and subspace units. The subspace units reflect variations of a pattern in data and the gate unit is responsible for activating the subspace units. Additionally, the gate unit can be seen as a pooling feature. We evaluate the behavior of subspaceRBM through experiments with MNIST digit recognition task, measuring reconstruction error and classification error.
Evaluation of the DiversiNews diversified news service
Venue: arXiv cs.CY 2014
Year: 2014

In this report we present the outcome of an extensive evaluation of the DiversiNews platform [8, 10] for diversified browsing of news, developed in the scope of the RENDER project. The evaluation was carried out along two main directions: a component evaluation, in which we assessed the maturity of the components underlying DiversiNews, and a user experience (UX) evaluation involving users of online news services. The results of the evaluation confirm the high value of DiversiNews as a novel paradigm for diversity-aware news browsing.
Virus Detection in Multiplexed Nanowire Arrays using Hidden Semi-Markov models
Venue: arXiv cs.AI 2014
Year: 2014

In this paper, we address the problem of real-time detection of viruses docking to nanowires, especially when multiple viruses dock to the same nano-wire. The task becomes more complicated when there is an array of nanowires coated with different antibodies, where different viruses can dock to each coated nanowire at different binding strengths. We model the array response to a viral agent as a pattern of conductance change over nanowires with known modifier --- this representation permits analysis of the output of such an array via belief network (Bayes) methods, as well as novel generative models like the Hidden Semi-Markov Model (HSMM).
Online Packet-Routing in Grids with Bounded Buffers
Venue: arXiv cs.DS 2014
Year: 2014

We present deterministic and randomized algorithms for the problem of online packet routing in grids in the competitive network throughput model \cite{AKOR}. In this model the network has nodes with bounded buffers and bounded link capacities. The goal in this model is to maximize the throughput, i.e., the number of delivered packets. Our deterministic algorithm is the first online algorithm with an $O\left(\log^{O(1)}(n)\right)$ competitive ratio for uni-directional grids (where $n$ denotes the size of the network). The deterministic online algorithm is centralized and handles packets with deadlines. This algorithm is applicable to various ranges of values of buffer sizes and communication link capacities. In particular, it holds for buffer size and communication link capacity in the range $[3 \ldots \log n]$. Our randomized algorithm achieves an expected competitive ratio of $O(\log n)$ for the uni-directional line. This algorithm is applicable to a wide range of buffer sizes and communication link capacities. In particular, it holds also for unit size buffers and unit capacity links. This algorithm improves the best previous $O(\log^2 n)$-competitive ratio of Azar and Zachut \cite{AZ}.
Hybrid Random/Deterministic Parallel Algorithms for Nonconvex Big Data Optimization
Venue: arXiv cs.DC 2014
Year: 2014

We propose a decomposition framework for the parallel optimization of the sum of a differentiable {(possibly nonconvex)} function and a nonsmooth (possibly nonseparable), convex one. The latter term is usually employed to enforce structure in the solution, typically sparsity. The main contribution of this work is a novel \emph{parallel, hybrid random/deterministic} decomposition scheme wherein, at each iteration, a subset of (block) variables is updated at the same time by minimizing local convex approximations of the original nonconvex function. To tackle with huge-scale problems, the (block) variables to be updated are chosen according to a \emph{mixed random and deterministic} procedure, which captures the advantages of both pure deterministic and random update-based schemes. Almost sure convergence of the proposed scheme is established. Numerical results show that on huge-scale problems the proposed hybrid random/deterministic algorithm outperforms both random and deterministic schemes.
On relative OR-complexity of Boolean matrices and their complements
Venue: arXiv cs.CC 2014
Year: 2014

We construct explicit Boolean square matrices whose rectifier complexity (OR-complexity) differs significantly from the complexity of their complement matrices.
Protein Folding in the Hexagonal Prism Lattice with Diagonals
Venue: arXiv cs.CE 2014
Year: 2014

Predicting protein secondary structure using lattice model is one of the most studied computational problem in bioinformatics. Here secondary structure or three dimensional structure of protein is predicted from its amino acid sequence. Secondary structure refers to local sub-structures of protein. Mostly founded secondary structures are alpha helix and beta sheets. Since, it is a problem of great potential complexity many simplified energy model have been proposed in literature on basis of interaction of amino acid residue in protein. Here we use well researched Hydrophobic-Polar (HP) energy model. In this paper, we proposed hexagonal prism lattice with diagonal that can overcome the problems of other lattice structure, e.g., parity problem. We give two approximation algorithm for protein folding on this lattice. Our first algorithm leads us to similar structure of helix structure which is commonly found in protein structure. This motivated us to find next algorithm which improves the algorithm ratio of 9/7.
A feature construction framework based on outlier detection and discriminative pattern mining
Venue: arXiv cs.LG 2014
Year: 2014

No matter the expressive power and sophistication of supervised learning algorithms, their effectiveness is restricted by the features describing the data. This is not a new insight in ML and many methods for feature selection, transformation, and construction have been developed. But while this is on-going for general techniques for feature selection and transformation, i.e. dimensionality reduction, work on feature construction, i.e. enriching the data, is by now mainly the domain of image, particularly character, recognition, and NLP. In this work, we propose a new general framework for feature construction. The need for feature construction in a data set is indicated by class outliers and discriminative pattern mining used to derive features on their k-neighborhoods. We instantiate the framework with LOF and C4.5-Rules, and evaluate the usefulness of the derived features on a diverse collection of UCI data sets. The derived features are more often useful than ones derived by DC-Fringe, and our approach is much less likely to overfit. But while a weak learner, Naive Bayes, benefits strongly from the feature construction, the effect is less pronounced for C4.5, and almost vanishes for an SVM leaner. Keywords: feature construction, classification, outlier detection
Hand Pointing Detection Using Live Histogram Template of Forehead Skin
Venue: arXiv cs.CV 2014
Year: 2014

Hand pointing detection has multiple applications in many fields such as virtual reality and control devices in smart homes. In this paper, we proposed a novel approach to detect pointing vector in 2D space of a room. After background subtraction, face and forehead is detected. In the second step, forehead skin H-S plane histograms in HSV space is calculated. By using these histogram templates of users skin, and back projection method, skin areas are detected. The contours of hand are extracted using Freeman chain code algorithm. Next step is finding fingertips. Points in hand contour which are candidates for the fingertip can be found in convex defects of convex hull and contour. We introduced a novel method for finding the fingertip based on the special points on the contour and their relationships. Our approach detects hand-pointing vectors in live video from a common webcam with 94%TP and 85%TN.
Sliced Slices: Separating Data and Control Influences
Venue: arXiv cs.SE 2014
Year: 2014

Backward slicing has been used extensively in program understanding, debugging and scaling up of program analysis. For large programs, the size of the conventional backward slice is about 25% of the program size. This may be too large to be useful. Our investigations reveal that in general, the size of a slice is influenced more by computations governing the control flow reaching the slicing criterion than by the computations governing the values relevant to the slicing criterion. We distinguish between the two by defining data slices and control slices both of which are smaller than the conventional slices which can be obtained by combining the two. This is useful because for many applications, the individual data or control slices are sufficient. Our experiments show that for more than 50% of cases, the data slice is smaller than 10% of the program in size. Besides, the time to compute data or control slice is comparable to that for computing the conventional slice.
Your Voice Assistant is Mine: How to Abuse Speakers to Steal Information and Control Your Phone
Venue: arXiv cs.CR 2014
Year: 2014

Previous research about sensor based attacks on Android platform focused mainly on accessing or controlling over sensitive device components, such as camera, microphone and GPS. These approaches get data from sensors directly and need corresponding sensor invoking permissions. This paper presents a novel approach (GVS-Attack) to launch permission bypassing attacks from a zero permission Android application (VoicEmployer) through the speaker. The idea of GVS-Attack utilizes an Android system built-in voice assistant module -- Google Voice Search. Through Android Intent mechanism, VoicEmployer triggers Google Voice Search to the foreground, and then plays prepared audio files (like "call number 1234 5678") in the background. Google Voice Search can recognize this voice command and execute corresponding operations. With ingenious designs, our GVS-Attack can forge SMS/Email, access privacy information, transmit sensitive data and achieve remote control without any permission. Also we found a vulnerability of status checking in Google Search app, which can be utilized by GVS-Attack to dial arbitrary numbers even when the phone is securely locked with password. A prototype of VoicEmployer has been implemented to demonstrate the feasibility of GVS-Attack in real world. In theory, nearly all Android devices equipped with Google Services Framework can be affected by GVS-Attack. This study may inspire application developers and researchers rethink that zero permission doesn't mean safety and the speaker can be treated as a new attack surface.
Into the Square - On the Complexity of Quadratic-Time Solvable Problems
Venue: arXiv cs.CC 2014
Year: 2014

This paper will analyze several quadratic-time solvable problems, and will classify them into two classes: problems that are solvable in truly subquadratic time (that is, in time $O(n^{2-ε})$ for some $ε>0$) and problems that are not, unless the well known Strong Exponential Time Hypothesis (SETH) is false. In particular, we will prove that some quadratic-time solvable problems are indeed easier than expected. We will provide an algorithm that computes the transitive closure of a directed graph in time $O(mn^{\frac{ω+1}{4}})$, where $m$ denotes the number of edges in the transitive closure and $ω$ is the exponent for matrix multiplication. As a side effect, we will prove that our algorithm runs in time $O(n^{\frac{5}{3}})$ if the transitive closure is sparse. The same time bounds hold if we want to check whether a graph is transitive, by replacing m with the number of edges in the graph itself. As far as we know, this is the fastest algorithm for sparse transitive digraph recognition. Finally, we will apply our algorithm to the comparability graph recognition problem (dating back to 1941), obtaining the first truly subquadratic algorithm. The second part of the paper deals with hardness results. Starting from an artificial quadratic-time solvable variation of the k-SAT problem, we will construct a graph of Karp reductions, proving that a truly subquadratic-time algorithm for any of the problems in the graph falsifies SETH. The analyzed problems are the following: computing the subset graph, finding dominating sets, computing the betweenness centrality of a vertex, computing the minimum closeness centrality, and computing the hyperbolicity of a pair of vertices. We will also be able to include in our framework three proofs already appeared in the literature, concerning the graph diameter computation, local alignment of strings and orthogonality of vectors.
A framework for community detection in heterogeneous multi-relational networks
Venue: arXiv cs.SI 2014
Year: 2014

There has been a surge of interest in community detection in homogeneous single-relational networks which contain only one type of nodes and edges. However, many real-world systems are naturally described as heterogeneous multi-relational networks which contain multiple types of nodes and edges. In this paper, we propose a new method for detecting communities in such networks. Our method is based on optimizing the composite modularity, which is a new modularity proposed for evaluating partitions of a heterogeneous multi-relational network into communities. Our method is parameter-free, scalable, and suitable for various networks with general structure. We demonstrate that it outperforms the state-of-the-art techniques in detecting pre-planted communities in synthetic networks. Applied to a real-world Digg network, it successfully detects meaningful communities.
Adaptive Image Denoising by Targeted Databases
Venue: arXiv cs.CV 2014
Year: 2014

We propose a data-dependent denoising procedure to restore noisy images. Different from existing denoising algorithms which search for patches from either the noisy image or a generic database, the new algorithm finds patches from a database that contains only relevant patches. We formulate the denoising problem as an optimal filter design problem and make two contributions. First, we determine the basis function of the denoising filter by solving a group sparsity minimization problem. The optimization formulation generalizes existing denoising algorithms and offers systematic analysis of the performance. Improvement methods are proposed to enhance the patch search process. Second, we determine the spectral coefficients of the denoising filter by considering a localized Bayesian prior. The localized prior leverages the similarity of the targeted database, alleviates the intensive Bayesian computation, and links the new method to the classical linear minimum mean squared error estimation. We demonstrate applications of the proposed method in a variety of scenarios, including text images, multiview images and face images. Experimental results show the superiority of the new algorithm over existing methods.
Classification of Passes in Football Matches using Spatiotemporal Data
Venue: arXiv cs.LG 2014
Year: 2014

A knowledgeable observer of a game of football (soccer) can make a subjective evaluation of the quality of passes made between players during the game. We investigate the problem of producing an automated system to make the same evaluation of passes. We present a model that constructs numerical predictor variables from spatiotemporal match data using feature functions based on methods from computational geometry, and then learns a classification function from labelled examples of the predictor variables. Furthermore, the learned classifiers are analysed to determine if there is a relationship between the complexity of the algorithm that computed the predictor variable and the importance of the variable to the classifier. Experimental results show that we are able to produce a classifier with 85.8% accuracy on classifying passes as Good, OK or Bad, and that the predictor variables computed using complex methods from computational geometry are of moderate importance to the learned classifiers. Finally, we show that the inter-rater agreement on pass classification between the machine classifier and a human observer is of similar magnitude to the agreement between two observers.