OpenRaiser/Intern-Atlas huggingface dataset:
Energy Harvesting Networks with Energy Cooperation: Procrastinating Policies
Venue: arXiv cs.IT 2015
Year: 2015

This paper considers multiterminal networks with energy harvesting transmitter nodes that are also capable of wirelessly transferring energy to or receiving energy from other nodes in the network. In particular, the jointly optimal transmit power and energy transfer policies that maximize sum-throughput for the two-way, two-hop, and multiple access channels are identified. It is shown for nodes with infinite-sized batteries that delaying energy transfers until energy is needed immediately at the receiving node is sum-throughput optimal. Focusing on such procrastinating policies without loss of optimality, the stated joint optimization problem can be decomposed into energy transfer and consumed energy allocation problems which are solved in tandem. This decomposition is shown to hold for the finite-sized battery case as well, using partially procrastinating policies that avoid battery overflows. It is observed that for the two-hop channel, the proposed algorithm has a two fluid water-filling interpretation, and for the multiple access channel, it reduces to a single transmitter problem with aggregate energy arrivals. Numerical results demonstrate the throughput improvement with bi-directional energy cooperation over no cooperation and uni-directional cooperation.
Tight space-noise tradeoffs in computing the ergodic measure
Venue: arXiv cs.CC 2015
Year: 2015

In this note we obtain tight bounds on the space-complexity of computing the ergodic measure of a low-dimensional discrete-time dynamical system affected by Gaussian noise. If the scale of the noise is $\varepsilon$, and the function describing the evolution of the system is not by itself a source of computational complexity, then the density function of the ergodic measure can be approximated within precision $δ$ in space polynomial in $\log 1/\varepsilon+\log\log 1/δ$. We also show that this bound is tight up to polynomial factors. In the course of showing the above, we prove a result of independent interest in space-bounded computation: that it is possible to exponentiate an $n$ by $n$ matrix to an exponentially large power in space polylogarithmic in $n$.
Exploiting Social Trust Assisted Reciprocity (STAR) towards Utility-Optimal Socially-aware Crowdsensing
Venue: arXiv cs.NI 2015
Year: 2015

Mobile crowdsensing takes advantage of pervasive mobile devices to collect and process data for a variety of applications (e.g., traffic monitoring, spectrum sensing). In this study, a socially-aware crowdsensing system is advocated, in which a cloud-based platform incentivizes mobile users to participate in sensing tasks} by leveraging social trust among users, upon receiving sensing requests. For this system, social trust assisted reciprocity (STAR) - a synergistic marriage of social trust and reciprocity, is exploited to design an incentive mechanism that stimulates users' participation. Given the social trust structure among users, the efficacy of STAR for satisfying users' sensing requests is thoroughly investigated. Specifically, it is first shown that all requests can be satisfied if and only if sufficient social credit can be "transferred" from users who request more sensing service than they can provide to users who can provide more than they request. Then utility maximization for sensing services under STAR is investigated, and it is shown that it boils down to maximizing the utility of a circulation flow in the combined social graph and request graph. Accordingly, an algorithm that iteratively cancels a cycle of positive weight in the residual graph is developed, which computes the optimal solution efficiently, for both cases of divisible and indivisible sensing service. Extensive simulation results corroborate that STAR can significantly outperform the mechanisms using social trust only or reciprocity only.
Necessary and Sufficient Conditions and a Provably Efficient Algorithm for Separable Topic Discovery
Venue: arXiv cs.LG 2015
Year: 2015

We develop necessary and sufficient conditions and a novel provably consistent and efficient algorithm for discovering topics (latent factors) from observations (documents) that are realized from a probabilistic mixture of shared latent factors that have certain properties. Our focus is on the class of topic models in which each shared latent factor contains a novel word that is unique to that factor, a property that has come to be known as separability. Our algorithm is based on the key insight that the novel words correspond to the extreme points of the convex hull formed by the row-vectors of a suitably normalized word co-occurrence matrix. We leverage this geometric insight to establish polynomial computation and sample complexity bounds based on a few isotropic random projections of the rows of the normalized word co-occurrence matrix. Our proposed random-projections-based algorithm is naturally amenable to an efficient distributed implementation and is attractive for modern web-scale distributed data mining applications.
Learning Sampling Distributions for Efficient Object Detection
Venue: arXiv cs.CV 2015
Year: 2015

Object detection is an important task in computer vision and learning systems. Multistage particle windows (MPW), proposed by Gualdi et al., is an algorithm of fast and accurate object detection. By sampling particle windows from a proposal distribution (PD), MPW avoids exhaustively scanning the image. Despite its success, it is unknown how to determine the number of stages and the number of particle windows in each stage. Moreover, it has to generate too many particle windows in the initialization step and it redraws unnecessary too many particle windows around object-like regions. In this paper, we attempt to solve the problems of MPW. An important fact we used is that there is large probability for a randomly generated particle window not to contain the object because the object is a sparse event relevant to the huge number of candidate windows. Therefore, we design the proposal distribution so as to efficiently reject the huge number of non-object windows. Specifically, we propose the concepts of rejection, acceptance, and ambiguity windows and regions. This contrasts to MPW which utilizes only on region of support. The PD of MPW is acceptance-oriented whereas the PD of our method (called iPW) is rejection-oriented. Experimental results on human and face detection demonstrate the efficiency and effectiveness of the iPW algorithm. The source code is publicly accessible.
Socially-Aware Distributed Hash Tables for Decentralized Online Social Networks
Venue: arXiv cs.DC 2015
Year: 2015

Many decentralized online social networks (DOSNs) have been proposed due to an increase in awareness related to privacy and scalability issues in centralized social networks. Such decentralized networks transfer processing and storage functionalities from the service providers towards the end users. DOSNs require individualistic implementation for services, (i.e., search, information dissemination, storage, and publish/subscribe). However, many of these services mostly perform social queries, where OSN users are interested in accessing information of their friends. In our work, we design a socially-aware distributed hash table (DHTs) for efficient implementation of DOSNs. In particular, we propose a gossip-based algorithm to place users in a DHT, while maximizing the social awareness among them. Through a set of experiments, we show that our approach reduces the lookup latency by almost 30% and improves the reliability of the communication by nearly 10% via trusted contacts.
FreeNet: Spectrum and Energy Harvesting Wireless Networks
Venue: arXiv cs.NI 2015
Year: 2015

The dramatic mobile data traffic growth is not only resulting in the spectrum crunch but is also leading to exorbitant energy consumption. It is thus desirable to liberate mobile and wireless networks from the constraint of the spectrum scarcity and to rein in the growing energy consumption. This article introduces FreeNet, figuratively synonymous to "Free Network", which engineers the spectrum and energy harvesting techniques to alleviate the spectrum and energy constraints by sensing and harvesting spare spectrum for data communications and utilizing renewable energy as power supplies, respectively. Hence, FreeNet increases the spectrum and energy efficiency of wireless networks and enhances the network availability. As a result, FreeNet can be deployed to alleviate network congestion in urban areas, provision broadband services in rural areas, and upgrade emergency communication capacity. This article provides a brief analysis of the design of FreeNet that accommodates the dynamics of the spare spectrum and employs renewable energy.
Detecting and Preventing "Multiple-Account" Cheating in Massive Open Online Courses
Venue: arXiv cs.CY 2015
Year: 2015

We describe a cheating strategy enabled by the features of massive open online courses (MOOCs) and detectable by virtue of the sophisticated data systems that MOOCs provide. The strategy, Copying Answers using Multiple Existences Online (CAMEO), involves a user who gathers solutions to assessment questions using a "harvester" account and then submits correct answers using a separate "master" account. We use "clickstream" learner data to detect CAMEO use among 1.9 million course participants in 115 MOOCs from two universities. Using conservative thresholds, we estimate CAMEO prevalence at 1,237 certificates, accounting for 1.3% of the certificates in the 69 MOOCs with CAMEO users. Among earners of 20 or more certificates, 25% have used the CAMEO strategy. CAMEO users are more likely to be young, male, and international than other MOOC certificate earners. We identify preventive strategies that can decrease CAMEO rates and show evidence of their effectiveness in science courses.
An Experimental Study of Distributed Quantile Estimation
Venue: arXiv cs.DB 2015
Year: 2015

Quantiles are very important statistics information used to describe the distribution of datasets. Given the quantiles of a dataset, we can easily know the distribution of the dataset, which is a fundamental problem in data analysis. However, quite often, computing quantiles directly is inappropriate due to the memory limitations. Further, in many settings such as data streaming and sensor network model, even the data size is unpredictable. Although the quantiles computation has been widely studied, it was mostly in the sequential setting. In this paper, we study several quantile computation algorithms in the distributed setting and compare them in terms of space usage, running time, and accuracy. Moreover, we provide detailed experimental comparisons between several popular algorithms. Our work focuses on the approximate quantile algorithms which provide error bounds. Approximate quantiles have received more attentions than exact ones since they are often faster, can be more easily adapted to the distributed setting while giving sufficiently good statistical information on the data sets.
Joint Frequency Estimation with Two Sub-Nyquist Sampling Sequences
Venue: arXiv cs.IT 2015
Year: 2015

In many applications of frequency estimation, the frequencies of the signals are so high that the data sampled at Nyquist rate are hard to acquire due to hardware limitation. In this paper, we propose a novel method based on subspace techniques to estimate the frequencies by using two sub-Nyquist sample sequences, provided that the two under-sampled ratios are relatively prime integers. We analyze the impact of under-sampling and expand the estimated frequencies which suffer from aliasing. Through jointing the results estimated from these two sequences, the frequencies approximate to the frequency components really contained in the signals are screened. The method requires a small quantity of hardware and calculation. Numerical results show that this method is valid and accurate at quite low sampling rates.
Multi-round Master-Worker Computing: a Repeated Game Approach
Venue: arXiv cs.DC 2015
Year: 2015

We consider a computing system where a master processor assigns tasks for execution to worker processors through the Internet. We model the workers decision of whether to comply (compute the task) or not (return a bogus result to save the computation cost) as a mixed extension of a strategic game among workers. That is, we assume that workers are rational in a game-theoretic sense, and that they randomize their strategic choice. Workers are assigned multiple tasks in subsequent rounds. We model the system as an infinitely repeated game of the mixed extension of the strategic game. In each round, the master decides stochastically whether to accept the answer of the majority or verify the answers received, at some cost. Incentives and/or penalties are applied to workers accordingly. Under the above framework, we study the conditions in which the master can reliably obtain tasks results, exploiting that the repeated games model captures the effect of long-term interaction. That is, workers take into account that their behavior in one computation will have an effect on the behavior of other workers in the future. Indeed, should a worker be found to deviate from some agreed strategic choice, the remaining workers would change their own strategy to penalize the deviator. Hence, being rational, workers do not deviate. We identify analytically the parameter conditions to induce a desired worker behavior, and we evaluate experi- mentally the mechanisms derived from such conditions. We also compare the performance of our mechanisms with a previously known multi-round mechanism based on reinforcement learning.
Euskahaldun: Euskararen Aldeko Martxa Baten Sare Sozialetako Islaren Bilketa eta Analisia
Venue: arXiv cs.SI 2015
Year: 2015

This work is motivated by the dearth of research that deals with social media content created from the Basque Country or written in Basque language. While social fingerprints during events have been analysed in numerous other locations and languages, this article aims to fill this gap so as to initiate a much-needed research area within the Basque scientific community. To this end, we describe the methodology we followed to collect tweets posted during the quintessential exhibition race in support of the Basque language. We also present the results of the analysis of these tweets. Our analysis shows that the most eventful moments lead to spikes in tweeting activity, producing more tweets. Furthermore, we emphasize the importance of having an official account for the event in question, which helps improve the visibility of the event in the social network as well as the dissemination of information to the Basque community. Along with the official account, journalists and news organisations play a crucial role in the diffusion of information.
Stochastic Behavior of the Nonnegative Least Mean Fourth Algorithm for Stationary Gaussian Inputs and Slow Learning
Venue: arXiv cs.NA 2015
Year: 2015

Some system identification problems impose nonnegativity constraints on the parameters to estimate due to inherent physical characteristics of the unknown system. The nonnegative least-mean-square (NNLMS) algorithm and its variants allow to address this problem in an online manner. A nonnegative least mean fourth (NNLMF) algorithm has been recently proposed to improve the performance of these algorithms in cases where the measurement noise is not Gaussian. This paper provides a first theoretical analysis of the stochastic behavior of the NNLMF algorithm for stationary Gaussian inputs and slow learning. Simulation results illustrate the accuracy of the proposed analysis.
gScan: Accelerating Graham Scan on the GPU
Venue: arXiv cs.CG 2015
Year: 2015

This paper presents a fast implementation of the Graham scan on the GPU. The proposed algorithm is composed of two stages: (1) two rounds of preprocessing performed on the GPU and (2) the finalization of finding the convex hull on the CPU. We first discard the interior points that locate inside a quadrilateral formed by four extreme points, sort the remaining points according to the angles, and then divide them into the left and the right regions. For each region, we perform a second round of filtering using the proposed preprocessing approach to discard the interior points in further. We finally obtain the expected convex hull by calculating the convex hull of the remaining points on the CPU. We directly employ the parallel sorting, reduction, and partitioning provided by the library Thrust for better efficiency and simplicity. Experimental results show that our implementation achieves 6x ~ 7x speedups over the Qhull implementation for 20M points.
STAC: Simultaneous Transmitting and Air Computing in Wireless Data Center Networks
Venue: arXiv cs.NI 2015
Year: 2015

The data center network (DCN), wired or wireless, features large amounts of Many-to-One (M2O) sessions. Each M2O session is currently operated based on Point-to-Point (P2P) communications and Store-and-Forward (SAF) relays, and is generally followed by certain further computation at the destination. %typically a weighted summation of the received digits. Different from this separate P2P/SAF-based-transmission and computation strategy, this paper proposes STAC, a novel physical layer scheme that achieves Simultaneous Transmission and Air Computation in wireless DCNs. In particular, STAC takes advantage of the superposition nature of electromagnetic (EM) waves, and allows multiple transmitters to transmit in the same time slot with appropriately chosen parameters, such that the received superimposed signal can be directly transformed to the needed summation at the receiver. Exploiting the static channel environment and compact space in DCN, we propose an enhanced Software Defined Network (SDN) architecture to enable STAC, where wired connections are established to provide the wireless transceivers external reference signals. Theoretical analysis and simulation show that with STAC used, both the bandwidth and energy efficiencies can be improved severalfold.
Formulations and algorithms for the multiple depot, fuel-constrained, multiple vehicle routing problem
Venue: arXiv cs.DS 2015
Year: 2015

We consider a multiple depot, multiple vehicle routing problem with fuel constraints. We are given a set of targets, a set of depots and a set of homogeneous vehicles, one for each depot. The depots are also allowed to act as refueling stations. The vehicles are allowed to refuel at any depot, and our objective is to determine a route for each vehicle with a minimum total cost such that each target is visited at least once by some vehicle, and the vehicles never run out fuel as it traverses its route. We refer this problem as Multiple Depot, Fuel-Constrained, Multiple Vehicle Routing Problem (FCMVRP). This paper presents four new mixed integer linear programming formulations to compute an optimal solution for the problem. Extensive computational results for a large set of instances are also presented.
Visualizing NLP annotations for Crowdsourcing
Venue: arXiv cs.CL 2015
Year: 2015

Visualizing NLP annotation is useful for the collection of training data for the statistical NLP approaches. Existing toolkits either provide limited visual aid, or introduce comprehensive operators to realize sophisticated linguistic rules. Workers must be well trained to use them. Their audience thus can hardly be scaled to large amounts of non-expert crowdsourced workers. In this paper, we present CROWDANNO, a visualization toolkit to allow crowd-sourced workers to annotate two general categories of NLP problems: clustering and parsing. Workers can finish the tasks with simplified operators in an interactive interface, and fix errors conveniently. User studies show our toolkit is very friendly to NLP non-experts, and allow them to produce high quality labels for several sophisticated problems. We release our source code and toolkit to spur future research.
Unsatisfiable Cores and Lower Bounding for Constraint Programming
Venue: arXiv cs.LO 2015
Year: 2015

Constraint Programming (CP) solvers typically tackle optimization problems by repeatedly finding solutions to a problem while placing tighter and tighter bounds on the solution cost. This approach is somewhat naive, especially for soft-constraint optimization problems in which the soft constraints are mostly satisfied. Unsatisfiable-core approaches to solving soft constraint problems in SAT (e.g. MAXSAT) force all soft constraints to be hard initially. When solving fails they return an unsatisfiable core, as a set of soft constraints that cannot hold simultaneously. These are reverted to soft and solving continues. Since lazy clause generation solvers can also return unsatisfiable cores we can adapt this approach to constraint programming. We adapt the original MAXSAT unsatisfiable core solving approach to be usable for constraint programming and define a number of extensions. Experimental results show that our methods are beneficial on a broad class of CP-optimization benchmarks involving soft constraints, cardinality or preferences.
BREN: Body Reflection Essence-Neuter Model for Separation of Reflection Components
Venue: arXiv cs.CV 2015
Year: 2015

We propose a novel reflection color model consisting of body essence and (mixed) neuter, and present an effective method for separating dichromatic reflection components using a single image. Body essence is an entity invariant to interface reflection, and has two degrees of freedom unlike hue and maximum chromaticity. As a result, the proposed method is insensitive to noise and proper for colors around CMY (cyan, magenta, and yellow) as well as RGB (red, green, and blue), contrary to the maximum chromaticity-based methods. Interface reflection is separated by using a Gaussian function, which removes a critical thresholding problem. Furthermore, the method does not require any region segmentation. Experimental results show the efficacy of the proposed model and method.
PolyDepth: Real-time Penetration Depth Computation using Iterative Contact-Space Projection
Venue: arXiv cs.GR 2015
Year: 2015

We present a real-time algorithm that finds the Penetration Depth (PD) between general polygonal models based on iterative and local optimization techniques. Given an in-collision configuration of an object in configuration space, we find an initial collision-free configuration using several methods such as centroid difference, maximally clear configuration, motion coherence, random configuration, and sampling-based search. We project this configuration on to a local contact space using a variant of continuous collision detection algorithm and construct a linear convex cone around the projected configuration. We then formulate a new projection of the in-collision configuration onto the convex cone as a Linear Complementarity Problem (LCP), which we solve using a type of Gauss-Seidel iterative algorithm. We repeat this procedure until a locally optimal PD is obtained. Our algorithm can process complicated models consisting of tens of thousands triangles at interactive rates.