OpenRaiser/Intern-Atlas huggingface dataset:
A Lossy Graph Model for Decoding Delay Reduction in Instantly Decodable Network Coding
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we study the broadcast decoding delay performance of generalized instantly decodable network coding (G-IDNC) in the lossy feedback scenario. The problem is formulated as a maximum weight clique problem over the G-IDNC graph in [1]. In order to further minimize the decoding delay, we introduce in this paper the lossy G-IDNC graph (LG-IDNC). Whereas the G-IDNC graph represents only doubtless combinable packets, the LG-IDNC graph represents also uncertain packet combinations when the expected decoding delay of the encoded packet is lower than the individual expected decoding delay of each packet encoded in it. Since the maximum weight clique problem is known to be NP-hard, we use the heuristic introduced in [2] to discover the maximum weight clique in the LG-IDNC graph and finally we compare the decoding delay performance of LG-IDNC and G-IDNC graphs through extensive simulations. Numerical results show that our new LG-IDNC graph formulation outperforms the G-IDNC graph formulation in all situations and achieves significant improvement in the decoding delay especially when the feedback erasure probability is higher than the packet erasure probability.
Deterministic Parameterized Algorithms for Matching and Packing Problems
Venue: arXiv cs.DS 2013
Year: 2013

We present three deterministic parameterized algorithms for well-studied packing and matching problems, namely, Weighted q-Dimensional p-Matching ((q,p)-WDM) and Weighted q-Set p-Packing ((q,p)-WSP). More specifically, we present an O*(2.85043^{(q-1)p}) time deterministic algorithm for (q,p)-WDM, an O*(8.04143^p) time deterministic algorithm for the unweighted version of (3,p)-WDM, and an O*((0.56201\cdot 2.85043^q)^p) time deterministic algorithm for (q,p)-WSP. Our algorithms significantly improve the previously best known O* running times in solving (q,p)-WDM and (q,p)-WSP, and the previously best known deterministic O* running times in solving the unweighted versions of these problems. Moreover, we present kernels of size O(e^qq(p-1)^q) for (q,p)-WDM and (q,p)-WSP, improving the previously best known kernels of size O(q!q(p-1)^q) for these problems.
On the optimal tradeoff of average service cost rate, average utility rate, and average delay for the state dependent M/M/1 queue
Venue: arXiv cs.PF 2013
Year: 2013

The optimal tradeoff between average service cost rate, average utility rate, and average delay is addressed for a state dependent M/M/1 queueing model, with controllable queue length dependent service rates and arrival rates. For a model with a constant arrival rate $λ$ for all queue lengths, we obtain an asymptotic characterization of the minimum average delay, when the average service cost rate is a small positive quantity, $V$, more than the minimum average service cost rate required for queue stability. We show that depending on the value of the arrival rate $λ$, the assumed service cost rate function, and the possible values of the service rates, the minimum average delay either: a) increases only to a finite value, b) increases without bound as $\log\frac{1}{V}$, c) increases without bound as $\frac{1}{V}$, or d) increases without bound as $\frac{1}{\sqrt{V}}$, when $V \downarrow 0$. We then extend our analysis to (i) a complementary problem, where the tradeoff of average utility rate and average delay is analysed for a M/M/1 queueing model, with controllable queue length dependent arrival rates, but a constant service rate $μ$ for all queue lengths, and (ii) a M/M/1 queueing model, with controllable queue length dependent service rates and arrival rates, for which we obtain an asymptotic characterization of the minimum average delay under constraints on both the average service cost rate as well as the average utility rate. The results that we obtain are useful in obtaining intuition as well guidance for the derivation of similar asymptotic lower bounds, such as the Berry-Gallager asymptotic lower bound, for discrete time queueing models.
Free-configuration Biased Sampling for Motion Planning: Errata
Venue: arXiv cs.RO 2013
Year: 2013

This document contains improved and updated proofs of convergence for the sampling method presented in our paper "Free-configuration Biased Sampling for Motion Planning".
An Exact Algorithm for the Generalized List $T$-Coloring Problem
Venue: arXiv cs.DM 2013
Year: 2013

The generalized list $T$-coloring is a common generalization of many graph coloring models, including classical coloring, $L(p,q)$-labeling, channel assignment and $T$-coloring. Every vertex from the input graph has a list of permitted labels. Moreover, every edge has a set of forbidden differences. We ask for such a labeling of vertices of the input graph with natural numbers, in which every vertex gets a label from its list of permitted labels and the difference of labels of the endpoints of each edge does not belong to the set of forbidden differences of this edge. In this paper we present an exact algorithm solving this problem, running in time $\mathcal{O}^*((τ+2)^n)$, where $τ$ is the maximum forbidden difference over all edges of the input graph and $n$ is the number of its vertices. Moreover, we show how to improve this bound if the input graph has some special structure, e.g. a bounded maximum degree, no big induced stars or a perfect matching.
Computation of the Marcum Q-function
Venue: arXiv cs.MS 2013
Year: 2013

Methods and an algorithm for computing the generalized Marcum $Q-$function ($Q_μ(x,y)$) and the complementary function ($P_μ(x,y)$) are described. These functions appear in problems of different technical and scientific areas such as, for example, radar detection and communications, statistics and probability theory, where they are called the non-central chi-square or the non central gamma cumulative distribution functions. The algorithm for computing the Marcum functions combines different methods of evaluation in different regions: series expansions, integral representations, asymptotic expansions, and use of three-term homogeneous recurrence relations. A relative accuracy close to $10^{-12}$ can be obtained in the parameter region $(x,y,μ) \in [0,\,A]\times [0,\,A]\times [1,\,A]$, $A=200$, while for larger parameters the accuracy decreases (close to $10^{-11}$ for $A=1000$ and close to $5\times 10^{-11}$ for $A=10000$).
Artificial Intelligence in Humans
Venue: arXiv cs.AI 2013
Year: 2013

In this paper, I put forward that in many instances, thinking mechanisms are equivalent to artificial intelligence modules programmed into the human mind.
On the inequality of the 3V's of Big Data Architectural Paradigms: A case for heterogeneity
Venue: arXiv cs.DB 2013
Year: 2013

The well-known 3V architectural paradigm for Big Data introduced by Laney (2011), provides a simplified framework for defining the architecture of a big data platform to be deployed in various scenarios tackling processing of massive datasets. While additional components such as Variability and Veracity have been discussed as an extension to the 3V model, the basic components (volume, variety, velocity) provide a quantitative framework while variability and veracity target a more qualitative approach. In this paper we argue why the basic 3V's are not equal due to the different requirements that need to be covered in case higher demands for a particular "V". Similar to other conjectures such as the CAP theorem 3V based architectures differ on their implementation. We call this paradigm heterogeneity and we provide a taxonomy of the existing tools (as of 2013) covering the Hadoop ecosystem from the perspective of heterogeneity. This paper contributes on the understanding of the Hadoop ecosystem from the perspective of different workloads and aims to help researchers and practitioners on the design of scalable platforms targeting different operational needs.
Initial validation of a virtual-reality learning environment for prostate biopsies: realism matters!
Venue: arXiv cs.CY 2013
Year: 2013

: Introduction-objectives: A virtual-reality learning environment dedicated to prostate biopsies was designed to overcome the limitations of current classical teaching methods. The aim of this study was to validate reliability, face, content and construct of the simulator. Materials and methods: The simulator is composed of a) a laptop computer, b) a haptic device with a stylus that mimics the ultrasound probe, c) a clinical case database including three dimensional (3D) ultrasound volumes and patient data and d) a learning environment with a set of progressive exercises including a randomized 12-core biopsy procedure. Both visual (3D biopsy mapping) and numerical (score) feedback are given to the user. The simulator evaluation was conducted in an academic urology department on 7 experts and 14 novices who each performed a virtual biopsy procedure and completed a face and content validity questionnaire. Results: The overall realism of the biopsy procedure was rated at a median of 9/10 by non-experts (7.1-9.8). Experts rated the usefulness of the simulator for the initial training of urologists at 8.2/10 (7.9-8.3), but reported the range of motion and force feedback as significantly less realistic than novices (p=0.01 and 0.03 respectively). Pearson's r correlation coefficient between correctly placed biopsies on the right and left side of the prostate for each user was 0.79 (p<0.001). The 7 experts had a median score of 64% (59-73), and the 14 novices a median score of 52% (43-67), without reaching statistical significance (p=0,19). Conclusion: The newly designed virtual reality learning environment proved its versatility and its reliability, face and content were validated. Demonstrating the construct validity will require improvements to the realism and scoring system used.
The Squared-Error of Generalized LASSO: A Precise Analysis
Venue: arXiv cs.IT 2013
Year: 2013

We consider the problem of estimating an unknown signal $x_0$ from noisy linear observations $y = Ax_0 + z\in R^m$. In many practical instances, $x_0$ has a certain structure that can be captured by a structure inducing convex function $f(\cdot)$. For example, $\ell_1$ norm can be used to encourage a sparse solution. To estimate $x_0$ with the aid of $f(\cdot)$, we consider the well-known LASSO method and provide sharp characterization of its performance. We assume the entries of the measurement matrix $A$ and the noise vector $z$ have zero-mean normal distributions with variances $1$ and $σ^2$ respectively. For the LASSO estimator $x^*$, we attempt to calculate the Normalized Square Error (NSE) defined as $\frac{\|x^*-x_0\|_2^2}{σ^2}$ as a function of the noise level $σ$, the number of observations $m$ and the structure of the signal. We show that, the structure of the signal $x_0$ and choice of the function $f(\cdot)$ enter the error formulae through the summary parameters $D(cone)$ and $D(λ)$, which are defined as the Gaussian squared-distances to the subdifferential cone and to the $λ$-scaled subdifferential, respectively. The first LASSO estimator assumes a-priori knowledge of $f(x_0)$ and is given by $\arg\min_{x}\{{\|y-Ax\|_2}~\text{subject to}~f(x)\leq f(x_0)\}$. We prove that its worst case NSE is achieved when $σ\rightarrow 0$ and concentrates around $\frac{D(cone)}{m-D(cone)}$. Secondly, we consider $\arg\min_{x}\{\|y-Ax\|_2+λf(x)\}$, for some $λ\geq 0$. This time the NSE formula depends on the choice of $λ$ and is given by $\frac{D(λ)}{m-D(λ)}$. We then establish a mapping between this and the third estimator $\arg\min_{x}\{\frac{1}{2}\|y-Ax\|_2^2+ λf(x)\}$. Finally, for a number of important structured signal classes, we translate our abstract formulae to closed-form upper bounds on the NSE.
A Comparative Study on Linguistic Feature Selection in Sentiment Polarity Classification
Venue: arXiv cs.CL 2013
Year: 2013

Sentiment polarity classification is perhaps the most widely studied topic. It classifies an opinionated document as expressing a positive or negative opinion. In this paper, using movie review dataset, we perform a comparative study with different single kind linguistic features and the combinations of these features. We find that the classic topic-based classifier(Naive Bayes and Support Vector Machine) do not perform as well on sentiment polarity classification. And we find that with some combination of different linguistic features, the classification accuracy can be boosted a lot. We give some reasonable explanations about these boosting outcomes.
A Divide-and-Conquer Solver for Kernel Support Vector Machines
Venue: arXiv cs.LG 2013
Year: 2013

The kernel support vector machine (SVM) is one of the most widely used classification methods; however, the amount of computation required becomes the bottleneck when facing millions of samples. In this paper, we propose and analyze a novel divide-and-conquer solver for kernel SVMs (DC-SVM). In the division step, we partition the kernel SVM problem into smaller subproblems by clustering the data, so that each subproblem can be solved independently and efficiently. We show theoretically that the support vectors identified by the subproblem solution are likely to be support vectors of the entire kernel SVM problem, provided that the problem is partitioned appropriately by kernel clustering. In the conquer step, the local solutions from the subproblems are used to initialize a global coordinate descent solver, which converges quickly as suggested by our analysis. By extending this idea, we develop a multilevel Divide-and-Conquer SVM algorithm with adaptive clustering and early prediction strategy, which outperforms state-of-the-art methods in terms of training speed, testing accuracy, and memory usage. As an example, on the covtype dataset with half-a-million samples, DC-SVM is 7 times faster than LIBSVM in obtaining the exact SVM solution (to within $10^{-6}$ relative error) which achieves 96.15% prediction accuracy. Moreover, with our proposed early prediction strategy, DC-SVM achieves about 96% accuracy in only 12 minutes, which is more than 100 times faster than LIBSVM.
Off-The-Grid Spectral Compressed Sensing With Prior Information
Venue: arXiv cs.IT 2013
Year: 2013

Recent research in off-the-grid compressed sensing (CS) has demonstrated that, under certain conditions, one can successfully recover a spectrally sparse signal from a few time-domain samples even though the dictionary is continuous. In this paper, we extend off-the-grid CS to applications where some prior information about spectrally sparse signal is known. We specifically consider cases where a few contributing frequencies or poles, but not their amplitudes or phases, are known a priori. Our results show that equipping off-the-grid CS with the known-poles algorithm can increase the probability of recovering all the frequency components.
On the Benefit of Information Centric Networks for Traffic Engineering
Venue: arXiv cs.NI 2013
Year: 2013

Current Internet performs traffic engineering (TE) by estimating traffic matrices on a regular schedule, and allocating flows based upon weights computed from these matrices. This means the allocation is based upon a guess of the traffic in the network based on its history. Information-Centric Networks on the other hand provide a finer-grained description of the traffic: a content between a client and a server is uniquely identified by its name, and the network can therefore learn the size of different content items, and perform traffic engineering and resource allocation accordingly. We claim that Information-Centric Networks can therefore provide a better handle to perform traffic engineering, resulting in significant performance gain. We present a mechanism to perform such resource allocation. We see that our traffic engineering method only requires knowledge of the flow size (which, in ICN, can be learned from previous data transfers) and outperforms a min-MLU allocation in terms of response time. We also see that our method identifies the traffic allocation patterns similar to that of min-MLU without having access to the traffic matrix ahead of time. We show a very significant gain in response time where min MLU is almost 50% slower than our ICN-based TE method.
Resource Management for Device-to-Device Underlay Communication
Venue: arXiv cs.GT 2013
Year: 2013

Device-to-Device (D2D) communication is a technology component for LTE-A. The existing researches allow D2D as an underlay to the cellular network to increase the spectral efficiency. In this book, D2D communication underlaying cellular networks is studied. Some physical-layer techniques and cross-layer optimization methods on resource management and interference avoidance are proposed and discussed. WINNER II channel models is applied to be the signal and interference model and simulation results show that the performance of D2D link is closely related to the distance between D2D transmitter and receiver and that between interference source and the receiver. Besides, by power control, D2D SINR degrades, which will naturally contribute to low interference to cellular communication. A simple mode selection method of D2D communication is introduced. Based on path-loss (PL) mode selection criterion, D2D gives better performance than traditional cellular system. When D2D pair is farther away from the BS, a better results can be obtained. Game theory, which offers a wide variety of analytical tools to study the complex interactions of players and predict their choices, can be used for power and radio resource management in D2D communication. A reverse iterative combinatorial auction is formulated as a mechanism to allocate the spectrum resources for D2D communications with multiple user pairs sharing the same channel. In addition, a game theoretic approach is developed to implement joint scheduling, power control and channel allocation for D2D communication. Finally, joint power and spectrum resource allocation method is studied under consideration of battery lifetime, which is an important application of D2D communication on increasing user's energy efficiency. The simulation results show that all these methods have beneficial effects on improving the system performance.
Semantic Stability in Social Tagging Streams
Venue: arXiv cs.CY 2013
Year: 2013

One potential disadvantage of social tagging systems is that due to the lack of a centralized vocabulary, a crowd of users may never manage to reach a consensus on the description of resources (e.g., books, users or songs) on the Web. Yet, previous research has provided interesting evidence that the tag distributions of resources may become semantically stable over time as more and more users tag them. At the same time, previous work has raised an array of new questions such as: (i) How can we assess the semantic stability of social tagging systems in a robust and methodical way? (ii) Does semantic stabilization of tags vary across different social tagging systems and ultimately, (iii) what are the factors that can explain semantic stabilization in such systems? In this work we tackle these questions by (i) presenting a novel and robust method which overcomes a number of limitations in existing methods, (ii) empirically investigating semantic stabilization processes in a wide range of social tagging systems with distinct domains and properties and (iii) detecting potential causes for semantic stabilization, specifically imitation behavior, shared background knowledge and intrinsic properties of natural language. Our results show that tagging streams which are generated by a combination of imitation dynamics and shared background knowledge exhibit faster and higher semantic stability than tagging streams which are generated via imitation dynamics or natural language streams alone.
Algorithmic and Hardness Results for the Colorful Components Problems
Venue: arXiv cs.DS 2013
Year: 2013

In this paper we investigate the colorful components framework, motivated by applications emerging from comparative genomics. The general goal is to remove a collection of edges from an undirected vertex-colored graph $G$ such that in the resulting graph $G'$ all the connected components are colorful (i.e., any two vertices of the same color belong to different connected components). We want $G'$ to optimize an objective function, the selection of this function being specific to each problem in the framework. We analyze three objective functions, and thus, three different problems, which are believed to be relevant for the biological applications: minimizing the number of singleton vertices, maximizing the number of edges in the transitive closure, and minimizing the number of connected components. Our main result is a polynomial time algorithm for the first problem. This result disproves the conjecture of Zheng et al. that the problem is $ NP$-hard (assuming $P \neq NP$). Then, we show that the second problem is $ APX$-hard, thus proving and strengthening the conjecture of Zheng et al. that the problem is $ NP$-hard. Finally, we show that the third problem does not admit polynomial time approximation within a factor of $|V|^{1/14 - ε}$ for any $ε> 0$, assuming $P \neq NP$ (or within a factor of $|V|^{1/2 - ε}$, assuming $ZPP \neq NP$).
Two are Better Than One: Adaptive Sparse System Identification using Affine Combination of Two Sparse Adaptive Filters
Venue: arXiv cs.IT 2013
Year: 2013

Sparse system identification problems often exist in many applications, such as echo interference cancellation, sparse channel estimation, and adaptive beamforming. One of popular adaptive sparse system identification (ASSI) methods is adopting only one sparse least mean square (LMS) filter. However, the adoption of only one sparse LMS filter cannot simultaneously achieve fast convergence speed and small steady-state mean state deviation (MSD). Unlike the conventional method, we propose an improved ASSI method using affine combination of two sparse LMS filters to simultaneously achieving fast convergence and low steady-state MSD. First, problem formulation and standard affine combination of LMS filters are introduced. Then an approximate optimum affine combiner is adopted for the proposed filter according to stochastic gradient search method. Later, to verify the proposed filter for ASSI, computer simulations are provided to confirm effectiveness of the proposed filter which can achieve better estimation performance than the conventional one and standard affine combination of LMS filters.
Onboarding in Open Source Software Projects: A Preliminary Analysis
Venue: arXiv cs.SE 2013
Year: 2013

Nowadays, many software projects are partially or completely open-source based. There is an increasing need for companies to participate in open-source software (OSS) projects, e.g., in order to benefit from open source ecosystems. OSS projects introduce particular challenges that have to be understood in order to gain the benefits. One such challenge is getting newcomers onboard into the projects effectively. Similar challenges may be present in other self-organised, virtual team environments. In this paper we present preliminary observations and results of in-progress research that studies the process of onboarding into virtual OSS teams. The study is based on a program created and conceived at Stanford University in conjunction with Facebook's Education Modernization program. It involves the collaboration of more than a dozen international universities and nine open source projects. More than 120 students participated in 2013. The students have been introduced to and supported by mentors experienced in the participating OSS projects. Our findings indicate that mentoring is an important factor for effective onboarding in OSS projects, promoting cohesion within distributed teams and maintaining an appropriate pace.