OpenRaiser/Intern-Atlas huggingface dataset:
Requirements of a Recovery Solution for Failure of Composite Web Services
Venue: arXiv cs.SE 2012
Year: 2012

Web services are building blocks of interoperable systems. Composing Web services makes the processes capable of doing complex tasks. Composite services may fail during their execution which can be diagnosed by a mediator. The mediator adapts the structure so that the failure is recovered. Moreover, future executions should avoid the situation or organize a strategy to repair the structure with a minimum delay. In this paper the failure reasons of a composite service are reviewed. Furthermore, the requirements of a solution for recovery of a system from a failure are investigated.
On Hidden Markov Processes with Infinite Excess Entropy
Venue: arXiv cs.IT 2012
Year: 2012

We investigate stationary hidden Markov processes for which mutual information between the past and the future is infinite. It is assumed that the number of observable states is finite and the number of hidden states is countably infinite. Under this assumption, we show that the block mutual information of a hidden Markov process is upper bounded by a power law determined by the tail index of the hidden state distribution. Moreover, we exhibit three examples of processes. The first example, considered previously, is nonergodic and the mutual information between the blocks is bounded by the logarithm of the block length. The second example is also nonergodic but the mutual information between the blocks obeys a power law. The third example obeys the power law and is ergodic.
New constructions of RIP matrices with fast multiplication and fewer rows
Venue: arXiv cs.DS 2012
Year: 2012

In compressed sensing, the "restricted isometry property" (RIP) is a sufficient condition for the efficient reconstruction of a nearly k-sparse vector x in C^d from m linear measurements Phi x. It is desirable for m to be small, and for Phi to support fast matrix-vector multiplication. In this work, we give a randomized construction of RIP matrices Phi in C^{m x d}, preserving the L_2 norms of all k-sparse vectors with distortion 1+eps, where the matrix-vector multiply Phi x can be computed in nearly linear time. The number of rows m is on the order of eps^{-2}klog dlog^2(klog d). Previous analyses of constructions of RIP matrices supporting fast matrix-vector multiplies, such as the sampled discrete Fourier matrix, required m to be larger by roughly a log k factor. Supporting fast matrix-vector multiplication is useful for iterative recovery algorithms which repeatedly multiply by Phi or Phi^*. Furthermore, our construction, together with a connection between RIP matrices and the Johnson-Lindenstrauss lemma in [Krahmer-Ward, SIAM. J. Math. Anal. 2011], implies fast Johnson-Lindenstrauss embeddings with asymptotically fewer rows than previously known. Our approach is a simple twist on previous constructions. Rather than choosing the rows for the embedding matrix to be rows sampled from some larger structured matrix (such as the discrete Fourier transform or a random circulant matrix), we instead choose each row of the embedding matrix to be a linear combination of a small number of rows of the original matrix, with random sign flips as coefficients. The main tool in our analysis is a recent bound for the supremum of certain types of Rademacher chaos processes in [Krahmer-Mendelson-Rauhut, arXiv:1207.0235].
A PRG for Lipschitz Functions of Polynomials with Applications to Sparsest Cut
Venue: arXiv cs.CC 2012
Year: 2012

We give improved pseudorandom generators (PRGs) for Lipschitz functions of low-degree polynomials over the hypercube. These are functions of the form psi(P(x)), where P is a low-degree polynomial and psi is a function with small Lipschitz constant. PRGs for smooth functions of low-degree polynomials have received a lot of attention recently and play an important role in constructing PRGs for the natural class of polynomial threshold functions. In spite of the recent progress, no nontrivial PRGs were known for fooling Lipschitz functions of degree O(log n) polynomials even for constant error rate. In this work, we give the first such generator obtaining a seed-length of (log n)\tilde{O}(d^2/eps^2) for fooling degree d polynomials with error eps. Previous generators had an exponential dependence on the degree. We use our PRG to get better integrality gap instances for sparsest cut, a fundamental problem in graph theory with many applications in graph optimization. We give an instance of uniform sparsest cut for which a powerful semi-definite relaxation (SDP) first introduced by Goemans and Linial and studied in the seminal work of Arora, Rao and Vazirani has an integrality gap of exp(Ω((log log n)^{1/2})). Understanding the performance of the Goemans-Linial SDP for uniform sparsest cut is an important open problem in approximation algorithms and metric embeddings and our work gives a near-exponential improvement over previous lower bounds which achieved a gap of Ω(log log n).
The validation of (advanced) bibliometric indicators through peer assessments: A comparative study using data from InCites and F1000
Venue: arXiv cs.DL 2012
Year: 2012

The data of F1000 provide us with the unique opportunity to investigate the relationship between peers' ratings and bibliometric metrics on a broad and comprehensive data set with high-quality ratings. F1000 is a post-publication peer review system of the biomedical literature. The comparison of metrics with peer evaluation has been widely acknowledged as a way of validating metrics. Based on the seven indicators offered by InCites, we analyzed the validity of raw citation counts (Times Cited, 2nd Generation Citations, and 2nd Generation Citations per Citing Document), normalized indicators (Journal Actual/Expected Citations, Category Actual/Expected Citations, and Percentile in Subject Area), and a journal based indicator (Journal Impact Factor). The data set consists of 125 papers published in 2008 and belonging to the subject category cell biology or immunology. As the results show, Percentile in Subject Area achieves the highest correlation with F1000 ratings; we can assert that for further three other indicators (Times Cited, 2nd Generation Citations, and Category Actual/Expected Citations) the 'true' correlation with the ratings reaches at least a medium effect size.
Information and Communication Technology in Combating Counterfeit Drugs
Venue: arXiv cs.OH 2012
Year: 2012

Pharma frauds are on the rise, counterfeit drugs are giving sleepless nights to patients, pharmaceutical companies and governments. The laws prohibiting the sales of counterfeit drugs cannot succeed without technological interventions. Several analytical techniques and tools including spectroscopy, holograms, barcoding, differentiated packing, radio frequency identification, fingerprints, hyperspectral imaging etc. have been employed over the years in combating this menace; however this challenge is becoming more sophisticated with the evolution of the World Wide Web and online pharmacies. This paper presents a review on the contribution of Information and Communication Technology (ICT) as a drug counterfeit countermeasure.
Application-centric Resource Provisioning for Amazon EC2 Spot Instances
Venue: arXiv cs.DC 2012
Year: 2012

In late 2009, Amazon introduced spot instances to offer their unused resources at lower cost with reduced reliability. Amazon's spot instances allow customers to bid on unused Amazon EC2 capacity and run those instances for as long as their bid exceeds the current spot price. The spot price changes periodically based on supply and demand, and customers whose bids exceed it gain access to the available spot instances. Customers may expect their services at lower cost with spot instances compared to on-demand or reserved. However the reliability is compromised since the instances(IaaS) providing the service(SaaS) may become unavailable at any time without any notice to the customer. Checkpointing and migration schemes are of great use to cope with such situation. In this paper we study various checkpointing schemes that can be used with spot instances. Also we device some algorithms for checkpointing scheme on top of application-centric resource provisioning framework that increase the reliability while reducing the cost significantly.
Preserving privacy for secure and outsourcing for Linear Programming in cloud computing
Venue: arXiv cs.CR 2012
Year: 2012

Cloud computing is the long dreamed vision of computing as a utility, where users can remotely store their data into the cloud so as to enjoy the on-demand high quality applications and services from a shared pool of configurable computing resources. By data outsourcing, users can be relieved from the burden of local data storage and maintenance. we utilize the public key based homomorphism authenticator and uniquely integrate it with random mask technique to achieve a privacy-preserving public auditing system for cloud data storage security while keeping all above requirements in mind. To support efficient handling of multiple auditing tasks, we further explore the technique of bilinear aggregate signature to extend our main result into a multi-user setting, where TPA can perform multiple auditing tasks simultaneously along with investigates secure outsourcing of widely applicable linear programming (LP) computations. In order to achieve practical efficiency, our mechanism design explicitly decomposes the LP computation outsourcing into public LP solvers running on the cloud and private LP parameters owned by the customer Extensive security and performance analysis shows the proposed schemes are provably secure and highly efficient.
Fast Hamiltonicity checking via bases of perfect matchings
Venue: arXiv cs.DS 2012
Year: 2012

For an even integer t \geq 2, the Matchings Connecivity matrix H_t is a matrix that has rows and columns both labeled by all perfect matchings of the complete graph K_t on t vertices; an entry H_t[M_1,M_2] is 1 if M_1\cup M_2 is a Hamiltonian cycle and 0 otherwise. Motivated by the computational study of the Hamiltonicity problem, we present three results on the structure of H_t: We first show that H_t has rank at most 2^{t/2-1} over GF(2) via an appropriate factorization that explicitly provides families of matchings X_t forming bases for H_t. Second, we show how to quickly change representation between such bases. Third, we notice that the sets of matchings X_t induce permutation matrices within H_t. Subsequently, we use the factorization to obtain an 1.888^n n^{O(1)} time Monte Carlo algorithm that solves the Hamiltonicity problem in directed bipartite graphs. Our algorithm as well counts the number of Hamiltonian cycles modulo two in directed bipartite or undirected graphs in the same time bound. Moreover, we use the fast basis change algorithm from the second result to present a Monte Carlo algorithm that given an undirected graph on n vertices along with a path decomposition of width at most pw decides Hamiltonicity in (2+\sqrt{2})^{pw}n^{O(1)} time. Finally, we use the third result to show that for every ε>0 this cannot be improved to (2+\sqrt{2}-ε)^{pw}n^{O(1)} time unless the Strong Exponential Time Hypothesis fails, i.e., a faster algorithm for this problem would imply the breakthrough result of a (2-ε)^n time algorithm for CNF-Sat.
A Riemannian geometry for low-rank matrix completion
Venue: arXiv cs.LG 2012
Year: 2012

We propose a new Riemannian geometry for fixed-rank matrices that is specifically tailored to the low-rank matrix completion problem. Exploiting the degree of freedom of a quotient space, we tune the metric on our search space to the particular least square cost function. At one level, it illustrates in a novel way how to exploit the versatile framework of optimization on quotient manifold. At another level, our algorithm can be considered as an improved version of LMaFit, the state-of-the-art Gauss-Seidel algorithm. We develop necessary tools needed to perform both first-order and second-order optimization. In particular, we propose gradient descent schemes (steepest descent and conjugate gradient) and trust-region algorithms. We also show that, thanks to the simplicity of the cost function, it is numerically cheap to perform an exact linesearch given a search direction, which makes our algorithms competitive with the state-of-the-art on standard low-rank matrix completion instances.
MISO Broadcast Channel with Delayed and Evolving CSIT
Venue: arXiv cs.IT 2012
Year: 2012

The work considers the two-user MISO broadcast channel with gradual and delayed accumulation of channel state information at the transmitter (CSIT), and addresses the question of how much feedback is necessary, and when, in order to achieve a certain degrees-of-freedom (DoF) performance. Motivated by limited-capacity feedback links that may not immediately convey perfect CSIT, and focusing on the block fading scenario, we consider a progressively increasing CSIT quality as time progresses across the coherence period (T channel uses - evolving current CSIT), or at any time after (delayed CSIT). Specifically, for any set of feedback quality exponents a_t, t=1,...,T, describing the high-SNR rates-of-decay of the mean square error of the current CSIT estimates at time t<=T (during the coherence period), the work describes the optimal DOF region in several different evolving CSIT settings, including the setting with perfect delayed CSIT, the asymmetric setting where the quality of feedback differs from user to user, as well as considers the DoF region in the presence of a imperfect delayed CSIT corresponding to having a limited number of overall feedback bits. These results are supported by novel multi-phase precoding schemes that utilize gradually improving CSIT. The approach here naturally incorporates different settings such as the perfect-delayed CSIT setting of Maddah-Ali and Tse, the imperfect current CSIT setting of Yang et al. and of Gou and Jafar, the asymmetric setting of Maleki et al., as well as the not-so-delayed CSIT setting of Lee and Heath.
Annotations for Supporting Collaboration through Artifacts
Venue: arXiv cs.HC 2012
Year: 2012

Shared artifacts and environments play a prominent role in shaping the collaboration between their users. This article describes this role and explains how annotations can provide a bridge between direct communication and collaboration through artifacts. The various functions of annotations are discussed through examples that represent some of the important trends in annotation research. Ultimately, some of the research issues are briefly discussed, followed by my perspective on the future of asynchronous distributed collaborative systems with respect to annotations.
James-Stein Type Center Pixel Weights for Non-Local Means Image Denoising
Venue: arXiv cs.CV 2012
Year: 2012

Non-Local Means (NLM) and variants have been proven to be effective and robust in many image denoising tasks. In this letter, we study the parameter selection problem of center pixel weights (CPW) in NLM. Our key contributions are: 1) we give a novel formulation of the CPW problem from the statistical shrinkage perspective; 2) we introduce the James-Stein type CPWs for NLM; and 3) we propose a new adaptive CPW that is locally tuned for each image pixel. Our experimental results showed that compared to existing CPW solutions, the new proposed CPWs are more robust and effective under various noise levels. In particular, the NLM with the James-Stein type CPWs attain higher means with smaller variances in terms of the peak signal and noise ratio, implying they improve the NLM robustness and make it less sensitive to parameter selection.
Pairings on Generalized Huff Curves
Venue: arXiv cs.CR 2012
Year: 2012

This paper presents the Tate pairing computation on generalized Huff curves proposed by Wu and Feng. In fact, we extend the results of the Tate pairing computation on the standard Huff elliptic curves done previously by Joye, Tibouchi and Vergnaud. We show that the addition step of the Miller loop can be performed in $1\mathbf{M}+(k+15)\mathbf{m}+2\mathbf{c}$ and the doubling one in $1\mathbf{M} + 1\mathbf{S} + (k + 12) \mathbf{m} + 5\mathbf{s} + 2\mathbf{c}$ on the generalized Huff curve.
Learning Monocular Reactive UAV Control in Cluttered Natural Environments
Venue: arXiv cs.RO 2012
Year: 2012

Autonomous navigation for large Unmanned Aerial Vehicles (UAVs) is fairly straight-forward, as expensive sensors and monitoring devices can be employed. In contrast, obstacle avoidance remains a challenging task for Micro Aerial Vehicles (MAVs) which operate at low altitude in cluttered environments. Unlike large vehicles, MAVs can only carry very light sensors, such as cameras, making autonomous navigation through obstacles much more challenging. In this paper, we describe a system that navigates a small quadrotor helicopter autonomously at low altitude through natural forest environments. Using only a single cheap camera to perceive the environment, we are able to maintain a constant velocity of up to 1.5m/s. Given a small set of human pilot demonstrations, we use recent state-of-the-art imitation learning techniques to train a controller that can avoid trees by adapting the MAVs heading. We demonstrate the performance of our system in a more controlled environment indoors, and in real natural forest environments outdoors.
A Novel Approach for Handling Misbehaving Nodes in Behavior-Aware Mobile Networking
Venue: arXiv cs.NI 2012
Year: 2012

Profile-cast is a service paradigm within the communication framework of delay tolerant networks (DTN). Instead of using destination addresses to determine the final destination it uses similarity-based forwarding protocol. With the rise in popularity of various wireless networks, the need to make wireless technologies robust, resilient to attacks and failure becomes mandatory. One issue that remains to be addressed in behavioral networks is node co-operation in forwarding packets. Nodes might behave selfishly (due to bandwidth preservation, energy /power constraints) or maliciously by dropping packets or not forwarding them to other nodes based on profile similarity. In both cases the net result is degradation in the performance of the network. It is our goal to show that the performance of the behavioral network can be improved by employing self-policing scheme that would detect node misbehavior and then decide how to tackle them in order to ensure node cooperation or so that the overall performance does not fall below a certain threshold. For this various existing self-policing techniques which are in use in ad-hoc networks will be first tried on this behavioral scenario.At various stages simulation would be used to measure performances of the network under different constraints, and after subjected to different techniques
Simple I/O-efficient flow accumulation on grid terrains
Venue: arXiv cs.DS 2012
Year: 2012

The flow accumulation problem for grid terrains takes as input a matrix of flow directions, that specifies for each cell of the grid to which of its eight neighbours any incoming water would flow. The problem is to compute, for each cell c, from how many cells of the terrain water would reach c. We show that this problem can be solved in O(scan(N)) I/Os for a terrain of N cells. Taking constant factors in the I/O-efficiency into account, our algorithm may be an order of magnitude faster than the previously known algorithm that is based on time-forward processing and needs O(sort(N)) I/Os.
An ICT Enhanced Life Quality for the Elderly in Developing Countries: Analysis Study Applied to Sri Lanka
Venue: arXiv cs.CY 2012
Year: 2012

In the recent years, the entire world has seen a tremendous increase in the elderly population. Even though countries differ in the numerical criterion for defining the old age, the UN has agreed that the cutoff of 60+ years refers to the older population. When the percentage of older population increases in a country, the country faces new challenges in the form of economical as well as social impacts. The economic impacts are felt in the form of a shortfall in labor supply, income, household savings while an increase in the payment of retirement benefits and healthcare expenditures. On the social side, the elderly population feels continuously isolated due to the changes in the value system. The United Nations has identified five quality of life characteristics for the elderly in its 1991 resolution named the United Nations Principles for Older Persons. In this paper the authors initially look at the trends in the increase of aged population in Asia in general and Sri Lanka in particular. Then they discuss how the quality of life characteristics can be achieved in a cost effective way through the use of Information and Communication Technology (ICT). The authors take an in depth look at the recent developments in field of ICT and its penetration in developing countries especially Sri Lanka with special emphasis to constraints and challenges in adopting ICT for the improving the quality of life of elderly.
Comparison of OpenMP & OpenCL Parallel Processing Technologies
Venue: arXiv cs.DC 2012
Year: 2012

This paper presents a comparison of OpenMP and OpenCL based on the parallel implementation of algorithms from various fields of computer applications. The focus of our study is on the performance of benchmark comparing OpenMP and OpenCL. We observed that OpenCL programming model is a good option for mapping threads on different processing cores. Balancing all available cores and allocating sufficient amount of work among all computing units, can lead to improved performance. In our simulation, we used Fedora operating system; a system with Intel Xeon Dual core processor having thread count 24 coupled with NVIDIA Quadro FX 3800 as graphical processing unit.
Efficiency Resource Allocation for Device-to-Device Underlay Communication Systems: A Reverse Iterative Combinatorial Auction Based Approach
Venue: arXiv cs.GT 2012
Year: 2012

Peer-to-peer communication has been recently considered as a popular issue for local area services. An innovative resource allocation scheme is proposed to improve the performance of mobile peer-to-peer, i.e., device-to-device (D2D), communications as an underlay in the downlink (DL) cellular networks. To optimize the system sum rate over the resource sharing of both D2D and cellular modes, we introduce a reverse iterative combinatorial auction as the allocation mechanism. In the auction, all the spectrum resources are considered as a set of resource units, which as bidders compete to obtain business while the packages of the D2D pairs are auctioned off as goods in each auction round. We first formulate the valuation of each resource unit, as a basis of the proposed auction. And then a detailed non-monotonic descending price auction algorithm is explained depending on the utility function that accounts for the channel gain from D2D and the costs for the system. Further, we prove that the proposed auction-based scheme is cheat-proof, and converges in a finite number of iteration rounds. We explain non-monotonicity in the price update process and show lower complexity compared to a traditional combinatorial allocation. The simulation results demonstrate that the algorithm efficiently leads to a good performance on the system sum rate.
I/O-optimal algorithms on grid graphs
Venue: arXiv cs.DS 2012
Year: 2012

Given a graph of which the n vertices form a regular two-dimensional grid, and in which each (possibly weighted and/or directed) edge connects a vertex to one of its eight neighbours, the following can be done in O(scan(n)) I/Os, provided M = Omega(B^2): computation of shortest paths with non-negative edge weights from a single source, breadth-first traversal, computation of a minimum spanning tree, topological sorting, time-forward processing (if the input is a plane graph), and an Euler tour (if the input graph is a tree). The minimum-spanning tree algorithm is cache-oblivious. The best previously published algorithms for these problems need Theta(sort(n)) I/Os. Estimates of the actual I/O volume show that the new algorithms may often be very efficient in practice.