OpenRaiser/Intern-Atlas huggingface dataset:
Scaling Distributed Transaction Processing and Recovery based on Dependency Logging
Venue: arXiv cs.DB 2017
Year: 2017

DGCC protocol has been shown to achieve good performance on multi-core in-memory system. However, distributed transactions complicate the dependency resolution, and therefore, an effective transaction partitioning strategy is essential to reduce expensive multi-node distributed transactions. During failure recovery, log must be examined from the last checkpoint onwards and the affected transactions are re-executed based on the way they are partitioned and executed. Existing approaches treat both transaction management and recovery as two separate problems, even though recovery is dependent on the sequence in which transactions are executed. In this paper, we propose to treat the transaction management and recovery problems as one. We first propose an efficient Distributed Dependency Graph based Concurrency Control (DistDGCC) protocol for handling transactions spanning multiple nodes, and propose a new novel and efficient logging protocol called Dependency Logging that also makes use of dependency graphs for efficient logging and recovery. DistDGCC optimizes the average cost for each distributed transaction by processing transactions in batch. Moreover, it also reduces the effects of thread blocking caused by distributed transactions and consequently improves the runtime performance. Further, dependency logging exploits the same data structure that is used by DistDGCC to reduce the logging overhead, as well as the logical dependency information to improve the recovery parallelism. Extensive experiments are conducted to evaluate the performance of our proposed technique against state-of-the-art techniques. Experimental results show that DistDGCC is efficient and scalable, and dependency logging supports fast recovery with marginal runtime overhead. Hence, the overall system performance is significantly improved as a result.
Evaluation of DVFS techniques on modern HPC processors and accelerators for energy-aware applications
Venue: arXiv cs.DC 2017
Year: 2017

Energy efficiency is becoming increasingly important for computing systems, in particular for large scale HPC facilities. In this work we evaluate, from an user perspective, the use of Dynamic Voltage and Frequency Scaling (DVFS) techniques, assisted by the power and energy monitoring capabilities of modern processors in order to tune applications for energy efficiency. We run selected kernels and a full HPC application on two high-end processors widely used in the HPC context, namely an NVIDIA K80 GPU and an Intel Haswell CPU. We evaluate the available trade-offs between energy-to-solution and time-to-solution, attempting a function-by-function frequency tuning. We finally estimate the benefits obtainable running the full code on a HPC multi-GPU node, with respect to default clock frequency governors. We instrument our code to accurately monitor power consumption and execution time without the need of any additional hardware, and we enable it to change CPUs and GPUs clock frequencies while running. We analyze our results on the different architectures using a simple energy-performance model, and derive a number of energy saving strategies which can be easily adopted on recent high-end HPC systems for generic applications.
Introduction to Formal Concept Analysis and Its Applications in Information Retrieval and Related Fields
Venue: arXiv cs.IR 2017
Year: 2017

This paper is a tutorial on Formal Concept Analysis (FCA) and its applications. FCA is an applied branch of Lattice Theory, a mathematical discipline which enables formalisation of concepts as basic units of human thinking and analysing data in the object-attribute form. Originated in early 80s, during the last three decades, it became a popular human-centred tool for knowledge representation and data analysis with numerous applications. Since the tutorial was specially prepared for RuSSIR 2014, the covered FCA topics include Information Retrieval with a focus on visualisation aspects, Machine Learning, Data Mining and Knowledge Discovery, Text Mining and several others.
A World of Difference: Divergent Word Interpretations among People
Venue: arXiv cs.CL 2017
Year: 2017

Divergent word usages reflect differences among people. In this paper, we present a novel angle for studying word usage divergence -- word interpretations. We propose an approach that quantifies semantic differences in interpretations among different groups of people. The effectiveness of our approach is validated by quantitative evaluations. Experiment results indicate that divergences in word interpretations exist. We further apply the approach to two well studied types of differences between people -- gender and region. The detected words with divergent interpretations reveal the unique features of specific groups of people. For gender, we discover that certain different interests, social attitudes, and characters between males and females are reflected in their divergent interpretations of many words. For region, we find that specific interpretations of certain words reveal the geographical and cultural features of different regions.
Constrained clustering via diagrams: A unified theory and its applications to electoral district design
Venue: arXiv cs.DS 2017
Year: 2017

The paper develops a general framework for constrained clustering which is based on the close connection of geometric clustering and diagrams. Various new structural and algorithmic results are proved (and known results generalized and unified) which show that the approach is computationally efficient and flexible enough to pursue various conflicting demands. The strength of the model is also demonstrated practically on real-world instances of the electoral district design problem where municipalities of a state have to be grouped into districts of nearly equal population while obeying certain politically motivated requirements.
Discriminative models for multi-instance problems with tree-structure
Venue: arXiv cs.CR 2017
Year: 2017

Modeling network traffic is gaining importance in order to counter modern threats of ever increasing sophistication. It is though surprisingly difficult and costly to construct reliable classifiers on top of telemetry data due to the variety and complexity of signals that no human can manage to interpret in full. Obtaining training data with sufficiently large and variable body of labels can thus be seen as prohibitive problem. The goal of this work is to detect infected computers by observing their HTTP(S) traffic collected from network sensors, which are typically proxy servers or network firewalls, while relying on only minimal human input in model training phase. We propose a discriminative model that makes decisions based on all computer's traffic observed during predefined time window (5 minutes in our case). The model is trained on collected traffic samples over equally sized time window per large number of computers, where the only labels needed are human verdicts about the computer as a whole (presumed infected vs. presumed clean). As part of training the model itself recognizes discriminative patterns in traffic targeted to individual servers and constructs the final high-level classifier on top of them. We show the classifier to perform with very high precision, while the learned traffic patterns can be interpreted as Indicators of Compromise. In the following we implement the discriminative model as a neural network with special structure reflecting two stacked multi-instance problems. The main advantages of the proposed configuration include not only improved accuracy and ability to learn from gross labels, but also automatic learning of server types (together with their detectors) which are typically visited by infected computers.
Redundancy Suppression In Time-Aware Dynamic Binary Instrumentation
Venue: arXiv cs.SE 2017
Year: 2017

Software tracing techniques are well-established and used by instrumentation tools to extract run-time information for program analysis and debugging. Dynamic binary instrumentation as one tool instruments program binaries to extract information. Unfortunately, instrumentation causes perturbation that is unacceptable for time-sensitive applications. Consequently we developed DIME*, a tool for dynamic binary instrumentation that considers timing constraints. DIME* uses Pin and a rate-based server approach to extract information only as long as user-specified constraints are maintained. Due to the large amount of redundancies in program traces, DIME* reduces the instrumentation overhead by one to three orders of magnitude compared to native Pin while extracting up to 99% of the information. We instrument VLC and PostgreSQL to demonstrate the usability of DIME*.
Memory Enriched Big Bang Big Crunch Optimization Algorithm for Data Clustering
Venue: arXiv cs.AI 2017
Year: 2017

Cluster analysis plays an important role in decision making process for many knowledge-based systems. There exist a wide variety of different approaches for clustering applications including the heuristic techniques, probabilistic models, and traditional hierarchical algorithms. In this paper, a novel heuristic approach based on big bang-big crunch algorithm is proposed for clustering problems. The proposed method not only takes advantage of heuristic nature to alleviate typical clustering algorithms such as k-means, but it also benefits from the memory based scheme as compared to its similar heuristic techniques. Furthermore, the performance of the proposed algorithm is investigated based on several benchmark test functions as well as on the well-known datasets. The experimental results show the significant superiority of the proposed method over the similar algorithms.
A quantum dynamic belief model to explain the interference effects of categorization on decision making
Venue: arXiv cs.AI 2017
Year: 2017

Categorization is necessary for many decision making tasks. However, the categorization process may interfere the decision making result and the law of total probability can be violated in some situations. To predict the interference effect of categorization, some model based on quantum probability has been proposed. In this paper, a new quantum dynamic belief (QDB) model is proposed. Considering the precise decision may not be made during the process, the concept of uncertainty is introduced in our model to simulate real human thinking process. Then the interference effect categorization can be predicted by handling the uncertain information. The proposed model is applied to a categorization decision-making experiment to explain the interference effect of categorization. Compared with other models, our model is relatively more succinct and the result shows the correctness and effectiveness of our model.
Assessing Code Authorship: The Case of the Linux Kernel
Venue: arXiv cs.SE 2017
Year: 2017

Code authorship is a key information in large-scale open source systems. Among others, it allows maintainers to assess division of work and identify key collaborators. Interestingly, open-source communities lack guidelines on how to manage authorship. This could be mitigated by setting to build an empirical body of knowledge on how authorship-related measures evolve in successful open-source communities. Towards that direction, we perform a case study on the Linux kernel. Our results show that: (a) only a small portion of developers (26 %) makes significant contributions to the code base; (b) the distribution of the number of files per author is highly skewed --- a small group of top authors (3 %) is responsible for hundreds of files, while most authors (75 %) are responsible for at most 11 files; (c) most authors (62 %) have a specialist profile; (d) authors with a high number of co-authorship connections tend to collaborate with others with less connections.
Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks
Venue: arXiv cs.LG 2017
Year: 2017

We prove new upper and lower bounds on the VC-dimension of deep neural networks with the ReLU activation function. These bounds are tight for almost the entire range of parameters. Letting $W$ be the number of weights and $L$ be the number of layers, we prove that the VC-dimension is $O(W L \log(W))$, and provide examples with VC-dimension $Ω( W L \log(W/L) )$. This improves both the previously known upper bounds and lower bounds. In terms of the number $U$ of non-linear units, we prove a tight bound $Θ(W U)$ on the VC-dimension. All of these bounds generalize to arbitrary piecewise linear activation functions, and also hold for the pseudodimensions of these function classes. Combined with previous results, this gives an intriguing range of dependencies of the VC-dimension on depth for networks with different non-linearities: there is no dependence for piecewise-constant, linear dependence for piecewise-linear, and no more than quadratic dependence for general piecewise-polynomial.
A linear streaming algorithm for community detection in very large networks
Venue: arXiv cs.SI 2017
Year: 2017

In this paper, we introduce a novel community detection algorithm in graphs, called SCoDA (Streaming Community Detection Algorithm), based on an edge streaming setting. This algorithm has an extremely low memory footprint and a lightning-fast execution time as it only stores two integers per node and processes each edge strictly once. The approach is based on the following simple observation: if we pick an edge uniformly at random in the network, this edge is more likely to connect two nodes of the same community than two nodes of distinct communities. We exploit this idea to build communities by local changes at each edge arrival. Using theoretical arguments, we relate the ability of SCoDA to detect communities to usual quality metrics of these communities like the conductance. Experimental results performed on massive real-life networks ranging from one million to more than one billion edges shows that SCoDA runs more than ten times faster than existing algorithms and leads to similar or better detection scores on the largest graphs.
Sigil3D: A Crowdsourcing Platform for Interactive 3D Content
Venue: arXiv cs.HC 2017
Year: 2017

In this paper we propose applying the crowdsourcing approach to a software platform that uses a modern and state-of-the-art 3D game engine. This platform could facilitate the generation and manipulation of interactive 3D environments by a community of users producing different content such as cultural heritage, scientific virtual labs, games, novel art forms and virtual museums.
Comprehension of Ads-supported and Paid Android Applications: Are They Different?
Venue: arXiv cs.SE 2017
Year: 2017

The Android market is a place where developers offer paid and-or free apps to users. Free apps are interesting to users because they can try them immediately without incurring a monetary cost. However, free apps often have limited features and-or contain ads when compared to their paid counterparts. Thus, users may eventually need to pay to get additional features and-or remove ads. While paid apps have clear market values, their ads-supported versions are not entirely free because ads have an impact on performance. In this paper, first, we perform an exploratory study about ads-supported and paid apps to understand their differences in terms of implementation and development process. We analyze 40 Android apps and we observe that (i) ads-supported apps are preferred by users although paid apps have a better rating, (ii) developers do not usually offer a paid app without a corresponding free version, (iii) ads-supported apps usually have more releases and are released more often than their corresponding paid versions, (iv) there is no a clear strategy about the way developers set prices of paid apps, (v) paid apps do not usually include more functionalities than their corresponding ads-supported versions, (vi) developers do not always remove ad networks in paid versions of their ads-supported apps, and (vii) paid apps require less permissions than ads-supported apps. Second, we carry out an experimental study to compare the performance of ads-supported and paid apps and we propose four equations to estimate the cost of ads-supported apps. We obtain that (i) ads-supported apps use more resources than their corresponding paid versions with statistically significant differences and (ii) paid apps could be considered a most cost-effective choice for users because their cost can be amortized in a short period of time, depending on their usage.
Deep Convolutional Neural Network Inference with Floating-point Weights and Fixed-point Activations
Venue: arXiv cs.LG 2017
Year: 2017

Deep convolutional neural network (CNN) inference requires significant amount of memory and computation, which limits its deployment on embedded devices. To alleviate these problems to some extent, prior research utilize low precision fixed-point numbers to represent the CNN weights and activations. However, the minimum required data precision of fixed-point weights varies across different networks and also across different layers of the same network. In this work, we propose using floating-point numbers for representing the weights and fixed-point numbers for representing the activations. We show that using floating-point representation for weights is more efficient than fixed-point representation for the same bit-width and demonstrate it on popular large-scale CNNs such as AlexNet, SqueezeNet, GoogLeNet and VGG-16. We also show that such a representation scheme enables compact hardware multiply-and-accumulate (MAC) unit design. Experimental results show that the proposed scheme reduces the weight storage by up to 36% and power consumption of the hardware multiplier by up to 50%.
Information Extraction in Illicit Domains
Venue: arXiv cs.CL 2017
Year: 2017

Extracting useful entities and attribute values from illicit domains such as human trafficking is a challenging problem with the potential for widespread social impact. Such domains employ atypical language models, have `long tails' and suffer from the problem of concept drift. In this paper, we propose a lightweight, feature-agnostic Information Extraction (IE) paradigm specifically designed for such domains. Our approach uses raw, unlabeled text from an initial corpus, and a few (12-120) seed annotations per domain-specific attribute, to learn robust IE models for unobserved pages and websites. Empirically, we demonstrate that our approach can outperform feature-centric Conditional Random Field baselines by over 18\% F-Measure on five annotated sets of real-world human trafficking datasets in both low-supervision and high-supervision settings. We also show that our approach is demonstrably robust to concept drift, and can be efficiently bootstrapped even in a serial computing environment.
Robust MPC for tracking of nonholonomic robots with additive disturbances
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, two robust model predictive control (MPC) schemes are proposed for tracking control of nonholonomic systems with bounded disturbances: tube-MPC and nominal robust MPC (NRMPC). In tube-MPC, the control signal consists of a control action and a nonlinear feedback law based on the deviation of the actual states from the states of a nominal system. It renders the actual trajectory within a tube centered along the optimal trajectory of the nominal system. Recursive feasibility and input-to-state stability are established and the constraints are ensured by tightening the input domain and the terminal region. While in NRMPC, an optimal control sequence is obtained by solving an optimization problem based on the current state, and the first portion of this sequence is applied to the real system in an open-loop manner during each sampling period. The state of nominal system model is updated by the actual state at each step, which provides additional a feedback. By introducing a robust state constraint and tightening the terminal region, recursive feasibility and input-to-state stability are guaranteed. Simulation results demonstrate the effectiveness of both strategies proposed.
Predictive and Recommendatory Spectrum Decision for Cognitive Radio
Venue: arXiv cs.NI 2017
Year: 2017

Cognitive radio technology enables improving the utilization efficiency of the precious and scarce radio spectrum. How to maximize the overall spectrum efficiency while minimizing the conflicts with primary users is vital to cognitive radio. The key is to make the right decisions of accessing the spectrum. Spectrum prediction can be employed to predict the future states of a spectrum band using previous states of the spectrum band, whereas spectrum recommendation recommends secondary users a subset of available spectrum bands based on secondary user's previous experiences of accessing the available spectrum bands. In this paper, a framework for spectrum decision based on spectrum prediction and spectrum recommendation is proposed. As a benchmark, a method based on extreme learning machine (ELM) for single-user spectrum prediction and a method based on Q-learning for multiple-user spectrum prediction are proposed. At the stage of spectrum decision, two methods based on Q-learning andMarkov decision process (MDP), respectively, are also proposed to enhance the overall performance of spectrum decision. Experimental results show that the performance of the spectrum decision framework is much better.
Image Classification of Melanoma, Nevus and Seborrheic Keratosis by Deep Neural Network Ensemble
Venue: arXiv cs.CV 2017
Year: 2017

This short paper reports the method and the evaluation results of Casio and Shinshu University joint team for the ISBI Challenge 2017 - Skin Lesion Analysis Towards Melanoma Detection - Part 3: Lesion Classification hosted by ISIC. Our online validation score was 0.958 with melanoma classifier AUC 0.924 and seborrheic keratosis classifier AUC 0.993.
Robustness in Highly Dynamic Networks
Venue: arXiv cs.DC 2017
Year: 2017

We investigate a special case of hereditary property that we refer to as {\em robustness}. A property is {\em robust} in a given graph if it is inherited by all connected spanning subgraphs of this graph. We motivate this definition in different contexts, showing that it plays a central role in highly dynamic networks, although the problem is defined in terms of classical (static) graph theory. In this paper, we focus on the robustness of {\em maximal independent sets} (MIS). Following the above definition, a MIS is said to be {\em robust} (RMIS) if it remains a valid MIS in all connected spanning subgraphs of the original graph. We characterize the class of graphs in which {\em all} possible MISs are robust. We show that, in these particular graphs, the problem of finding a robust MIS is {\em local}; that is, we present an RMIS algorithm using only a sublogarithmic number of rounds (in the number of nodes $n$) in the ${\cal LOCAL}$ model. On the negative side, we show that, in general graphs, the problem is not local. Precisely, we prove a $Ω(n)$ lower bound on the number of rounds required for the nodes to decide consistently in some graphs. This result implies a separation between the RMIS problem and the MIS problem in general graphs. It also implies that any strategy in this case is asymptotically (in order) as bad as collecting all the network information at one node and solving the problem in a centralized manner. Motivated by this observation, we present a centralized algorithm that computes a robust MIS in a given graph, if one exists, and rejects otherwise. Significantly, this algorithm requires only a polynomial amount of local computation time, despite the fact that exponentially many MISs and exponentially many connected spanning subgraphs may exist.