OpenRaiser/Intern-Atlas huggingface dataset:
Overview of EIREX 2011: Crowdsourcing
Venue: arXiv cs.IR 2012
Year: 2012

The second Information Retrieval Education through EXperimentation track (EIREX 2011) was run at the University Carlos III of Madrid, during the 2011 spring semester. EIREX 2011 is the second in a series of experiments designed to foster new Information Retrieval (IR) education methodologies and resources, with the specific goal of teaching undergraduate IR courses from an experimental perspective. For an introduction to the motivation behind the EIREX experiments, see the first sections of [Urbano et al., 2011a]. For information on other editions of EIREX and related data, see the website at http://ir.kr.inf.uc3m.es/eirex/. The EIREX series have the following goals: a) to help students get a view of the Information Retrieval process as they would find it in a real-world scenario, either industrial or academic; b) to make students realize the importance of laboratory experiments in Computer Science and have them initiated in their execution and analysis; c) to create a public repository of resources to teach Information Retrieval courses; d) to seek the collaboration and active participation of other Universities in this endeavor. This overview paper summarizes the results of the EIREX 2011 track, focusing on the creation of the test collection and the analysis to assess its reliability.
Hypothesis Testing and Decision Theoretic Approach for Fault Detection in Wireless Sensor Networks
Venue: arXiv cs.NI 2012
Year: 2012

Sensor networks aim at monitoring their surroundings for event detection and object tracking. But due to failure or death of sensors, false signal can be transmitted. In this paper, we consider the problem of fault detection in wireless sensor network (WSN), in particular, addressing both the noise-related measurement error and sensor fault simultaneously in fault detection. We assume that the sensors are placed at the center of a square (or hexagonal) cell in region of interest (ROI) and, if the event occurs, it occurs at a particular cell of the ROI. We propose fault detection schemes that take into account error probabilities into the optimal event detection process. We develop the schemes under the consideration of Neyman-Pearson test and Bayes test.
Bayesian inference under differential privacy
Venue: arXiv cs.DB 2012
Year: 2012

Bayesian inference is an important technique throughout statistics. The essence of Beyesian inference is to derive the posterior belief updated from prior belief by the learned information, which is a set of differentially private answers under differential privacy. Although Bayesian inference can be used in a variety of applications, it becomes theoretically hard to solve when the number of differentially private answers is large. To facilitate Bayesian inference under differential privacy, this paper proposes a systematic mechanism. The key step of the mechanism is the implementation of Bayesian updating with the best linear unbiased estimator derived by Gauss-Markov theorem. In addition, we also apply the proposed inference mechanism into an online queryanswering system, the novelty of which is that the utility for users is guaranteed by Bayesian inference in the form of credible interval and confidence level. Theoretical and experimental analysis are shown to demonstrate the efficiency and effectiveness of both inference mechanism and online query-answering system.
Checking Tests for Read-Once Functions over Arbitrary Bases
Venue: arXiv cs.DM 2012
Year: 2012

A Boolean function is called read-once over a basis B if it can be expressed by a formula over B where no variable appears more than once. A checking test for a read-once function f over B depending on all its variables is a set of input vectors distinguishing f from all other read-once functions of the same variables. We show that every read-once function f over B has a checking test containing O(n^l) vectors, where n is the number of relevant variables of f and l is the largest arity of functions in B. For some functions, this bound cannot be improved by more than a constant factor. The employed technique involves reconstructing f from its l-variable projections and provides a stronger form of Kuznetsov's classic theorem on read-once representations.
On Modeling Dependency between MapReduce Configuration Parameters and Total Execution Time
Venue: arXiv cs.DC 2012
Year: 2012

In this paper, we propose an analytical method to model the dependency between configuration parameters and total execution time of Map-Reduce applications. Our approach has three key phases: profiling, modeling, and prediction. In profiling, an application is run several times with different sets of MapReduce configuration parameters to profile the execution time of the application on a given platform. Then in modeling, the relation between these parameters and total execution time is modeled by multivariate linear regression. Among the possible configuration parameters, two main parameters have been used in this study: the number of Mappers, and the number of Reducers. For evaluation, two standard applications (WordCount, and Exim Mainlog parsing) are utilized to evaluate our technique on a 4-node MapReduce platform.
A likelihood-based framework for the analysis of discussion threads
Venue: arXiv cs.SI 2012
Year: 2012

Online discussion threads are conversational cascades in the form of posted messages that can be generally found in social systems that comprise many-to-many interaction such as blogs, news aggregators or bulletin board systems. We propose a framework based on generative models of growing trees to analyse the structure and evolution of discussion threads. We consider the growth of a discussion to be determined by an interplay between popularity, novelty and a trend (or bias) to reply to the thread originator. The relevance of these features is estimated using a full likelihood approach and allows to characterize the habits and communication patterns of a given platform and/or community.
Target set selection problem for honeycomb networks
Venue: arXiv cs.DM 2012
Year: 2012

Let $G$ be a graph with a threshold function $θ:V(G)\rightarrow \mathbb{N}$ such that $1\leq θ(v)\leq d_G(v)$ for every vertex $v$ of $G$, where $d_G(v)$ is the degree of $v$ in $G$. Suppose we are given a target set $S\subseteq V(G)$. The paper considers the following repetitive process on $G$. At time step 0 the vertices of $S$ are colored black and the other vertices are colored white. After that, at each time step $t>0$, the colors of white vertices (if any) are updated according to the following rule. All white vertices $v$ that have at least $θ(v)$ black neighbors at the time step $t-1$ are colored black, and the colors of the other vertices do not change. The process runs until no more white vertices can update colors from white to black. The following optimization problem is called Target Set Selection: Finding a target set $S$ of smallest possible size such that all vertices in $G$ are black at the end of the process. Such an $S$ is called an {\em optimal target set} for $G$ under the threshold function $θ$. We are interested in finding an optimal target set for the well-known class of honeycomb networks under an important threshold function called {\em strict majority threshold}, where $θ(v)=\lceil (d_G(v)+1)/2\rceil$ for each vertex $v$ in $G$. In a graph $G$, a {\em feedback vertex set} is a subset $S\subseteq V(G)$ such that the subgraph induced by $V(G)\setminus S$ is cycle-free. In this paper we give exact value on the size of the optimal target set for various kinds of honeycomb networks under strict majority threshold, and as a by-product we also provide a minimum feedback vertex set for different kinds regular graphs in the class of honeycomb networks
Manual and Fast C Code Optimization
Venue: arXiv cs.PL 2012
Year: 2012

Developing an application with high performance through the code optimization places a greater responsibility on the programmers. While most of the existing compilers attempt to automatically optimize the program code, manual techniques remain the predominant method for performing optimization. Deciding where to try to optimize code is difficult, especially for large complex applications. For manual optimization, the programmers can use his experiences in writing the code, and then he can use a software profiler in order to collect and analyze the performance data from the code. In this work, we have gathered the most experiences which can be applied to improve the style of writing programs in C language as well as we present an implementation of the manual optimization of the codes using the Intel VTune profiler. The paper includes two case studies to illustrate our optimization on the Heap Sort and Factorial functions.
A handy systematic method for data hazards detection in an instruction set of a pipelined microprocessor
Venue: arXiv cs.AR 2012
Year: 2012

It is intended in this document to introduce a handy systematic method for enumerating all possible data dependency cases that could occur between any two instructions that might happen to be processed at the same time at different stages of the pipeline. Given instructions of the instruction set, specific information about operands of each instruction and when an instruction reads or writes data, the method could be used to enumerate all possible data hazard cases and to determine whether forwarding or stalling is suitable for resolving each case.
Faster Parameterized Algorithms using Linear Programming
Venue: arXiv cs.DS 2012
Year: 2012

We investigate the parameterized complexity of Vertex Cover parameterized by the difference between the size of the optimal solution and the value of the linear programming (LP) relaxation of the problem. By carefully analyzing the change in the LP value in the branching steps, we argue that combining previously known preprocessing rules with the most straightforward branching algorithm yields an $O^*((2.618)^k)$ algorithm for the problem. Here $k$ is the excess of the vertex cover size over the LP optimum, and we write $O^*(f(k))$ for a time complexity of the form $O(f(k)n^{O(1)})$, where $f (k)$ grows exponentially with $k$. We proceed to show that a more sophisticated branching algorithm achieves a runtime of $O^*(2.3146^k)$. Following this, using known and new reductions, we give $O^*(2.3146^k)$ algorithms for the parameterized versions of Above Guarantee Vertex Cover, Odd Cycle Transversal, Split Vertex Deletion and Almost 2-SAT, and an $O^*(1.5214^k)$ algorithm for Konig Vertex Deletion, Vertex Cover Param by OCT and Vertex Cover Param by KVD. These algorithms significantly improve the best known bounds for these problems. The most notable improvement is the new bound for Odd Cycle Transversal - this is the first algorithm which beats the dependence on $k$ of the seminal $O^*(3^k)$ algorithm of Reed, Smith and Vetta. Finally, using our algorithm, we obtain a kernel for the standard parameterization of Vertex Cover with at most $2k - c \log k$ vertices. Our kernel is simpler than previously known kernels achieving the same size bound.
Online Discriminative Dictionary Learning for Image Classification Based on Block-Coordinate Descent Method
Venue: arXiv cs.CV 2012
Year: 2012

Previous researches have demonstrated that the framework of dictionary learning with sparse coding, in which signals are decomposed as linear combinations of a few atoms of a learned dictionary, is well adept to reconstruction issues. This framework has also been used for discrimination tasks such as image classification. To achieve better performances of classification, experts develop several methods to learn a discriminative dictionary in a supervised manner. However, another issue is that when the data become extremely large in scale, these methods will be no longer effective as they are all batch-oriented approaches. For this reason, we propose a novel online algorithm for discriminative dictionary learning, dubbed \textbf{ODDL} in this paper. First, we introduce a linear classifier into the conventional dictionary learning formulation and derive a discriminative dictionary learning problem. Then, we exploit an online algorithm to solve the derived problem. Unlike the most existing approaches which update dictionary and classifier alternately via iteratively solving sub-problems, our approach directly explores them jointly. Meanwhile, it can largely shorten the runtime for training and is also particularly suitable for large-scale classification issues. To evaluate the performance of the proposed ODDL approach in image recognition, we conduct some experiments on three well-known benchmarks, and the experimental results demonstrate ODDL is fairly promising for image classification tasks.
Lower bounds for Arrangement-based Range-Free Localization in Sensor Networks
Venue: arXiv cs.CG 2012
Year: 2012

Colander are location aware entities that collaborate to determine approximate location of mobile or static objects when beacons from an object are received by all colanders that are within its distance $R$. This model, referred to as arrangement-based localization, does not require distance estimation between entities, which has been shown to be highly erroneous in practice. Colander are applicable in localization in sensor networks and tracking of mobile objects. A set $S \subset {\mathbb R}^2$ is an $(R,ε)$-colander if by placing receivers at the points of $S$, a wireless device with transmission radius $R$ can be localized to within a circle of radius $ε$. We present tight upper and lower bounds on the size of $(R,ε)$-colanders. We measure the expected size of colanders that will form $(R, ε)$-colanders if they distributed uniformly over the plane.
A New Analysis Method for Simulations Using Node Categorizations
Venue: arXiv cs.SI 2012
Year: 2012

Most research concerning the influence of network structure on phenomena taking place on the network focus on relationships between global statistics of the network structure and characteristic properties of those phenomena, even though local structure has a significant effect on the dynamics of some phenomena. In the present paper, we propose a new analysis method for phenomena on networks based on a categorization of nodes. First, local statistics such as the average path length and the clustering coefficient for a node are calculated and assigned to the respective node. Then, the nodes are categorized using the self-organizing map (SOM) algorithm. Characteristic properties of the phenomena of interest are visualized for each category of nodes. The validity of our method is demonstrated using the results of two simulation models. The proposed method is useful as a research tool to understand the behavior of networks, in particular, for the large-scale networks that existing visualization techniques cannot work well.
Secure and Privacy-Preserving Data Aggregation Protocols for Wireless Sensor Networks
Venue: arXiv cs.CR 2012
Year: 2012

This chapter discusses the need of security and privacy protection mechanisms in aggregation protocols used in wireless sensor networks (WSN). It presents a comprehensive state of the art discussion on the various privacy protection mechanisms used in WSNs and particularly focuses on the CPDA protocols proposed by He et al. (INFOCOM 2007). It identifies a security vulnerability in the CPDA protocol and proposes a mechanism to plug that vulnerability. To demonstrate the need of security in aggregation process, the chapter further presents various threats in WSN aggregation mechanisms. A large number of existing protocols for secure aggregation in WSN are discussed briefly and a protocol is proposed for secure aggregation which can detect false data injected by malicious nodes in a WSN. The performance of the protocol is also presented. The chapter concludes while highlighting some future directions of research in secure data aggregation in WSNs.
Enumeration and Structure of Trapezoidal Words
Venue: arXiv cs.FL 2012
Year: 2012

Trapezoidal words are words having at most $n+1$ distinct factors of length $n$ for every $n\ge 0$. They therefore encompass finite Sturmian words. We give combinatorial characterizations of trapezoidal words and exhibit a formula for their enumeration. We then separate trapezoidal words into two disjoint classes: open and closed. A trapezoidal word is closed if it has a factor that occurs only as a prefix and as a suffix; otherwise it is open. We investigate open and closed trapezoidal words, in relation with their special factors. We prove that Sturmian palindromes are closed trapezoidal words and that a closed trapezoidal word is a Sturmian palindrome if and only if its longest repeated prefix is a palindrome. We also define a new class of words, \emph{semicentral words}, and show that they are characterized by the property that they can be written as $uxyu$, for a central word $u$ and two different letters $x,y$. Finally, we investigate the prefixes of the Fibonacci word with respect to the property of being open or closed trapezoidal words, and show that the sequence of open and closed prefixes of the Fibonacci word follows the Fibonacci sequence.
The collective oscillation period of inter-coupled Goodwin oscillators
Venue: arXiv cs.SY 2012
Year: 2012

Many biological oscillators are arranged in networks composed of many inter-coupled cellular oscillators. However, results are still lacking on the collective oscillation period of inter-coupled gene regulatory oscillators, which, as has been reported, may be different from the oscillation period of an autonomous cellular oscillator. Based on the Goodwin oscillator, we analyze the collective oscillation pattern of coupled cellular oscillator networks. First we give a condition under which the oscillator network exhibits oscillatory and synchronized behavior, then we estimate the collective oscillation period based on a multivariable harmonic balance technique. Analytical results are derived in terms of biochemical parameters, thus giving insight into the basic mechanism of biological oscillation and providing guidance in synthetic biology design. Simulation results are given to confirm the theoretical predictions.
Efficient recovery-based error estimation for the smoothed finite element method for smooth and singular linear elasticity
Venue: arXiv cs.NA 2012
Year: 2012

An error control technique aimed to assess the quality of smoothed finite element approximations is presented in this paper. Finite element techniques based on strain smoothing appeared in 2007 were shown to provide significant advantages compared to conventional finite element approximations. In particular, a widely cited strength of such methods is improved accuracy for the same computational cost. Yet, few attempts have been made to directly assess the quality of the results obtained during the simulation by evaluating an estimate of the discretization error. Here we propose a recovery type error estimator based on an enhanced recovery technique. The salient features of the recovery are: enforcement of local equilibrium and, for singular problems a "smooth+singular" decomposition of the recovered stress. We evaluate the proposed estimator on a number of test cases from linear elastic structural mechanics and obtain precise error estimations whose effectivities, both at local and global levels, are improved compared to recovery procedures not implementing these features.
Simplifying products of fractional powers of powers
Venue: arXiv cs.SC 2012
Year: 2012

Most computer algebra systems incorrectly simplify (z - z)/(sqrt(w^2)/w^3 - 1/(w*sqrt(w^2))) to 0 rather than to 0/0. The reasons for this are: 1. The default simplification doesn't succeed in simplifying the denominator to 0. 2. There is a rule that 0 is the result of 0 divided by anything that doesn't simplify to either 0 or 0/0. Try it on your computer algebra systems! This article describes how to simplify products of the form w^a*(w^b1)^g1 ... (w^bn)^gn correctly and well, where w is any real or complex expression and the exponents are rational numbers. It might seem that correct good simplification of such a restrictive expression class must already be published and/or built into at least one widely used computer-algebra system, but apparently this issue has been overlooked. Default and relevant optional simplification was tested with 86 examples for n=1 on Derive, Maple, Mathematica, Maxima and TI-CAS. Totaled over all five systems, 11% of the results were not equivalent to the input everywhere, 50% of the results did not simplify to 0 a result that was equivalent to 0, and at least 16% of the results exhibited one or more of four additional flaw types. There was substantial room for improvement in all five systems, including the two for which I was a co-author. The good news is: These flaws are easy to fix.
Epidemic Intelligence for the Crowd, by the Crowd (Full Version)
Venue: arXiv cs.SI 2012
Year: 2012

Tracking Twitter for public health has shown great potential. However, most recent work has been focused on correlating Twitter messages to influenza rates, a disease that exhibits a marked seasonal pattern. In the presence of sudden outbreaks, how can social media streams be used to strengthen surveillance capacity? In May 2011, Germany reported an outbreak of Enterohemorrhagic Escherichia coli (EHEC). It was one of the largest described outbreaks of EHEC/HUS worldwide and the largest in Germany. In this work, we study the crowd's behavior in Twitter during the outbreak. In particular, we report how tracking Twitter helped to detect key user messages that triggered signal detection alarms before MedISys and other well established early warning systems. We also introduce a personalized learning to rank approach that exploits the relationships discovered by: (i) latent semantic topics computed using Latent Dirichlet Allocation (LDA), and (ii) observing the social tagging behavior in Twitter, to rank tweets for epidemic intelligence. Our results provide the grounds for new public health research based on social media.
Swarm Behavior of Intelligent Cloud
Venue: arXiv cs.DC 2012
Year: 2012

In this paper, the main aim is to exhibit swarm intelligence power in cloud based scenario. Heterogeneous environment has been configured at server-side network of the whole cloud network. In the proposed system, different types of servers are being used to manage useful assorted atmosphere. Swarm intelligence has been adopted for enhancing the performance of overall system network. Specific location at server-side of the network is going to be selected by the swarm intelligence concept for accessing desired elements. Flexibility, robustness and self-organization, which are to be considered at the time of designing the system environment, are the main features of swarm intelligence.
Performance Evaluation of Biometric Template Update
Venue: arXiv cs.OH 2012
Year: 2012

Template update allows to modify the biometric reference of a user while he uses the biometric system. With such kind of mechanism we expect the biometric system uses always an up to date representation of the user, by capturing his intra-class (temporary or permanent) variability. Although several studies exist in the literature, there is no commonly adopted evaluation scheme. This does not ease the comparison of the different systems of the literature. In this paper, we show that using different evaluation procedures can lead in different, and contradictory, interpretations of the results. We use a keystroke dynamics (which is a modality suffering of template ageing quickly) template update system on a dataset consisting of height different sessions to illustrate this point. Even if we do not answer to this problematic, it shows that it is necessary to normalize the template update evaluation procedures.