OpenRaiser/Intern-Atlas huggingface dataset:
The Case for Cloud Service Trustmarks and Assurance-as-a-Service
Venue: arXiv cs.DC 2014
Year: 2014

Cloud computing represents a significant economic opportunity for Europe. However, this growth is threatened by adoption barriers largely related to trust. This position paper examines trust and confidence issues in cloud computing and advances a case for addressing them through the implementation of a novel trustmark scheme for cloud service providers. The proposed trustmark would be both active and dynamic featuring multi-modal information about the performance of the underlying cloud service. The trustmarks would be informed by live performance data from the cloud service provider, or ideally an independent third-party accountability and assurance service that would communicate up-to-date information relating to service performance and dependability. By combining assurance measures with a remediation scheme, cloud service providers could both signal dependability to customers and the wider marketplace and provide customers, auditors and regulators with a mechanism for determining accountability in the event of failure or non-compliance. As a result, the trustmarks would convey to consumers of cloud services and other stakeholders that strong assurance and accountability measures are in place for the service in question and thereby address trust and confidence issues in cloud computing.
Dual Power Assignment via Second Hamiltonian Cycle
Venue: arXiv cs.DM 2014
Year: 2014

A power assignment is an assignment of transmission power to each of the wireless nodes of a wireless network, so that the induced graph satisfies some desired properties. The cost of a power assignment is the sum of the assigned powers. In this paper, we consider the dual power assignment problem, in which each wireless node is assigned a high- or low-power level, so that the induced graph is strongly connected and the cost of the assignment is minimized. We improve the best known approximation ratio from $\frac{π^2}{6}-\frac{1}{36}+ε\thickapprox 1.617$ to $\frac{11}{7}\thickapprox 1.571$. Moreover, we show that the algorithm of Khuller et al. for the strongly connected spanning subgraph problem, which achieves an approximation ratio of $1.61$, is $1.522$-approximation algorithm for symmetric directed graphs. The innovation of this paper is in achieving these results via utilizing interesting properties for the existence of a second Hamiltonian cycle.
Sparse phase retrieval via group-sparse optimization
Venue: arXiv cs.IT 2014
Year: 2014

This paper deals with sparse phase retrieval, i.e., the problem of estimating a vector from quadratic measurements under the assumption that few components are nonzero. In particular, we consider the problem of finding the sparsest vector consistent with the measurements and reformulate it as a group-sparse optimization problem with linear constraints. Then, we analyze the convex relaxation of the latter based on the minimization of a block l1-norm and show various exact recovery and stability results in the real and complex cases. Invariance to circular shifts and reflections are also discussed for real vectors measured via complex matrices.
Friend Inspector: A Serious Game to Enhance Privacy Awareness in Social Networks
Venue: arXiv cs.CY 2014
Year: 2014

Currently, many users of Social Network Sites are insufficiently aware of who can see their shared personal items. Nonetheless, most approaches focus on enhancing privacy in Social Networks through improved privacy settings, neglecting the fact that privacy awareness is a prerequisite for privacy control. Social Network users first need to know about privacy issues before being able to make adjustments. In this paper, we introduce Friend Inspector, a serious game that allows its users to playfully increase their privacy awareness on Facebook. Since its launch, Friend Inspector has attracted a significant number of visitors, emphasising the need for better tools to understand privacy settings on Social Networks.
Filter Bank Multicarrier for Massive MIMO
Venue: arXiv cs.IT 2014
Year: 2014

This paper introduces filter bank multicarrier (FBMC) as a potential candidate in the application of massive MIMO communication. It also points out the advantages of FBMC over OFDM (orthogonal frequency division multiplexing) in the application of massive MIMO. The absence of cyclic prefix in FBMC increases the bandwidth efficiency. In addition, FBMC allows carrier aggregation straightforwardly. Self-equalization, a property of FBMC in massive MIMO that is introduced in this paper, has the impact of reducing (i) complexity; (ii) sensitivity to carrier frequency offset (CFO); (iii) peak-to-average power ratio (PAPR); (iv) system latency; and (v) increasing bandwidth efficiency. The numerical results that corroborate these claims are presented.
Navigation Function Based Decentralized Control of A Multi-Agent System with Network Connectivity Constraints
Venue: arXiv cs.SY 2014
Year: 2014

A wide range of applications require or can benefit from collaborative behavior of a group of agents. The technical challenge addressed in this chapter is the development of a decentralized control strategy that enables each agent to independently navigate to ensure agents achieve a collective goal while maintaining network connectivity. Specifically, cooperative controllers are developed for networked agents with limited sensing and network connectivity constraints. By modeling the interaction among the agents as a graph, several different approaches to address the problems of preserving network connectivity are presented, with the focus on a method that utilizes navigation function frameworks. By modeling network connectivity constraints as artificial obstacles in navigation functions, a decentralized control strategy is presented in two particular applications, formation control and rendezvous for a system of autonomous agents, which ensures global convergence to the unique minimum of the potential field (i.e., desired formation or desired destination) while preserving network connectivity. Simulation results are provided to demonstrate the developed strategy.
Multi-Dimensional Customization Modelling Based On Metagraph For Saas Multi-Tenant Applications
Venue: arXiv cs.SE 2014
Year: 2014

Software as a Service (SaaS) is a new software delivery model in which pre-built applications are delivered to customers as a service. SaaS providers aim to attract a large number of tenants (users) with minimal system modifications to meet economics of scale. To achieve this aim, SaaS applications have to be customizable to meet requirements of each tenant. However, due to the rapid growing of the SaaS, SaaS applications could have thousands of tenants with a huge number of ways to customize applications. Modularizing such customizations still is a highly complex task. Additionally, due to the big variation of requirements for tenants, no single customization model is appropriate for all tenants. In this paper, we propose a multi-dimensional customization model based on metagraph. The proposed mode addresses the modelling variability among tenants, describes customizations and their relationships, and guarantees the correctness of SaaS customizations made by tenants.
Towards rational and minimal change propagation in model evolution
Venue: arXiv cs.SE 2014
Year: 2014

A critical issue in the evolution of software models is change propagation: given a primary change that is made to a model in order to meet a new or changed requirement, what additional secondary changes are needed to maintain consistency within the model, and between the model and other models in the system? In practice, there are many ways of propagating changes to fix a given inconsistency, and how to justify and automate the selection between such change options remains a critical challenge. In this paper, we propose a number of postulates, inspired by the mature belief revision theory, that a change propagation process should satisfy to be considered rational and minimal. Such postulates enable us to reason about selecting alternative change options, and consequently to develop a machinery that automatically performs this task. We further argue that a possible implementation of such a change propagation process can be considered as a classical state space search in which each state represents a snapshot of the model in the process. This view naturally reflects the cascading nature of change propagation, where each change can require further changes to be made.
Machine Learning at Scale
Venue: arXiv cs.LG 2014
Year: 2014

It takes skill to build a meaningful predictive model even with the abundance of implementations of modern machine learning algorithms and readily available computing resources. Building a model becomes challenging if hundreds of terabytes of data need to be processed to produce the training data set. In a digital advertising technology setting, we are faced with the need to build thousands of such models that predict user behavior and power advertising campaigns in a 24/7 chaotic real-time production environment. As data scientists, we also have to convince other internal departments critical to implementation success, our management, and our customers that our machine learning system works. In this paper, we present the details of the design and implementation of an automated, robust machine learning platform that impacts billions of advertising impressions monthly. This platform enables us to continuously optimize thousands of campaigns over hundreds of millions of users, on multiple continents, against varying performance objectives.
Uncovering the information core in recommender systems
Venue: arXiv cs.IR 2014
Year: 2014

With the rapid growth of the Internet and overwhelming amount of information that people are confronted with, recommender systems have been developed to effiectively support users' decision-making process in online systems. So far, much attention has been paid to designing new recommendation algorithms and improving existent ones. However, few works considered the different contributions from different users to the performance of a recommender system. Such studies can help us improve the recommendation efficiency by excluding irrelevant users. In this paper, we argue that in each online system there exists a group of core users who carry most of the information for recommendation. With them, the recommender systems can already generate satisfactory recommendation. Our core user extraction method enables the recommender systems to achieve 90% of the accuracy by taking only 20% of the data into account.
Improved Upper and Lower Bound Heuristics for Degree Anonymization in Social Networks
Venue: arXiv cs.SI 2014
Year: 2014

Motivated by a strongly growing interest in anonymizing social network data, we investigate the NP-hard Degree Anonymization problem: given an undirected graph, the task is to add a minimum number of edges such that the graph becomes k-anonymous. That is, for each vertex there have to be at least k-1 other vertices of exactly the same degree. The model of degree anonymization has been introduced by Liu and Terzi [ACM SIGMOD'08], who also proposed and evaluated a two-phase heuristic. We present an enhancement of this heuristic, including new algorithms for each phase which significantly improve on the previously known theoretical and practical running times. Moreover, our algorithms are optimized for large-scale social networks and provide upper and lower bounds for the optimal solution. Notably, on about 26 % of the real-world data we provide (provably) optimal solutions; whereas in the other cases our upper bounds significantly improve on known heuristic solutions.
Understanding the impact of socialbot attacks in online social networks
Venue: arXiv cs.SI 2014
Year: 2014

Online social networks (OSN) like Twitter or Facebook are popular and powerful since they allow reaching millions of users online. They are also a popular target for socialbot attacks. Without a deep understanding of the impact of such attacks, the potential of online social networks as an instrument for facilitating discourse or democratic processes is in jeopardy. In this extended abstract we present insights from a live lab experiment in which social bots aimed at manipulating the social graph of an online social network, in our case Twitter. We explored the link creation behavior between targeted human users and our results suggest that socialbots may indeed have the ability to shape and influence the social graph in online social networks. However, our results also show that external factors may play an important role in the creation of social links in OSNs.
On the Algebraic Structure of Linear Trellises
Venue: arXiv cs.IT 2014
Year: 2014

Trellises are crucial graphical representations of codes. While conventional trellises are well understood, the general theory of (tail-biting) trellises is still under development. Iterative decoding concretely motivates such theory. In this paper we first develop a new algebraic framework for a systematic analysis of linear trellises which enables us to address open foundational questions. In particular, we present a useful and powerful characterization of linear trellis isomorphy. We also obtain a new proof of the Factorization Theorem of Koetter/Vardy and point out unnoticed problems for the group case. Next, we apply our work to: describe all the elementary trellis factorizations of linear trellises and consequently to determine all the minimal linear trellises for a given code; prove that nonmergeable one-to-one linear trellises are strikingly determined by the edge-label sequences of certain closed paths; prove self-duality theorems for minimal linear trellises; analyze quasi-cyclic linear trellises and consequently extend results on reduced linear trellises to nonreduced ones. To achieve this, we also provide new insight into mergeability and path connectivity properties of linear trellises. Our classification results are important for iterative decoding as we show that minimal linear trellises can yield different pseudocodewords even if they have the same graph structure.
Electromagnetic fault injection: towards a fault model on a 32-bit microcontroller
Venue: arXiv cs.CR 2014
Year: 2014

Injection of transient faults as a way to attack cryptographic implementations has been largely studied in the last decade. Several attacks that use electromagnetic fault injection against hardware or software architectures have already been presented. On microcontrollers, electromagnetic fault injection has mostly been seen as a way to skip assembly instructions or subroutine calls. However, to the best of our knowledge, no precise study about the impact of an electromagnetic glitch fault injection on a microcontroller has been proposed yet. The aim of this paper is twofold: providing a more in-depth study of the effects of electromagnetic glitch fault injection on a state-of-the-art microcontroller and building an associated register-transfer level fault model.
Estimating verification time
Venue: arXiv cs.SE 2014
Year: 2014

This essay is divided in four parts: In section (I) I explain why I think detecting hot-spots in verification is complicated and in particular, more complicated than detection when developing crude software. In section (II) I introduce the factors I think mostly affect performance in verification. In section (III) I propose a method to find functions that are most promising to be optimized. Finally, in section (IV) I draw some conclusions and discuss pros/cons of the proposed solution.
Performance Analysis of Interference-Limited Three-Phase Two-Way Relaying with Direct Channel
Venue: arXiv cs.IT 2014
Year: 2014

This paper investigates the performance of interference-limited three-phase two-way relaying with direct channel between two terminals in Rayleigh fading channels. The outage probability, sum bit error rate (BER) and ergodic sum rate are analyzed for a general model that both terminals and relay are corrupted by co-channel interference. We first derive the closed-form expressions of cumulative distribution function (CDF) for received signal-to-interference-plus-noise ratio (SINR) at the terminal. Based on the results for CDF, the lower bounds, approximate expressions as well as the asymptotic expressions for outage probability and sum BER are derived in closed-form with different computational complexities and accuracies. The approximate expression for ergodic sum rate is also presented. With the theoretic results, we consider the optimal power allocation at the relay and optimal relay location problems that aiming to minimize the outage and sum BER performances of the protocol. It is shown that jointly optimization of power and relay location can provide the best performance. Simulation results are presented to study the effect of system parameters while verify the theoretic analysis. The results show that three-phase TWR protocol can outperform two-phase TWR protocol in ergodic sum rate when the interference power at the relay is much larger than that at the terminals. This is in sharp contrast with the conclusion in interference free scenario. Moreover, we show that an estimation error on the interference channel will not affect the system performance significantly, while a very small estimation error on the desired channels can degrade the performance considerably.
Evolutionary solving of the debts' clearing problem
Venue: arXiv cs.NE 2014
Year: 2014

The debts' clearing problem is about clearing all the debts in a group of n entities (persons, companies etc.) using a minimal number of money transaction operations. The problem is known to be NP-hard in the strong sense. As for many intractable problems, techniques from the field of artificial intelligence are useful in finding solutions close to optimum for large inputs. An evolutionary algorithm for solving the debts' clearing problem is proposed.
Complex Beauty
Venue: arXiv cs.OH 2014
Year: 2014

Complex systems and their underlying convoluted networks are ubiquitous, all we need is an eye for them. They pose problems of organized complexity which cannot be approached with a reductionist method. Complexity science and its emergent sister network science both come to grips with the inherent complexity of complex systems with an holistic strategy. The relevance of complexity, however, transcends the sciences. Complex systems and networks are the focal point of a philosophical, cultural and artistic turn of our tightly interrelated and interdependent postmodern society. Here I take a different, aesthetic perspective on complexity. I argue that complex systems can be beautiful and can the object of artification - the neologism refers to processes in which something that is not regarded as art in the traditional sense of the word is changed into art. Complex systems and networks are powerful sources of inspiration for the generative designer, for the artful data visualizer, as well as for the traditional artist. I finally discuss the benefits of a cross-fertilization between science and art.
Fundamental Limits of Video Coding: A Closed-form Characterization of Rate Distortion Region from First Principles
Venue: arXiv cs.IT 2014
Year: 2014

Classical motion-compensated video coding methods have been standardized by MPEG over the years and video codecs have become integral parts of media entertainment applications. Despite the ubiquitous use of video coding techniques, it is interesting to note that a closed form rate-distortion characterization for video coding is not available in the literature. In this paper, we develop a simple, yet, fundamental characterization of rate-distortion region in video coding based on information-theoretic first principles. The concept of conditional motion estimation is used to derive the closedform expression for rate-distortion region without losing its generality. Conditional motion estimation offers an elegant means to analyze the rate-distortion trade-offs and demonstrates the viability of achieving the bounds derived. The concept involves classifying image regions into active and inactive based on the amount of motion activity. By appropriately modeling the residuals corresponding to active and inactive regions, a closed form expression for rate-distortion function is derived in terms of motion activity and spatio-temporal correlation that commonly exist in video content. Experiments on real video clips using H.264 codec are presented to demonstrate the practicality and validity of the proposed rate-distortion analysis.
Exploiting the Statistics of Learning and Inference
Venue: arXiv cs.LG 2014
Year: 2014

When dealing with datasets containing a billion instances or with simulations that require a supercomputer to execute, computational resources become part of the equation. We can improve the efficiency of learning and inference by exploiting their inherent statistical nature. We propose algorithms that exploit the redundancy of data relative to a model by subsampling data-cases for every update and reasoning about the uncertainty created in this process. In the context of learning we propose to test for the probability that a stochastically estimated gradient points more than 180 degrees in the wrong direction. In the context of MCMC sampling we use stochastic gradients to improve the efficiency of MCMC updates, and hypothesis tests based on adaptive mini-batches to decide whether to accept or reject a proposed parameter update. Finally, we argue that in the context of likelihood free MCMC one needs to store all the information revealed by all simulations, for instance in a Gaussian process. We conclude that Bayesian methods will remain to play a crucial role in the era of big data and big simulations, but only if we overcome a number of computational challenges.
Parameter security characterization of knapsack public-key crypto under quantum computing
Venue: arXiv cs.CR 2014
Year: 2014

In order to research the security of the knapsack problem under quantum algorithm attack, we study the quantum algorithm for knapsack problem over Z_r based on the relation between the dimension of the knapsack vector and r. First, the oracle function is designed based on the knapsack vector B and S, and the quantum algorithm for the knapsack problem over Z_r is presented. The observation probability of target state is not improved by designing unitary transform, but oracle function. Its complexity is polynomial. And its success probability depends on the relation between n and r. From the above discussion, we give the essential condition for the knapsack problem over Z_r against the existing quantum algorithm attacks, i.e. r<O(2^n). Then we analyze the security of the Chor-Rivest public-key crypto.
SPARQL for Networks of Embedded Systems
Venue: arXiv cs.DB 2014
Year: 2014

The Semantic Web (or Web of Data) represents the successful efforts towards linking and sharing data over the Web. The cornerstones of the Web of Data are RDF as data format and SPARQL as de-facto standard query language. Recent trends show the evolution of the Web of Data towards the Web of Things, integrating embedded devices and smart objects. Data stemming from such devices do not share a common format, making the integration and querying impossible. To overcome this problem, we present our approach to make embedded systems first-class citizens of the Web of Things. Our framework abstracts from individual deployments to represent them as common data sources in line with the ideas behind the Semantic Web. This includes the execution of arbitrary SPARQL queries over the data from a pool of embedded devices and/or external data sources. Handling verbose RDF data and executing SPARQL queries in an embedded network poses major challenges to minimize the involved processing and communication cost. We therefore present an in-network query processor aiming to push processing steps onto devices. We demonstrate the practical application and the potential benefits of our framework in a comprehensive evaluation using a real-world deployment and a range of SPARQL queries stemming from a common use case of the Web of Things.