OpenRaiser/Intern-Atlas huggingface dataset:
A Latent Social Approach to YouTube Popularity Prediction
Venue: arXiv cs.SI 2013
Year: 2013

Current works on Information Centric Networking assume the spectrum of caching strategies under the Least Recently/ Frequently Used (LRFU) scheme as the de-facto standard, due to the ease of implementation and easier analysis of such strategies. In this paper we predict the popularity distribution of YouTube videos within a campus network. We explore two broad approaches in predicting the popularity of videos in the network: consensus approaches based on aggregate behavior in the network, and social approaches based on the information diffusion over an implicit network. We measure the performance of our approaches under a simple caching framework by picking the k most popular videos according to our predicted distribution and calculating the hit rate on the cache. We develop our approach by first incorporating video inter-arrival time (based on the power-law distribution governing the transmission time between two receivers of the same message in scale-free networks) to the baseline (LRFU), then combining with an information diffusion model over the inferred latent social graph that governs diffusion of videos in the network. We apply techniques from latent social network inference to learn the sharing probabilities between users in the network and apply a virus propagation model borrowed from mathematical epidemiology to estimate the number of times a video will be accessed in the future. Our approach gives rise to a 14% hit rate improvement over the baseline.
Interference Reduction in High Density WLAN Deployments using antenna Selection
Venue: arXiv cs.NI 2013
Year: 2013

In this work, we present a novel, robust scheme for high density WLAN deployments. This scheme uses well known selection diversity at the transmitter. We show that our scheme increases the number of simultaneous transmissions at any given time without excessive overhead (compared to other schemes such as Multi-user MIMO). Furthermore, this scheme can be easily implemented using existing standards.
Invitation to Ezhil: A Tamil Programming Language for Early Computer-Science Education
Venue: arXiv cs.CY 2013
Year: 2013

Ezhil is a Tamil programming language with support for imperative programming, with mixed use of Tamil and English identifiers and function-names. Ezhil programing system is targeted toward the K-12 (junior high-school) level Tamil speaking students, as an early introduction to thinking like a computer-scientist. We believe this 'numeracy' knowledge is easily transferred over from a native language (Tamil) to the pervasive English language programming systems, in Java, dot-Net, Ruby or Python. Ezhil is an effort to improve access to computing in the 21st Century.
Power Control and Coding Formulation for State Estimation with Wireless Sensors
Venue: arXiv cs.IT 2013
Year: 2013

Technological advances have made wireless sensors cheap and reliable enough to be brought into industrial use. A major challenge arises from the fact that wireless channels introduce random packet dropouts. Power control and coding are key enabling technologies in wireless communications to ensure efficient communications. In the present work, we examine the role of power control and coding for Kalman filtering over wireless correlated channels. Two estimation architectures are considered: In the first, the sensors send their measurements directly to a single gateway. In the second scheme, wireless relay nodes provide additional links. The gateway decides on the coding scheme and the transmitter power levels of the wireless nodes. The decision process is carried out on-line and adapts to varying channel conditions in order to improve the trade-off between state estimation accuracy and energy expenditure. In combination with predictive power control, we investigate the use of multiple-description coding, zero-error coding and network coding and provide sufficient conditions for the expectation of the estimation error covariance matrix to be bounded. Numerical results suggest that the proposed method may lead to energy savings of around 50 %, when compared to an alternative scheme, wherein transmission power levels and bit-rates are governed by simple logic. In particular, zero-error coding is preferable at time instances with high channel gains, whereas multiple-description coding is superior for time instances with low gains. When channels between the sensors and the gateway are in deep fades, network coding improves estimation accuracy significantly without sacrificing energy efficiency.
Online Decision Making in Crowdsourcing Markets: Theoretical Challenges (Position Paper)
Venue: arXiv cs.SI 2013
Year: 2013

Over the past decade, crowdsourcing has emerged as a cheap and efficient method of obtaining solutions to simple tasks that are difficult for computers to solve but possible for humans. The popularity and promise of crowdsourcing markets has led to both empirical and theoretical research on the design of algorithms to optimize various aspects of these markets, such as the pricing and assignment of tasks. Much of the existing theoretical work on crowdsourcing markets has focused on problems that fall into the broad category of online decision making; task requesters or the crowdsourcing platform itself make repeated decisions about prices to set, workers to filter out, problems to assign to specific workers, or other things. Often these decisions are complex, requiring algorithms that learn about the distribution of available tasks or workers over time and take into account the strategic (or sometimes irrational) behavior of workers. As human computation grows into its own field, the time is ripe to address these challenges in a principled way. However, it appears very difficult to capture all pertinent aspects of crowdsourcing markets in a single coherent model. In this paper, we reflect on the modeling issues that inhibit theoretical research on online decision making for crowdsourcing, and identify some steps forward. This paper grew out of the authors' own frustration with these issues, and we hope it will encourage the community to attempt to understand, debate, and ultimately address them. The authors welcome feedback for future revisions of this paper.
Tweeting biomedicine: an analysis of tweets and citations in the biomedical literature
Venue: arXiv cs.DL 2013
Year: 2013

Data collected by social media platforms have recently been introduced as a new source for indicators to help measure the impact of scholarly research in ways that are complementary to traditional citation-based indicators. Data generated from social media activities related to scholarly content can be used to reflect broad types of impact. This paper aims to provide systematic evidence regarding how often Twitter is used to diffuse journal articles in the biomedical and life sciences. The analysis is based on a set of 1.4 million documents covered by both PubMed and Web of Science (WoS) and published between 2010 and 2012. The number of tweets containing links to these documents was analyzed to evaluate the degree to which certain journals, disciplines, and specialties were represented on Twitter. It is shown that, with less than 10% of PubMed articles mentioned on Twitter, its uptake is low in general. The relationship between tweets and WoS citations was examined for each document at the level of journals and specialties. The results show that tweeting behavior varies between journals and specialties and correlations between tweets and citations are low, implying that impact metrics based on tweets are different from those based on citations. A framework utilizing the coverage of articles and the correlation between Twitter mentions and citations is proposed to facilitate the evaluation of novel social-media based metrics and to shed light on the question in how far the number of tweets is a valid metric to measure research impact.
Developing and Testing the Automated Post-Event Earthquake Loss Estimation and Visualisation (APE-ELEV) Technique
Venue: arXiv cs.CY 2013
Year: 2013

An automated, real-time, multiple sensor data source relying and globally applicable earthquake loss model and visualiser is desirable for post-event earthquake analysis. To achieve this there is a need to support rapid data ingestion, loss estimation and integration of data from multiple data sources and rapid visualisation at multiple geographic levels. In this paper, the design and development of the Automated Post-Event Earthquake Loss Estimation and Visualisation (APE-ELEV) system for real-time estimation and visualisation of insured losses incurred due to earthquakes is presented. A model for estimating ground up and net of facultative losses due to earthquakes in near real-time is implemented. Since post-event data is often available immediately from multiple disparate sources, a geo-browser is employed to facilitate the visualisation and integration of earthquake hazard, exposure and loss data. The feasibility of APE-ELEV is demonstrated using a test case earthquake that occurred in Tohoku, Japan (2011). The APE-ELEV model is further validated for ten global earthquakes using industry loss data.
PANAS-t: A Pychometric Scale for Measuring Sentiments on Twitter
Venue: arXiv cs.SI 2013
Year: 2013

Online social networks have become a major communication platform, where people share their thoughts and opinions about any topic real-time. The short text updates people post in these network contain emotions and moods, which when measured collectively can unveil the public mood at population level and have exciting implications for businesses, governments, and societies. Therefore, there is an urgent need for developing solid methods for accurately measuring moods from large-scale social media data. In this paper, we propose PANAS-t, which measures sentiments from short text updates in Twitter based on a well-established psychometric scale, PANAS (Positive and Negative Affect Schedule). We test the efficacy of PANAS-t over 10 real notable events drawn from 1.8 billion tweets and demonstrate that it can efficiently capture the expected sentiments of a wide variety of issues spanning tragedies, technology releases, political debates, and healthcare.
Strand-Based Approach to Patch Security Protocols
Venue: arXiv cs.CR 2013
Year: 2013

In this paper, we introduce a mechanism that aims to speed up the development cycle of security protocols, by adding automated aid for diagnosis and repair. Our mechanism relies on existing verification tools analyzing intermediate protocols and synthesizing potential attacks if the protocol is flawed. The analysis of these attacks (including type flaw attacks) pinpoints the source of the failure and controls the synthesis of appropriate patches to the protocol. Using strand spaces, we have developed general guidelines for protocol repair, and captured them into formal requirements on (sets of) protocol steps. For each requirement, there is a collection of rules that transform a set of protocol steps violating the requirement into a set conforming it. We have implemented our mechanism into a tool, called SHRIMP. We have successfully tested SHRIMP on numerous faulty protocols, all of which were successfully repaired, fully automatically.
Citation Counts and Evaluation of Researchers in the Internet Age
Venue: arXiv cs.DL 2013
Year: 2013

Bibliometric measures derived from citation counts are increasingly being used as a research evaluation tool. Their strengths and weaknesses have been widely analyzed in the literature and are often subject of vigorous debate. We believe there are a few fundamental issues related to the impact of the web that are not taken into account with the importance they deserve. We focus on evaluation of researchers, but several of our arguments may be applied also to evaluation of research institutions as well as of journals and conferences.
Evolution of IEEE 802.11 compatible standards and impact on Energy Consumption
Venue: arXiv cs.NI 2013
Year: 2013

Over the last decade, the IEEE 802.11 has emerged as the most popular protocol in the wireless domain. Since the release of the first standard version, several amendments have been introduced in an effort to improve its throughput performance, with the most recent one being the IEEE 802.11n extension. In this work, we present detailed experimentally obtained measurements that evaluate the energy efficiency of the base standard in comparison with the latest 802.11n version. Moreover, we investigate the impact of various MAC layer enhancements, both vendor specific and standard compliant ones, on the energy consumption of wireless transceivers and total nodes as well. Results obtained under a wide range of settings, indicate that the latest standard enables reduction of energy expenditure, by more than 75%, when combined with innovative frame aggregation mechanisms.
Finite p-groups, entropy vectors and the Ingleton inequality for nilpotent groups
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we study the capacity/entropy region of finite, directed, acyclic, multiple-sources, multiple-sinks network by means of group theory and entropy vectors coming from groups. There is a one-to-one correspondence between the entropy vector of a collection of n random variables and a certain group-characterizable vector obtained from a finite group and n of its subgroups. We are looking at nilpotent group characterizable entropy vectors and show that they are all also Abelian group characterizable, and hence they satisfy the Ingleton inequality. It is known that not all entropic vectors can be obtained from Abelian groups, so our result implies that in order to get more exotic entropic vectors, one has to go at least to soluble groups or larger nilpotency classes. The result also implies that Ingleton inequality is satisfied by nilpotent groups of bounded class, depending on the order of the group.
In-Core Computation of Geometric Centralities with HyperBall: A Hundred Billion Nodes and Beyond
Venue: arXiv cs.DS 2013
Year: 2013

Given a social network, which of its nodes are more central? This question has been asked many times in sociology, psychology and computer science, and a whole plethora of centrality measures (a.k.a. centrality indices, or rankings) were proposed to account for the importance of the nodes of a network. In this paper, we approach the problem of computing geometric centralities, such as closeness and harmonic centrality, on very large graphs; traditionally this task requires an all-pairs shortest-path computation in the exact case, or a number of breadth-first traversals for approximated computations, but these techniques yield very weak statistical guarantees on highly disconnected graphs. We rather assume that the graph is accessed in a semi-streaming fashion, that is, that adjacency lists are scanned almost sequentially, and that a very small amount of memory (in the order of a dozen bytes) per node is available in core memory. We leverage the newly discovered algorithms based on HyperLogLog counters, making it possible to approximate a number of geometric centralities at a very high speed and with high accuracy. While the application of similar algorithms for the approximation of closeness was attempted in the MapReduce framework, our exploitation of HyperLogLog counters reduces exponentially the memory footprint, paving the way for in-core processing of networks with a hundred billion nodes using "just" 2TiB of RAM. Moreover, the computations we describe are inherently parallelizable, and scale linearly with the number of available cores.
Surprise: Youve got some explaining to do
Venue: arXiv cs.AI 2013
Year: 2013

Why are some events more surprising than others? We propose that events that are more difficult to explain are those that are more surprising. The two experiments reported here test the impact of different event outcomes (Outcome-Type) and task demands (Task) on ratings of surprise for simple story scenarios. For the Outcome-Type variable, participants saw outcomes that were either known or less-known surprising outcomes for each scenario. For the Task variable, participants either answered comprehension questions or provided an explanation of the outcome. Outcome-Type reliably affected surprise judgments; known outcomes were rated as less surprising than less-known outcomes. Task also reliably affected surprise judgments; when people provided an explanation it lowered surprise judgments relative to simply answering comprehension questions. Both experiments thus provide evidence on this less-explored explanation aspect of surprise, specifically showing that ease of explanation is a key factor in determining the level of surprise experienced.
Cognitive residues of similarity
Venue: arXiv cs.AI 2013
Year: 2013

What are the cognitive after-effects of making a similarity judgement? What, cognitively, is left behind and what effect might these residues have on subsequent processing? In this paper, we probe for such after-effects using a visual search task, performed after a task in which pictures of real-world objects were compared. So, target objects were first presented in a comparison task (e.g., rate the similarity of this object to another) thus, presumably, modifying some of their features before asking people to visually search for the same object in complex scenes (with distractors and camouflaged backgrounds). As visual search is known to be influenced by the features of target objects, then any after-effects of the comparison task should be revealed in subsequent visual searches. Results showed that when people previously rated an object as being high on a scale (e.g., colour similarity or general similarity) then visual search is inhibited (slower RTs and more saccades in eye-tracking) relative to an object being rated as low in the same scale. There was also some evidence that different comparison tasks (e.g., compare on colour or compare on general similarity) have differential effects on visual search.
Lossless Data Compression with Error Detection using Cantor Set
Venue: arXiv cs.IT 2013
Year: 2013

In 2009, a lossless compression algorithm based on 1D chaotic maps known as Generalized Luröth Series (or GLS) has been proposed. This algorithm (GLS-coding) encodes the input message as a symbolic sequence on an appropriate 1D chaotic map (GLS) and the compressed file is obtained as the initial value by iterating backwards on the map. For ergodic sources, it was shown that GLS-coding achieves the best possible lossless compression (in the noiseless setting) bounded by Shannon entropy. However, in the presence of noise, even small errors in the compressed file leads to catastrophic decoding errors owing to sensitive dependence on initial values. In this paper, we first show that Repetition codes $\mathcal{R}_n$ (every symbol is repeated $n$ times, where $n$ is a positive odd integer), the oldest and the most basic error correction and detection codes in literature, actually lie on a Cantor set with a fractal dimension of $\frac{1}{n}$, which is also the rate of the code. Inspired by this, we incorporate error detection capability to GLS-coding by ensuring that the compressed file (initial value on the map) lies on a Cantor set of measure zero. Even a 1-bit error in the initial value will throw it outside the Cantor set which can be detected while decoding. The error detection performance (and also the rate of the code) can be controlled by the fractal dimension of the Cantor set and could be suitably adjusted depending on the noise level of the communication channel.
High-Dimensional Regression with Gaussian Mixtures and Partially-Latent Response Variables
Venue: arXiv cs.LG 2013
Year: 2013

In this work we address the problem of approximating high-dimensional data with a low-dimensional representation. We make the following contributions. We propose an inverse regression method which exchanges the roles of input and response, such that the low-dimensional variable becomes the regressor, and which is tractable. We introduce a mixture of locally-linear probabilistic mapping model that starts with estimating the parameters of inverse regression, and follows with inferring closed-form solutions for the forward parameters of the high-dimensional regression problem of interest. Moreover, we introduce a partially-latent paradigm, such that the vector-valued response variable is composed of both observed and latent entries, thus being able to deal with data contaminated by experimental artifacts that cannot be explained with noise models. The proposed probabilistic formulation could be viewed as a latent-variable augmentation of regression. We devise expectation-maximization (EM) procedures based on a data augmentation strategy which facilitates the maximum-likelihood search over the model parameters. We propose two augmentation schemes and we describe in detail the associated EM inference procedures that may well be viewed as generalizations of a number of EM regression, dimension reduction, and factor analysis algorithms. The proposed framework is validated with both synthetic and real data. We provide experimental evidence that our method outperforms several existing regression techniques.
An Adaptable Fast Matrix Multiplication Algorithm, Going Beyond the Myth of Decimal War
Venue: arXiv cs.DS 2013
Year: 2013

In this paper we present an adaptable fast matrix multiplication (AFMM) algorithm, for two nxn dense matrices which computes the product matrix with average complexity Tavg(n) = d1d2n3 with the acknowledgement that the average count is obtained for addition as the basic operation rather than multiplication which is probably the unquestionable choice for basic operation in existing matrix multiplication algorithms.
On the Parameterized Complexity of Reconfiguration Problems
Venue: arXiv cs.CC 2013
Year: 2013

We present the first results on the parameterized complexity of reconfiguration problems, where a reconfiguration version of an optimization problem $Q$ takes as input two feasible solutions $S$ and $T$ and determines if there is a sequence of {\em reconfiguration steps} that can be applied to transform $S$ into $T$ such that each step results in a feasible solution to $Q$. For most of the results in this paper, $S$ and $T$ are subsets of vertices of a given graph and a reconfiguration step adds or deletes a vertex. Our study is motivated by recent results establishing that for most NP-hard problems, the classical complexity of reconfiguration is PSPACE-complete. We address the question for several important graph properties under two natural parameterizations: $k$, the size of the solutions, and $\ell$, the length of the sequence of steps. Our first general result is an algorithmic paradigm, the {\em reconfiguration kernel}, used to obtain fixed-parameter algorithms for the reconfiguration versions of {\sc Vertex Cover} and, more generally, {\sc Bounded Hitting Set} and {\sc Feedback Vertex Set}, all parameterized by $k$. In contrast, we show that reconfiguring {\sc Unbounded Hitting Set} is $W[2]$-hard when parameterized by $k+\ell$. We also demonstrate the $W[1]$-hardness of the reconfiguration versions of a large class of maximization problems parameterized by $k+\ell$, and of their corresponding deletion problems parameterized by $\ell$; in doing so, we show that there exist problems in FPT when parameterized by $k$, but whose reconfiguration versions are $W[1]$-hard when parameterized by $k+\ell$.