OpenRaiser/Intern-Atlas huggingface dataset:
Special Guards in Chromatic Art Gallery
Venue: arXiv cs.CG 2017
Year: 2017

We present two new versions of the chromatic art gallery problem that can improve upper bound of the required colors pretty well. In our version, we employ restricted angle guards so that these modern guards can visit $α$-degree of their surroundings. If $α$ is between $0$ and $180$ degree, we demonstrate that the strong chromatic guarding number is constant. Then we use orthogonal $90$-degree guards for guarding the polygons. We prove that the strong chromatic guarding number with orthogonal guards is the logarithmic order. First, we show that for the special cases of the orthogonal polygon such as snake polygon, staircase polygon and convex polygon, the number of colors is constant. We decompose the polygon into parts so that the number of the conflicted parts is logarithmic and every part is snake. Next, we explain the chromatic art gallery for the orthogonal polygon with guards that have rectangular visibility. We prove that the strong chromatic guarding number for orthogonal polygon with rectangular guards is logarithmic order, too. We use a partitioning for orthogonal polygon such that every part is a mount, then we show that a tight bound for strong chromatic number with rectangular guards is $θ(\log n)$
Improving average ranking precision in user searches for biomedical research datasets
Venue: arXiv cs.IR 2017
Year: 2017

Availability of research datasets is keystone for health and life science study reproducibility and scientific progress. Due to the heterogeneity and complexity of these data, a main challenge to be overcome by research data management systems is to provide users with the best answers for their search queries. In the context of the 2016 bioCADDIE Dataset Retrieval Challenge, we investigate a novel ranking pipeline to improve the search of datasets used in biomedical experiments. Our system comprises a query expansion model based on word embeddings, a similarity measure algorithm that takes into consideration the relevance of the query terms, and a dataset categorisation method that boosts the rank of datasets matching query constraints. The system was evaluated using a corpus with 800k datasets and 21 annotated user queries. Our system provides competitive results when compared to the other challenge participants. In the official run, it achieved the highest infAP among the participants, being +22.3% higher than the median infAP of the participant's best submissions. Overall, it is ranked at top 2 if an aggregated metric using the best official measures per participant is considered. The query expansion method showed positive impact on the system's performance increasing our baseline up to +5.0% and +3.4% for the infAP and infNDCG metrics, respectively. Our similarity measure algorithm seems to be robust, in particular compared to Divergence From Randomness framework, having smaller performance variations under different training conditions. Finally, the result categorization did not have significant impact on the system's performance. We believe that our solution could be used to enhance biomedical dataset management systems. In particular, the use of data driven query expansion methods could be an alternative to the complexity of biomedical terminologies.
Survivable Probability of SDN-enabled Cloud Networking with Random Physical Link Failure
Venue: arXiv cs.NI 2017
Year: 2017

Software-driven cloud networking is a new paradigm in orchestrating physical resources (CPU, network bandwidth, energy, storage) allocated to network functions, services, and applications, which is commonly modeled as a cross-layer network. This model carries a physical network representing the physical infrastructure, a logical network showing demands, and logical-to-physical node/link mappings. In such networks, a single failure in the physical network may trigger cascading failures in the logical network and disable network services and connectivity. In this paper, we propose an evaluation metric, survivable probability, to evaluate the reliability of such networks under random physical link failure(s). We propose the concept of base protecting spanning tree and prove the necessary and sufficient conditions for its existence and relation to survivability. We then develop mathematical programming formulations for reliable cross-layer network routing design with the maximal reliable probability. Computation results demonstrate the viability of our approach.
Fully Convolutional Neural Networks for Dynamic Object Detection in Grid Maps
Venue: arXiv cs.CV 2017
Year: 2017

Grid maps are widely used in robotics to represent obstacles in the environment and differentiating dynamic objects from static infrastructure is essential for many practical applications. In this work, we present a methods that uses a deep convolutional neural network (CNN) to infer whether grid cells are covering a moving object or not. Compared to tracking approaches, that use e.g. a particle filter to estimate grid cell velocities and then make a decision for individual grid cells based on this estimate, our approach uses the entire grid map as input image for a CNN that inspects a larger area around each cell and thus takes the structural appearance in the grid map into account to make a decision. Compared to our reference method, our concept yields a performance increase from 83.9% to 97.2%. A runtime optimized version of our approach yields similar improvements with an execution time of just 10 milliseconds.
Data Discovery and Anomaly Detection Using Atypicality: Theory
Venue: arXiv cs.IT 2017
Year: 2017

A central question in the era of 'big data' is what to do with the enormous amount of information. One possibility is to characterize it through statistics, e.g., averages, or classify it using machine learning, in order to understand the general structure of the overall data. The perspective in this paper is the opposite, namely that most of the value in the information in some applications is in the parts that deviate from the average, that are unusual, atypical. We define what we mean by 'atypical' in an axiomatic way as data that can be encoded with fewer bits in itself rather than using the code for the typical data. We show that this definition has good theoretical properties. We then develop an implementation based on universal source coding, and apply this to a number of real world data sets.
New characterization and parametrization of LCD Codes
Venue: arXiv cs.IT 2017
Year: 2017

Linear complementary dual (LCD) cyclic codes were referred historically to as reversible cyclic codes, which had applications in data storage. Due to a newly discovered application in cryptography, there has been renewed interest in LCD codes. In particular, it has been shown that binary LCD codes play an important role in implementations against side-channel attacks and fault injection attacks. In this paper, we first present a new characterization of binary LCD codes in terms of their symplectic basis. Using such a characterization,we solve a conjecture proposed by Galvez et al. on the minimum distance of binary LCD codes. Next, we consider the action of the orthogonal group on the set of all LCD codes, determine all possible orbits of this action, derive simple closed formulas of the size of the orbits, and present some asymptotic results of the size of the corresponding orbits. Our results show that almost all binary LCD codes are odd-like codes with odd-like duals, and about half of q-ary LCD codes have orthonormal basis, where q is a power of an odd prime.
Secure and Trustable Distributed Aggregation based on Kademlia
Venue: arXiv cs.CR 2017
Year: 2017

Aggregation of values that need to be kept confidential while guaranteeing the robustness of the process and the correctness of the result is required in an increasing number of applications. We propose an aggregation algorithm, which supports a large spectrum of potential applications including complex voting protocols. It relies on the distributed hash table Kademlia, used in BitTorrent, for pseudonymous communication between randomly predetermined peers to ensure a high degree of confidentiality which does not solely relies on cryptography. The distribution of data and computation limits the potential for data breaches, and reduces the need for institutional trust. Experimental results confirm the complexity of O(n) for n peers allowing for large-scale applications.
Discriminant chronicles mining: Application to care pathways analytics
Venue: arXiv cs.AI 2017
Year: 2017

Pharmaco-epidemiology (PE) is the study of uses and effects of drugs in well defined populations. As medico-administrative databases cover a large part of the population, they have become very interesting to carry PE studies. Such databases provide longitudinal care pathways in real condition containing timestamped care events, especially drug deliveries. Temporal pattern mining becomes a strategic choice to gain valuable insights about drug uses. In this paper we propose DCM, a new discriminant temporal pattern mining algorithm. It extracts chronicle patterns that occur more in a studied population than in a control population. We present results on the identification of possible associations between hospitalizations for seizure and anti-epileptic drug switches in care pathway of epileptic patients.
Performance Analysis of Massive MIMO Networks with Random Unitary Pilot Matrices
Venue: arXiv cs.IT 2017
Year: 2017

A common approach to obtain channel state information for massive MIMO networks is to use the same orthogonal training sequences in each cell. We call this the full-pilot reuse (FPR) scheme. In this paper, we study an alternative approach where each cell uses different sets of orthogonal pilot (DOP) sequences. Considering uplink communications with matched filter (MF) receivers, we first derive the SINR in the large system regime where the number of antennas at the base station, the number of users in each cell, and training duration grow large with fixed ratios. For tractability in the analysis, the orthogonal pilots are drawn from Haar distributed random unitary matrices. The resulting expression is simple and easy to compute. As shown by the numerical simulations, the asymptotic SINR approximates the finite-size systems accurately. Secondly, we derive the user capacity of the DOP scheme under a simple power control and show that it is generally better than that of the FPR scheme.
Collaborative Reuse of Streaming Dataflows in IoT Applications
Venue: arXiv cs.DC 2017
Year: 2017

Distributed Stream Processing Systems (DSPS) like Apache Storm and Spark Streaming enable composition of continuous dataflows that execute persistently over data streams. They are used by Internet of Things (IoT) applications to analyze sensor data from Smart City cyber-infrastructure, and make active utility management decisions. As the ecosystem of such IoT applications that leverage shared urban sensor streams continue to grow, applications will perform duplicate pre-processing and analytics tasks. This offers the opportunity to collaboratively reuse the outputs of overlapping dataflows, thereby improving the resource efficiency. In this paper, we propose \emph{dataflow reuse algorithms} that given a submitted dataflow, identifies the intersection of reusable tasks and streams from a collection of running dataflows to form a \emph{merged dataflow}. Similar algorithms to unmerge dataflows when they are removed are also proposed. We implement these algorithms for the popular Apache Storm DSPS, and validate their performance and resource savings for 35 synthetic dataflows based on public OPMW workflows with diverse arrival and departure distributions, and on 21 real IoT dataflows from RIoTBench.
Social Media Text Processing and Semantic Analysis for Smart Cities
Venue: arXiv cs.SI 2017
Year: 2017

With the rise of Social Media, people obtain and share information almost instantly on a 24/7 basis. Many research areas have tried to gain valuable insights from these large volumes of freely available user generated content. With the goal of extracting knowledge from social media streams that might be useful in the context of intelligent transportation systems and smart cities, we designed and developed a framework that provides functionalities for parallel collection of geo-located tweets from multiple pre-defined bounding boxes (cities or regions), including filtering of non-complying tweets, text pre-processing for Portuguese and English language, topic modeling, and transportation-specific text classifiers, as well as, aggregation and data visualization. We performed an exploratory data analysis of geo-located tweets in 5 different cities: Rio de Janeiro, São Paulo, New York City, London and Melbourne, comprising a total of more than 43 million tweets in a period of 3 months. Furthermore, we performed a large scale topic modelling comparison between Rio de Janeiro and São Paulo. Interestingly, most of the topics are shared between both cities which despite being in the same country are considered very different regarding population, economy and lifestyle. We take advantage of recent developments in word embeddings and train such representations from the collections of geo-located tweets. We then use a combination of bag-of-embeddings and traditional bag-of-words to train travel-related classifiers in both Portuguese and English to filter travel-related content from non-related. We created specific gold-standard data to perform empirical evaluation of the resulting classifiers. Results are in line with research work in other application areas by showing the robustness of using word embeddings to learn word similarities that bag-of-words is not able to capture.
One-Shot Learning for Semantic Segmentation
Venue: arXiv cs.CV 2017
Year: 2017

Low-shot learning methods for image classification support learning from sparse data. We extend these techniques to support dense semantic image segmentation. Specifically, we train a network that, given a small set of annotated images, produces parameters for a Fully Convolutional Network (FCN). We use this FCN to perform dense pixel-level prediction on a test image for the new semantic class. Our architecture shows a 25% relative meanIoU improvement compared to the best baseline methods for one-shot segmentation on unseen classes in the PASCAL VOC 2012 dataset and is at least 3 times faster.
UI-Net: Interactive Artificial Neural Networks for Iterative Image Segmentation Based on a User Model
Venue: arXiv cs.CV 2017
Year: 2017

For complex segmentation tasks, fully automatic systems are inherently limited in their achievable accuracy for extracting relevant objects. Especially in cases where only few data sets need to be processed for a highly accurate result, semi-automatic segmentation techniques exhibit a clear benefit for the user. One area of application is medical image processing during an intervention for a single patient. We propose a learning-based cooperative segmentation approach which includes the computing entity as well as the user into the task. Our system builds upon a state-of-the-art fully convolutional artificial neural network (FCN) as well as an active user model for training. During the segmentation process, a user of the trained system can iteratively add additional hints in form of pictorial scribbles as seed points into the FCN system to achieve an interactive and precise segmentation result. The segmentation quality of interactive FCNs is evaluated. Iterative FCN approaches can yield superior results compared to networks without the user input channel component, due to a consistent improvement in segmentation quality after each interaction.
Subspace Least Squares Multidimensional Scaling
Venue: arXiv cs.CG 2017
Year: 2017

Multidimensional Scaling (MDS) is one of the most popular methods for dimensionality reduction and visualization of high dimensional data. Apart from these tasks, it also found applications in the field of geometry processing for the analysis and reconstruction of non-rigid shapes. In this regard, MDS can be thought of as a \textit{shape from metric} algorithm, consisting of finding a configuration of points in the Euclidean space that realize, as isometrically as possible, some given distance structure. In the present work we cast the least squares variant of MDS (LS-MDS) in the spectral domain. This uncovers a multiresolution property of distance scaling which speeds up the optimization by a significant amount, while producing comparable, and sometimes even better, embeddings.
DNA translocation through alpha-haemolysin nano-pores with potential application to macromolecular data storage
Venue: arXiv cs.ET 2017
Year: 2017

Digital information can be encoded in the building-block sequence of macromolecules, such as RNA and single-stranded DNA. Methods of "writing" and "reading" macromolecular strands are currently available, but they are slow and expensive. In an ideal molecular data storage system, routine operations such as write, read, erase, store, and transfer must be done reliably and at high speed within an integrated chip. As a first step toward demonstrating the feasibility of this concept, we report preliminary results of DNA readout experiments conducted in miniaturized chambers that are scalable to even smaller dimensions. We show that translocation of a single-stranded DNA molecule (consisting of 50 adenosine bases followed by 100 cytosine bases) through an ion-channel yields a characteristic signal that is attributable to the 2-segment structure of the molecule. We also examine the dependence of the translocation rate and speed on the adjustable parameters of the experiment.
Learning from development of a third-party patient-oriented application using Australian national personal health records system
Venue: arXiv cs.CY 2017
Year: 2017

Large-scale national level Personal Health Record (PHR) has been implemented in Australia. However, usability, data quality and poor functionalities have resulted in low utility affecting enrollment and participation rates by both patients and clinicians alike. Development of new applications deriving secondary utility of data can enhance use of PHRs but there is limited understanding on processes involved in development of third-party applications with nationally run PHRs. This paper prsents an analysis of processes and regulatory requirements for developing applications of data from My Health Record, Australian nationally run PHR and subsequently implementation of a patient oriented software application using data sourced from My Health Record.
Evaluation of the efficiency and quality in structured crime reports
Venue: arXiv cs.CY 2017
Year: 2017

This work evaluates a novel structured method for reporting crime and registering crime scene data by comparing the method with traditional text-based crime reports. Swedish law enforcement officers were asked to register a residential burglary using both methods in order to measure the effectiveness of each method. The effectiveness was quantified as both the time it took to register the crime as well as the number of relevant unique crime scene details that were collected. The results show the structured method to be significantly more efficient than traditional text-based crime reports (p < 0.05). Also, the novel method registers 2.96 times more relevant and unique crime scene details on average. In addition to the differences in efficiency this work also discusses more qualitative pros and cons with the novel method, as well as various data analysis methods that could be used on the registered data. It is concluded that the novel method can benefit law enforcement agencies in two ways. First, related to increased quality and more elaborate crime reports. Secondly, related to significant time-savings, which according to a rough estimate is expect to lie in the range 11-30 full-time positions per year for Swedish law enforcement agencies, particularly for volume crime categories. Those resources could instead be used for unburden the workload for our law enforcement officers, and to some extent free resources that could be used in other parts of the organization. Note: this pre-print manuscript is written in Swedish.
What were you expecting? Using Expectancy Features to Predict Expressive Performances of Classical Piano Music
Venue: arXiv cs.SD 2017
Year: 2017

In this paper we present preliminary work examining the relationship between the formation of expectations and the realization of musical performances, paying particular attention to expressive tempo and dynamics. To compute features that reflect what a listener is expecting to hear, we employ a computational model of auditory expectation called the Information Dynamics of Music model (IDyOM). We then explore how well these expectancy features -- when combined with score descriptors using the Basis-Function modeling approach -- can predict expressive tempo and dynamics in a dataset of Mozart piano sonata performances. Our results suggest that using expectancy features significantly improves the predictions for tempo.
Community Recovery in Hypergraphs
Venue: arXiv cs.IT 2017
Year: 2017

Community recovery is a central problem that arises in a wide variety of applications such as network clustering, motion segmentation, face clustering and protein complex detection. The objective of the problem is to cluster data points into distinct communities based on a set of measurements, each of which is associated with the values of a certain number of data points. While most of the prior works focus on a setting in which the number of data points involved in a measurement is two, this work explores a generalized setting in which the number can be more than two. Motivated by applications particularly in machine learning and channel coding, we consider two types of measurements: (1) homogeneity measurement which indicates whether or not the associated data points belong to the same community; (2) parity measurement which denotes the modulo-2 sum of the values of the data points. Such measurements are possibly corrupted by Bernoulli noise. We characterize the fundamental limits on the number of measurements required to reconstruct the communities for the considered models.
A Practically Competitive and Provably Consistent Algorithm for Uplift Modeling
Venue: arXiv cs.LG 2017
Year: 2017

Randomized experiments have been critical tools of decision making for decades. However, subjects can show significant heterogeneity in response to treatments in many important applications. Therefore it is not enough to simply know which treatment is optimal for the entire population. What we need is a model that correctly customize treatment assignment base on subject characteristics. The problem of constructing such models from randomized experiments data is known as Uplift Modeling in the literature. Many algorithms have been proposed for uplift modeling and some have generated promising results on various data sets. Yet little is known about the theoretical properties of these algorithms. In this paper, we propose a new tree-based ensemble algorithm for uplift modeling. Experiments show that our algorithm can achieve competitive results on both synthetic and industry-provided data. In addition, by properly tuning the "node size" parameter, our algorithm is proved to be consistent under mild regularity conditions. This is the first consistent algorithm for uplift modeling that we are aware of.