OpenRaiser/Intern-Atlas huggingface dataset:
A Highly Literate Approach to Ontology Building
Venue: arXiv cs.DL 2015
Year: 2015

Ontologies present an attractive technology for describing bio-medicine, because they can be shared, and have rich computational properties. However, they lack the rich expressivity of English and fit poorly with the current scientific "publish or perish" model. While, there have been attempts to combine free text and ontologies, most of these perform \textit{post-hoc} annotation of text. In this paper, we introduce our new environment which borrows from literate programming, to allow an author to co-develop both text and ontological description. We are currently using this environment to document the Karyotype Ontology which allows rich descriptions of the chromosomal complement in humans. We explore some of the advantages and difficulties of this form of ontology development.
OFDM Channel Estimation via Phase Retrieval
Venue: arXiv cs.IT 2015
Year: 2015

Pilot-aided channel estimation is nowadays a standard component in each wireless receiver enabling coherent transmission of complex-valued constellations, only affected by noise and interference. Whenever these disturbances are sufficiently small and long data frames are used, high data rates can be achieved and the resource overhead due to the pilots vanishes asymptotically. On the other, it is expected that for the next generation of mobile networks not only data rate is in the main focus but also low latency, short and sporadic messages, massive connectivity, distributed & adhoc processing and robustness with respect to asynchronism. Therefore a review of several well-established principles in communication has been started already. A particular implication when using complex-valued pilots is that these values have to be known at the receiver and therefore these resources can not be used simultaneously for user data. For an OFDM-like multicarrier scheme this means that pilot tones (usually placed equidistantly according to the Nyquist theorem) are allocated with globally known amplitudes and phases to reconstruct the channel impulse response. Phases are designed and allocated globally which is in contrast to a distributed infrastructure. In this work we present therefore a new phaseless pilot scheme where only pilot amplitudes need to be known at the receiver, i.e., phases are available again and can be used for various other purposes. The idea is based on a phase retrieval result for symmetrized and zero-padded magnitude Fourier measurements obtained by two of the authors. The phases on the pilot tones can now be used to carry additional user-specific data or compensate for other signal characteristics, like the PAPR.
A Distributed Multi-agent Market Place for HPC Compute Cycle Resource Trading
Venue: arXiv cs.DC 2015
Year: 2015

Computer simulation is finding a role in an increasing number of scientific disciplines, concomitant with the rise in available computing power. Realizing this inevitably requires access to computational power beyond the desktop, making use of clusters, supercomputers, data repositories, networks and distributed aggregations of these resources. Accessing one such resource entails a number of usability and security problems; when multiple geographically distributed resources are involved, the difficulty is compounded. This presents the user with the problem of how to gain access to suitable resources to run their workloads as they need them. In this paper we present our solutions to this problem, a resource trading platform that allows users to purchase access to resources within a distributed e-infrastructure. We present the implementation of this Resource Allocation Market Place as a distributed multi-agent system, and show how it provides a highly flexible, efficient tool to schedule workflows across high performance computing resources.
DGD Gallery: Storage, sharing, and publication of digital research data
Venue: arXiv cs.OH 2015
Year: 2015

We describe a project, called the "Discretization in Geometry and Dynamics Gallery", or DGD Gallery for short, whose goal is to store geometric data and to make it publicly available. The DGD Gallery offers an online web service for the storage, sharing, and publication of digital research data.
Sparse Representation of a Blur Kernel for Blind Image Restoration
Venue: arXiv cs.CV 2015
Year: 2015

Blind image restoration is a non-convex problem which involves restoration of images from an unknown blur kernel. The factors affecting the performance of this restoration are how much prior information about an image and a blur kernel are provided and what algorithm is used to perform the restoration task. Prior information on images is often employed to restore the sharpness of the edges of an image. By contrast, no consensus is still present regarding what prior information to use in restoring from a blur kernel due to complex image blurring processes. In this paper, we propose modelling of a blur kernel as a sparse linear combinations of basic 2-D patterns. Our approach has a competitive edge over the existing blur kernel modelling methods because our method has the flexibility to customize the dictionary design, which makes it well-adaptive to a variety of applications. As a demonstration, we construct a dictionary formed by basic patterns derived from the Kronecker product of Gaussian sequences. We also compare our results with those derived by other state-of-the-art methods, in terms of peak signal to noise ratio (PSNR).
Teaching the Foundations of Data Science: An Interdisciplinary Approach
Venue: arXiv cs.CY 2015
Year: 2015

The astronomical growth of data has necessitated the need for educating well-qualified data scientists to derive deep insights from large and complex data sets generated by organizations. In this paper, we present our interdisciplinary approach and experiences in teaching a Data Science course, the first of its kind offered at the Wright State University. Two faculty members from the Management Information Systems (MIS) and Computer Science (CS) departments designed and co-taught the course with perspectives from their previous research and teaching experiences. Students in the class had mix backgrounds with mainly MIS and CS majors. Students' learning outcomes and post course survey responses suggested that the course delivered a broad overview of data science as desired, and that students worked synergistically with those of different majors in collaborative lab assignments and in a semester long project. The interdisciplinary pedagogy helped build collaboration and create satisfaction among learners.
Breaking the Variance: Approximating the Hamming Distance in $\tilde O(1/ε)$ Time Per Alignment
Venue: arXiv cs.DS 2015
Year: 2015

The algorithmic tasks of computing the Hamming distance between a given pattern of length $m$ and each location in a text of length $n$ is one of the most fundamental algorithmic tasks in string algorithms. Unfortunately, there is evidence that for a text $T$ of size $n$ and a pattern $P$ of size $m$, one cannot compute the exact Hamming distance for all locations in $T$ in time which is less than $\tilde O(n\sqrt m)$. However, Karloff~\cite{karloff} showed that if one is willing to suffer a $1\pmε$ approximation, then it is possible to solve the problem with high probability, in $\tilde O(\frac n {ε^2})$ time. Due to related lower bounds for computing the Hamming distance of two strings in the one-way communication complexity model, it is strongly believed that obtaining an algorithm for solving the approximation version cannot be done much faster as a function of $\frac 1 ε$. We show here that this belief is false by introducing a new $\tilde O(\frac{n}ε)$ time algorithm that succeeds with high probability. The main idea behind our algorithm, which is common in sparse recovery problems, is to reduce the variance of a specific randomized experiment by (approximately) separating heavy hitters from non-heavy hitters. However, while known sparse recovery techniques work very well on vectors, they do not seem to apply here, where we are dealing with mismatches between pairs of characters. We introduce two main algorithmic ingredients. The first is a new sparse recovery method that applies for pair inputs (such as in our setting). The second is a new construction of hash/projection functions, which allows to count the number of projections that induce mismatches between two characters exponentially faster than brute force. We expect that these algorithmic techniques will be of independent interest.
Reducing Parallel Communication in Algebraic Multigrid through Sparsification
Venue: arXiv cs.DC 2015
Year: 2015

Algebraic multigrid (AMG) is an $\mathcal{O}(n)$ solution process for many large sparse linear systems. A hierarchy of progressively coarser grids is constructed that utilize complementary relaxation and interpolation operators. High-energy error is reduced by relaxation, while low-energy error is mapped to coarse-grids and reduced there. However, large parallel communication costs often limit parallel scalability. As the multigrid hierarchy is formed, each coarse matrix is formed through a triple matrix product. The resulting coarse-grids often have significantly more nonzeros per row than the original fine-grid operator, thereby generating high parallel communication costs on coarse-levels. In this paper, we introduce a method that systematically removes entries in coarse-grid matrices after the hierarchy is formed, leading to an improved communication costs. We sparsify by removing weakly connected or unimportant entries in the matrix, leading to improved solve time. The main trade-off is that if the heuristic identifying unimportant entries is used too aggressively, then AMG convergence can suffer. To counteract this, the original hierarchy is retained, allowing entries to be reintroduced into the solver hierarchy if convergence is too slow. This enables a balance between communication cost and convergence, as necessary. In this paper we present new algorithms for reducing communication and present a number of computational experiments in support.
Design and Analysis of Secure Exam Protocols
Venue: arXiv cs.CR 2015
Year: 2015

Except for the traditional threat that candidates may want to cheat, exams have historically not been seen as a serious security problem. That threat is routinely thwarted by having invigilators ensure that candidates do not misbehave during testing. However, as recent exam scandals confirm, also invigilators and exam authorities may have interest in frauds, hence they may pose security threats as well. Moreover, new security issues arise from the recent use of computers, which can facilitate the exam experience for example by allowing candidates to register from home. Thus, exams must be designed with the care normally devoted to security protocols. This dissertation studies exam protocol security and provides an in-depth understanding that can be also useful for the study of the security of similar systems, such as personnel selections, project reviews, and conference management systems. It introduces an unambiguous terminology that leads to the specification of a taxonomy of various exam types, depending on the level of computer assistance. It then establishes a theoretical framework for the formal analysis of exams. The framework defines several authentication, privacy, and verifiability requirements that modern exams should meet, and enables the security of exam protocols to be studied. Using the framework, we formally analyse traditional, computer-assisted, and Internet-based exam protocols. We find some security issues and propose modifications to partially achieve the desired requirements. This dissertation also designs three novel exam protocols that guarantee a wide set of security requirements. Finally, this dissertation looks at exams as carried out through modern browsers. We advance a formal analysis of requirements that are not only logically conditioned on the technology but also on user actions. We conclude with best-practice recommendations to browser vendors.
Learning optimal nonlinearities for iterative thresholding algorithms
Venue: arXiv cs.LG 2015
Year: 2015

Iterative shrinkage/thresholding algorithm (ISTA) is a well-studied method for finding sparse solutions to ill-posed inverse problems. In this letter, we present a data-driven scheme for learning optimal thresholding functions for ISTA. The proposed scheme is obtained by relating iterations of ISTA to layers of a simple deep neural network (DNN) and developing a corresponding error backpropagation algorithm that allows to fine-tune the thresholding functions. Simulations on sparse statistical signals illustrate potential gains in estimation quality due to the proposed data adaptive ISTA.
Supporting the monitoring of the verification process of critical systems'software
Venue: arXiv cs.SE 2015
Year: 2015

Critical software systems face stringent requirements in safety, security, and reliability due to the circumstances surrounding their operation. Safety and security have progressively gained importance over the years due to the integration of hardware with software-intensive deployments that introduce additional sources of errors. It is, then, necessary to follow high-quality exhaustive software development processes that besides the needed development activities to increase safety and security also integrate techniques to increase the reliability of the software development process itself. In practice, the use of automated techniques for the verification of the verification process is, however, not sufficiently wide spread. This is mainly due to the high cost of the required techniques and to their degree of complexity when adjusting to the different norms and regulations. This work presents an approach for comprehensive management of the verification processes; the approach allows engineers to monitor and control the project status regarding the applicable standards. This approach has been validated through its implementation in a tool and its application to real projects.
Context Driven Label Fusion for segmentation of Subcutaneous and Visceral Fat in CT Volumes
Venue: arXiv cs.CV 2015
Year: 2015

Quantification of adipose tissue (fat) from computed tomography (CT) scans is conducted mostly through manual or semi-automated image segmentation algorithms with limited efficacy. In this work, we propose a completely unsupervised and automatic method to identify adipose tissue, and then separate Subcutaneous Adipose Tissue (SAT) from Visceral Adipose Tissue (VAT) at the abdominal region. We offer a three-phase pipeline consisting of (1) Initial boundary estimation using gradient points, (2) boundary refinement using Geometric Median Absolute Deviation and Appearance based Local Outlier Scores (3) Context driven label fusion using Conditional Random Fields (CRF) to obtain the final boundary between SAT and VAT. We evaluate the proposed method on 151 abdominal CT scans and obtain state-of-the-art 94% and 91% dice similarity scores for SAT and VAT segmentation, as well as significant reduction in fat quantification error measure.
Simultaneous Acoustic Localization of Multiple Smartphones with Euclidean Distance Matrices
Venue: arXiv cs.NI 2015
Year: 2015

In this paper, we present an acoustic localization system for multiple devices. In contrast to systems which localise a device relative to one or several anchor points, we focus on the joint localisation of several devices relative to each other. We present a prototype of our system on off-the-shelf smartphones. No user interaction is required, the phones emit acoustic pulses according to a precomputed schedule. Using the elapsed time between two times of arrivals (ETOA) method with sample counting, distances between the devices are estimated. These, possibly incomplete, distances are the input to an efficient and robust multi-dimensional scaling algorithm returning a position for each phone. We evaluated our system in real-world scenarios, achieving error margins of 15 cm in an office environment.
Throughput Bound of XOR Coded Wireless Multicasting to Three Clients
Venue: arXiv cs.NI 2015
Year: 2015

It is a well-known result that constructing codewords over $GF(2)$ to minimize the number of transmissions for a single-hop wireless multicasting is an NP-complete problem. Linearly independent codewords can be constructed in polynomial time for all the $n$ clients, known as maximum distance separable (MDS) code, when the finite field size $q$ is larger than or equal to the number of clients, $q\geq n$. In this paper we quantify the exact minimum number of transmissions for a multicast network using erasure code when $q=2$ and $n=3$, such that $q<n$. We first show that the use of Markov chain model to derive the minimum number of transmissions for such a network is limited for very small number of input packets. We then use combinatorial approach to derive an upper bound on the exact minimum number of transmissions. Our results show that the difference between the expected number of transmissions using XOR coding and MDS coding is negligible for $n=3$.
Blockout: Dynamic Model Selection for Hierarchical Deep Networks
Venue: arXiv cs.CV 2015
Year: 2015

Most deep architectures for image classification--even those that are trained to classify a large number of diverse categories--learn shared image representations with a single model. Intuitively, however, categories that are more similar should share more information than those that are very different. While hierarchical deep networks address this problem by learning separate features for subsets of related categories, current implementations require simplified models using fixed architectures specified via heuristic clustering methods. Instead, we propose Blockout, a method for regularization and model selection that simultaneously learns both the model architecture and parameters. A generalization of Dropout, our approach gives a novel parametrization of hierarchical architectures that allows for structure learning via back-propagation. To demonstrate its utility, we evaluate Blockout on the CIFAR and ImageNet datasets, demonstrating improved classification accuracy, better regularization performance, faster training, and the clear emergence of hierarchical network structures.
Impact of exponential long range and Gaussian short range lateral connectivity on the distributed simulation of neural networks including up to 30 billion synapses
Venue: arXiv cs.DC 2015
Year: 2015

Recent experimental neuroscience studies are pointing out the role of long-range intra-areal connectivity that can be modeled by a distance dependent exponential decay of the synaptic probability distribution. This short report provides a preliminary measure of the impact of exponentially decaying lateral connectivity compared to that of shorter-range Gaussian decays on the scaling behaviour and memory occupation of a distributed spiking neural network simulator (DPSNN). Two-dimensional grids of cortical columns composed by point-like spiking neurons have been connected by up to 30 billion synapses using exponential and Gaussian connectivity models. Up to 1024 hardware cores, hosted on a 64 nodes server platform, executed the MPI processes composing the distributed simulator. The hardware platform was a cluster of IBM NX360 M5 16-core compute nodes, each one containing two Intel Xeon Haswell 8-core E5-2630 v3 processors, with a clock of 2.40GHz, interconnected through an InfiniBand network. This study is conducted in the framework of the CORTICONIC FET project, also in view of the next -to-start activities foreseen as part of the Human Brain Project (HBP), SubProject 3 Cognitive and Systems Neuroscience, WaveScalES work-package.
PMSR - Poor Man's Segment Routing, a minimalistic approach to Segment Routing and a Traffic Engineering use case
Venue: arXiv cs.NI 2015
Year: 2015

The current specification of the Segment Routing (SR) architecture requires enhancements to the intra-domain routing protocols (e.g. OSPF and IS-IS) so that the nodes can advertise the Segment Identifiers (SIDs). We propose a simpler solution called PMSR (Poor Man's Segment Routing), that does not require any enhancement to routing protocol. We compare the procedures of PMSR with traditional SR, showing that PMSR can reduce the operation and management complexity. We analyze the set of use cases in the current SR drafts and we claim that PMSR can support the large majority of them. Thanks to the drastic simplification of the Control Plane, we have been able to develop an Open Source prototype of PMSR. In the second part of the paper, we consider a Traffic Engineering use case, starting from a traditional flow assignment optimization problem which allocates hop-by-hop paths to flows. We propose a SR path assignment algorithm and prove that it is optimal with respect to the number of segments allocated to a flow.
Non-Local Probes Do Not Help with Graph Problems
Venue: arXiv cs.DS 2015
Year: 2015

This work bridges the gap between distributed and centralised models of computing in the context of sublinear-time graph algorithms. A priori, typical centralised models of computing (e.g., parallel decision trees or centralised local algorithms) seem to be much more powerful than distributed message-passing algorithms: centralised algorithms can directly probe any part of the input, while in distributed algorithms nodes can only communicate with their immediate neighbours. We show that for a large class of graph problems, this extra freedom does not help centralised algorithms at all: for example, efficient stateless deterministic centralised local algorithms can be simulated with efficient distributed message-passing algorithms. In particular, this enables us to transfer existing lower bound results from distributed algorithms to centralised local algorithms.
Breaking the Barriers to True Augmented Reality
Venue: arXiv cs.HC 2015
Year: 2015

In recent years, Augmented Reality (AR) and Virtual Reality (VR) have gained considerable commercial traction, with Facebook acquiring Oculus VR for \$2 billion, Magic Leap attracting more than \$500 million of funding, and Microsoft announcing their HoloLens head-worn computer. Where is humanity headed: a brave new dystopia-or a paradise come true? In this article, we present discussions, which started at the symposium "Making Augmented Reality Real", held at Nara Institute of Science and Technology in August 2014. Ten scientists were invited to this three-day event, which started with a full day of public presentations and panel discussions (video recordings are available at the event web page), followed by two days of roundtable discussions addressing the future of AR and VR.