OpenRaiser/Intern-Atlas huggingface dataset:
Color graph based wavelet transform with perceptual information
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we propose a numerical strategy to define a multiscale analysis for color and multicomponent images based on the representation of data on a graph. Our approach consists in computing the graph of an image using the psychovisual information and analysing it by using the spectral graph wavelet transform. We suggest introducing color dimension into the computation of the weights of the graph and using the geodesic distance as a means of distance measurement. We thus have defined a wavelet transform based on a graph with perceptual information by using the CIELab color distance. This new representation is illustrated with denoising and inpainting applications. Overall, by introducing psychovisual information in the graph computation for the graph wavelet transform we obtain very promising results. Therefore results in image restoration highlight the interest of the appropriate use of color information.
Characterizing SEAndroid Policies in the Wild
Venue: arXiv cs.CR 2015
Year: 2015

Starting from the 5.0 Lollipop release all Android processes must be run inside confined SEAndroid access control domains. As a result, Android device manufacturers were compelled to develop SEAndroid expertise in order to create policies for their device-specific components. In this paper we analyse SEAndroid policies from a number of 5.0 Lollipop devices on the market, and identify patterns of common problems we found. We also suggest some practical tools that can improve policy design and analysis. We implemented the first of such tools, SEAL.
Image-based Modelling of Organogenesis
Venue: arXiv cs.CE 2015
Year: 2015

One of the major challenges in biology concerns the integration of data across length and time scales into a consistent framework: how do macroscopic properties and functionalities arise from the molecular regulatory networks - and how can they change as a result of mutations? Morphogenesis provides an excellent model system to study how simple molecular networks robustly control complex processes on the macroscopic scale in spite of molecular noise, and how important functional variants can emerge from small genetic changes. Recent advancements in 3D imaging technologies, computer algorithms, and computer power now allow us to develop and analyse increasingly realistic models of biological control. Here we present our pipeline for image-based modeling that includes the segmentation of images, the determination of displacement fields, and the solution of systems of partial differential equations (PDEs) on the growing, embryonic domains. The development of suitable mathematical models, the data-based inference of parameter sets, and the evaluation of competing models are still challenging, and current approaches are discussed.
Estimating the Causal Impact of Recommendation Systems from Observational Data
Venue: arXiv cs.SI 2015
Year: 2015

Recommendation systems are an increasingly prominent part of the web, accounting for up to a third of all traffic on several of the world's most popular sites. Nevertheless, little is known about how much activity such systems actually cause over and above activity that would have occurred via other means (e.g., search) if recommendations were absent. Although the ideal way to estimate the causal impact of recommendations is via randomized experiments, such experiments are costly and may inconvenience users. In this paper, therefore, we present a method for estimating causal effects from purely observational data. Specifically, we show that causal identification through an instrumental variable is possible when a product experiences an instantaneous shock in direct traffic and the products recommended next to it do not. We then apply our method to browsing logs containing anonymized activity for 2.1 million users on Amazon.com over a 9 month period and analyze over 4,000 unique products that experience such shocks. We find that although recommendation click-throughs do account for a large fraction of traffic among these products, at least 75% of this activity would likely occur in the absence of recommendations. We conclude with a discussion about the assumptions under which the method is appropriate and caveats around extrapolating results to other products, sites, or settings.
Replication-based Outer bounds and the Optimality of "Half the Cake" for Rank-Deficient MIMO Interference Networks
Venue: arXiv cs.IT 2015
Year: 2015

In order to gain new insights into MIMO interference networks, the optimality of $\sum_{k=1}^K M_k/2$ (half the cake per user) degrees of freedom is explored for a $K$-user multiple-input-multiple-output (MIMO) interference channel where the cross-channels have arbitrary rank constraints, and the $k^{th}$ transmitter and receiver are equipped with $M_k$ antennas each. The result consolidates and significantly generalizes results from prior studies by Krishnamurthy et al., of rank-deficient interference channels where all users have $M$ antennas, and by Tang et al., of full rank interference channels where the $k^{th}$ user pair has $M_k$ antennas. The broader outcome of this work is a novel class of replication-based outer bounds for arbitrary rank-constrained MIMO interference networks where replicas of existing users are added as auxiliary users and the network connectivity is chosen to ensure that any achievable scheme for the original network also works in the new network. The replicated network creates a new perspective of the problem, so that even simple arguments such as user cooperation become quite powerful when applied in the replicated network, giving rise to stronger outer bounds, than when applied directly in the original network. Remarkably, the replication based bounds are broadly applicable not only to MIMO interference channels with arbitrary rank-constraints, but much more broadly, even beyond Gaussian settings.
User Applications Driven by the Community Contribution Framework MPContribs in the Materials Project
Venue: arXiv cs.CY 2015
Year: 2015

This work discusses how the MPContribs framework in the Materials Project (MP) allows user-contributed data to be shown and analyzed alongside the core MP database. The Materials Project is a searchable database of electronic structure properties of over 65,000 bulk solid materials that is accessible through a web-based science-gateway. We describe the motivation for enabling user contributions to the materials data and present the framework's features and challenges in the context of two real applications. These use-cases illustrate how scientific collaborations can build applications with their own "user-contributed" data using MPContribs. The Nanoporous Materials Explorer application provides a unique search interface to a novel dataset of hundreds of thousands of materials, each with tables of user-contributed values related to material adsorption and density at varying temperature and pressure. The Unified Theoretical and Experimental x-ray Spectroscopy application discusses a full workflow for the association, dissemination and combined analyses of experimental data from the Advanced Light Source with MP's theoretical core data, using MPContribs tools for data formatting, management and exploration. The capabilities being developed for these collaborations are serving as the model for how new materials data can be incorporated into the Materials Project website with minimal staff overhead while giving powerful tools for data search and display to the user community.
Clarifying the Role of Distance in Friendships on Twitter: Discovery of a Double Power-Law Relationship
Venue: arXiv cs.SI 2015
Year: 2015

This study analyzes friendships in online social networks involving geographic distance with a geo-referenced Twitter dataset, which provides the exact distance between corresponding users. We start by introducing a strong definition of "friend" on Twitter, requiring bidirectional communication. Next, by utilizing geo-tagged mentions delivered by users to determine their locations, we introduce a two-stage distance estimation algorithm. As our main contribution, our study provides the following newly-discovered friendship degree related to the issue of space: The number of friends according to distance follows a double power-law (i.e., a double Pareto law) distribution, indicating that the probability of befriending a particular Twitter user is significantly reduced beyond a certain geographic distance between users, termed the separation point. Our analysis provides much more fine-grained social ties in space, compared to the conventional results showing a homogeneous power-law with distance.
Sequential Score Adaptation with Extreme Value Theory for Robust Railway Track Inspection
Venue: arXiv cs.CV 2015
Year: 2015

Periodic inspections are necessary to keep railroad tracks in state of good repair and prevent train accidents. Automatic track inspection using machine vision technology has become a very effective inspection tool. Because of its non-contact nature, this technology can be deployed on virtually any railway vehicle to continuously survey the tracks and send exception reports to track maintenance personnel. However, as appearance and imaging conditions vary, false alarm rates can dramatically change, making it difficult to select a good operating point. In this paper, we use extreme value theory (EVT) within a Bayesian framework to optimally adjust the sensitivity of anomaly detectors. We show that by approximating the lower tail of the probability density function (PDF) of the scores with an Exponential distribution (a special case of the Generalized Pareto distribution), and using the Gamma conjugate prior learned from the training data, it is possible to reduce the variability in false alarm rate and improve the overall performance. This method has shown an increase in the defect detection rate of rail fasteners in the presence of clutter (at PFA 0.1%) from 95.40% to 99.26% on the 85-mile Northeast Corridor (NEC) 2012-2013 concrete tie dataset.
Hiding in Plain Sight: The Anatomy of Malicious Facebook Pages
Venue: arXiv cs.SI 2015
Year: 2015

Facebook is the world's largest Online Social Network, having more than 1 billion users. Like most other social networks, Facebook is home to various categories of hostile entities who abuse the platform by posting malicious content. In this paper, we identify and characterize Facebook pages that engage in spreading URLs pointing to malicious domains. We used the Web of Trust API to determine domain reputations of URLs published by pages, and identified 627 pages publishing untrustworthy information, misleading content, adult and child unsafe content, scams, etc. which are deemed as "Page Spam" by Facebook, and do not comply with Facebook's community standards. Our findings revealed dominant presence of politically polarized entities engaging in spreading content from untrustworthy web domains. Anger and religion were the most prominent topics in the textual content published by these pages. We found that at least 8% of all malicious pages were dedicated to promote a single malicious domain. Studying the temporal posting activity of pages revealed that malicious pages were more active than benign pages. We further identified collusive behavior within a set of malicious pages spreading adult and pornographic content. We believe our findings will enable technologists to devise efficient automated solutions to identify and curb the spread of malicious content through such pages. To the best of our knowledge, this is the first attempt in literature, focused exclusively on characterizing malicious Facebook pages.
Semantic, Cognitive, and Perceptual Computing: Advances toward Computing for Human Experience
Venue: arXiv cs.AI 2015
Year: 2015

The World Wide Web continues to evolve and serve as the infrastructure for carrying massive amounts of multimodal and multisensory observations. These observations capture various situations pertinent to people's needs and interests along with all their idiosyncrasies. To support human-centered computing that empower people in making better and timely decisions, we look towards computation that is inspired by human perception and cognition. Toward this goal, we discuss computing paradigms of semantic computing, cognitive computing, and an emerging aspect of computing, which we call perceptual computing. In our view, these offer a continuum to make the most out of vast, growing, and diverse data pertinent to human needs and interests. We propose details of perceptual computing characterized by interpretation and exploration operations comparable to the interleaving of bottom and top brain processing. This article consists of two parts. First we describe semantic computing, cognitive computing, and perceptual computing to lay out distinctions while acknowledging their complementary capabilities. We then provide a conceptual overview of the newest of these three paradigms--perceptual computing. For further insights, we focus on an application scenario of asthma management converting massive, heterogeneous and multimodal (big) data into actionable information or smart data.
Input Sparsity and Hardness for Robust Subspace Approximation
Venue: arXiv cs.DS 2015
Year: 2015

In the subspace approximation problem, we seek a k-dimensional subspace F of R^d that minimizes the sum of p-th powers of Euclidean distances to a given set of n points a_1, ..., a_n in R^d, for p >= 1. More generally than minimizing sum_i dist(a_i,F)^p,we may wish to minimize sum_i M(dist(a_i,F)) for some loss function M(), for example, M-Estimators, which include the Huber and Tukey loss functions. Such subspaces provide alternatives to the singular value decomposition (SVD), which is the p=2 case, finding such an F that minimizes the sum of squares of distances. For p in [1,2), and for typical M-Estimators, the minimizing $F$ gives a solution that is more robust to outliers than that provided by the SVD. We give several algorithmic and hardness results for these robust subspace approximation problems. We think of the n points as forming an n x d matrix A, and letting nnz(A) denote the number of non-zero entries of A. Our results hold for p in [1,2). We use poly(n) to denote n^{O(1)} as n -> infty. We obtain: (1) For minimizing sum_i dist(a_i,F)^p, we give an algorithm running in O(nnz(A) + (n+d)poly(k/eps) + exp(poly(k/eps))), (2) we show that the problem of minimizing sum_i dist(a_i, F)^p is NP-hard, even to output a (1+1/poly(d))-approximation, answering a question of Kannan and Vempala, and complementing prior results which held for p >2, (3) For loss functions for a wide class of M-Estimators, we give a problem-size reduction: for a parameter K=(log n)^{O(log k)}, our reduction takes O(nnz(A) log n + (n+d) poly(K/eps)) time to reduce the problem to a constrained version involving matrices whose dimensions are poly(K eps^{-1} log n). We also give bicriteria solutions, (4) Our techniques lead to the first O(nnz(A) + poly(d/eps)) time algorithms for (1+eps)-approximate regression for a wide class of convex M-Estimators.
Regularization vs. Relaxation: A conic optimization perspective of statistical variable selection
Venue: arXiv cs.LG 2015
Year: 2015

Variable selection is a fundamental task in statistical data analysis. Sparsity-inducing regularization methods are a popular class of methods that simultaneously perform variable selection and model estimation. The central problem is a quadratic optimization problem with an l0-norm penalty. Exactly enforcing the l0-norm penalty is computationally intractable for larger scale problems, so dif- ferent sparsity-inducing penalty functions that approximate the l0-norm have been introduced. In this paper, we show that viewing the problem from a convex relaxation perspective offers new insights. In particular, we show that a popular sparsity-inducing concave penalty function known as the Minimax Concave Penalty (MCP), and the reverse Huber penalty derived in a recent work by Pilanci, Wainwright and Ghaoui, can both be derived as special cases of a lifted convex relaxation called the perspective relaxation. The optimal perspective relaxation is a related minimax problem that balances the overall convexity and tightness of approximation to the l0 norm. We show it can be solved by a semidefinite relaxation. Moreover, a probabilistic interpretation of the semidefinite relaxation reveals connections with the boolean quadric polytope in combinatorial optimization. Finally by reformulating the l0-norm pe- nalized problem as a two-level problem, with the inner level being a Max-Cut problem, our proposed semidefinite relaxation can be realized by replacing the inner level problem with its semidefinite relaxation studied by Goemans and Williamson. This interpretation suggests using the Goemans-Williamson rounding procedure to find approximate solutions to the l0-norm penalized problem. Numerical experiments demonstrate the tightness of our proposed semidefinite relaxation, and the effectiveness of finding approximate solutions by Goemans-Williamson rounding.
Unveiling Architecture Documentation: Brazilian Stakeholders in Perspective
Venue: arXiv cs.SE 2015
Year: 2015

Over the years, software architecture has become a established discipline, both in academia and industry, and the interest on software architecture documentation has increased. In this context, the improvement of methods, tools, and techniques around architecture documentation is of paramount importance. We conducted a survey with 147 industrial participants (31 from Brazil), analyzing their current problems and future wishes. We identified that Brazilian stakeholders need updated architecture documents with the right information. Finally, the automation of some parts of the documentation will reduce the effort during the creation of the documents. But first, is necessary to change the culture of the stakeholders. They have to participate actively in the architecture documents creation.
Symmetric Blind Decryption with Perfect Secrecy
Venue: arXiv cs.CR 2015
Year: 2015

A blind decryption scheme enables a user to query decryptions from a decryption server without revealing information about the plaintext message. Such schemes are useful, for example, for the implementation of privacy preserving encrypted file storages and payment systems. In terms of functionality, blind decryption is close to oblivious transfer. For noiseless channels, information-theoretically secure oblivious transfer is impossible. However, in this paper we show that this is not the case for blind decryption. We formulate a definition of perfect secrecy of symmetric blind decryption for the following setting: at most one of the scheme participants is a malicious observer. We also devise a symmetric blind decryption scheme based on modular arithmetic on a ring $\mathbb{Z}_{p^2}$, where $p$ is a prime, and show that it satisfies our notion of perfect secrecy.
Computing LZ77 in Run-Compressed Space
Venue: arXiv cs.DS 2015
Year: 2015

In this paper, we show that the LZ77 factorization of a text T {\inΣ^n} can be computed in O(R log n) bits of working space and O(n log R) time, R being the number of runs in the Burrows-Wheeler transform of T reversed. For extremely repetitive inputs, the working space can be as low as O(log n) bits: exponentially smaller than the text itself. As a direct consequence of our result, we show that a class of repetition-aware self-indexes based on a combination of run-length encoded BWT and LZ77 can be built in asymptotically optimal O(R + z) words of working space, z being the size of the LZ77 parsing.
Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer
Venue: arXiv cs.DB 2015
Year: 2015

The D-Wave adiabatic quantum annealer solves hard combinatorial optimization problems leveraging quantum physics. The newest version features over 1000 qubits and was released in August 2015. We were given access to such a machine, currently hosted at NASA Ames Research Center in California, to explore the potential for hard optimization problems that arise in the context of databases. In this paper, we tackle the problem of multiple query optimization (MQO). We show how an MQO problem instance can be transformed into a mathematical formula that complies with the restrictive input format accepted by the quantum annealer. This formula is translated into weights on and between qubits such that the configuration minimizing the input formula can be found via a process called adiabatic quantum annealing. We analyze the asymptotic growth rate of the number of required qubits in the MQO problem dimensions as the number of qubits is currently the main factor restricting applicability. We experimentally compare the performance of the quantum annealer against other MQO algorithms executed on a traditional computer. While the problem sizes that can be treated are currently limited, we already find a class of problem instances where the quantum annealer is three orders of magnitude faster than other approaches.
When ICN Meets C-RAN for HetNets: An SDN Approach
Venue: arXiv cs.NI 2015
Year: 2015

In this paper, we contribute to novelly proposing and elaborating the integration of the ICN, C-RAN and SDN for the HetNet to achieve win-win situation. The vision of the proposed system is demonstrated, followed by the advantages and challenges. We further present the hybrid system with a large-scale wireless heterogeneous campus network.
Multi-antenna Wireless Powered Communication with Co-channel Energy and Information Transfer
Venue: arXiv cs.IT 2015
Year: 2015

This letter studies a multi-antenna wireless powered communication (WPC) system with co-channel energy and information transfer, where a wireless device (WD), powered up by wireless energy transfer (WET) from an energy transmitter (ET), communicates to an information receiver (IR) over the same frequency band. We maximize the achievable data rate from the WD to the IR by jointly optimizing the energy beamforming at the ET and the information beamforming at the WD, subject to their individual transmit power constraints. We obtain the optimal solution to this problem in closed-form, where the optimal energy beamforming at the ET achieves a best energy/interference tradeoff between maximizing the energy transfer efficiency to the WD and minimizing the co-channel interference to the IR. Numerical results show that our proposed optimal co-channel design is superior to other reference schemes.
Reliable and Efficient Autonomous Driving: the Need for Heterogeneous Vehicular Networks
Venue: arXiv cs.NI 2015
Year: 2015

Autonomous driving technology has been regarded as a promising solution to reduce road accidents and traffic congestion, as well as to optimize the usage of fuel and lane. Reliable and high efficient Vehicle-to-Vehicle (V2V) and Vehicle-to-Infrastructure (V2I) communications are essential to let commercial autonomous driving vehicles be on the road before 2020. The current paper firstly presents the concept of Heterogeneous Vehicular NETworks (HetVNETs) for autonomous driving, in which an improved protocol stack is proposed to satisfy the communication requirements of not only safety but also non-safety services. We then consider and study in detail several typical scenarios for autonomous driving. In order to tackle the potential challenges raised by the autonomous driving vehicles in HetVNETs, new techniques from transmission to networking are proposed as potential solutions.