OpenRaiser/Intern-Atlas huggingface dataset:
The Dynamics of Triads in Aggregated Journal-Journal Citation Relations: Specialty Developments at the Above-Journal Level
Venue: arXiv cs.DL 2015
Year: 2015

Dyads of journals related by citations can agglomerate into specialties through the mechanism of triadic closure. Using the Journal Citation Reports 2011, 2012, and 2013, we analyze triad formation as indicators of integration (specialty growth) and disintegration (restructuring). The strongest integration is found among the large journals that report on studies in different scientific specialties, such as PLoS ONE, Nature Communications, Nature, and Science. This tendency towards large-scale integration has not yet stabilized. Using the Islands algorithm, we also distinguish 51 local maxima of integration. We zoom into the cited articles that carry the integration for: (i) a new development within high-energy physics and (ii) an emerging interface between the journals Applied Mathematical Modeling and the International Journal of Advanced Manufacturing Technology. In the first case, integration is brought about by a specific communication reaching across specialty boundaries, whereas in the second, the dyad of journals indicates an emerging interface between specialties. These results suggest that integration picks up substantive developments at the specialty level. An advantage of the bottom-up method is that no ex ante classification of journals is assumed in the dynamic analysis.
Super-Resolution of Mutually Interfering Signals
Venue: arXiv cs.IT 2015
Year: 2015

We consider simultaneously identifying the membership and locations of point sources that are convolved with different low-pass point spread functions, from the observation of their superpositions. This problem arises in three-dimensional super-resolution single-molecule imaging, neural spike sorting, multi-user channel identification, among others. We propose a novel algorithm, based on convex programming, and establish its near-optimal performance guarantee for exact recovery by exploiting the sparsity of the point source model as well as incoherence between the point spread functions. Numerical examples are provided to demonstrate the effectiveness of the proposed approach.
svcR: An R Package for Support Vector Clustering improved with Geometric Hashing applied to Lexical Pattern Discovery
Venue: arXiv cs.LG 2015
Year: 2015

We present a new R package which takes a numerical matrix format as data input, and computes clusters using a support vector clustering method (SVC). We have implemented an original 2D-grid labeling approach to speed up cluster extraction. In this sense, SVC can be seen as an efficient cluster extraction if clusters are separable in a 2-D map. Secondly we showed that this SVC approach using a Jaccard-Radial base kernel can help to classify well enough a set of terms into ontological classes and help to define regular expression rules for information extraction in documents; our case study concerns a set of terms and documents about developmental and molecular biology.
Sparse Radial Sampling LBP for Writer Identification
Venue: arXiv cs.CV 2015
Year: 2015

In this paper we present the use of Sparse Radial Sampling Local Binary Patterns, a variant of Local Binary Patterns (LBP) for text-as-texture classification. By adapting and extending the standard LBP operator to the particularities of text we get a generic text-as-texture classification scheme and apply it to writer identification. In experiments on CVL and ICDAR 2013 datasets, the proposed feature-set demonstrates State-Of-the-Art (SOA) performance. Among the SOA, the proposed method is the only one that is based on dense extraction of a single local feature descriptor. This makes it fast and applicable at the earliest stages in a DIA pipeline without the need for segmentation, binarization, or extraction of multiple features.
A New Thesis concerning Synchronised Parallel Computing - Simplified Parallel ASM Thesis
Venue: arXiv cs.LO 2015
Year: 2015

A behavioural theory consists of machine-independent postulates characterizing a particular class of algorithms or systems, an abstract machine model that provably satisfies these postulates, and a rigorous proof that any algorithm or system stipulated by the postulates is captured by the abstract machine model. The class of interest in this article is that of synchronous parallel algorithms. For this class a behavioural theory has already been developed by Blass and Gurevich, which unfortunately, though mathematically correct, fails to be convincing, as it is not intuitively clear that the postulates really capture the essence of (synchronous) parallel algorithms. In this article we present a much simpler (and presumably more convincing) set of four postulates for (synchronous) parallel algorithms, which are rather close to those used in Gurevich's celebrated sequential ASM thesis, i.e. the behavioural theory of sequential algorithms. The key difference is made by an extension of the bounded exploration postulate using multiset comprehension terms instead of ground terms formulated over the signature of the states. In addition, all implicit assumptions are made explicit, which amounts to considering states of a parallel algorithm to be represented by meta-finite first-order structures. The article first provides the necessary evidence that the axiomatization presented in this article characterizes indeed the whole class of deterministic, synchronous, parallel algorithms, then formally proves that parallel algorithms are captured by Abstract State Machines (ASMs). The proof requires some recourse to methods from finite model theory, by means of which it can be shown that if a critical tuple defines an update in some update set, then also every other tuple that is logically indistinguishable defines an update in that update set.
Dictionary matching in a stream
Venue: arXiv cs.DS 2015
Year: 2015

We consider the problem of dictionary matching in a stream. Given a set of strings, known as a dictionary, and a stream of characters arriving one at a time, the task is to report each time some string in our dictionary occurs in the stream. We present a randomised algorithm which takes O(log log(k + m)) time per arriving character and uses O(k log m) words of space, where k is the number of strings in the dictionary and m is the length of the longest string in the dictionary.
40 Gbps Access for Metro networks: Implications in terms of Sustainability and Innovation from an LCA Perspective
Venue: arXiv cs.CY 2015
Year: 2015

In this work, the implications of new technologies, more specifically the new optical FTTH technologies, are studied both from the functional and non-functional perspectives. In particular, some direct impacts are listed in the form of abandoning non-functional technologies, such as micro-registration, which would be implicitly required for having a functioning operation before arrival the new high-bandwidth access technologies. It is shown that such abandonment of non-functional best practices, which are mainly at the management level of ICT, immediately results in additional consumption and environmental footprint, and also there is a chance that some other new innovations might be 'missed.' Therefore, unconstrained deployment of these access technologies is not aligned with a possible sustainable ICT picture, except if they are regulated. An approach to pricing the best practices, including both functional and non-functional technologies, is proposed in order to develop a regulation and policy framework for a sustainable broadband access.
Evolving Fuzzy Image Segmentation with Self-Configuration
Venue: arXiv cs.CV 2015
Year: 2015

Current image segmentation techniques usually require that the user tune several parameters in order to obtain maximum segmentation accuracy, a computationally inefficient approach, especially when a large number of images must be processed sequentially in daily practice. The use of evolving fuzzy systems for designing a method that automatically adjusts parameters to segment medical images according to the quality expectation of expert users has been proposed recently (Evolving fuzzy image segmentation EFIS). However, EFIS suffers from a few limitations when used in practice mainly due to some fixed parameters. For instance, EFIS depends on auto-detection of the object of interest for feature calculation, a task that is highly application-dependent. This shortcoming limits the applicability of EFIS, which was proposed with the ultimate goal of offering a generic but adjustable segmentation scheme. In this paper, a new version of EFIS is proposed to overcome these limitations. The new EFIS, called self-configuring EFIS (SC-EFIS), uses available training data to self-estimate the parameters that are fixed in EFIS. As well, the proposed SC-EFIS relies on a feature selection process that does not require auto-detection of an ROI. The proposed SC-EFIS was evaluated using the same segmentation algorithms and the same dataset as for EFIS. The results show that SC-EFIS can provide the same results as EFIS but with a higher level of automation.
Realization independent single time-delay dynamical model interpolation and $\mathcal{H}_2$-optimal approximation
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, the realization-free model approximation problem, as stated in \cite{mayo2007framework,beattie2012realization}, is revisited in the case where the interpolating model might be time-delay dependent. To this aim, the Loewner framework, initially settled for delay-free realization, is firstly generalized to the single delay case. Secondly, the (infinite) model approximation $\mathcal{H}_2$ optimality conditions are established through the use of the Lambert functions. Finally, a numerically effective iterative scheme, named \textbf{dTF-IRKA}, similar to the \textbf{TF-IRKA} \cite{beattie2012realization}, is proposed to reach a part of the aforementioned optimality conditions. The proposed method validity and interest are assessed on different numerical examples.
Run Generation Revisited: What Goes Up May or May Not Come Down
Venue: arXiv cs.DS 2015
Year: 2015

In this paper, we revisit the classic problem of run generation. Run generation is the first phase of external-memory sorting, where the objective is to scan through the data, reorder elements using a small buffer of size M , and output runs (contiguously sorted chunks of elements) that are as long as possible. We develop algorithms for minimizing the total number of runs (or equivalently, maximizing the average run length) when the runs are allowed to be sorted or reverse sorted. We study the problem in the online setting, both with and without resource augmentation, and in the offline setting. (1) We analyze alternating-up-down replacement selection (runs alternate between sorted and reverse sorted), which was studied by Knuth as far back as 1963. We show that this simple policy is asymptotically optimal. Specifically, we show that alternating-up-down replacement selection is 2-competitive and no deterministic online algorithm can perform better. (2) We give online algorithms having smaller competitive ratios with resource augmentation. Specifically, we exhibit a deterministic algorithm that, when given a buffer of size 4M , is able to match or beat any optimal algorithm having a buffer of size M . Furthermore, we present a randomized online algorithm which is 7/4-competitive when given a buffer twice that of the optimal. (3) We demonstrate that performance can also be improved with a small amount of foresight. We give an algorithm, which is 3/2-competitive, with foreknowledge of the next 3M elements of the input stream. For the extreme case where all future elements are known, we design a PTAS for computing the optimal strategy a run generation algorithm must follow. (4) Finally, we present algorithms tailored for nearly sorted inputs which are guaranteed to have optimal solutions with sufficiently long runs.
Local Variation as a Statistical Hypothesis Test
Venue: arXiv cs.CV 2015
Year: 2015

The goal of image oversegmentation is to divide an image into several pieces, each of which should ideally be part of an object. One of the simplest and yet most effective oversegmentation algorithms is known as local variation (LV) (Felzenszwalb and Huttenlocher 2004). In this work, we study this algorithm and show that algorithms similar to LV can be devised by applying different statistical models and decisions, thus providing further theoretical justification and a well-founded explanation for the unexpected high performance of the LV approach. Some of these algorithms are based on statistics of natural images and on a hypothesis testing decision; we denote these algorithms probabilistic local variation (pLV). The best pLV algorithm, which relies on censored estimation, presents state-of-the-art results while keeping the same computational complexity of the LV algorithm.
Object Level Deep Feature Pooling for Compact Image Representation
Venue: arXiv cs.CV 2015
Year: 2015

Convolutional Neural Network (CNN) features have been successfully employed in recent works as an image descriptor for various vision tasks. But the inability of the deep CNN features to exhibit invariance to geometric transformations and object compositions poses a great challenge for image search. In this work, we demonstrate the effectiveness of the objectness prior over the deep CNN features of image regions for obtaining an invariant image representation. The proposed approach represents the image as a vector of pooled CNN features describing the underlying objects. This representation provides robustness to spatial layout of the objects in the scene and achieves invariance to general geometric transformations, such as translation, rotation and scaling. The proposed approach also leads to a compact representation of the scene, making each image occupy a smaller memory footprint. Experiments show that the proposed representation achieves state of the art retrieval results on a set of challenging benchmark image datasets, while maintaining a compact representation.
Digital Backpropagation in the Nonlinear Fourier Domain
Venue: arXiv cs.IT 2015
Year: 2015

Nonlinear and dispersive transmission impairments in coherent fiber-optic communication systems are often compensated by reverting the nonlinear Schrödinger equation, which describes the evolution of the signal in the link, numerically. This technique is known as digital backpropagation. Typical digital backpropagation algorithms are based on split-step Fourier methods in which the signal has to be discretized in time and space. The need to discretize in both time and space however makes the real-time implementation of digital backpropagation a challenging problem. In this paper, a new fast algorithm for digital backpropagation based on nonlinear Fourier transforms is presented. Aiming at a proof of concept, the main emphasis will be put on fibers with normal dispersion in order to avoid the issue of solitonic components in the signal. However, it is demonstrated that the algorithm also works for anomalous dispersion if the signal power is low enough. Since the spatial evolution of a signal governed by the nonlinear Schrödinger equation can be reverted analytically in the nonlinear Fourier domain through simple phase-shifts, there is no need to discretize the spatial domain. The proposed algorithm requires only $\mathcal{O}(D\log^{2}D)$ floating point operations to backpropagate a signal given by $D$ samples, independently of the fiber's length, and is therefore highly promising for real-time implementations. The merits of this new approach are illustrated through numerical simulations.
A Scheduling Model of Battery-powered Embedded System
Venue: arXiv cs.SY 2015
Year: 2015

Fundamental theory on battery-powered cyber-physical systems (CPS) calls for dynamic models that are able to describe and predict the status of processors and batteries at any given time. We believe that the idealized system of single processor powered by single battery (SPSB) can be viewed as a generic case for the modeling effort. This paper introduces a dynamic model for multiple aperiodic tasks on a SPSB system under a scheduling algorithm that resembles the rate monotonic scheduling (RMS) within finite time windows. The model contains two major modules. The first module is an online battery capacity model based on the Rakhmatov-Vrudhula-Wallach (RVW) model. This module provides predictions of remaining battery capacity based on the knowledge of the battery discharging current. The second module is a dynamical scheduling model that can predict the scheduled behavior of tasks within any finite time window, without the need to store all past information about each task before the starting time of the finite time window. The module provides a complete analytical description of the relationship among tasks and it delineates all possible modes of the processor utilization as square-wave functions of time. The two modules i.e. the scheduling model and the battery model are integrated to obtain a hybrid scheduling model that describes the dynamic behaviors of the SPSB system. Our effort may have demonstrated that through dynamic modeling, different components of CPS may be integrated under a unified theoretical framework centered around hybrid systems theory.
Fast and Rigorous DC Solution in Finite Element Method for Integrated Circuit Analysis
Venue: arXiv cs.CE 2015
Year: 2015

Large scale circuit simulation, such as power delivery network analysis, has become increasingly challenge in the VLSI design verification flow. Power delivery network can be simulated by both SPICE-type circuit-based model and eletromagnetics-based model when full-wave accuracy is desired. In the early time of the time domain finite element simulation for integrated circuit, the modes having the highest eigenvalues supported by the numerical system will be excited. Because of the band limited source, after the early time, the modes having a resonance frequency well beyond the input frequency band will die down, and all physically important high-order modes and DC mode will show up and become dominant. Among these modes, the DC mode is the last one to show up. Although the convergence criterion is not applied on the DC mode, the existence of DC mode in the field solution will deteriorate the convergence rate of the first several high order modes. Therefore, this paper first analyzed the mathematic characteristics of the DC mode and proposed a rigorous and fast solution to extract the DC mode from the numerical system in order to speed up the convergence rate. Experimental results demonstrated the robustness and superior performance of this method.
Improving software team collaboration with Synchronized Software Development
Venue: arXiv cs.SE 2015
Year: 2015

Effective collaboration is a key factor in the success of a software project developed by a team. In this work, we suggest the approach of Synchronized Software Development (SSD), which promotes a new mechanism of collaboration in general, and for code synchronization in particular. In SSD, code changes made by one developer are automatically propagated to others as long as they keep the code free of compilation errors. Changes that introduce compilation errors are not propagated until the errors are fixed. Moreover, other developers are restricted from concurrently editing the entities involved in these changes. While in this state, developers are, however, free to modify the rest of the entities. The novelty of our approach is that it actively synchronizes developers with the latest error free version of the source code, preventing possible conflicts and merges that may arise due to concurrent changes made by fellow team members. SSD also allows for a more transparent an practically near real time awareness of new code that is being introduced by multiple developers. We built CSI (Code Synchronizing Intelligence), a prototype demonstrating key features of SSD.
TurkerGaze: Crowdsourcing Saliency with Webcam based Eye Tracking
Venue: arXiv cs.CV 2015
Year: 2015

Traditional eye tracking requires specialized hardware, which means collecting gaze data from many observers is expensive, tedious and slow. Therefore, existing saliency prediction datasets are order-of-magnitudes smaller than typical datasets for other vision recognition tasks. The small size of these datasets limits the potential for training data intensive algorithms, and causes overfitting in benchmark evaluation. To address this deficiency, this paper introduces a webcam-based gaze tracking system that supports large-scale, crowdsourced eye tracking deployed on Amazon Mechanical Turk (AMTurk). By a combination of careful algorithm and gaming protocol design, our system obtains eye tracking data for saliency prediction comparable to data gathered in a traditional lab setting, with relatively lower cost and less effort on the part of the researchers. Using this tool, we build a saliency dataset for a large number of natural images. We will open-source our tool and provide a web server where researchers can upload their images to get eye tracking results from AMTurk.
An Approximately Optimal Algorithm for Scheduling Phasor Data Transmissions in Smart Grid Networks
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we devise a scheduling algorithm for ordering transmission of synchrophasor data from the substation to the control center in as short a time frame as possible, within the realtime hierarchical communications infrastructure in the electric grid. The problem is cast in the framework of the classic job scheduling with precedence constraints. The optimization setup comprises the number of phasor measurement units (PMUs) to be installed on the grid, a weight associated with each PMU, processing time at the control center for the PMUs, and precedence constraints between the PMUs. The solution to the PMU placement problem yields the optimum number of PMUs to be installed on the grid, while the processing times are picked uniformly at random from a predefined set. The weight associated with each PMU and the precedence constraints are both assumed known. The scheduling problem is provably NP-hard, so we resort to approximation algorithms which provide solutions that are suboptimal yet possessing polynomial time complexity. A lower bound on the optimal schedule is derived using branch and bound techniques, and its performance evaluated using standard IEEE test bus systems. The scheduling policy is power grid-centric, since it takes into account the electrical properties of the network under consideration.
Overhead-Aware Distributed CSI Selection in the MIMO Interference Channel
Venue: arXiv cs.IT 2015
Year: 2015

We consider a MIMO interference channel in which the transmitters and receivers operate in frequency-division duplex mode. In this setting, interference management through coordinated transceiver design necessitates channel state information at the transmitters (CSI-T). The acquisition of CSI-T is done through feedback from the receivers, which entitles a loss in degrees of freedom, due to training and feedback. This loss increases with the amount of CSI-T. In this work, after formulating an overhead model for CSI acquisition at the transmitters, we propose a distributed mechanism to find for each transmitter a subset of the complete CSI, which is used to perform interference management. The mechanism is based on many-to-many stable matching. We prove the existence of a stable matching and exploit an algorithm to reach it. Simulation results show performance improvement compared to full and minimal CSI-T.