OpenRaiser/Intern-Atlas huggingface dataset:
How to Discreetly Spread a Rumor in a Crowd
Venue: arXiv cs.DS 2016
Year: 2016

In this paper, we study PUSH-PULL style rumor spreading algorithms in the mobile telephone model, a variant of the classical telephone model in which each node can participate in at most one connection per round; i.e., you can no longer have multiple nodes pull information from the same source in a single round. Our model also includes two new parameterized generalizations: (1) the network topology can undergo a bounded rate of change (for a parameterized rate that spans from no changes to changes in every round); and (2) in each round, each node can advertise a bounded amount of information to all of its neighbors before connection decisions are made (for a parameterized number of bits that spans from no advertisement to large advertisements). We prove that in the mobile telephone model with no advertisements and no topology changes, PUSH-PULL style algorithms perform poorly with respect to a graph's vertex expansion and graph conductance as compared to the known tight results in the classical telephone model. We then prove, however, that if nodes are allowed to advertise a single bit in each round, a natural variation of PUSH-PULL terminates in time that matches (within logarithmic factors) this strategy's performance in the classical telephone model---even in the presence of frequent topology changes. We also analyze how the performance of this algorithm degrades as the rate of change increases toward the maximum possible amount. We argue that our model matches well the properties of emerging peer-to-peer communication standards for mobile devices, and that our efficient PUSH-PULL variation that leverages small advertisements and adapts well to topology changes is a good choice for rumor spreading in this increasingly important setting.
Lowering IrGL to CUDA
Venue: arXiv cs.PL 2016
Year: 2016

The IrGL intermediate representation is an explicitly parallel representation for irregular programs that targets GPUs. In this report, we describe IrGL constructs, examples of their use and how IrGL is compiled to CUDA by the Galois GPU compiler.
Features and Kernels for Audio Event Recognition
Venue: arXiv cs.SD 2016
Year: 2016

One of the most important problems in audio event detection research is absence of benchmark results for comparison with any proposed method. Different works consider different sets of events and datasets which makes it difficult to comprehensively analyze any novel method with an existing one. In this paper we propose to establish results for audio event recognition on two recent publicly-available datasets. In particular we use Gaussian Mixture model based feature representation and combine them with linear as well as non-linear kernel Support Vector Machines.
Deploying an Information Centric Smart Lighting System in the Wild
Venue: arXiv cs.NI 2016
Year: 2016

In this paper, we present a NDN based smart home lighting solution where lights are automatically controlled in near real time based on occupancy and daylight. We implemented a reliable solution using NDN architecture exploiting the primitive NDN features in push based data dissemination, multicast forwarding through name prefixes and Interest filtering in application layer. Performance was evaluated benchmarking with respect to a cloud based approach in terms of message delivery latency. Scalability of the solution was also analyzed presenting an analysis on FIB scalability based on Interest filtering. Finally, from this study, we recommend and highlight a few requirements that could improve NDN for sustainable IoT applications.
On the Geodesic Centers of Polygonal Domains
Venue: arXiv cs.CG 2016
Year: 2016

In this paper, we study the problem of computing Euclidean geodesic centers of a polygonal domain $\mathcal{P}$ with a total of $n$ vertices. We discover many interesting observations. We give a necessary condition for a point being a geodesic center. We show that there is at most one geodesic center among all points of $\mathcal{P}$ that have topologically-equivalent shortest path maps. This implies that the total number of geodesic centers is bounded by the combinatorial size of the shortest path map equivalence decomposition of $\mathcal{P}$, which is known to be $O(n^{10})$. One key observation is a $π$-range property on shortest path lengths when points are moving. With these observations, we propose an algorithm that computes all geodesic centers in $O(n^{11}\log n)$ time. Previously, an algorithm of $O(n^{12+ε})$ time was known for this problem, for any $ε>0$.
Evaluating the Strength of Genomic Privacy Metrics
Venue: arXiv cs.CR 2016
Year: 2016

The genome is a unique identifier for human individuals. The genome also contains highly sensitive information, creating a high potential for misuse of genomic data (for example, genetic discrimination). In this paper, I investigated how genomic privacy can be measured in scenarios where an adversary aims to infer a person's genomic markers by constructing probability distributions on the values of genetic variations. I measured the strength of privacy metrics by requiring that metrics are monotonic with increasing adversary strength and uncovered serious problems with several existing metrics currently used to measure genomic privacy. I provide suggestions on metric selection, interpretation, and visualization, and illustrate the work flow using a case study on Alzheimer's disease.
Closed-Loop Estimation of Oscillator g-Sensitivity in a GNSS/IMU System
Venue: arXiv cs.SY 2016
Year: 2016

We propose a simple method for estimating crystal oscillator g-sensitivity in inertially aided Global Navigation Satellite System (GNSS) receivers. It does not require any specific equipment, like GNSS signal simulators or rate tables. The method is based on analyzing closed-loop phase tracking errors. This enables us to utilize the actual GNSS signal as the frequency reference, despite the presence of an unknown Doppler shift in it. The method has been successfully applied to the calibration of an oven-controlled crystal oscillator.
Protocol-independent critical node detection
Venue: arXiv cs.NI 2016
Year: 2016

This article explains how to construct a protocol-independent model for passing traffic through a wireless network with a single channel carrier sense multiple access/collision detection (CSMA/CD) media access model.
A Topological Lowpass Filter for Quasiperiodic Signals
Venue: arXiv cs.CV 2016
Year: 2016

This article presents a two-stage topological algorithm for recovering an estimate of a quasiperiodic function from a set of noisy measurements. The first stage of the algorithm is a topological phase estimator, which detects the quasiperiodic structure of the function without placing additional restrictions on the function. By respecting this phase estimate, the algorithm avoids creating distortion even when it uses a large number of samples for the estimate of the function.
Hashmod: A Hashing Method for Scalable 3D Object Detection
Venue: arXiv cs.CV 2016
Year: 2016

We present a scalable method for detecting objects and estimating their 3D poses in RGB-D data. To this end, we rely on an efficient representation of object views and employ hashing techniques to match these views against the input frame in a scalable way. While a similar approach already exists for 2D detection, we show how to extend it to estimate the 3D pose of the detected objects. In particular, we explore different hashing strategies and identify the one which is more suitable to our problem. We show empirically that the complexity of our method is sublinear with the number of objects and we enable detection and pose estimation of many 3D objects with high accuracy while outperforming the state-of-the-art in terms of runtime.
Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds
Venue: arXiv cs.DS 2016
Year: 2016

It was recently found that there are very close connections between the existence of additive spanners (subgraphs where all distances are preserved up to an additive stretch), distance preservers (subgraphs in which demand pairs have their distance preserved exactly), and pairwise spanners (subgraphs in which demand pairs have their distance preserved up to a multiplicative or additive stretch) [Abboud-Godwin SODA '16, Godwin-Williams SODA '16]. We study these problems from an optimization point of view, where rather than studying the existence of extremal instances we are given an instance and are asked to find the sparsest possible spanner/preserver. We give an $O(n^{3/5 + ε})$-approximation for distance preservers and pairwise spanners (for arbitrary constant $ε> 0$). This is the first nontrivial upper bound for either problem, both of which are known to be as hard to approximate as Label Cover. We also prove Label Cover hardness for approximating additive spanners, even for the cases of additive 1 stretch (where one might expect a polylogarithmic approximation, since the related multiplicative 2-spanner problem admits an $O(\log n)$-approximation) and additive polylogarithmic stretch (where the related multiplicative spanner problem has an $O(1)$-approximation). Interestingly, the techniques we use in our approximation algorithm extend beyond distance-based problem to pure connectivity network design problems. In particular, our techniques allow us to give an $O(n^{3/5 + ε})$-approximation for the Directed Steiner Forest problem (for arbitrary constant $ε> 0$) when all edges have uniform costs, improving the previous best $O(n^{2/3 + ε})$-approximation due to Berman et al.~[ICALP '11] (which holds for general edge costs).
Predicting Branch Visits and Credit Card Up-selling using Temporal Banking Data
Venue: arXiv cs.LG 2016
Year: 2016

There is an abundance of temporal and non-temporal data in banking (and other industries), but such temporal activity data can not be used directly with classical machine learning models. In this work, we perform extensive feature extraction from the temporal user activity data in an attempt to predict user visits to different branches and credit card up-selling utilizing user information and the corresponding activity data, as part of \emph{ECML/PKDD Discovery Challenge 2016 on Bank Card Usage Analysis}. Our solution ranked \nth{4} for \emph{Task 1} and achieved an AUC of \textbf{$0.7056$} for \emph{Task 2} on public leaderboard.
Improved bounds on the decoding failure probability of network coding over multi-source multi-relay networks
Venue: arXiv cs.IT 2016
Year: 2016

This paper considers a multi-source multi-relay network, in which relay nodes employ a coding scheme based on random linear network coding on source packets and generate coded packets. If a destination node collects enough coded packets, it can recover the packets of all source nodes. The links between source-to-relay nodes and relay-to-destination nodes are modeled as packet erasure channels. Improved bounds on the probability of decoding failure are presented, which are markedly close to simulation results and notably better than previous bounds. Examples demonstrate the tightness and usefulness of the new bounds over the old bounds.
Exploring phrase-compositionality in skip-gram models
Venue: arXiv cs.CL 2016
Year: 2016

In this paper, we introduce a variation of the skip-gram model which jointly learns distributed word vector representations and their way of composing to form phrase embeddings. In particular, we propose a learning procedure that incorporates a phrase-compositionality function which can capture how we want to compose phrases vectors from their component word vectors. Our experiments show improvement in word and phrase similarity tasks as well as syntactic tasks like dependency parsing using the proposed joint models.
A Multi-cut Formulation for Joint Segmentation and Tracking of Multiple Objects
Venue: arXiv cs.CV 2016
Year: 2016

Recently, Minimum Cost Multicut Formulations have been proposed and proven to be successful in both motion trajectory segmentation and multi-target tracking scenarios. Both tasks benefit from decomposing a graphical model into an optimal number of connected components based on attractive and repulsive pairwise terms. The two tasks are formulated on different levels of granularity and, accordingly, leverage mostly local information for motion segmentation and mostly high-level information for multi-target tracking. In this paper we argue that point trajectories and their local relationships can contribute to the high-level task of multi-target tracking and also argue that high-level cues from object detection and tracking are helpful to solve motion segmentation. We propose a joint graphical model for point trajectories and object detections whose Multicuts are solutions to motion segmentation {\it and} multi-target tracking problems at once. Results on the FBMS59 motion segmentation benchmark as well as on pedestrian tracking sequences from the 2D MOT 2015 benchmark demonstrate the promise of this joint approach.
Hierarchical Manifold Clustering on Diffusion Maps for Connectomics (MIT 18.S096 final project)
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we introduce a novel algorithm for segmentation of imperfect boundary probability maps (BPM) in connectomics. Our algorithm can be a considered as an extension of spectral clustering. Instead of clustering the diffusion maps with traditional clustering algorithms, we learn the manifold and compute an estimate of the minimum normalized cut. We proceed by divide and conquer. We also introduce a novel criterion for determining if further splits are necessary in a component based on it's topological properties. Our algorithm complements the currently popular agglomeration approaches in connectomics, which overlook the geometrical aspects of this segmentation problem.
Modelling Office Energy Consumption: An Agent Based Approach
Venue: arXiv cs.AI 2016
Year: 2016

In this paper, we develop an agent-based model which integrates four important elements, i.e. organisational energy management policies/regulations, energy management technologies, electric appliances and equipment, and human behaviour, based on a case study, to simulate the energy consumption in office buildings. With the model, we test the effectiveness of different energy management strategies, and solve practical office energy consumption problems. This paper theoretically contributes to an integration of four elements involved in the complex organisational issue of office energy consumption, and practically contributes to an application of agent-based approach for office building energy consumption study.
Reasoning about Body-Parts Relations for Sign Language Recognition
Venue: arXiv cs.CV 2016
Year: 2016

Over the years, hand gesture recognition has been mostly addressed considering hand trajectories in isolation. However, in most sign languages, hand gestures are defined on a particular context (body region). We propose a pipeline to perform sign language recognition which models hand movements in the context of other parts of the body captured in the 3D space using the MS Kinect sensor. In addition, we perform sign recognition based on the different hand postures that occur during a sign. Our experiments show that considering different body parts brings improved performance when compared to other methods which only consider global hand trajectories. Finally, we demonstrate that the combination of hand postures features with hand gestures features helps to improve the prediction of a given sign.
#Sleep_as_Android: Feasibility of Using Sleep Logs on Twitter for Sleep Studies
Venue: arXiv cs.HC 2016
Year: 2016

Social media enjoys a growing popularity as a platform to seek and share personal health information. For sleep studies using data from social media, most researchers focused on inferring sleep-related artifacts from self-reported anecdotal pointers to sleep patterns or issues such as insomnia. The data shared by "quantified-selfers" on social media presents an opportunity to study more quantitative and objective measures of sleep. We propose and validate the approach of collecting and analyzing sleep logs that are generated and shared through a sleep-tracking mobile application. We highlight the value of this data by combining it with users' social media data. The results provide a validation of using social media for sleep studies as the collected sleep data is aligned with sleep data from other sources. The results of combining social media data with sleep data provide preliminary evidence that higher social media activity is associated with lower sleep duration and quality.
Rate-distance tradeoff for codes above graph capacity
Venue: arXiv cs.IT 2016
Year: 2016

The capacity of a graph is defined as the rate of exponential growth of independent sets in the strong powers of the graph. In the strong power an edge connects two sequences if at each position their letters are equal or adjacent. We consider a variation of the problem where edges in the power graphs are removed between sequences which differ in more than a fraction $δ$ of coordinates. The proposed generalization can be interpreted as the problem of determining the highest rate of zero undetected-error communication over a link with adversarial noise, where only a fraction $δ$ of symbols can be perturbed and only some substitutions are allowed. We derive lower bounds on achievable rates by combining graph homomorphisms with a graph-theoretic generalization of the Gilbert-Varshamov bound. We then give an upper bound, based on Delsarte's linear programming approach, which combines Lovász' theta function with the construction used by McEliece et al. for bounding the minimum distance of codes in Hamming spaces.
A Fine-grained Indoor Location-based Social Network
Venue: arXiv cs.CY 2016
Year: 2016

Existing Location-based social networks (LBSNs), e.g., Foursquare, depend mainly on GPS or cellular-based localization to infer users' locations. However, GPS is unavailable indoors and cellular-based localization provides coarse-grained accuracy. This limits the accuracy of current LBSNs in indoor environments, where people spend 89% of their time. This in turn affects the user experience, in terms of the accuracy of the ranked list of venues, especially for the small screens of mobile devices; misses business opportunities; and leads to reduced venues coverage. In this paper, we present CheckInside: a system that can provide a fine-grained indoor location-based social network. CheckInside leverages the crowd-sensed data collected from users' mobile devices during the check-in operation and knowledge extracted from current LBSNs to associate a place with a logical name and a semantic fingerprint. This semantic fingerprint is used to obtain a more accurate list of nearby places as well as to automatically detect new places with similar signature. A novel algorithm for detecting fake check-ins and inferring a semantically-enriched floorplan is proposed as well as an algorithm for enhancing the system performance based on the user implicit feedback. Furthermore, CheckInside encompasses a coverage extender module to automatically predict names of new venues increasing the coverage of current LBSNs. Experimental evaluation of CheckInside in four malls over the course of six weeks with 20 participants shows that it can infer the actual user place within the top five venues 99% of the time. This is compared to 17% only in the case of current LBSNs. In addition, it increases the coverage of existing LBSNs by more than 37%.
An Interesting Gadget for Chain Pair Simplification
Venue: arXiv cs.CG 2016
Year: 2016

In this paper we present an interesting gadget based on the chain pair simplification problem under the discrete Fréchet distance (CPS-3F), which allows the construction of arbitrarily long paths that must be chosen in the simplification of the two curves. A pseudopolynomial time reduction from set partition is given as an example. For clarification, CPS-3F was recently shown to be in \textbf{P}, and the reduction is merely to show how the gadget works.
LWB and FS-LWB implementation for Sky platform using Contiki
Venue: arXiv cs.NI 2016
Year: 2016

The low-power wireless bus (LWB) is a highly efficient communication protocol for wireless sensor networks (WSN). However, a lack of open implementation for this protocol prompted the implementation of the protocol for the most common platform of WSN related research, the sky nodes using the Contiki operating system. This document provides the detailed description of the implementation. A forwarder-selection mechanism is developed to improve energy-efficiency of LWB in data collection scenario. The implementation also consists the forwarder selection mechanism. One can either use the original features of LWB or enforce the forwarder selection mechanism.
Cloud Service Matchmaking using Constraint Programming
Venue: arXiv cs.DC 2016
Year: 2016

Service requesters with limited technical knowledge should be able to compare services based on their quality of service (QoS) requirements in cloud service marketplaces. Existing service matching approaches focus on QoS requirements as discrete numeric values and intervals. The analysis of existing research on non-functional properties reveals two improvement opportunities: list-typed QoS properties as well as explicit handling of preferences for lower or higher property values. We develop a concept and constraint models for a service matcher which contributes to existing approaches by addressing these issues using constraint solvers. The prototype uses an API at the standardisation stage and discovers implementation challenges. This paper concludes that constraint solvers provide a valuable tool to solve the service matching problem with soft constraints and are capable of covering all QoS property types in our analysis. Our approach is to be further investigated in the application context of cloud federations.
Fast Longest Common Extensions in Small Space
Venue: arXiv cs.DS 2016
Year: 2016

In this paper we address the longest common extension (LCE) problem: to compute the length $\ell$ of the longest common prefix between any two suffixes of $T\in Σ^n$ with $ Σ= \{0, \ldots σ-1\} $. We present two fast and space-efficient solutions based on (Karp-Rabin) \textit{fingerprinting} and \textit{sampling}. Our first data structure exploits properties of Mersenne prime numbers when used as moduli of the Karp-Rabin hash function and takes $n\lceil \log_2σ\rceil$ bits of space. Our second structure works with any prime modulus and takes $n\lceil \log_2σ\rceil + n/w + w\log_2 n$ bits of space ($ w $ memory-word size). Both structures support $\mathcal O\left(m\logσ/w \right)$-time extraction of any length-$m$ text substring, $\mathcal O(\log\ell)$-time LCE queries with high probability, and can be built in optimal $\mathcal O(n)$ time. In the first case, ours is the first result showing that it is possible to answer LCE queries in $o(n)$ time while using only $\mathcal O(1)$ words on top of the space required to store the text. Our results improve the state of the art in space usage, query times, and preprocessing times and are extremely practical: we present a C++ implementation that is very fast and space-efficient in practice.