OpenRaiser/Intern-Atlas huggingface dataset:
On Modelling and Prediction of Total CPU Usage for Applications in MapReduce Environments
Venue: arXiv cs.DC 2012
Year: 2012

Recently, businesses have started using MapReduce as a popular computation framework for processing large amount of data, such as spam detection, and different data mining tasks, in both public and private clouds. Two of the challenging questions in such environments are (1) choosing suitable values for MapReduce configuration parameters -e.g., number of mappers, number of reducers, and DFS block size-, and (2) predicting the amount of resources that a user should lease from the service provider. Currently, the tasks of both choosing configuration parameters and estimating required resources are solely the users' responsibilities. In this paper, we present an approach to provision the total CPU usage in clock cycles of jobs in MapReduce environment. For a MapReduce job, a profile of total CPU usage in clock cycles is built from the job past executions with different values of two configuration parameters e.g., number of mappers, and number of reducers. Then, a polynomial regression is used to model the relation between these configuration parameters and total CPU usage in clock cycles of the job. We also briefly study the influence of input data scaling on measured total CPU usage in clock cycles. This derived model along with the scaling result can then be used to provision the total CPU usage in clock cycles of the same jobs with different input data size. We validate the accuracy of our models using three realistic applications (WordCount, Exim MainLog parsing, and TeraSort). Results show that the predicted total CPU usage in clock cycles of generated resource provisioning options are less than 8% of the measured total CPU usage in clock cycles in our 20-node virtual Hadoop cluster.
Reducing the Arity in Unbiased Black-Box Complexity
Venue: arXiv cs.NE 2012
Year: 2012

We show that for all $1<k \leq \log n$ the $k$-ary unbiased black-box complexity of the $n$-dimensional $\onemax$ function class is $O(n/k)$. This indicates that the power of higher arity operators is much stronger than what the previous $O(n/\log k)$ bound by Doerr et al. (Faster black-box algorithms through higher arity operators, Proc. of FOGA 2011, pp. 163--172, ACM, 2011) suggests. The key to this result is an encoding strategy, which might be of independent interest. We show that, using $k$-ary unbiased variation operators only, we may simulate an unrestricted memory of size $O(2^k)$ bits.
A More Reliable Greedy Heuristic for Maximum Matchings in Sparse Random Graphs
Venue: arXiv cs.DS 2012
Year: 2012

We propose a new greedy algorithm for the maximum cardinality matching problem. We give experimental evidence that this algorithm is likely to find a maximum matching in random graphs with constant expected degree c>0, independent of the value of c. This is contrary to the behavior of commonly used greedy matching heuristics which are known to have some range of c where they probably fail to compute a maximum matching.
CRM 2.0 within E-Health Systems: Towards Achieving Health Literacy & Customer Satisfaction
Venue: arXiv cs.OH 2012
Year: 2012

Customer Relationship Management (CRM) within healthcare organization can be viewed as a strategy to attract new customers and retaining them throughout their entire lifetime of relationships. At the same time, the advancement of Web technology known as Web 2.0 plays a significant part in the CRM transition which drives social change that impacts all institutions including business and healthcare organizations. This new paradigm has been named as Social CRM or CRM 2.0 because it is based on Web 2.0. We conducted survey to examine the features of CRM 2.0 in healthcare scenario to the customer in Brunei Darussalam. We draw the conclusion that the CRM 2.0 in healthcare technologies has brought a possibility to extend the services of e-health by enabling patients, patient's families, and community at large to participate more actively in the process of health education; it helps improve health literacy through empowerment, social networking process, and online health educator. This paper is based on our works presented at ICID 2011.
Distributed Consensus Resilient to Both Crash Failures and Strategic Manipulations
Venue: arXiv cs.DC 2012
Year: 2012

In this paper, we study distributed consensus in synchronous systems subject to both unexpected crash failures and strategic manipulations by rational agents in the system. We adapt the concept of collusion-resistant Nash equilibrium to model protocols that are resilient to both crash failures and strategic manipulations of a group of colluding agents. For a system with $n$ distributed agents, we design a deterministic protocol that tolerates 2 colluding agents and a randomized protocol that tolerates $n - 1$ colluding agents, and both tolerate any number of failures. We also show that if colluders are allowed an extra communication round after each synchronous round, there is no protocol that can tolerate even 2 colluding agents and 1 crash failure.
Dynamic PL&T using Two Reference Nodes Equipped with Steered Directional Antenna for Significant PL&T Accuracy
Venue: arXiv cs.NI 2012
Year: 2012

Dynamic Position Location and Tracking (PL&T) is proposed deploying the integrated approach of zone finding and triangulation using two friendly nodes equipped with Steered Directional Antenna (DA) in Mobile Ad hoc Networks (MANET). This approach allows the system to use only two references instead of a typical 3 references for a straight triangulation. Moreover, the performance of the proposed algorithm with references using directional antennas shows significant improvement over triangulation using references with Omnidirectional antennas as the beam power is concentrated. However, dynamic switching of reference nodes is frequently required as the target moves outside the predicted zone. This paper presents a better tracking accuracy in using proposed dynamic PL&T as compared to other PL&T techniques. The multipath fading is also addressed with the use of KV transform coding technique which uses forward error correction and sample interleaving achieves greater than 90% tracking accuracy with BERs of 10-6 or better.
Arabic Keyphrase Extraction using Linguistic knowledge and Machine Learning Techniques
Venue: arXiv cs.CL 2012
Year: 2012

In this paper, a supervised learning technique for extracting keyphrases of Arabic documents is presented. The extractor is supplied with linguistic knowledge to enhance its efficiency instead of relying only on statistical information such as term frequency and distance. During analysis, an annotated Arabic corpus is used to extract the required lexical features of the document words. The knowledge also includes syntactic rules based on part of speech tags and allowed word sequences to extract the candidate keyphrases. In this work, the abstract form of Arabic words is used instead of its stem form to represent the candidate terms. The Abstract form hides most of the inflections found in Arabic words. The paper introduces new features of keyphrases based on linguistic knowledge, to capture titles and subtitles of a document. A simple ANOVA test is used to evaluate the validity of selected features. Then, the learning model is built using the LDA - Linear Discriminant Analysis - and training documents. Although, the presented system is trained using documents in the IT domain, experiments carried out show that it has a significantly better performance than the existing Arabic extractor systems, where precision and recall values reach double their corresponding values in the other systems especially for lengthy and non-scientific articles.
An Arithmetic and Geometric Mean Invariant
Venue: arXiv cs.NA 2012
Year: 2012

A positive real interval, [a, b], can be partitioned into sub-intervals such that sub-interval widths divided by sub-interval "average" values remains constant. That both Arithmetic Mean and Geometric Mean "average" values produce constant ratios for the same log scale is the stated invariance proved in this short note. The continuous analog is briefly considered and shown to have similar properties.
Online Load Balancing on Unrelated Machines with Startup Costs
Venue: arXiv cs.DS 2012
Year: 2012

Motivated by applications in energy-efficient scheduling in data centers, Khuller, Li, and Saha introduced the {\em machine activation} problem as a generalization of the classical optimization problems of set cover and load balancing on unrelated machines. In this problem, a set of $n$ jobs have to be distributed among a set of $m$ (unrelated) machines, given the processing time of each job on each machine, where each machine has a startup cost. The goal is to produce a schedule of minimum total startup cost subject to a constraint $\bf L$ on its makespan. While Khuller {\em et al} considered the offline version of this problem, a typical scenario in scheduling is one where jobs arrive online and have to be assigned to a machine immediately on arrival. We give an $(O(\log (mn)\log m), O(\log m))$-competitive randomized online algorithm for this problem, i.e. the schedule produced by our algorithm has a makespan of $O({\bf L} \log m)$ with high probability, and a total expected startup cost of $O(\log (mn)\log m)$ times that of an optimal offline schedule with makespan $\bf L$. The competitive ratios of our algorithm are (almost) optimal. Our algorithms use the online primal dual framework introduced by Alon {\em et al} for the online set cover problem, and subsequently developed further by Buchbinder, Naor, and co-authors. To the best of our knowledge, all previous applications of this framework have been to linear programs (LPs) with either packing or covering constraints. One novelty of our application is that we use this framework for a mixed LP that has both covering and packing constraints. We hope that the algorithmic techniques developed in this paper to simultaneously handle packing and covering constraints will be useful for solving other online optimization problems as well.
A Unifying Framework to Characterize the Power of a Language to Express Relations
Venue: arXiv cs.DB 2012
Year: 2012

In this extended abstract we provide a unifying framework that can be used to characterize and compare the expressive power of query languages for different data base models. The framework is based upon the new idea of valid partition, that is a partition of the elements of a given data base, where each class of the partition is composed by elements that cannot be separated (distinguished) according to some level of information contained in the data base. We describe two applications of this new framework, first by deriving a new syntactic characterization of the expressive power of relational algebra which is equivalent to the one given by Paredaens, and subsequently by studying the expressive power of a simple graph-based data model.
A Co-Prime Blur Scheme for Data Security in Video Surveillance
Venue: arXiv cs.CV 2012
Year: 2012

This paper presents a novel Coprime Blurred Pair (CBP) model for visual data-hiding for security in camera surveillance. While most previous approaches have focused on completely encrypting the video stream, we introduce a spatial encryption scheme by blurring the image/video contents to create a CBP. Our goal is to obscure detail in public video streams by blurring while allowing behavior to be recognized and to quickly deblur the stream so that details are available if behavior is recognized as suspicious. We create a CBP by blurring the same latent image with two unknown kernels. The two kernels are coprime when mapped to bivariate polynomials in the z domain. To deblur the CBP we first use the coprime constraint to approximate the kernels and sample the bivariate CBP polynomials in one dimension on the unit circle. At each sample point, we factor the 1D polynomial pair and compose the results into a 2D kernel matrix. Finally, we compute the inverse Fast Fourier Transform (FFT) of the kernel matrices to recover the coprime kernels and then the latent video stream. It is therefore only possible to deblur the video stream if a user has access to both streams. To improve the practicability of our algorithm, we implement our algorithm using a graphics processing unit (GPU) to decrypt the blurred video streams in real-time, and extensive experimental results demonstrate that our new scheme can effectively protect sensitive identity information in surveillance videos and faithfully reconstruct the unblurred video stream when two blurred sequences are available.
Single pass sparsification in the streaming model with edge deletions
Venue: arXiv cs.DS 2012
Year: 2012

In this paper we give a construction of cut sparsifiers of Benczur and Karger in the {\em dynamic} streaming setting in a single pass over the data stream. Previous constructions either required multiple passes or were unable to handle edge deletions. We use $\tilde{O}(1/\e^2)$ time for each stream update and $\tilde{O}(n/\e^2)$ time to construct a sparsifier. Our $\e$-sparsifiers have $O(n\log^3 n/\e^2)$ edges. The main tools behind our result are an application of sketching techniques of Ahn et al.[SODA'12] to estimate edge connectivity together with a novel application of sampling with limited independence and sparse recovery to produce the edges of the sparsifier.
On the Power of Centralization in Distributed Processing
Venue: arXiv cs.DC 2012
Year: 2012

In this thesis, we propose and analyze a multi-server model that captures a performance trade-off between centralized and distributed processing. In our model, a fraction $p$ of an available resource is deployed in a centralized manner (e.g., to serve a most-loaded station) while the remaining fraction $1-p$ is allocated to local servers that can only serve requests addressed specifically to their respective stations. Using a fluid model approach, we demonstrate a surprising phase transition in the steady-state delay, as $p$ changes: in the limit of a large number of stations, and when any amount of centralization is available ($p>0$), the average queue length in steady state scales as $\log_{1/(1-p)} 1/(1-λ)$ when the traffic intensity $λ$ goes to 1. This is exponentially smaller than the usual M/M/1-queue delay scaling of $1/(1-λ)$, obtained when all resources are fully allocated to local stations ($p=0$). This indicates a strong qualitative impact of even a small degree of centralization. We prove convergence to a fluid limit, and characterize both the transient and steady-state behavior of the finite system, in the limit as the number of stations $N$ goes to infinity. We show that the sequence of queue-length processes converges to a unique fluid trajectory (over any finite time interval, as $N$ approaches infinity, and that this fluid trajectory converges to a unique invariant state $v^I$, for which a simple closed-form expression is obtained. We also show that the steady-state distribution of the $N$-server system concentrates on $v^I$ as $N$ goes to infinity.
An Annotation Scheme for Reichenbach's Verbal Tense Structure
Venue: arXiv cs.CL 2012
Year: 2012

In this paper we present RTMML, a markup language for the tenses of verbs and temporal relations between verbs. There is a richness to tense in language that is not fully captured by existing temporal annotation schemata. Following Reichenbach we present an analysis of tense in terms of abstract time points, with the aim of supporting automated processing of tense and temporal relations in language. This allows for precise reasoning about tense in documents, and the deduction of temporal relations between the times and verbal events in a discourse. We define the syntax of RTMML, and demonstrate the markup in a range of situations.
USFD at KBP 2011: Entity Linking, Slot Filling and Temporal Bounding
Venue: arXiv cs.CL 2012
Year: 2012

This paper describes the University of Sheffield's entry in the 2011 TAC KBP entity linking and slot filling tasks. We chose to participate in the monolingual entity linking task, the monolingual slot filling task and the temporal slot filling tasks. We set out to build a framework for experimentation with knowledge base population. This framework was created, and applied to multiple KBP tasks. We demonstrated that our proposed framework is effective and suitable for collaborative development efforts, as well as useful in a teaching environment. Finally we present results that, while very modest, provide improvements an order of magnitude greater than our 2010 attempt.
Massively Increasing TIMEX3 Resources: A Transduction Approach
Venue: arXiv cs.CL 2012
Year: 2012

Automatic annotation of temporal expressions is a research challenge of great interest in the field of information extraction. Gold standard temporally-annotated resources are limited in size, which makes research using them difficult. Standards have also evolved over the past decade, so not all temporally annotated data is in the same format. We vastly increase available human-annotated temporal expression resources by converting older format resources to TimeML/TIMEX3. This task is difficult due to differing annotation methods. We present a robust conversion tool and a new, large temporal expression resource. Using this, we evaluate our conversion process by using it as training data for an existing TimeML annotation tool, achieving a 0.87 F1 measure -- better than any system in the TempEval-2 timex recognition exercise.
Parallel Matrix Factorization for Binary Response
Venue: arXiv cs.LG 2012
Year: 2012

Predicting user affinity to items is an important problem in applications like content optimization, computational advertising, and many more. While bilinear random effect models (matrix factorization) provide state-of-the-art performance when minimizing RMSE through a Gaussian response model on explicit ratings data, applying it to imbalanced binary response data presents additional challenges that we carefully study in this paper. Data in many applications usually consist of users' implicit response that are often binary -- clicking an item or not; the goal is to predict click rates, which is often combined with other measures to calculate utilities to rank items at runtime of the recommender systems. Because of the implicit nature, such data are usually much larger than explicit rating data and often have an imbalanced distribution with a small fraction of click events, making accurate click rate prediction difficult. In this paper, we address two problems. First, we show previous techniques to estimate bilinear random effect models with binary data are less accurate compared to our new approach based on adaptive rejection sampling, especially for imbalanced response. Second, we develop a parallel bilinear random effect model fitting framework using Map-Reduce paradigm that scales to massive datasets. Our parallel algorithm is based on a "divide and conquer" strategy coupled with an ensemble approach. Through experiments on the benchmark MovieLens data, a small Yahoo! Front Page data set, and a large Yahoo! Front Page data set that contains 8M users and 1B binary observations, we show that careful handling of binary response as well as identifiability issues are needed to achieve good performance for click rate prediction, and that the proposed adaptive rejection sampler and the partitioning as well as ensemble techniques significantly improve model performance.
A linear time algorithm for the next-to-shortest path problem on undirected graphs with nonnegative edge lengths
Venue: arXiv cs.DS 2012
Year: 2012

For two vertices $s$ and $t$ in a graph $G=(V,E)$, the next-to-shortest path is an $st$-path which length is minimum amongst all $st$-paths strictly longer than the shortest path length. In this paper we show that, when the graph is undirected and all edge lengths are nonnegative, the problem can be solved in linear time if the distances from $s$ and $t$ to all other vertices are given. This result generalizes the previous work (DOI 10.1007/s00453-011-9601-7) to allowing zero-length edges.
Clique problem, cutting plane proofs and communication complexity
Venue: arXiv cs.CC 2012
Year: 2012

Motivated by its relation to the length of cutting plane proofs for the Maximum Biclique problem, we consider the following communication game on a given graph G, known to both players. Let K be the maximal number of vertices in a complete bipartite subgraph of G, which is not necessarily an induced subgraph if G is not bipartite. Alice gets a set A of vertices, and Bob gets a disjoint set B of vertices such that |A|+|B|>K. The goal is to find a nonedge of G between A and B. We show that O(\log n) bits of communication are enough for every n-vertex graph.
Mutual or Unrequited Love: Identifying Stable Clusters in Social Networks with Uni- and Bi-directional Links
Venue: arXiv cs.SI 2012
Year: 2012

Many social networks, e.g., Slashdot and Twitter, can be represented as directed graphs (digraphs) with two types of links between entities: mutual (bi-directional) and one-way (uni-directional) connections. Social science theories reveal that mutual connections are more stable than one-way connections, and one-way connections exhibit various tendencies to become mutual connections. It is therefore important to take such tendencies into account when performing clustering of social networks with both mutual and one-way connections. In this paper, we utilize the dyadic methods to analyze social networks, and develop a generalized mutuality tendency theory to capture the tendencies of those node pairs which tend to establish mutual connections more frequently than those occur by chance. Using these results, we develop a mutuality-tendency-aware spectral clustering algorithm to identify more stable clusters by maximizing the within-cluster mutuality tendency and minimizing the cross-cluster mutuality tendency. Extensive simulation results on synthetic datasets as well as real online social network datasets such as Slashdot, demonstrate that our proposed mutuality-tendency-aware spectral clustering algorithm extracts more stable social community structures than traditional spectral clustering methods.
Wireless Video Transmission with Over-the-Air Packet Mixing
Venue: arXiv cs.NI 2012
Year: 2012

In this paper, we propose a system for wireless video transmission with a wireless physical layer (PHY) that supports cooperative forwarding of interfered/superimposed packets. Our system model considers multiple and independent unicast transmissions between network nodes while a number of them serve as relays of the interfered/superimposed signals. For this new PHY the average transmission rate that each node can achieve is estimated first. Next, we formulate a utility optimization framework for the video transmission problem and we show that it can be simplified due to the features of the new PHY. Simulation results reveal the system operating regions for which superimposing wireless packets is a better choice than a typical cooperative PHY.