OpenRaiser/Intern-Atlas huggingface dataset:
Will This Paper Increase Your h-index? Scientific Impact Prediction
Venue: arXiv cs.SI 2014
Year: 2014

Scientific impact plays a central role in the evaluation of the output of scholars, departments, and institutions. A widely used measure of scientific impact is citations, with a growing body of literature focused on predicting the number of citations obtained by any given publication. The effectiveness of such predictions, however, is fundamentally limited by the power-law distribution of citations, whereby publications with few citations are extremely common and publications with many citations are relatively rare. Given this limitation, in this work we instead address a related question asked by many academic researchers in the course of writing a paper, namely: "Will this paper increase my h-index?" Using a real academic dataset with over 1.7 million authors, 2 million papers, and 8 million citation relationships from the premier online academic service ArnetMiner, we formalize a novel scientific impact prediction problem to examine several factors that can drive a paper to increase the primary author's h-index. We find that the researcher's authority on the publication topic and the venue in which the paper is published are crucial factors to the increase of the primary author's h-index, while the topic popularity and the co-authors' h-indices are of surprisingly little relevance. By leveraging relevant factors, we find a greater than 87.5% potential predictability for whether a paper will contribute to an author's h-index within five years. As a further experiment, we generate a self-prediction for this paper, estimating that there is a 76% probability that it will contribute to the h-index of the co-author with the highest current h-index in five years. We conclude that our findings on the quantification of scientific impact can help researchers to expand their influence and more effectively leverage their position of "standing on the shoulders of giants."
Report on a User Test and Extension of a Type Debugger for Novice Programmers
Venue: arXiv cs.PL 2014
Year: 2014

A type debugger interactively detects the expressions that cause type errors. It asks users whether they intend the types of identifiers to be those that the compiler inferred. However, it seems that novice programmers often get in trouble when they think about how to fix type errors by reading the messages given by the type debugger. In this paper, we analyze the user tests of a type debugger and report problems of the current type debugger. We then extend the type debugger to address these problems. Specifically, we introduce expression-specific error messages and language levels. Finally, we show type errors that we think are difficult to explain to novice programmers. The subjects of the user tests were 40 novice students belonging to the department of information science at Ochanomizu University.
Simple Balanced Binary Search Trees
Venue: arXiv cs.PL 2014
Year: 2014

Efficient implementations of sets and maps (dictionaries) are important in computer science, and balanced binary search trees are the basis of the best practical implementations. Pedagogically, however, they are often quite complicated, especially with respect to deletion. I present complete code (with justification and analysis not previously available in the literature) for a purely-functional implementation based on AA trees, which is the simplest treatment of the subject of which I am aware.
Overlapping Communities in Social Networks
Venue: arXiv cs.SI 2014
Year: 2014

Complex networks can be typically broken down into groups or modules. Discovering this "community structure" is an important step in studying the large-scale structure of networks. Many algorithms have been proposed for community detection and benchmarks have been created to evaluate their performance. Typically algorithms for community detection either partition the graph (non-overlapping communities) or find node covers (overlapping communities). In this paper, we propose a particularly simple semi-supervised learning algorithm for finding out communities. In essence, given the community information of a small number of "seed nodes", the method uses random walks from the seed nodes to uncover the community information of the whole network. The algorithm runs in time $O(k \cdot m \cdot \log n)$, where $m$ is the number of edges; $n$ the number of links; and $k$ the number of communities in the network. In sparse networks with $m = O(n)$ and a constant number of communities, this running time is almost linear in the size of the network. Another important feature of our algorithm is that it can be used for either non-overlapping or overlapping communities. We test our algorithm using the LFR benchmark created by Lancichinetti, Fortunato, and Radicchi specifically for the purpose of evaluating such algorithms. Our algorithm can compete with the best of algorithms for both non-overlapping and overlapping communities as found in the comprehensive study of Lancichinetti and Fortunato.
What is a salient object? A dataset and a baseline model for salient object detection
Venue: arXiv cs.CV 2014
Year: 2014

Salient object detection or salient region detection models, diverging from fixation prediction models, have traditionally been dealing with locating and segmenting the most salient object or region in a scene. While the notion of most salient object is sensible when multiple objects exist in a scene, current datasets for evaluation of saliency detection approaches often have scenes with only one single object. We introduce three main contributions in this paper: First, we take an indepth look at the problem of salient object detection by studying the relationship between where people look in scenes and what they choose as the most salient object when they are explicitly asked. Based on the agreement between fixations and saliency judgments, we then suggest that the most salient object is the one that attracts the highest fraction of fixations. Second, we provide two new less biased benchmark datasets containing scenes with multiple objects that challenge existing saliency models. Indeed, we observed a severe drop in performance of 8 state-of-the-art models on our datasets (40% to 70%). Third, we propose a very simple yet powerful model based on superpixels to be used as a baseline for model evaluation and comparison. While on par with the best models on MSRA-5K dataset, our model wins over other models on our data highlighting a serious drawback of existing models, which is convoluting the processes of locating the most salient object and its segmentation. We also provide a review and statistical analysis of some labeled scene datasets that can be used for evaluating salient object detection models. We believe that our work can greatly help remedy the over-fitting of models to existing biased datasets and opens new venues for future research in this fast-evolving field.
A Programming Model and Runtime System for Significance-Aware Energy-Efficient Computing
Venue: arXiv cs.PL 2014
Year: 2014

Reducing energy consumption is one of the key challenges in computing technology. One factor that contributes to high energy consumption is that all parts of the program are considered equally significant for the accuracy of the end-result. However, in many cases, parts of computations can be performed in an approximate way, or even dropped, without affecting the quality of the final output to a significant degree. In this paper, we introduce a task-based programming model and runtime system that exploit this observation to trade off the quality of program outputs for increased energy-efficiency. This is done in a structured and flexible way, allowing for easy exploitation of different execution points in the quality/energy space, without code modifications and without adversely affecting application performance. The programmer specifies the significance of tasks, and optionally provides approximations for them. Moreover, she provides hints to the runtime on the percentage of tasks that should be executed accurately in order to reach the target quality of results. The runtime system can apply a number of different policies to decide whether it will execute each individual less-significant task in its accurate form, or in its approximate version. Policies differ in terms of their runtime overhead but also the degree to which they manage to execute tasks according to the programmer's specification. The results from experiments performed on top of an Intel-based multicore/multiprocessor platform show that, depending on the runtime policy used, our system can achieve an energy reduction of up to 83% compared with a fully accurate execution and up to 35% compared with an approximate version employing loop perforation. At the same time, our approach always results in graceful quality degradation.
An Algebraical Model for Gray Level Images
Venue: arXiv cs.CV 2014
Year: 2014

In this paper we propose a new algebraical model for the gray level images. It can be used for digital image processing. The model adresses to those images which are generated in improper light conditions (very low or high level). The vector space structure is able to illustrate some features into the image using modified level of contrast and luminosity. Also, the defined structure could be used in image enhancement. The general approach is presented with experimental results to demonstrate image enhancement.
Analysis of Two-Tier LTE Network with Randomized Resource Allocation and Proactive Offloading
Venue: arXiv cs.IT 2014
Year: 2014

The heterogeneity in cellular networks that comprise multiple base stations types imposes new challenges in network planning and deployment. The Radio Resource Management (RRM) techniques, such as dynamic sharing of the available resources and advanced user association strategies determine the overall network capacity and the network/spectrum efficiency. This paper evaluates the downlink performance of a two-tier heterogeneous LTE network (consisting of macro and femto tiers) in terms of rate distribution, i.e. the percentage of users that achieve certain rate in the system. The paper specifically addresses: (1) the femto tier RRM by randomization of the allocated resources; (2) the user association process by introducing novel proactive offloading scheme and (3) femto tier access control. System level simulation results show that an optimal RRM strategy can be designed for different scenarios (e.g. congested and uncongested networks). The proposed proactive offloading scheme in the association phase improves the performance of congested networks by efficiently utilizing the available femto tier resources. Finally, the introduced hybrid access in femto tier is shown to perform nearly identical as the open access.
Noise Resilient Recovery Algorithm for Compressed Sensing
Venue: arXiv cs.IT 2014
Year: 2014

In this article, we discuss a novel greedy algorithm for the recovery of compressive sampled signals under noisy conditions. Most of the greedy recovery algorithms proposed in the literature require sparsity of the signal to be known or they estimate sparsity, for a known representation basis, from the number of measurements. These algorithms recover signals when noise level is significantly low. We propose Entropy minimization based Matching Pursuit (EMP) which has the capability to reject noise even when noise level is comparable to that of signal level. The proposed algorithm can cater to compressible signals and signals for which sparsity is not known in advance. Simulation study of the proposed scheme shows improved robustness to white Gaussian noise in comparison with the conventional greedy recovery algorithms.
Conversion of G-code programs for milling into STEP-NC
Venue: arXiv cs.CE 2014
Year: 2014

STEP-NC (ISO 14649) is becoming a promising standard to replace or supplement the conventional G-code programs based on ISO 6983 due to its feature based machine independent characteristics and its centric role to enable efficient CAD/CAM/CNC interoperability. The re-use of G-code programs is important for both manufacturing and capitalization of machining knowledge, nevertheless the conversion is a tedious task when carried out manually and machining knowledge is almost hidden in the low level G-code. Mapping G-code into STEP-NC should benefit from more expressiveness of the manufacturing feature-based characteristics of this new standard. The work presented here proposes an overall method for G-code to STEP-NC conversion. First, G-code is converted into canonical machining functions, this can make the method more applicable and make subsequent processes easier to implement; then these functions are parsed to generate the neutral format of STEP-NC Part21 toolpath file, this turns G-code into object instances, and can facilitate company's usage of legacy programs; and finally, also optionally, machining features are extracted to generate Part21 CC2 (conformance class) file. The proposed extraction method employs geometric information of cutting area inferred from toolpaths and machining strategies, in addition to cutting tools' data and workpiece's dimension data. This comprehensive use of available data makes the extraction more accurate and reliable. The conversion method is holistic, and can be extended to process a wide range of G-code programs (e.g. turning or mill-turn codes) with as few user interventions as possible.
Learning from Data with Heterogeneous Noise using SGD
Venue: arXiv cs.LG 2014
Year: 2014

We consider learning from data of variable quality that may be obtained from different heterogeneous sources. Addressing learning from heterogeneous data in its full generality is a challenging problem. In this paper, we adopt instead a model in which data is observed through heterogeneous noise, where the noise level reflects the quality of the data source. We study how to use stochastic gradient algorithms to learn in this model. Our study is motivated by two concrete examples where this problem arises naturally: learning with local differential privacy based on data from multiple sources with different privacy requirements, and learning from data with labels of variable quality. The main contribution of this paper is to identify how heterogeneous noise impacts performance. We show that given two datasets with heterogeneous noise, the order in which to use them in standard SGD depends on the learning rate. We propose a method for changing the learning rate as a function of the heterogeneity, and prove new regret bounds for our method in two cases of interest. Experiments on real data show that our method performs better than using a single learning rate and using only the less noisy of the two datasets when the noise level is low to moderate.
Numerical solution of nonstationary problems for a space-fractional diffusion equation
Venue: arXiv cs.NA 2014
Year: 2014

An unsteady problem is considered for a space-fractional diffusion equation in a bounded domain. A first-order evolutionary equation containing a fractional power of an elliptic operator of second order is studied for general boundary conditions of Robin type. Finite element approximation in space is employed. To construct approximation in time, regularized two-level schemes are used. The numerical implementation is based on solving the equation with the fractional power of the elliptic operator using an auxiliary Cauchy problem for a pseudo-parabolic equation. The results of numerical experiments are presented for a model two-dimensional problem.
Continuity of the Value Function in Sparse Optimal Control
Venue: arXiv cs.SY 2014
Year: 2014

We prove the continuity of the value function of the sparse optimal control problem. The sparse optimal control is a control whose support is minimum among all admissible controls. Under the normality assumption, it is known that a sparse optimal control is given by L^1 optimal control. Furthermore, the value function of the sparse optimal control problem is identical with that of the L1-optimal control problem. From these properties, we prove the continuity of the value function of the sparse optimal control problem by verifying that of the L1-optimal control problem.
Naming game with learning errors in communications
Venue: arXiv cs.SI 2014
Year: 2014

Naming game simulates the process of naming an objective by a population of agents organized in a certain communication network topology. By pair-wise iterative interactions, the population reaches a consensus state asymptotically. In this paper, we study naming game with communication errors during pair-wise conversations, where errors are represented by error rates in a uniform probability distribution. First, a model of naming game with learning errors in communications (NGLE) is proposed. Then, a strategy for agents to prevent learning errors is suggested. To that end, three typical topologies of communication networks, namely random-graph, small-world and scale-free networks with different parameters, are employed to investigate the effects of various learning errors. Simulation results on these models show that 1) learning errors slightly affect the convergence speed but distinctively increase the requirement for memory of each agent during lexicon propagation; 2) the maximum number of different words held by the whole population increases linearly as the value of the error rate increases; 3) without applying any strategy to eliminate learning errors, there is a threshold value of the learning errors which impairs the convergence. The new findings help to better understand the role of learning errors in naming game as well as human language development from a network science perspective.
A theoretical basis for efficient computations with noisy spiking neurons
Venue: arXiv cs.NE 2014
Year: 2014

Network of neurons in the brain apply - unlike processors in our current generation of computer hardware - an event-based processing strategy, where short pulses (spikes) are emitted sparsely by neurons to signal the occurrence of an event at a particular point in time. Such spike-based computations promise to be substantially more power-efficient than traditional clocked processing schemes. However it turned out to be surprisingly difficult to design networks of spiking neurons that are able to carry out demanding computations. We present here a new theoretical framework for organizing computations of networks of spiking neurons. In particular, we show that a suitable design enables them to solve hard constraint satisfaction problems from the domains of planning - optimization and verification - logical inference. The underlying design principles employ noise as a computational resource. Nevertheless the timing of spikes (rather than just spike rates) plays an essential role in the resulting computations. Furthermore, one can demonstrate for the Traveling Salesman Problem a surprising computational advantage of networks of spiking neurons compared with traditional artificial neural networks and Gibbs sampling. The identification of such advantage has been a well-known open problem.
Real root finding for determinants of linear matrices
Venue: arXiv cs.SC 2014
Year: 2014

Let $\A_0, \A_1, \ldots, \A_n$ be given square matrices of size $m$ with rational coefficients. The paper focuses on the exact computation of one point in each connected component of the real determinantal variety $\{\X \in\RR^n \: :\: \det(\A_0+x_1\A_1+\cdots+x_n\A_n)=0\}$. Such a problem finds applications in many areas such as control theory, computational geometry, optimization, etc. Using standard complexity results this problem can be solved using $m^{O(n)}$ arithmetic operations. Under some genericity assumptions on the coefficients of the matrices, we provide an algorithm solving this problem whose runtime is essentially quadratic in ${{n+m}\choose{n}}^{3}$. We also report on experiments with a computer implementation of this algorithm. Its practical performance illustrates the complexity estimates. In particular, we emphasize that for subfamilies of this problem where $m$ is fixed, the complexity is polynomial in $n$.
Games for Active XML Revisited
Venue: arXiv cs.DB 2014
Year: 2014

The paper studies the rewriting mechanisms for intensional documents in the Active XML framework, abstracted in the form of active context-free games. The safe rewriting problem studied in this paper is to decide whether the first player, Juliet, has a winning strategy for a given game and (nested) word; this corresponds to a successful rewriting strategy for a given intensional document. The paper examines several extensions to active context-free games. The primary extension allows more expressive schemas (namely XML schemas and regular nested word languages) for both target and replacement languages and has the effect that games are played on nested words instead of (flat) words as in previous studies. Other extensions consider validation of input parameters of web services, and an alternative semantics based on insertion of service call results. In general, the complexity of the safe rewriting problem is highly intractable (doubly exponential time), but the paper identifies interesting tractable cases.
Low-Complexity Cloud Image Privacy Protection via Matrix Perturbation
Venue: arXiv cs.CR 2014
Year: 2014

Cloud-assisted image services are widely used for various applications. Due to the high computational complexity of existing image encryption technology, it is extremely challenging to provide privacy preserving image services for resource-constrained smart device. In this paper, we propose a novel encrypressive cloud-assisted image service scheme, called eCIS. The key idea of eCIS is to shift the high computational cost to the cloud allowing reduction in complexity of encoder and decoder on resource-constrained device. This is done via compressive sensing (CS) techniques, compared with existing approaches, we are able to achieve privacy protection at no additional transmission cost. In particular, we design an encryption matrix by taking care of image compression and encryption simultaneously. Such that, the goal of our design is to minimize the mutual information of original image and encrypted image. In addition to the theoretical analysis that demonstrates the security properties and complexity of our system, we also conduct extensive experiment to evaluate its performance. The experiment results show that eCIS can effectively protect image privacy and meet the user's adaptive secure demand. eCIS reduced the system overheads by up to $4.1\times\sim6.8\times$ compared with the existing CS based image processing approach.
Complexity of distance fraud attacks in graph-based distance bounding
Venue: arXiv cs.CR 2014
Year: 2014

Distance bounding (DB) emerged as a countermeasure to the so-called \emph{relay attack}, which affects several technologies such as RFID, NFC, Bluetooth, and Ad-hoc networks. A prominent family of DB protocols are those based on graphs, which were introduced in 2010 to resist both mafia and distance frauds. The security analysis in terms of distance fraud is performed by considering an adversary that, given a vertex labeled graph $G = (V, E)$ and a vertex $v \in V$, is able to find the most frequent $n$-long sequence in $G$ starting from $v$ (MFS problem). However, to the best of our knowledge, it is still an open question whether the distance fraud security can be computed considering the aforementioned adversarial model. Our first contribution is a proof that the MFS problem is NP-Hard even when the graph is constrained to meet the requirements of a graph-based DB protocol. Although this result does not invalidate the model, it does suggest that a \emph{too-strong} adversary is perhaps being considered (i.e., in practice, graph-based DB protocols might resist distance fraud better than the security model suggests.) Our second contribution is an algorithm addressing the distance fraud security of the tree-based approach due to Avoine and Tchamkerten. The novel algorithm improves the computational complexity $O(2^{2^n+n})$ of the naive approach to $O(2^{2n}n)$ where $n$ is the number of rounds.