OpenRaiser/Intern-Atlas huggingface dataset:
The misleading narrative of the canonical faculty productivity trajectory
Venue: arXiv cs.DL 2017
Year: 2017

A scientist may publish tens or hundreds of papers over a career, but these contributions are not evenly spaced in time. Sixty years of studies on career productivity patterns in a variety of fields suggest an intuitive and universal pattern: productivity tends to rise rapidly to an early peak and then gradually declines. Here, we test the universality of this conventional narrative by analyzing the structures of individual faculty productivity time series, constructed from over 200,000 publications and matched with hiring data for 2453 tenure-track faculty in all 205 Ph.D-granting computer science departments in the U.S. and Canada. Unlike prior studies, which considered only some faculty or some institutions, or lacked common career reference points, here we combine a large bibliographic dataset with comprehensive information on career transitions that covers an entire field of study. We show that the conventional narrative confidently describes only one fifth of faculty, regardless of department prestige or researcher gender, and the remaining four fifths of faculty exhibit a rich diversity of productivity patterns. To explain this diversity, we introduce a simple model of productivity trajectories, and explore correlations between its parameters and researcher covariates, showing that departmental prestige predicts overall individual productivity and the timing of the transition from first- to last-author publications. These results demonstrate the unpredictability of productivity over time, and open the door for new efforts to understand how environmental and individual factors shape scientific productivity.
Neutron induced strike: On the likelihood of multiple bit-flips in logic circuits
Venue: arXiv cs.AR 2017
Year: 2017

High energy particles from cosmic rays or packaging materials can generate a glitch or a current transient (single event transient or SET) in a logic circuit. This SET can eventually get captured in a register resulting in a flip of the register content, which is known as soft error or single-event upset (SEU). A soft error is typically modeled as a probabilistic single bit-flip model. In developing such abstract fault models, an important issue to consider is the likelihood of multiple bit errors caused by particle strikes. The fact that an SET causes multiple flips is noted in the literature. We perform a characterization study of the impact of an SET on a logic circuit to quantify the extent to which an SET can cause multiple bit flips. We use post-layout circuit simulations and Monte Carlo sampling scheme to get accurate bit-flip statistics. We perform our simulations on ISCAS'85, ISCAS'89 and ITC'99 benchmarks in 180nm and 65nm technologies. We find that a substantial fraction of SEU outcomes had multiple register flips. We futher analyse the individual contributions of the strike on a register and the strike on a logic gate, to multiple flips. We find that, amongst the erroneous outcomes, the probability of multiple bit-flips for 'gate-strike' cases was substantial and went up to 50%, where as those for 'register-strike' cases was just about 2%. This implies that, in principle, we can eliminate the flips due to register strikes using hardened flip-flop designs. However, in such designs, out of the remaining flips which will be due to gate strikes, a large fraction is likely to be multiple flips.
Network Slicing Games: Enabling Customization in Multi-Tenant Networks
Venue: arXiv cs.GT 2017
Year: 2017

Network slicing to enable resource sharing among multiple tenants --network operators and/or services-- is considered a key functionality for next generation mobile networks. This paper provides an analysis of a well-known model for resource sharing, the 'share-constrained proportional allocation' mechanism, to realize network slicing. This mechanism enables tenants to reap the performance benefits of sharing, while retaining the ability to customize their own users' allocation. This results in a network slicing game in which each tenant reacts to the user allocations of the other tenants so as to maximize its own utility. We show that, under appropriate conditions, the game associated with such strategic behavior converges to a Nash equilibrium. At the Nash equilibrium, a tenant always achieves the same, or better, performance than under a static partitioning of resources, hence providing the same level of protection as such static partitioning. We further analyze the efficiency and fairness of the resulting allocations, providing tight bounds for the price of anarchy and envy-freeness. Our analysis and extensive simulation results confirm that the mechanism provides a comprehensive practical solution to realize network slicing. Our theoretical results also fill a gap in the literature regarding the analysis of this resource allocation model under strategic players.
Quantum Optimal Transport for Tensor Field Processing
Venue: arXiv cs.GR 2017
Year: 2017

This article introduces a new notion of optimal transport (OT) between tensor fields, which are measures whose values are positive semidefinite (PSD) matrices. This "quantum" formulation of OT (Q-OT) corresponds to a relaxed version of the classical Kantorovich transport problem, where the fidelity between the input PSD-valued measures is captured using the geometry of the Von-Neumann quantum entropy. We propose a quantum-entropic regularization of the resulting convex optimization problem, which can be solved efficiently using an iterative scaling algorithm. This method is a generalization of the celebrated Sinkhorn algorithm to the quantum setting of PSD matrices. We extend this formulation and the quantum Sinkhorn algorithm to compute barycenters within a collection of input tensor fields. We illustrate the usefulness of the proposed approach on applications to procedural noise generation, anisotropic meshing, diffusion tensor imaging and spectral texture synthesis.
Automated timetabling for small colleges and high schools using huge integer programs
Venue: arXiv cs.AI 2017
Year: 2017

We formulate an integer program to solve a highly constrained academic timetabling problem at the United States Merchant Marine Academy. The IP instance that results from our real case study has approximately both 170,000 rows and columns and solves to optimality in 4--24 hours using a commercial solver on a portable computer (near optimal feasible solutions were often found in 4--12 hours). Our model is applicable to both high schools and small colleges who wish to deviate from group scheduling. We also solve a necessary preprocessing student subgrouping problem, which breaks up big groups of students into small groups so they can optimally fit into small capacity classes.
Community-based Outlier Detection for Edge-attributed Graphs
Venue: arXiv cs.SI 2017
Year: 2017

The study of networks has emerged in diverse disciplines as a means of analyzing complex relationship data. Beyond graph analysis tasks like graph query processing, link analysis, influence propagation, there has recently been some work in the area of outlier detection for information network data. Although various kinds of outliers have been studied for graph data, there is not much work on anomaly detection from edge-attributed graphs. In this paper, we introduce a method that detects novel outlier graph nodes by taking into account the node data and edge data simultaneously to detect anomalies. We model the problem as a community detection task, where outliers form a separate community. We propose a method that uses a probabilistic graph model (Hidden Markov Random Field) for joint modeling of nodes and edges in the network to compute Holistic Community Outliers (HCOutliers). Thus, our model presents a natural setting for heterogeneous graphs that have multiple edges/relationships between two nodes. EM (Expectation Maximization) is used to learn model parameters, and infer hidden community labels. Experimental results on synthetic datasets and the DBLP dataset show the effectiveness of our approach for finding novel outliers from networks.
Feedback Networks
Venue: arXiv cs.CV 2017
Year: 2017

Currently, the most successful learning models in computer vision are based on learning successive representations followed by a decision layer. This is usually actualized through feedforward multilayer neural networks, e.g. ConvNets, where each layer forms one of such successive representations. However, an alternative that can achieve the same goal is a feedback based approach in which the representation is formed in an iterative manner based on a feedback received from previous iteration's output. We establish that a feedback based approach has several fundamental advantages over feedforward: it enables making early predictions at the query time, its output naturally conforms to a hierarchical structure in the label space (e.g. a taxonomy), and it provides a new basis for Curriculum Learning. We observe that feedback networks develop a considerably different representation compared to feedforward counterparts, in line with the aforementioned advantages. We put forth a general feedback based learning architecture with the endpoint results on par or better than existing feedforward networks with the addition of the above advantages. We also investigate several mechanisms in feedback architectures (e.g. skip connections in time) and design choices (e.g. feedback length). We hope this study offers new perspectives in quest for more natural and practical learning models.
A Unified Tensor-based Active Appearance Face Model
Venue: arXiv cs.CV 2017
Year: 2017

Appearance variations result in many difficulties in face image analysis. To deal with this challenge, we present a Unified Tensor-based Active Appearance Model (UT-AAM) for jointly modelling the geometry and texture information of 2D faces. For each type of face information, namely shape and texture, we construct a unified tensor model capturing all relevant appearance variations. This contrasts with the variation-specific models of the classical tensor AAM. To achieve the unification across pose variations, a strategy for dealing with self-occluded faces is proposed to obtain consistent shape and texture representations of pose-varied faces. In addition, our UT-AAM is capable of constructing the model from an incomplete training dataset, using tensor completion methods. Last, we use an effective cascaded-regression-based method for UT-AAM fitting. With these advancements, the utility of UT-AAM in practice is considerably enhanced. As an example, we demonstrate the improvements in training facial landmark detectors through the use of UT-AAM to synthesise a large number of virtual samples. Experimental results obtained using the Multi-PIE and 300-W face datasets demonstrate the merits of the proposed approach.
Fast counting of medium-sized rooted subgraphs
Venue: arXiv cs.DM 2017
Year: 2017

We prove that counting copies of any graph $F$ in another graph $G$ can be achieved using basic matrix operations on the adjacency matrix of $G$. Moreover, the resulting algorithm is competitive for medium-sized $F$: our algorithm recovers the best known complexity for rooted 6-clique counting and improves on the best known for 9-cycle counting. Underpinning our proofs is the new result that, for a general class of graph operators, matrix operations are homomorphisms for operations on rooted graphs.
A scalable approach for tree segmentation within small-footprint airborne LiDAR data
Venue: arXiv cs.DC 2017
Year: 2017

This paper presents a distributed approach that scales up to segment tree crowns within a LiDAR point cloud representing an arbitrarily large forested area. The approach uses a single-processor tree segmentation algorithm as a building block in order to process the data delivered in the shape of tiles in parallel. The distributed processing is performed in a master-slave manner, in which the master maintains the global map of the tiles and coordinates the slaves that segment tree crowns within and across the boundaries of the tiles. A minimal bias was introduced to the number of detected trees because of trees lying across the tile boundaries, which was quantified and adjusted for. Theoretical and experimental analyses of the runtime of the approach revealed a near linear speedup. The estimated number of trees categorized by crown class and the associated error margins as well as the height distribution of the detected trees aligned well with field estimations, verifying that the distributed approach works correctly. The approach enables providing information of individual tree locations and point cloud segments for a forest-level area in a timely manner, which can be used to create detailed remotely sensed forest inventories. Although the approach was presented for tree segmentation within LiDAR point clouds, the idea can also be generalized to scale up processing other big spatial datasets. Highlights: - A scalable distributed approach for tree segmentation was developed and theoretically analyzed. - ~2 million trees in a 7440 ha forest was segmented in 2.5 hours using 192 cores. - 2% false positive trees were identified as a result of the distributed run. - The approach can be used to scale up processing other big spatial data
Construction and Encoding of QC-LDPC Codes Using Group Rings
Venue: arXiv cs.IT 2017
Year: 2017

Quasi-cyclic (QC) low-density parity-check (LDPC) codes which are known as QC-LDPC codes, have many applications due to their simple encoding implementation by means of cyclic shift registers. In this paper, we construct QC-LDPC codes from group rings. A group ring is a free module (at the same time a ring) constructed in a natural way from any given ring and any given group. We present a structure based on the elements of a group ring for constructing QC-LDPC codes. Some of the previously addressed methods for constructing QC-LDPC codes based on finite fields are special cases of the proposed construction method. The constructed QC-LDPC codes perform very well over the additive white Gaussian noise (AWGN) channel with iterative decoding in terms of bit-error probability and block-error probability. Simulation results demonstrate that the proposed codes have competitive performance in comparison with the similar existing LDPC codes. Finally, we propose a new encoding method for the proposed group ring based QC-LDPC codes that can be implemented faster than the current encoding methods. The encoding complexity of the proposed method is analyzed mathematically, and indicates a significate reduction in the required number of operations, even when compared to the available efficient encoding methods that have linear time and space complexities.
Some Repeated-Root Constacyclic Codes over Galois Rings
Venue: arXiv cs.IT 2017
Year: 2017

Codes over Galois rings have been studied extensively during the last three decades. Negacyclic codes over $GR(2^a,m)$ of length $2^s$ have been characterized: the ring $\mathcal{R}_2(a,m,-1)= \frac{GR(2^a,m)[x]}{\langle x^{2^s}+1\rangle}$ is a chain ring. Furthermore, these results have been generalized to $λ$-constacyclic codes for any unit $λ$ of the form $4z-1$, $z\in GR(2^a, m)$. In this paper, we study more general cases and investigate all cases where $\mathcal{R}_p(a,m,γ)= \frac{GR(p^a,m)[x]}{\langle x^{p^s}-γ\rangle}$ is a chain ring. In particular, necessary and sufficient conditions for the ring $\mathcal{R}_p(a,m,γ)$ to be a chain ring are obtained. In addition, by using this structure we investigate all $γ$-constacyclic codes over $GR(p^a,m)$ when $\mathcal{R}_p(a,m,γ)$ is a chain ring. Necessary and sufficient conditions for the existence of self-orthogonal and self-dual $γ$-constacyclic codes are also provided. Among others, for any prime $p$, the structure of $\mathcal{R}_p(a,m,γ)=\frac{GR(p^a,m)[x]}{\langle x^{p^s}-γ\rangle}$ is used to establish the Hamming and homogeneous distances of $γ$-constacyclic codes.
Stochastic Geometry-based Comparison of Secrecy Enhancement Techniques in D2D Networks
Venue: arXiv cs.IT 2017
Year: 2017

This letter presents a performance comparison of two popular secrecy enhancement techniques in wireless networks: (i) creating guard zones by restricting transmissions of legitimate transmitters whenever any eavesdropper is detected in their vicinity, and (ii) adding artificial noise to the confidential messages to make it difficult for the eavesdroppers to decode them. Focusing on a noise-limited regime, we use tools from stochastic geometry to derive the secrecy outage probability at the eavesdroppers as well as the coverage probability at the legitimate users for both these techniques. Using these results, we derive a threshold on the density of the eavesdroppers below which no secrecy enhancing technique is required to ensure a target secrecy outage probability. For eavesdropper densities above this threshold, we concretely characterize the regimes in which each technique outperforms the other. Our results demonstrate that guard zone technique is better when the distances between the transmitters and their legitimate receivers are higher than a certain threshold.
(Quasi-)linear time algorithm to compute LexDFS, LexUP and LexDown orderings
Venue: arXiv cs.DS 2017
Year: 2017

We consider the three graph search algorithm LexDFS, LexUP and LexDOWN. We show that LexUP orderings can be computed in linear time by an algorithm similar to the one which compute LexBFS. Furthermore, LexDOWN orderings and LexDFS orderings can be computed in time $\left(n+m\log m\right)$ where $n$ is the number of vertices and $m$ the number of edges.
A modeling and simulation language for biological cells with coupled mechanical and chemical processes
Venue: arXiv cs.CE 2017
Year: 2017

Biological cells are the prototypical example of active matter. Cells sense and respond to mechanical, chemical and electrical environmental stimuli with a range of behaviors, including dynamic changes in morphology and mechanical properties, chemical uptake and secretion, cell differentiation, proliferation, death, or migration. Modeling and simulation of such dynamic phenomena poses a number of computational challenges. A modeling language to describe cellular dynamics must be able to naturally represent complex intra and extra-cellular spatial structures, and coupled mechanical, chemical and electrical processes. In order to be useful to domain experts, a modeling language should be based on concepts, terms and principles native to the problem domain. A compiler must then be able to generate an executable model from this physically motivated description. Finally, an executable model must efficiently calculate the time evolution of such dynamic and inhomogeneous phenomena. We present a spatial hybrid systems modeling language, compiler and mesh-free Lagrangian based simulation engine which will enable domain experts to define models using natural, biologically motivated constructs and to simulate time evolution of coupled cellular, mechanical and chemical processes acting on a time varying number of cells and their environment.
A generalized power iteration method for solving quadratic problem on the Stiefel manifold
Venue: arXiv cs.DS 2017
Year: 2017

In this paper, we first propose a novel generalized power iteration method (GPI) to solve the quadratic problem on the Stiefel manifold (QPSM) as min_{W^TW=I}Tr(W^TAW-2W^TB) along with the theoretical analysis. Accordingly, its special case known as the orthogonal least square regression (OLSR) is under further investigation. Based on the aforementioned studies, we then cast major focus on solving the unbalanced orthogonal procrustes problem (UOPP). As a result, not only a general convergent algorithm is derived theoretically but the efficiency of the proposed approach is verified empirically as well.
Evaluating the Dynamic Behavior of Database Applications
Venue: arXiv cs.DB 2017
Year: 2017

This paper explores the effect that changing access patterns has on the performance of database management systems. Changes in access patterns play an important role in determining the efficiency of key performance optimization techniques, such as dynamic clustering, prefetching, and buffer replacement. However, all existing benchmarks or evaluation frameworks produce static access patterns in which objects are always accessed in the same order repeatedly. Hence, we have proposed the Dynamic Evaluation Framework (DEF) that simulates access pattern changes using configurable styles of change. DEF has been designed to be open and fully extensible (e.g., new access pattern change models can be added easily). In this paper, we instantiate DEF into the Dynamic object Evaluation Framework (DoEF) which is designed for object databases, i.e., object-oriented or object-relational databases such as multi-media databases or most XML databases.The capabilities of DoEF have been evaluated by simulating the execution of four different dynamic clustering algorithms. The results confirm our analysis that flexible conservative re-clustering is the key in determining a clustering algorithm's ability to adapt to changes in access pattern. These results show the effectiveness of DoEF at determining the adaptability of each dynamic clustering algorithm to changes in access pattern in a simulation environment. In a second set of experiments, we have used DoEF to compare the performance of two real-life object stores : Platypus and SHORE. DoEF has helped to reveal the poor swapping performance of Platypus.
Study and Development of a Symmetric protocol to secure communications in WSN
Venue: arXiv cs.CR 2017
Year: 2017

Wireless Sensor Network (WSN) is consisting of independent and distributed sensors to monitor physical or environmental conditions, such as temperature, sound, pressure, etc. The most crucial and fundamental challenge facing WSN is security. Due to minimum capacity in-term of memory cost, processing and physical accessibility to sensors devices the security attacks are problematic. They are mostly deployed in open area, which expose them to different kinds of attacks. In this paper, we present an illustration of different attacks and vulnerabilities in WSN. Then we proposed a new lightweight cryptography algorithm for identifying compromised node in WSN called Leap Enhanced. Our evaluations on TOSSIM give a precise and detailed idea of the extra cost of consumption of resources needed to ensure the high level of expected security compared to other cryptography schemes in literature.
A Computational Approach to Finding RNA Tertiary Motifs in Genomic Sequences
Venue: arXiv cs.CE 2017
Year: 2017

Motif finding in DNA, RNA and proteins plays an important role in life science research. Recent patents concerning motif finding in the biomolecular data are recorded in the DNA Patent Database which serves as a resource for policy makers and members of the general public interested in fields like genomics, genetics and biotechnology. In this paper we present a computational approach to mining for RNA tertiary motifs in genomic sequences. Specifically we describe a method, named CSminer, for finding RNA coaxial helical stackings in genomes. A coaxial helical stacking occurs in an RNA tertiary structure where two separate helical elements form a pseudocontiguous helix and provides thermodynamic stability to the molecule as a whole. Experimental results demonstrate the effectiveness of our approach.