OpenRaiser/Intern-Atlas huggingface dataset:
The Impact of Communication Delays on Distributed Consensus Algorithms
Venue: arXiv cs.DC 2012
Year: 2012

We study the effect of communication delays on distributed consensus algorithms. Two ways to model delays on a network are presented. The first model assumes that each link delivers messages with a fixed (constant) amount of delay, and the second model is more realistic, allowing for i.i.d. time-varying bounded delays. In contrast to previous work studying the effects of delays on consensus algorithms, the models studied here allow for a node to receive multiple messages from the same neighbor in one iteration. The analysis of the fixed delay model shows that convergence to a consensus is guaranteed and the rate of convergence is reduced by no more than a factor O(B^2) where B is the maximum delay on any link. For the time-varying delay model we also give a convergence proof which, for row-stochastic consensus protocols, is not a trivial consequence of ergodic matrix products. In both delay models, the consensus value is no longer the average, even if the original protocol was an averaging protocol. For this reason, we propose the use of a different consensus algorithm called Push-Sum [Kempe et al. 2003]. We model delays in the Push-Sum framework and show that convergence to the average consensus is guaranteed. This suggests that Push-Sum might be a better choice from a practical standpoint.
Using Open Standards for Interoperability - Issues, Solutions, and Challenges facing Cloud Computing
Venue: arXiv cs.DC 2012
Year: 2012

Virtualization offers several benefits for optimal resource utilization over traditional non-virtualized server farms. With improvements in internetworking technologies and increase in network bandwidth speeds, a new era of computing has been ushered in, that of grids and clouds. With several commercial cloud providers coming up, each with their own APIs, application description formats, and varying support for SLAs, vendor lock-in has become a serious issue for end users. This article attempts to describe the problem, issues, possible solutions and challenges in achieving cloud interoperability. These issues will be analyzed in the ambit of the European project Contrail that is trying to adopt open standards with available virtualization solutions to enhance users' trust in the clouds by attempting to prevent vendor lock-ins, supporting and enforcing SLAs together with adequate data protection for sensitive data.
Analysis of cloud storage prices
Venue: arXiv cs.DC 2012
Year: 2012

Cloud storage is fast securing its role as a major repository for both consumers and business customers. Many companies now offer storage solutions, sometimes for free for limited amounts of capacity. We have surveyed the pricing plans of a selection of major cloud providers and compared them using the unit price as the means of comparison. All the providers, excepting Amazon, adopt a bundling pricing scheme; Amazon follows instead a block-declining pricing policy. We compare the pricing plans through a double approach: a pointwise comparison for each value of capacity, and an overall comparison using a two-part tariff approximation and a Pareto-dominance criterion. Under both approaches, most providers appear to offer pricing plans that are more expensive and can be excluded from a procurement selection in favour of a limited number of dominant providers.
The 2008 Australian study of remnant data contained on 2nd hand hard disks: the saga continues
Venue: arXiv cs.CR 2012
Year: 2012

This study looked for remnant data on enterprise level hard drives that were purchased through auctions. The drives were analysed for information, be it topical or formatted. In the event that drives were formatted, forensic tools were used to recover this data. This years study revealed a high level of not simply un-erased drives, but drives which contained information that related to critical infrastructure providers. That such a small sample size yielded such a high rate of un-erased drives is of considerable concern, and it may be necessary for the government to become involved.
Effective Retrieval of Resources in Folksonomies Using a New Tag Similarity Measure
Venue: arXiv cs.IR 2012
Year: 2012

Social (or folksonomic) tagging has become a very popular way to describe content within Web 2.0 websites. However, as tags are informally defined, continually changing, and ungoverned, it has often been criticised for lowering, rather than increasing, the efficiency of searching. To address this issue, a variety of approaches have been proposed that recommend users what tags to use, both when labeling and when looking for resources. These techniques work well in dense folksonomies, but they fail to do so when tag usage exhibits a power law distribution, as it often happens in real-life folksonomies. To tackle this issue, we propose an approach that induces the creation of a dense folksonomy, in a fully automatic and transparent way: when users label resources, an innovative tag similarity metric is deployed, so to enrich the chosen tag set with related tags already present in the folksonomy. The proposed metric, which represents the core of our approach, is based on the mutual reinforcement principle. Our experimental evaluation proves that the accuracy and coverage of searches guaranteed by our metric are higher than those achieved by applying classical metrics.
Customer Empowerment in Healthcare Organisations Through CRM 2.0: Survey Results from Brunei Tracking a Future Path in E-Health Research
Venue: arXiv cs.CY 2012
Year: 2012

Customer Relationship Management (CRM) with the Web technology provides healthcare organizations the ability to broaden services beyond its usual practices, and thus provides a particular advantageous environment to achieve complex e-health goals. This paper discusses and demonstrates how a new approach in CRM based on Web 2.0 namely CRM 2.0 will help customers to have greater control in the sense of controlling the process of interaction (empowerment) between healthcare organizations with its customers, and among customers themselves. A survey was conducted to gather preliminary requirements and expectations on empowerment in Brunei. The survey revealed that there is a high demand for empowering customers in Brunei through the Web. Regardless of the limitations of the survey, the general public has responded with a great support for the capabilities of empowerment listed from the questionnaires. The data were analyzed to provide initial ideas and recommendation to a future direction on research for customers' empowerment in e-health services.
Framework of Social Customer Relationship Management in E-Health Services
Venue: arXiv cs.CY 2012
Year: 2012

Healthcare organization is implementing Customer Relationship Management (CRM) as a strategy for managing interactions with patients involving technology to organize, automate, and coordinate business processes. Web-based CRM provides healthcare organization with the ability to broaden service beyond its usual practices in achieving a complex patient care goal, and this paper discusses and demonstrates how a new approach in CRM based on Web 2.0 or Social CRM helps healthcare organizations to improve their customer support, and at the same time avoiding possible conflicts, and promoting better healthcare to patients. A conceptual framework of the new approach will be proposed and highlighted. The framework includes some important features of Social CRM such as customer's empowerment, social interactivity between healthcare organization-patients, and patients-patients. The framework offers new perspective in building relationships between healthcare organizations and customers and among customers in e-health scenario. It is developed based on the latest development of CRM literatures and case studies analysis. In addition, customer service paradigm in social network's era, the important of online health education, and empowerment in healthcare organization will be taken into consideration.
A CLT on the SNR of Diagonally Loaded MVDR Filters
Venue: arXiv cs.IT 2012
Year: 2012

This paper studies the fluctuations of the signal-to-noise ratio (SNR) of minimum variance distorsionless response (MVDR) filters implementing diagonal loading in the estimation of the covariance matrix. Previous results in the signal processing literature are generalized and extended by considering both spatially as well as temporarily correlated samples. Specifically, a central limit theorem (CLT) is established for the fluctuations of the SNR of the diagonally loaded MVDR filter, under both supervised and unsupervised training settings in adaptive filtering applications. Our second-order analysis is based on the Nash-Poincaré inequality and the integration by parts formula for Gaussian functionals, as well as classical tools from statistical asymptotic theory. Numerical evaluations validating the accuracy of the CLT confirm the asymptotic Gaussianity of the fluctuations of the SNR of the MVDR filter.
On Mimicking Networks Representing Minimum Terminal Cuts
Venue: arXiv cs.DS 2012
Year: 2012

Given a capacitated undirected graph $G=(V,E)$ with a set of terminals $K \subset V$, a mimicking network is a smaller graph $H=(V_H,E_H)$ that exactly preserves all the minimum cuts between the terminals. Specifically, the vertex set of the sparsifier $V_H$ contains the set of terminals $K$ and for every bipartition $U, K-U $ of the terminals $K$, the size of the minimum cut separating $U$ from $K-U$ in $G$ is exactly equal to the size of the minimum cut separating $U$ from $K-U$ in $H$. This notion of a mimicking network was introduced by Hagerup, Katajainen, Nishimura and Ragde (1995) who also exhibited a mimicking network of size $2^{2^{k}}$ for every graph with $k$ terminals. The best known lower bound on the size of a mimicking network is linear in the number of terminals. More precisely, the best known lower bound is $k+1$ for graphs with $k$ terminals (Chaudhuri et al. 2000). In this work, we improve both the upper and lower bounds reducing the doubly-exponential gap between them to a single-exponential gap. Specifically, we obtain the following upper and lower bounds on mimicking networks: 1) Given a graph $G$, we exhibit a construction of mimicking network with at most $(|K|-1)$'th Dedekind number ($\approx 2^{{(k-1)} \choose {\lfloor {{(k-1)}/2} \rfloor}}$) of vertices (independent of size of $V$). Furthermore, we show that the construction is optimal among all {\it restricted mimicking networks} -- a natural class of mimicking networks that are obtained by clustering vertices together. 2) There exists graphs with $k$ terminals that have no mimicking network of size smaller than $2^{\frac{k-1}{2}}$. We also exhibit improved constructions of mimicking networks for trees and graphs of bounded tree-width.
Identifying Users From Their Rating Patterns
Venue: arXiv cs.IR 2012
Year: 2012

This paper reports on our analysis of the 2011 CAMRa Challenge dataset (Track 2) for context-aware movie recommendation systems. The train dataset comprises 4,536,891 ratings provided by 171,670 users on 23,974$ movies, as well as the household groupings of a subset of the users. The test dataset comprises 5,450 ratings for which the user label is missing, but the household label is provided. The challenge required to identify the user labels for the ratings in the test set. Our main finding is that temporal information (time labels of the ratings) is significantly more useful for achieving this objective than the user preferences (the actual ratings). Using a model that leverages on this fact, we are able to identify users within a known household with an accuracy of approximately 96% (i.e. misclassification rate around 4%).
Efficient implementations of minimum-cost flow algorithms
Venue: arXiv cs.DM 2012
Year: 2012

This paper presents efficient implementations of several algorithms for solving the minimum-cost network flow problem. Various practical heuristics and other important implementation aspects are also discussed. A novel result of this work is the application of Goldberg's recent partial augment-relabel method in the cost-scaling algorithm. The presented implementations are available as part of the LEMON open source C++ optimization library (\url{http://lemon.cs.elte.hu/}). The performance of these codes is compared to well-known and efficient minimum-cost flow solvers, namely CS2, RelaxIV, MCF, and the corresponding method of the LEDA library. According to thorough experimental analysis, the presented cost-scaling and network simplex implementations turned out to be more efficient than LEDA and MCF. Furthermore, the cost-scaling implementation is competitive with CS2. The RelaxIV algorithm is often much slower than the other codes, although it is quite efficient on particular problem instances.
Deciding football sequences
Venue: arXiv cs.DM 2012
Year: 2012

An open problem posed by the first author is the complexity to decide whether a sequence of nonnegative integer numbers can be the final score of a football tournament. In this paper we propose polynomial time approximate and exponential time exact algorithms which solve the problem.
Economics of WiFi Offloading: Trading Delay for Cellular Capacity
Venue: arXiv cs.NI 2012
Year: 2012

Cellular networks are facing severe traffic overloads due to the proliferation of smart handheld devices and traffic-hungry applications. A cost-effective and practical solution is to offload cellular data through WiFi. Recent theoretical and experimental studies show that a scheme, referred to as delayed WiFi offloading, can significantly save the cellular capacity by delaying users' data and exploiting mobility and thus increasing chance of meeting WiFi APs (Access Points). Despite a huge potential of WiFi offloading in alleviating mobile data explosion, its success largely depends on the economic incentives provided to users and operators to deploy and use delayed offloading. In this paper, we study how much economic benefits can be generated due to delayed WiFi offloading, by modeling a market based on a two-stage sequential game between a monopoly provider and users. We also provide extensive numerical results computed using a set of parameters from the real traces and Cisco's projection of traffic statistics in year 2015. In both analytical and numerical results, we model a variety of practical scenarios and control knobs in terms of traffic demand and willingness to pay of users, spatio-temporal dependence of pricing and traffic, and diverse pricing and delay tolerance. We demonstrate that delayed WiFi offloading has considerable economic benefits, where the increase ranges from 21% to 152% in the provider's revenue, and from 73% to 319% in the users' surplus, compared to on-the-spot WiFi offloading.
Exploring Promising Stepping Stones by Combining Novelty Search with Interactive Evolution
Venue: arXiv cs.NE 2012
Year: 2012

The field of evolutionary computation is inspired by the achievements of natural evolution, in which there is no final objective. Yet the pursuit of objectives is ubiquitous in simulated evolution. A significant problem is that objective approaches assume that intermediate stepping stones will increasingly resemble the final objective when in fact they often do not. The consequence is that while solutions may exist, searching for such objectives may not discover them. This paper highlights the importance of leveraging human insight during search as an alternative to articulating explicit objectives. In particular, a new approach called novelty-assisted interactive evolutionary computation (NA-IEC) combines human intuition with novelty search for the first time to facilitate the serendipitous discovery of agent behaviors. In this approach, the human user directs evolution by selecting what is interesting from the on-screen population of behaviors. However, unlike in typical IEC, the user can now request that the next generation be filled with novel descendants. The experimental results demonstrate that combining human insight with novelty search finds solutions significantly faster and at lower genomic complexities than fully-automated processes, including pure novelty search, suggesting an important role for human users in the search for solutions.
FMLtoHOL (version 1.0): Automating First-order Modal Logics with LEO-II and Friends
Venue: arXiv cs.LO 2012
Year: 2012

A converter from first-order modal logics to classical higher- order logic is presented. This tool enables the application of off-the-shelf higher-order theorem provers and model finders for reasoning within first- order modal logics. The tool supports logics K, K4, D, D4, T, S4, and S5 with respect to constant, varying and cumulative domain semantics.
An Algebraic Theory of Complexity for Discrete Optimisation
Venue: arXiv cs.CC 2012
Year: 2012

Discrete optimisation problems arise in many different areas and are studied under many different names. In many such problems the quantity to be optimised can be expressed as a sum of functions of a restricted form. Here we present a unifying theory of complexity for problems of this kind. We show that the complexity of a finite-domain discrete optimisation problem is determined by certain algebraic properties of the objective function, which we call weighted polymorphisms. We define a Galois connection between sets of rational-valued functions and sets of weighted polymorphisms and show how the closed sets of this Galois connection can be characterised. These results provide a new approach to studying the complexity of discrete optimisation. We use this approach to identify certain maximal tractable subproblems of the general problem, and hence derive a complete classification of complexity for the Boolean case.
Low-Speed ADC Sampling Based High-Resolution Compressive Channel Estimation
Venue: arXiv cs.IT 2012
Year: 2012

Broadband channel is often characterized by a sparse multipath channel where dominant multipath taps are widely separated in time, thereby resulting in a large delay spread. Traditionally, accurate channel estimation is done by sampling received signal by analog-to-digital converter (ADC) at Nyquist rate (high-speed ADC sampling) and then estimate all channel taps with high-resolution. However, traditional linear estimation methods have two mainly disadvantages: 1) demand of the high-speed ADC sampling rate which already exceeds the capability of current ADC and also the high-speed ADC is very expensive for regular wireless communications; 2) neglect the inherent channel sparsity and the low spectral efficiency wireless communication is unavoidable. To solve these challenges, in this paper, we propose a high-resolution compressive channel estimation method by using low-speed ADC sampling. Our proposed method can achieve close performance comparing with traditional sparse channel estimation methods. At the same time, the proposed method has following advantages: 1) reduce communication cost by utilizing cheap low-speed ADC; 2) improve spectral efficiency by extracting potential training signal resource. Numerical simulations confirm our proposed method using low-speed ADC sampling.
Finite Automata with Time-Delay Blocks (Extended Version)
Venue: arXiv cs.FL 2012
Year: 2012

The notion of delays arises naturally in many computational models, such as, in the design of circuits, control systems, and dataflow languages. In this work, we introduce \emph{automata with delay blocks} (ADBs), extending finite state automata with variable time delay blocks, for deferring individual transition output symbols, in a discrete-time setting. We show that the ADB languages strictly subsume the regular languages, and are incomparable in expressive power to the context-free languages. We show that ADBs are closed under union, concatenation and Kleene star, and under intersection with regular languages, but not closed under complementation and intersection with other ADB languages. We show that the emptiness and the membership problems are decidable in polynomial time for ADBs, whereas the universality problem is undecidable. Finally we consider the linear-time model checking problem, i.e., whether the language of an ADB is contained in a regular language, and show that the model checking problem is PSPACE-complete.
Impact of channel partitioning and relay placement on resource allocation in OFDMA Cellular networks
Venue: arXiv cs.NI 2012
Year: 2012

Tremendous growth in the demand for wireless applications such as streaming audio/videos, Skype and video games require high data rate irrespective of user's location in the cellular network. However, the Quality of Service (QoS) of users degrades at the cell boundary. Relay enhanced multi-hop cellular network is one of the cost effective solution to improve the performance of cell edge users. Optimal deployment of Fixed Relay Nodes (FRNs) is essential to satisfy the QoS requirement of edge users. We propose new schemes for channel partitioning and FRN placement in cellular networks. Path-loss, Signal to Interference and Noise Ratio (SINR) experienced by users, and effects of shadowing have been considered. The analysis gives more emphasis on the cell-edge users (worst case scenario). The results show that these schemes achieve higher system performance in terms of spectral efficiency and also increase the user data rate at the cell edge.
Optimizing MapReduce for Highly Distributed Environments
Venue: arXiv cs.DC 2012
Year: 2012

MapReduce, the popular programming paradigm for large-scale data processing, has traditionally been deployed over tightly-coupled clusters where the data is already locally available. The assumption that the data and compute resources are available in a single central location, however, no longer holds for many emerging applications in commercial, scientific and social networking domains, where the data is generated in a geographically distributed manner. Further, the computational resources needed for carrying out the data analysis may be distributed across multiple data centers or community resources such as Grids. In this paper, we develop a modeling framework to capture MapReduce execution in a highly distributed environment comprising distributed data sources and distributed computational resources. This framework is flexible enough to capture several design choices and performance optimizations for MapReduce execution. We propose a model-driven optimization that has two key features: (i) it is end-to-end as opposed to myopic optimizations that may only make locally optimal but globally suboptimal decisions, and (ii) it can control multiple MapReduce phases to achieve low runtime, as opposed to single-phase optimizations that may control only individual phases. Our model results show that our optimization can provide nearly 82% and 64% reduction in execution time over myopic and single-phase optimizations, respectively. We have modified Hadoop to implement our model outputs, and using three different MapReduce applications over an 8-node emulated PlanetLab testbed, we show that our optimized Hadoop execution plan achieves 31-41% reduction in runtime over a vanilla Hadoop execution. Our model-driven optimization also provides several insights into the choice of techniques and execution parameters based on application and platform characteristics.