OpenRaiser/Intern-Atlas huggingface dataset:
An Efficient Data Structure for Dynamic Two-Dimensional Reconfiguration
Venue: arXiv cs.DS 2017
Year: 2017

In the presence of dynamic insertions and deletions into a partially reconfigurable FPGA, fragmentation is unavoidable. This poses the challenge of developing efficient approaches to dynamic defragmentation and reallocation. One key aspect is to develop efficient algorithms and data structures that exploit the two-dimensional geometry of a chip, instead of just one. We propose a new method for this task, based on the fractal structure of a quadtree, which allows dynamic segmentation of the chip area, along with dynamically adjusting the necessary communication infrastructure. We describe a number of algorithmic aspects, and present different solutions. We also provide a number of basic simulations that indicate that the theoretical worst-case bound may be pessimistic.
Multichannel Linear Prediction for Blind Reverberant Audio Source Separation
Venue: arXiv cs.SD 2017
Year: 2017

A class of methods based on multichannel linear prediction (MCLP) can achieve effective blind dereverberation of a source, when the source is observed with a microphone array. We propose an inventive use of MCLP as a pre-processing step for blind source separation with a microphone array. We show theoretically that, under certain assumptions, such pre-processing reduces the original blind reverberant source separation problem to a non-reverberant one, which in turn can be effectively tackled using existing methods. We demonstrate our claims using real recordings obtained with an eight-microphone circular array in reverberant environments.
Video and Accelerometer-Based Motion Analysis for Automated Surgical Skills Assessment
Venue: arXiv cs.CV 2017
Year: 2017

Purpose: Basic surgical skills of suturing and knot tying are an essential part of medical training. Having an automated system for surgical skills assessment could help save experts time and improve training efficiency. There have been some recent attempts at automated surgical skills assessment using either video analysis or acceleration data. In this paper, we present a novel approach for automated assessment of OSATS based surgical skills and provide an analysis of different features on multi-modal data (video and accelerometer data). Methods: We conduct the largest study, to the best of our knowledge, for basic surgical skills assessment on a dataset that contained video and accelerometer data for suturing and knot-tying tasks. We introduce "entropy based" features - Approximate Entropy (ApEn) and Cross-Approximate Entropy (XApEn), which quantify the amount of predictability and regularity of fluctuations in time-series data. The proposed features are compared to existing methods of Sequential Motion Texture (SMT), Discrete Cosine Transform (DCT) and Discrete Fourier Transform (DFT), for surgical skills assessment. Results: We report average performance of different features across all applicable OSATS criteria for suturing and knot tying tasks. Our analysis shows that the proposed entropy based features out-perform previous state-of-the-art methods using video data. For accelerometer data, our method performs better for suturing only. We also show that fusion of video and acceleration features can improve overall performance with the proposed entropy features achieving highest accuracy. Conclusions: Automated surgical skills assessment can be achieved with high accuracy using the proposed entropy features. Such a system can significantly improve the efficiency of surgical training in medical schools and teaching hospitals.
A Stochastic Operator Approach to Model Inadequacy with Applications to Contaminant Transport
Venue: arXiv cs.CE 2017
Year: 2017

The mathematical models used to represent physical phenomena are generally known to be imperfect representations of reality. Model inadequacies arise for numerous reasons, such as incomplete knowledge of the phenomena or computational intractability of more accurate models. In such situations it is impractical or impossible to improve the model, but necessity requires its use to make predictions. With this in mind, it is important to represent the uncertainty that a model's inadequacy causes in its predictions, as neglecting to do so can cause overconfidence in its accuracy. A powerful approach to addressing model inadequacy leverages the composite nature of physical models by enriching a flawed embedded closure model with a stochastic error representation. This work outlines steps in the development of a stochastic operator as an inadequacy representation by establishing the framework for inferring an infinite-dimensional operator and by introducing a novel method for interrogating available high-fidelity models to learn about modeling error.
Residual Convolutional CTC Networks for Automatic Speech Recognition
Venue: arXiv cs.CL 2017
Year: 2017

Deep learning approaches have been widely used in Automatic Speech Recognition (ASR) and they have achieved a significant accuracy improvement. Especially, Convolutional Neural Networks (CNNs) have been revisited in ASR recently. However, most CNNs used in existing work have less than 10 layers which may not be deep enough to capture all human speech signal information. In this paper, we propose a novel deep and wide CNN architecture denoted as RCNN-CTC, which has residual connections and Connectionist Temporal Classification (CTC) loss function. RCNN-CTC is an end-to-end system which can exploit temporal and spectral structures of speech signals simultaneously. Furthermore, we introduce a CTC-based system combination, which is different from the conventional frame-wise senone-based one. The basic subsystems adopted in the combination are different types and thus mutually complementary to each other. Experimental results show that our proposed single system RCNN-CTC can achieve the lowest word error rate (WER) on WSJ and Tencent Chat data sets, compared to several widely used neural network systems in ASR. In addition, the proposed system combination can offer a further error reduction on these two data sets, resulting in relative WER reductions of $14.91\%$ and $6.52\%$ on WSJ dev93 and Tencent Chat data sets respectively.
Revealing Task Driven Knowledge Worker Behaviors in Open Source Software Communities
Venue: arXiv cs.SE 2017
Year: 2017

Collaborative activities among knowledge workers such as software developers underlie the development of modern society, but the in-depth understanding of their behavioral patterns in open online communities is very challenging. The availability of large volumes of data in open-source software (OSS) repositories (e.g. bug tracking data, emails, and comments) enables us to investigate this issue in a quantitative way. In this paper, we conduct an empirical analysis of online collaborative activities closely related to assure software quality in two well-known OSS communities, namely Eclipse and Mozilla. Our main findings include two aspects: (1) developers exhibit two diametrically opposite behavioral patterns in spatial and temporal scale when they work under two different states (i.e. normal and overload), and (2) the processing times (including bug fixing times and bug tossing times) follow a stretched exponential distribution instead of the common power law distribution. Our work reveals regular patterns in human dynamics beyond online collaborative activities among skilled developers who work under different task-driven load conditions, and it could be an important supplementary to the current work on human dynamics.
Approval Voting with Intransitive Preferences
Venue: arXiv cs.GT 2017
Year: 2017

We extend Approval voting to the settings where voters may have intransitive preferences. The major obstacle to applying Approval voting in these settings is that voters are not able to clearly determine who they should approve or disapprove, due to the intransitivity of their preferences. An approach to address this issue is to apply tournament solutions to help voters make the decision. We study a class of voting systems where first each voter casts a vote defined as a tournament, then a well-defined tournament solution is applied to select the candidates who are assumed to be approved by the voter. Winners are the ones receiving the most approvals. We study axiomatic properties of this class of voting systems and complexity of control and bribery problems for these voting systems.
Rician MIMO Channel- and Jamming-Aware Decision Fusion
Venue: arXiv cs.IT 2017
Year: 2017

In this manuscript we study channel-aware decision fusion (DF) in a wireless sensor network (WSN) where: (i) the sensors transmit their decisions simultaneously for spectral efficiency purposes and the DF center (DFC) is equipped with multiple antennas; (ii) each sensor-DFC channel is described via a Rician model. As opposed to the existing literature, in order to account for stringent energy constraints in the WSN, only statistical channel information is assumed for the non-line-of sight (scattered) fading terms. For such a scenario, sub-optimal fusion rules are developed in order to deal with the exponential complexity of the likelihood ratio test (LRT) and impractical (complete) system knowledge. Furthermore, the considered model is extended to the case of (partially unknown) jamming-originated interference. Then the obtained fusion rules are modified with the use of composite hypothesis testing framework and generalized LRT. Coincidence and statistical equivalence among them are also investigated under some relevant simplified scenarios. Numerical results compare the proposed rules and highlight their jammingsuppression capability.
The Hardness of Solving Simple Word Equations
Venue: arXiv cs.FL 2017
Year: 2017

We investigate the class of regular-ordered word equations. In such equations, each variable occurs at most once in each side and the order of the variables occurring in both sides is the preserved (the variables can be, however, separated by potentially distinct constant factors). Surprisingly, we obtain that solving such simple equations, even when the sides contain exactly the same variables, is NP-hard. By considerations regarding the combinatorial structure of the minimal solutions of the more general quadratic equations we obtain that the satisfiability problem for regular-ordered equations is in NP. Finally, we also show that a related class of simple word equations, that generalises one-variable equations, is in P.
Citation personal display: A case study of personal websites by physicists in 11 well-known universities
Venue: arXiv cs.DL 2017
Year: 2017

This paper aims to investigate the extent to which researchers display citation, and wants to examine whether there are researcher differences in citation personal display at the level of university, country, and academic rank. Physicists in 11 well-known universities in USA, Britain, and China were chosen as the object of study. It was manually identified if physicists had mentioned citation counts, citation-based indices, or a link to Google Scholar Citations (GSC) on the personal websites. A chi-square test is constructed to test researcher differences in citation personal display. Results showed that the overall proportion of citation personal display is not high (14.8%), with 129 of 870 physicists displaying citation. And physicists from different well-known universities indeed had a significant difference in citation personal display. Moreover, at the national level, it was noticed that physicists in well-known Chinese universities had the highest level of citation personal display, followed by Britain and the USA. Further, this study also found that researchers who had the academic rank of professor had the highest citation personal display. In addition, the differences in h-index personal display by university, country or academic rank were analyzed, and the results showed that they were not statistically significant.
Building Fast and Compact Convolutional Neural Networks for Offline Handwritten Chinese Character Recognition
Venue: arXiv cs.CV 2017
Year: 2017

Like other problems in computer vision, offline handwritten Chinese character recognition (HCCR) has achieved impressive results using convolutional neural network (CNN)-based methods. However, larger and deeper networks are needed to deliver state-of-the-art results in this domain. Such networks intuitively appear to incur high computational cost, and require the storage of a large number of parameters, which renders them unfeasible for deployment in portable devices. To solve this problem, we propose a Global Supervised Low-rank Expansion (GSLRE) method and an Adaptive Drop-weight (ADW) technique to solve the problems of speed and storage capacity. We design a nine-layer CNN for HCCR consisting of 3,755 classes, and devise an algorithm that can reduce the networks computational cost by nine times and compress the network to 1/18 of the original size of the baseline model, with only a 0.21% drop in accuracy. In tests, the proposed algorithm surpassed the best single-network performance reported thus far in the literature while requiring only 2.3 MB for storage. Furthermore, when integrated with our effective forward implementation, the recognition of an offline character image took only 9.7 ms on a CPU. Compared with the state-of-the-art CNN model for HCCR, our approach is approximately 30 times faster, yet 10 times more cost efficient.
Simplified Biased Contribution Index (SBCI): A Mechanism to Make P2P Network Fair and Efficient for Resource Sharing
Venue: arXiv cs.NI 2017
Year: 2017

To balance the load and to discourage the free-riding in peer-to-peer (P2P) networks, many incentive mechanisms and policies have been proposed in recent years. Global peer ranking is one such mechanism. In this mechanism, peers are ranked based on a metric called contribution index. Contribution index is defined in such a manner that peers are motivated to share the resources in the network. Fairness in the terms of upload to download ratio in each peer can be achieved by this method. However, calculation of contribution index is not trivial. It is computed distributively and iteratively in the entire network and requires strict clock synchronization among the peers. A very small error in clock synchronization may lead to wrong results. Furthermore, iterative calculation requires a lot of message overhead and storage capacity, which makes its implementation more complex. In this paper, we are proposing a simple incentive mechanism based on the contributions of peers, which can balance the upload and download amount of resources in each peer. It does not require iterative calculation, therefore, can be implemented with lesser message overhead and storage capacity without requiring strict clock synchronization. This approach is efficient as there are very less rejections among the cooperative peers. It can be implemented in a truly distributed fashion with $O(N)$ time complexity per peer.
Row-Centric Lossless Compression of Markov Images
Venue: arXiv cs.IT 2017
Year: 2017

Motivated by the question of whether the recently introduced Reduced Cutset Coding (RCC) offers rate-complexity performance benefits over conventional context-based conditional coding for sources with two-dimensional Markov structure, this paper compares several row-centric coding strategies that vary in the amount of conditioning as well as whether a model or an empirical table is used in the encoding of blocks of rows. The conclusion is that, at least for sources exhibiting low-order correlations, 1-sided model-based conditional coding is superior to the method of RCC for a given constraint on complexity, and conventional context-based conditional coding is nearly as good as the 1-sided model-based coding.
Topological Interference Management with Decoded Message Passing
Venue: arXiv cs.IT 2017
Year: 2017

The topological interference management (TIM) problem studies partially-connected interference networks with no channel state information except for the network topology (i.e., connectivity graph) at the transmitters. In this paper, we consider a similar problem in the uplink cellular networks, while message passing is enabled at the receivers (e.g., base stations), so that the decoded messages can be routed to other receivers via backhaul links to help further improve network performance. For this TIM problem with decoded message passing (TIM-MP), we model the interference pattern by conflict digraphs, connect orthogonal access to the acyclic set coloring on conflict digraphs, and show that one-to-one interference alignment boils down to orthogonal access because of message passing. With the aid of polyhedral combinatorics, we identify the structural properties of certain classes of network topologies where orthogonal access achieves the optimal degrees-of-freedom (DoF) region in the information-theoretic sense. The relation to the conventional index coding with simultaneous decoding is also investigated by formulating a generalized index coding problem with successive decoding as a result of decoded message passing. The properties of reducibility and criticality are also studied, by which we are able to prove the linear optimality of orthogonal access in terms of symmetric DoF for the networks up to four users with all possible network topologies (218 instances). Practical issues of the tradeoff between the overhead of message passing and the achievable symmetric DoF are also discussed, in the hope of facilitating efficient backhaul utilization.
Comparison of Guidance Modes for the AUV "Slocum Glider" in Time-Varying Ocean Flows
Venue: arXiv cs.RO 2017
Year: 2017

This paper presents possibilities for the reliable guidance of an AUV "Slocum Glider" in time-varying ocean flows. The presented guidance modes consider the restricted information during a real mission about the actual position and ocean current conditions as well as the available control modes of a glider. A faster-than-real-time, full software stack simulator for the Slocum glider will be described in order to test the developed guidance modes under real mission conditions.
Lattice Coding and Decoding for Multiple-Antenna Ergodic Fading Channels
Venue: arXiv cs.IT 2017
Year: 2017

For ergodic fading, a lattice coding and decoding strategy is proposed and its performance is analyzed for the single-input single-output (SISO) and multiple-input multiple-output (MIMO) point-to-point channel as well as the multiple-access channel (MAC), with channel state information available only at the receiver (CSIR). At the decoder a novel strategy is proposed consisting of a time-varying equalization matrix followed by decision regions that depend only on channel statistics, not individual realizations. Our encoder has a similar structure to that of Erez and Zamir. For the SISO channel, the gap to capacity is bounded by a constant under a wide range of fading distributions. For the MIMO channel under Rayleigh fading, the rate achieved is within a gap to capacity that does not depend on the signal-to-noise ratio (SNR), and diminishes with the number of receive antennas. The analysis is extended to the K-user MAC where similar results hold. Achieving a small gap to capacity while limiting the use of CSIR to the equalizer highlights the scope for efficient decoder implementations, since decision regions are fixed, i.e., independent of channel realizations.
Multi-scale Image Fusion Between Pre-operative Clinical CT and X-ray Microtomography of Lung Pathology
Venue: arXiv cs.CV 2017
Year: 2017

Computational anatomy allows the quantitative analysis of organs in medical images. However, most analysis is constrained to the millimeter scale because of the limited resolution of clinical computed tomography (CT). X-ray microtomography ($μ$CT) on the other hand allows imaging of ex-vivo tissues at a resolution of tens of microns. In this work, we use clinical CT to image lung cancer patients before partial pneumonectomy (resection of pathological lung tissue). The resected specimen is prepared for $μ$CT imaging at a voxel resolution of 50 $μ$m (0.05 mm). This high-resolution image of the lung cancer tissue allows further insides into understanding of tumor growth and categorization. For making full use of this additional information, image fusion (registration) needs to be performed in order to re-align the $μ$CT image with clinical CT. We developed a multi-scale non-rigid registration approach. After manual initialization using a few landmark points and rigid alignment, several levels of non-rigid registration between down-sampled (in the case of $μ$CT) and up-sampled (in the case of clinical CT) representations of the image are performed. Any non-lung tissue is ignored during the computation of the similarity measure used to guide the registration during optimization. We are able to recover the volume differences introduced by the resection and preparation of the lung specimen. The average ($\pm$ std. dev.) minimum surface distance between $μ$CT and clinical CT at the resected lung surface is reduced from 3.3 $\pm$ 2.9 (range: [0.1, 15.9]) to 2.3 mm $\pm$ 2.8 (range: [0.0, 15.3]) mm. The alignment of clinical CT with $μ$CT will allow further registration with even finer resolutions of $μ$CT (up to 10 $μ$m resolution) and ultimately with histopathological microscopy images for further macro to micro image fusion that can aid medical image analysis.
Tars: Timeliness-aware Adaptive Replica Selection for Key-Value Stores
Venue: arXiv cs.DC 2017
Year: 2017

In current large-scale distributed key-value stores, a single end-user request may lead to key-value access across tens or hundreds of servers. The tail latency of these key-value accesses is crucial to the user experience and greatly impacts the revenue. To cut the tail latency, it is crucial for clients to choose the fastest replica server as much as possible for the service of each key-value access. Aware of the challenges on the time varying performance across servers and the herd behaviors, an adaptive replica selection scheme C3 is proposed recently. In C3, feedback from individual servers is brought into replica ranking to reflect the time-varying performance of servers, and the distributed rate control and backpressure mechanism is invented. Despite of C3's good performance, we reveal the timeliness issue of C3, which has large impacts on both the replica ranking and the rate control, and propose the Tars (timeliness-aware adaptive replica selection) scheme. Following the same framework as C3, Tars improves the replica ranking by taking the timeliness of the feedback information into consideration, as well as revises the rate control of C3. Simulation results confirm that Tars outperforms C3.
Another Look at the Implementation of Read/write Registers in Crash-prone Asynchronous Message-Passing Systems (Extended Version)
Venue: arXiv cs.DC 2017
Year: 2017

" Yet another paper on " the implementation of read/write registers in crash-prone asynchronous message-passing systems! Yes..., but, differently from its predecessors, this paper looks for a communication abstraction which captures the essence of such an implementation in the same sense that total order broadcast can be associated with consensus, or message causal delivery can be associated with causal read/write registers. To this end, the paper introduces a new communication abstraction, named SCD-broadcast (SCD standing for " Set Constrained Delivery "), which, instead of a single message, delivers to processes sets of messages (whose size can be arbitrary), such that the sequences of message sets delivered to any two processes satisfies some constraints. The paper then shows that: (a) SCD-broadcast allows for a very simple implementation of a snapshot object (and consequently also of atomic read/write registers) in crash-prone asynchronous message-passing systems, (b) SCD-broadcast can be built from snapshot objects (hence SCD-broadcast and snapshot objects --or read/write registers-- are " computationally equivalent "), (c) SCD-broadcast can be built in message-passing systems where any minority of processes may crash (which is the weakest assumption on the number of possible process crashes needed to implement a read/write register).