OpenRaiser/Intern-Atlas huggingface dataset:
Trending Videos: Measurement and Analysis
Venue: arXiv cs.SI 2014
Year: 2014

Unlike popular videos, which would have already achieved high viewership numbers by the time they are declared popular, YouTube trending videos represent content that targets viewers attention over a relatively short time, and has the potential of becoming popular. Despite their importance and visibility, YouTube trending videos have not been studied or analyzed thoroughly. In this paper, we present our findings for measuring, analyzing, and comparing key aspects of YouTube trending videos. Our study is based on collecting and monitoring high-resolution time-series of the viewership and related statistics of more than 8,000 YouTube videos over an aggregate period of nine months. Since trending videos are declared as such just several hours after they are uploaded, we are able to analyze trending videos time-series across critical and sufficiently-long durations of their lifecycle. In addition, we analyze the profile of users who upload trending videos, to potentially identify the role that these users profile plays in getting their uploaded videos trending. Furthermore, we conduct a directional-relationship analysis among all pairs of trending videos time-series that we have monitored. We employ Granger Causality (GC) with significance testing to conduct this analysis. Unlike traditional correlation measures, our directional-relationship analysis provides a deeper insight onto the viewership pattern of different categories of trending videos. Trending videos and their channels have clear distinct statistical attributes when compared to other YouTube content that has not been labeled as trending. Our results also reveal a highly asymmetric directional-relationship among different categories of trending videos. Our directionality analysis also shows a clear pattern of viewership toward popular categories, whereas some categories tend to be isolated.
Using Answer Set Programming for pattern mining
Venue: arXiv cs.AI 2014
Year: 2014

Serial pattern mining consists in extracting the frequent sequential patterns from a unique sequence of itemsets. This paper explores the ability of a declarative language, such as Answer Set Programming (ASP), to solve this issue efficiently. We propose several ASP implementations of the frequent sequential pattern mining task: a non-incremental and an incremental resolution. The results show that the incremental resolution is more efficient than the non-incremental one, but both ASP programs are less efficient than dedicated algorithms. Nonetheless, this approach can be seen as a first step toward a generic framework for sequential pattern mining with constraints.
Abstracting an operational semantics to finite automata
Venue: arXiv cs.PL 2014
Year: 2014

There is an apparent similarity between the descriptions of small-step operational semantics of imperative programs and the semantics of finite automata, so defining an abstraction mapping from semantics to automata and proving a simulation property seems to be easy. This paper aims at identifying the reasons why simple proofs break, among them artifacts in the semantics that lead to stuttering steps in the simulation. We then present a semantics based on the zipper data structure, with a direct interpretation of evaluation as navigation in the syntax tree. The abstraction function is then defined by equivalence class construction.
A Survey on Deadline Constrained Workflow Scheduling Algorithms in Cloud Environment
Venue: arXiv cs.DC 2014
Year: 2014

Cloud Computing is the latest blooming technology in the era of Computer Science and Information Technology domain. There is an enormous pool of data centres, which are termed as Clouds where the services and associated data are being deployed and users need a constant Internet connection to access them. One of the highlights in Cloud is the delivering of applications or services in an on-demand environment. One of the most promising areas in Cloud scheduling is Scheduling of workflows which is intended to match the request of the user to the appropriate resources. There are several algorithms to automate the workflows in a way to satisfy the Quality of service (QoS) of the user among which deadline is considered as a major criterion, i.e. Satisfying the needs of the user with minimized cost and within the minimum stipulated time. This paper surveys various workflow scheduling algorithms that have a deadline as its criterion.
A New DoF Upper Bound and Its Achievability for $K$-User MIMO Y Channels
Venue: arXiv cs.IT 2014
Year: 2014

This work is to study the degrees of freedom (DoF) for the $K$-user MIMO Y channel. Previously, two transmission frameworks have been proposed for the DoF analysis when $N \geq 2M$, where $M$ and $N$ denote the number of antennas at each source node and the relay node respectively. The first method is named as signal group based alignment proposed by Hua et al. in [1]. The second is named as signal pattern approach introduced by Wang et al. in [2]. But both of them only studied certain antenna configurations. The maximum achievable DoF in the general case still remains unknown. In this work, we first derive a new upper bound of the DoF using the genie-aided approach. Then, we propose a more general transmission framework, generalized signal alignment (GSA), and show that the previous two methods are both special cases of GSA. With GSA, we prove that the new DoF upper bound is achievable when $\frac{N}{M} \in \left(0,2+\frac{4}{K(K-1)}\right] \cup \left[K-2, +\infty\right)$. The DoF analysis in this paper provides a major step forward towards the fundamental capacity limit of the $K$-user MIMO Y channel. It also offers a new approach of integrating interference alignment with physical layer network coding.
On the Closest Vector Problem with a Distance Guarantee
Venue: arXiv cs.DS 2014
Year: 2014

We present a substantially more efficient variant, both in terms of running time and size of preprocessing advice, of the algorithm by Liu, Lyubashevsky, and Micciancio for solving CVPP (the preprocessing version of the Closest Vector Problem, CVP) with a distance guarantee. For instance, for any $α< 1/2$, our algorithm finds the (unique) closest lattice point for any target point whose distance from the lattice is at most $α$ times the length of the shortest nonzero lattice vector, requires as preprocessing advice only $N \approx \widetilde{O}(n \exp(α^2 n /(1-2α)^2))$ vectors, and runs in time $\widetilde{O}(nN)$. As our second main contribution, we present reductions showing that it suffices to solve CVP, both in its plain and preprocessing versions, when the input target point is within some bounded distance of the lattice. The reductions are based on ideas due to Kannan and a recent sparsification technique due to Dadush and Kun. Combining our reductions with the LLM algorithm gives an approximation factor of $O(n/\sqrt{\log n})$ for search CVPP, improving on the previous best of $O(n^{1.5})$ due to Lagarias, Lenstra, and Schnorr. When combined with our improved algorithm we obtain, somewhat surprisingly, that only O(n) vectors of preprocessing advice are sufficient to solve CVPP with (the only slightly worse) approximation factor of O(n).
Random Access Protocols with Collision Resolution in a Noncoherent Setting
Venue: arXiv cs.IT 2014
Year: 2014

Wireless systems are increasingly used for Machine-Type Communication (MTC), where the users sporadically send very short messages. In such a setting, the overhead imposed by channel estimation is substantial, thereby demanding noncoherent communication. In this paper we consider a noncoherent setup in which users randomly access the medium to send short messages to a common receiver. We propose a transmission scheme based on Gabor frames, where each user has a dedicated codebook of M possible codewords, while the codebook simultaneously serves as an ID for the user. The scheme is used as a basis for a simple protocol for collision resolution.
A note on the Minimum Norm Point algorithm
Venue: arXiv cs.DS 2014
Year: 2014

We present a provably more efficient implementation of the Minimum Norm Point Algorithm conceived by Fujishige than the one presented in \cite{FUJI06}. The algorithm solves the minimization problem for a class of functions known as submodular. Many important functions, such as minimum cut in the graph, have the so called submodular property \cite{FUJI82}. It is known that the problem can also be efficiently solved in strongly polynomial time \cite{IWAT01}, however known theoretical bounds are far from being practical. We present an improved implementation of the algorithm, for which unfortunately no worst case bounds are know, but which performs very well in practice. With the modifications presented, the algorithm performs an order of magnitude faster for certain submodular functions.
Controversy and Sentiment in Online News
Venue: arXiv cs.CY 2014
Year: 2014

How do news sources tackle controversial issues? In this work, we take a data-driven approach to understand how controversy interplays with emotional expression and biased language in the news. We begin by introducing a new dataset of controversial and non-controversial terms collected using crowdsourcing. Then, focusing on 15 major U.S. news outlets, we compare millions of articles discussing controversial and non-controversial issues over a span of 7 months. We find that in general, when it comes to controversial issues, the use of negative affect and biased language is prevalent, while the use of strong emotion is tempered. We also observe many differences across news sources. Using these findings, we show that we can indicate to what extent an issue is controversial, by comparing it with other issues in terms of how they are portrayed across different media.
An Analysis of BitTorrent Cross-Swarm Peer Participation and Geolocational Distribution
Venue: arXiv cs.NI 2014
Year: 2014

Peer-to-Peer (P2P) file-sharing is becoming increasingly popular in recent years. In 2012, it was reported that P2P traffic consumed over 5,374 petabytes per month, which accounted for approximately 20.5% of consumer internet traffic. TV is the popular content type on The Pirate Bay (the world's largest BitTorrent indexing website). In this paper, an analysis of the swarms of the most popular pirated TV shows is conducted. The purpose of this data gathering exercise is to enumerate the peer distribution at different geolocational levels, to measure the temporal trend of the swarm and to discover the amount of cross-swarm peer participation. Snapshots containing peer related information involved in the unauthorised distribution of this content were collected at a high frequency resulting in a more accurate landscape of the total involvement. The volume of data collected throughout the monitoring of the network exceeded 2 terabytes. The presented analysis and the results presented can aid in network usage prediction, bandwidth provisioning and future network design.
Arabic Spelling Correction using Supervised Learning
Venue: arXiv cs.LG 2014
Year: 2014

In this work, we address the problem of spelling correction in the Arabic language utilizing the new corpus provided by QALB (Qatar Arabic Language Bank) project which is an annotated corpus of sentences with errors and their corrections. The corpus contains edit, add before, split, merge, add after, move and other error types. We are concerned with the first four error types as they contribute more than 90% of the spelling errors in the corpus. The proposed system has many models to address each error type on its own and then integrating all the models to provide an efficient and robust system that achieves an overall recall of 0.59, precision of 0.58 and F1 score of 0.58 including all the error types on the development set. Our system participated in the QALB 2014 shared task "Automatic Arabic Error Correction" and achieved an F1 score of 0.6, earning the sixth place out of nine participants.
Digital Evidence Bag Selection for P2P Network Investigation
Venue: arXiv cs.NI 2014
Year: 2014

The collection and handling of court admissible evidence is a fundamental component of any digital forensic investigation. While the procedures for handling digital evidence take much of their influence from the established policies for the collection of physical evidence, due to the obvious differences in dealing with non-physical evidence, a number of extra policies and procedures are required. This paper compares and contrasts some of the existing digital evidence formats or "bags" and analyses them for their compatibility with evidence gathered from a network source. A new digital extended evidence bag is proposed to specifically deal with evidence gathered from P2P networks, incorporating the network byte stream and on-the-fly metadata generation to aid in expedited identification and analysis.
ProbFuse: A Probabilistic Approach to Data Fusion
Venue: arXiv cs.IR 2014
Year: 2014

Data fusion is the combination of the results of independent searches on a document collection into one single output result set. It has been shown in the past that this can greatly improve retrieval effectiveness over that of the individual results. This paper presents probFuse, a probabilistic approach to data fusion. ProbFuse assumes that the performance of the individual input systems on a number of training queries is indicative of their future performance. The fused result set is based on probabilities of relevance calculated during this training process. Retrieval experiments using data from the TREC ad hoc collection demonstrate that probFuse achieves results superior to that of the popular CombMNZ fusion algorithm.
Optimal Tourist Problem and Anytime Planning of Trip Itineraries
Venue: arXiv cs.RO 2014
Year: 2014

We introduce and study the problem in which a mobile sensing robot (our tourist) is tasked to travel among and gather intelligence at a set of spatially distributed point-of-interests (POIs). The quality of the information collected at each POI is characterized by some non-decreasing reward function over the time spent at the POI. With limited time budget, the robot must balance between spending time traveling to POIs and spending time at POIs for information collection (sensing) so as to maximize the total reward. Alternatively, the robot may be required to acquire a minimum mount of reward and hopes to do so with the least amount of time. We propose a mixed integer programming (MIP) based anytime algorithm for solving these two NP-hard optimization problems to arbitrary precision. The effectiveness of our algorithm is demonstrated using an extensive set of computational experiments including the planning of a realistic itinerary for a first-time tourist in Istanbul.
Freshness-Aware Thompson Sampling
Venue: arXiv cs.IR 2014
Year: 2014

To follow the dynamicity of the user's content, researchers have recently started to model interactions between users and the Context-Aware Recommender Systems (CARS) as a bandit problem where the system needs to deal with exploration and exploitation dilemma. In this sense, we propose to study the freshness of the user's content in CARS through the bandit problem. We introduce in this paper an algorithm named Freshness-Aware Thompson Sampling (FA-TS) that manages the recommendation of fresh document according to the user's risk of the situation. The intensive evaluation and the detailed analysis of the experimental results reveals several important discoveries in the exploration/exploitation (exr/exp) behaviour.
Performance Evaluation for MIMO In Vivo WBAN Systems
Venue: arXiv cs.IT 2014
Year: 2014

In this paper we present the performance evaluation for a MIMO in vivo WBAN system, using ANSYS HFSS and the associated complete Human Body Model. We analyzed MIMO system capacity statistically and FER performance based upon an IEEE 802.11n system model, with receiver antennas placed at various angular positions around the human body. We also analyzed MIMO system capacity with receiver antennas at the front of the body at various distances from transmitter antennas. The results were compared to SISO arrangements and we demonstrate that by using 2x2 MIMO in vivo, better performance can be achieved, and significantly higher system capacity can be achieved when receiver antennas are located at the back of the body and in front of the body.
Coupling Top-down and Bottom-up Methods for 3D Human Pose and Shape Estimation from Monocular Image Sequences
Venue: arXiv cs.CV 2014
Year: 2014

Until recently Intelligence, Surveillance, and Reconnaissance (ISR) focused on acquiring behavioral information of the targets and their activities. Continuous evolution of intelligence being gathered of the human centric activities has put increased focus on the humans, especially inferring their innate characteristics - size, shapes and physiology. These bio-signatures extracted from the surveillance sensors can be used to deduce age, ethnicity, gender and actions, and further characterize human actions in unseen scenarios. However, recovery of pose and shape of humans in such monocular videos is inherently an ill-posed problem, marked by frequent depth and view based ambiguities due to self-occlusion, foreshortening and misalignment. The likelihood function often yields a highly multimodal posterior that is difficult to propagate even using the most advanced particle filtering(PF) algorithms. Motivated by the recent success of the discriminative approaches to efficiently predict 3D poses directly from the 2D images, we present several principled approaches to integrate predictive cues using learned regression models to sustain multimodality of the posterior during tracking. Additionally, these learned priors can be actively adapted to the test data using a likelihood based feedback mechanism. Estimated 3D poses are then used to fit 3D human shape model to each frame independently for inferring anthropometric bio-signatures. The proposed system is fully automated, robust to noisy test data and has ability to swiftly recover from tracking failures even after confronting with significant errors. We evaluate the system on a large number of monocular human motion sequences.
Non-parametric Image Registration of Airborne LiDAR, Hyperspectral and Photographic Imagery of Forests
Venue: arXiv cs.CV 2014
Year: 2014

There is much current interest in using multi-sensor airborne remote sensing to monitor the structure and biodiversity of forests. This paper addresses the application of non-parametric image registration techniques to precisely align images obtained from multimodal imaging, which is critical for the successful identification of individual trees using object recognition approaches. Non-parametric image registration, in particular the technique of optimizing one objective function containing data fidelity and regularization terms, provides flexible algorithms for image registration. Using a survey of woodlands in southern Spain as an example, we show that non-parametric image registration can be successful at fusing datasets when there is little prior knowledge about how the datasets are interrelated (i.e. in the absence of ground control points). The validity of non-parametric registration methods in airborne remote sensing is demonstrated by a series of experiments. Precise data fusion is a prerequisite to accurate recognition of objects within airborne imagery, so non-parametric image registration could make a valuable contribution to the analysis pipeline.
Improved Bounds for the Flat Wall Theorem
Venue: arXiv cs.DS 2014
Year: 2014

The Flat Wall Theorem of Robertson and Seymour states that there is some function $f$, such that for all integers $w,t>1$, every graph $G$ containing a wall of size $f(w,t)$, must contain either (i) a $K_t$-minor; or (ii) a small subset $A\subset V(G)$ of vertices, and a flat wall of size $w$ in $G\setminus A$. Kawarabayashi, Thomas and Wollan recently showed a self-contained proof of this theorem with the following two sets of parameters: (1) $f(w,t)=Θ(t^{24}(t^2+w))$ with $|A|=O(t^{24})$, and (2) $f(w,t)=w^{2^{Θ(t^{24})}}$ with $|A|\leq t-5$. The latter result gives the best possible bound on $|A|$. In this paper we improve their bounds to $f(w,t)=Θ(t(t+w))$ with $|A|\leq t-5$. For the special case where the maximum vertex degree in $G$ is bounded by $D$, we show that, if $G$ contains a wall of size $Ω(Dt(t+w))$, then either $G$ contains a $K_t$-minor, or there is a flat wall of size $w$ in $G$. This setting naturally arises in algorithms for the Edge-Disjoint Paths problem, with $D\leq 4$. Like the proof of Kawarabayashi et al., our proof is self-contained, except for using a well-known theorem on routing pairs of disjoint paths. We also provide efficient algorithms that return either a model of the $K_t$-minor, or a vertex set $A$ and a flat wall of size $w$ in $G\setminus A$. We complement our result for the low-degree scenario by proving an almost matching lower bound: namely, for all integers $w,t>1$, there is a graph $G$, containing a wall of size $Ω(wt)$, such that the maximum vertex degree in $G$ is 5, and $G$ contains no flat wall of size $w$, and no $K_t$-minor.
Teaching Parallel Programming Using Java
Venue: arXiv cs.CY 2014
Year: 2014

This paper presents an overview of the "Applied Parallel Computing" course taught to final year Software Engineering undergraduate students in Spring 2014 at NUST, Pakistan. The main objective of the course was to introduce practical parallel programming tools and techniques for shared and distributed memory concurrent systems. A unique aspect of the course was that Java was used as the principle programming language. The course was divided into three sections. The first section covered parallel programming techniques for shared memory systems that include multicore and Symmetric Multi-Processor (SMP) systems. In this section, Java threads was taught as a viable programming API for such systems. The second section was dedicated to parallel programming tools meant for distributed memory systems including clusters and network of computers. We used MPJ Express-a Java MPI library-for conducting programming assignments and lab work for this section. The third and the final section covered advanced topics including the MapReduce programming model using Hadoop and the General Purpose Computing on Graphics Processing Units (GPGPU).
Cross-layer design of distributed sensing-estimation with quality feedback, Part I: Optimal schemes
Venue: arXiv cs.SY 2014
Year: 2014

This two-part paper presents a feedback-based cross-layer framework for distributed sensing and estimation of a dynamic process by a wireless sensor network (WSN). Sensor nodes wirelessly communicate measurements to the fusion center (FC). Cross-layer factors such as packet collisions and the sensing-transmission costs are considered. Each SN adapts its sensing-transmission action based on its own local observation quality and the estimation quality feedback from the FC under cost constraints for each SN. In this first part, the optimization complexity is reduced by exploiting the statistical symmetry and large network approximation of the WSN. Structural properties of the optimal policy are derived for a coordinated and a decentralized scheme. It is proved that a dense WSN provides sensing diversity, so that only a few SNs with the best local observation quality need to be activated, despite the fluctuations of the WSN. The optimal policy dictates that, when the estimation quality is poor, only the best SNs activate, otherwise all SNs remain idle to preserve energy. The costs of coordination and feedback are evaluated, revealing the scalability of the decentralized scheme to large WSNs, at the cost of performance degradation. Simulation results demonstrate cost savings from 30% to 70% over a non-adaptive scheme, and significant gains over a previously proposed estimator which does not consider these cross-layer factors.