OpenRaiser/Intern-Atlas huggingface dataset:
Online Influence Maximization (Extended Version)
Venue: arXiv cs.SI 2015
Year: 2015

Social networks are commonly used for marketing purposes. For example, free samples of a product can be given to a few influential social network users (or "seed nodes"), with the hope that they will convince their friends to buy it. One way to formalize marketers' objective is through influence maximization (or IM), whose goal is to find the best seed nodes to activate under a fixed budget, so that the number of people who get influenced in the end is maximized. Recent solutions to IM rely on the influence probability that a user influences another one. However, this probability information may be unavailable or incomplete. In this paper, we study IM in the absence of complete information on influence probability. We call this problem Online Influence Maximization (OIM) since we learn influence probabilities at the same time we run influence campaigns. To solve OIM, we propose a multiple-trial approach, where (1) some seed nodes are selected based on existing influence information; (2) an influence campaign is started with these seed nodes; and (3) users' feedback is used to update influence information. We adopt the Explore-Exploit strategy, which can select seed nodes using either the current influence probability estimation (exploit), or the confidence bound on the estimation (explore). Any existing IM algorithm can be used in this framework. We also develop an incremental algorithm that can significantly reduce the overhead of handling users' feedback information. Our experiments show that our solution is more effective than traditional IM methods on the partial information.
Quantized Fusion Rules for Energy-Based Distributed Detection in Wireless Sensor Networks
Venue: arXiv cs.IT 2015
Year: 2015

We consider the problem of soft decision fusion in a bandwidth-constrained wireless sensor network (WSN). The WSN is tasked with the detection of an intruder transmitting an unknown signal over a fading channel. A binary hypothesis testing is performed using the soft decision of the sensor nodes (SNs). Using the likelihood ratio test, the optimal soft fusion rule at the fusion center (FC) has been shown to be the weighted distance from the soft decision mean under the null hypothesis. But as the optimal rule requires a-priori knowledge that is difficult to attain in practice, suboptimal fusion rules are proposed that are realizable in practice. We show how the effect of quantizing the test statistic can be mitigated by increasing the number of SN samples, i.e., bandwidth can be traded off against increased latency. The optimal power and bit allocation for the WSN is also derived. Simulation results show that SNs with good channels are allocated more bits, while SNs with poor channels are censored.
A Nearly Optimal and Agnostic Algorithm for Properly Learning a Mixture of k Gaussians, for any Constant k
Venue: arXiv cs.DS 2015
Year: 2015

Learning a Gaussian mixture model (GMM) is a fundamental problem in machine learning, learning theory, and statistics. One notion of learning a GMM is proper learning: here, the goal is to find a mixture of $k$ Gaussians $\mathcal{M}$ that is close to the density $f$ of the unknown distribution from which we draw samples. The distance between $\mathcal{M}$ and $f$ is typically measured in the total variation or $L_1$-norm. We give an algorithm for learning a mixture of $k$ univariate Gaussians that is nearly optimal for any fixed $k$. The sample complexity of our algorithm is $\tilde{O}(\frac{k}{ε^2})$ and the running time is $(k \cdot \log\frac{1}ε)^{O(k^4)} + \tilde{O}(\frac{k}{ε^2})$. It is well-known that this sample complexity is optimal (up to logarithmic factors), and it was already achieved by prior work. However, the best known time complexity for proper learning a $k$-GMM was $\tilde{O}(\frac{1}{ε^{3k-1}})$. In particular, the dependence between $\frac{1}ε$ and $k$ was exponential. We significantly improve this dependence by replacing the $\frac{1}ε$ term with a $\log \frac{1}ε$ while only increasing the exponent moderately. Hence, for any fixed $k$, the $\tilde{O} (\frac{k}{ε^2})$ term dominates our running time, and thus our algorithm runs in time which is nearly-linear in the number of samples drawn. Achieving a running time of $\textrm{poly}(k, \frac{1}ε)$ for proper learning of $k$-GMMs has recently been stated as an open problem by multiple researchers, and we make progress on this question. Moreover, our approach offers an agnostic learning guarantee: our algorithm returns a good GMM even if the distribution we are sampling from is not a mixture of Gaussians. To the best of our knowledge, our algorithm is the first agnostic proper learning algorithm for GMMs.
A Distributed and Privacy-Aware Speed Advisory System for Optimising Conventional and Electric Vehicles Networks
Venue: arXiv cs.SY 2015
Year: 2015

One of the key ideas to make Intelligent Transportation Systems (ITS) work effectively is to deploy advanced communication and cooperative control technologies among the vehicles and road infrastructures. In this spirit, we propose a consensus-based distributed speed advisory system that optimally determines a recommended common speed for a given area in order that the group emissions, or group battery consumptions, are minimised. Our algorithms achieve this in a privacy-aware manner; namely, individual vehicles do not reveal in-vehicle information to other vehicles or to infrastructure. A mobility simulator is used to illustrate the efficacy of the algorithm, and hardware-in-the-loop tests involving a real vehicle are given to illustrate user acceptability and ease of the deployment.
Service Networks Monitoring for better Quality of Service
Venue: arXiv cs.SE 2015
Year: 2015

Today, the deployment of Web services in many enterprise applications has gained much attention. Service network inhibits certain common properties as they arise spontaneously and are subject to high fluctuation. The objective of consumer is to compose services for stable business processes in coherence with their legacy system capabilities and with better quality of services. For this purpose we have proposed a dynamic decision model that integrates several performance metrics and attributes to monitor the performance of service oriented systems in order to ensure their sustainability. Based on the available metrics, we have identified performance metrics criteria and classified into categories like time based QoS, size based QoS, combined QoS and estimated attributes. Then we have designed service network monitoring ontology (SNM). Our decision model will take user query and SNM as input, measures the performance capabilities and suggests some new performance configurations like selected service is not available, physical resource is not available and no maintenance will be available for the selected service for composition.
Survey Results on Threats To External Validity, Generalizability Concerns, Data Sharing and University-Industry Collaboration in Mining Software Repository (MSR) Research
Venue: arXiv cs.SE 2015
Year: 2015

Mining Software Repositories (MSR) is an applied and practise-oriented field aimed at solving real problems encountered by practitioners and bringing value to Industry. Replication of results and findings, generalizability and external validity, University-Industry collaboration, data sharing and creation dataset repositories are important issues in MSR research. Research consisting of bibliometric analysis of MSR paper shows lack of University-Industry collaboration, deficiency of studies on closed or propriety source dataset and lack of data as well as tool sharing by researchers. We conduct a survey of authors of past three years of MSR conference (2012, 2013 and 2014) to collect data on their views and suggestions to address the stated concerns. We asked 20 questions from more than 100 authors and received a response from 39 authors. Our results shows that about one-third of the respondents always make their dataset publicly available and about one-third believe that data sharing should be a mandatory condition for publication in MSR conferences. Our survey reveals that more than 50% authors used solely open-source software (OSS) dataset for their research. More than 50% of the respondents mentioned that difficulty in sharing Industrial dataset outside the company is one of the major impediments in University-Industry collaboration.
Social signals and algorithmic trading of Bitcoin
Venue: arXiv cs.SI 2015
Year: 2015

The availability of data on digital traces is growing to unprecedented sizes, but inferring actionable knowledge from large-scale data is far from being trivial. This is especially important for computational finance, where digital traces of human behavior offer a great potential to drive trading strategies. We contribute to this by providing a consistent approach that integrates various datasources in the design of algorithmic traders. This allows us to derive insights into the principles behind the profitability of our trading strategies. We illustrate our approach through the analysis of Bitcoin, a cryptocurrency known for its large price fluctuations. In our analysis, we include economic signals of volume and price of exchange for USD, adoption of the Bitcoin technology, and transaction volume of Bitcoin. We add social signals related to information search, word of mouth volume, emotional valence, and opinion polarization as expressed in tweets related to Bitcoin for more than 3 years. Our analysis reveals that increases in opinion polarization and exchange volume precede rising Bitcoin prices, and that emotional valence precedes opinion polarization and rising exchange volumes. We apply these insights to design algorithmic trading strategies for Bitcoin, reaching very high profits in less than a year. We verify this high profitability with robust statistical methods that take into account risk and trading costs, confirming the long-standing hypothesis that trading based social media sentiment has the potential to yield positive returns on investment.
decimalInfinite: All Decimals In Bits, No Loss, Same Order, Simple
Venue: arXiv cs.MS 2015
Year: 2015

This paper introduces a binary encoding that supports arbitrarily large, small and precise decimals. It completely preserves information and order. It does not rely on any arbitrary use-case-based choice of calibration and is readily implementable and usable, as is. Finally, it is also simple to explain and understand.
What do they know about me? Contents and Concerns of Online Behavioral Profiles
Venue: arXiv cs.CY 2015
Year: 2015

Data aggregators collect large amount of information about individual users and create detailed online behavioral profiles of individuals. Behavioral profiles benefit users by improving products and services. However, they have also raised concerns regarding user privacy, transparency of collection practices and accuracy of data in the profiles. To improve transparency, some companies are allowing users to access their behavioral profiles. In this work, we investigated behavioral profiles of users by utilizing these access mechanisms. Using in-person interviews (n=8), we analyzed the data shown in the profiles, elicited user concerns, and estimated accuracy of profiles. We confirmed our interview findings via an online survey (n=100). To assess the claim of improving transparency, we compared data shown in profiles with the data that companies have about users. More than 70% of the participants expressed concerns about collection of sensitive data such as credit and health information, level of detail and how their data may be used. We found a large gap between the data shown in profiles and the data possessed by companies. A large number of profiles were inaccurate with as much as 80% inaccuracy. We discuss implications for public policy management.
Massively Parallel Phase-Field Simulations for Ternary Eutectic Directional Solidification
Venue: arXiv cs.DC 2015
Year: 2015

Microstructures forming during ternary eutectic directional solidification processes have significant influence on the macroscopic mechanical properties of metal alloys. For a realistic simulation, we use the well established thermodynamically consistent phase-field method and improve it with a new grand potential formulation to couple the concentration evolution. This extension is very compute intensive due to a temperature dependent diffusive concentration. We significantly extend previous simulations that have used simpler phase-field models or were performed on smaller domain sizes. The new method has been implemented within the massively parallel HPC framework waLBerla that is designed to exploit current supercomputers efficiently. We apply various optimization techniques, including buffering techniques, explicit SIMD kernel vectorization, and communication hiding. Simulations utilizing up to 262,144 cores have been run on three different supercomputing architectures and weak scalability results are shown. Additionally, a hierarchical, mesh-based data reduction strategy is developed to keep the I/O problem manageable at scale.
The Long-Short Story of Movie Description
Venue: arXiv cs.CV 2015
Year: 2015

Generating descriptions for videos has many applications including assisting blind people and human-robot interaction. The recent advances in image captioning as well as the release of large-scale movie description datasets such as MPII Movie Description allow to study this task in more depth. Many of the proposed methods for image captioning rely on pre-trained object classifier CNNs and Long-Short Term Memory recurrent networks (LSTMs) for generating descriptions. While image description focuses on objects, we argue that it is important to distinguish verbs, objects, and places in the challenging setting of movie description. In this work we show how to learn robust visual classifiers from the weak annotations of the sentence descriptions. Based on these visual classifiers we learn how to generate a description using an LSTM. We explore different design choices to build and train the LSTM and achieve the best performance to date on the challenging MPII-MD dataset. We compare and analyze our approach and prior work along various dimensions to better understand the key challenges of the movie description task.
Sparsity and cosparsity for audio declipping: a flexible non-convex approach
Venue: arXiv cs.SD 2015
Year: 2015

This work investigates the empirical performance of the sparse synthesis versus sparse analysis regularization for the ill-posed inverse problem of audio declipping. We develop a versatile non-convex heuristics which can be readily used with both data models. Based on this algorithm, we report that, in most cases, the two models perform almost similarly in terms of signal enhancement. However, the analysis version is shown to be amenable for real time audio processing, when certain analysis operators are considered. Both versions outperform state-of-the-art methods in the field, especially for the severely saturated signals.
Power Efficient and Secure Full-Duplex Wireless Communication Systems
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we study resource allocation for a full-duplex (FD) radio base station serving multiple half-duplex (HD) downlink and uplink users simultaneously. The considered resource allocation algorithm design is formulated as a non-convex optimization problem taking into account minimum required receive signal-to-interference-plus-noise ratios (SINRs) for downlink and uplink communication and maximum tolerable SINRs at potential eavesdroppers. The proposed optimization framework enables secure downlink and uplink communication via artificial noise generation in the downlink for interfering the potential eavesdroppers. We minimize the weighted sum of the total downlink and uplink transmit power by jointly optimizing the downlink beamformer, the artificial noise covariance matrix, and the uplink transmit power. We adopt a semidefinite programming (SDP) relaxation approach to obtain a tractable solution for the considered problem. The tightness of the SDP relaxation is revealed by examining a sufficient condition for the global optimality of the solution. Simulation results demonstrate the excellent performance achieved by the proposed scheme and the significant transmit power savings enabled optimization of the artificial noise covariance matrix.
Reconstruction of sparse wavelet signals from partial Fourier measurements
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we show that high-dimensional sparse wavelet signals of finite levels can be constructed from their partial Fourier measurements on a deterministic sampling set with cardinality about a multiple of signal sparsity.
Logics of Essence and Accident
Venue: arXiv cs.LO 2015
Year: 2015

In the literature, essence is formalized in two different ways, either de dicto, or de re. Following \cite{Marcos:2005}, we adopt its de dicto formalization: a formula is essential, if once it is true, it is necessarily true; otherwise, it is accidental. In this article, we study the model theory and axiomatization of the logic of essence and accident, i.e. the logic with essence operator (or accident operator) as the only primitive modality. We show that the logic of essence and accident is less expressive than modal logic on non-reflexive models, but the two logics are equally expressive on reflexive models. We prove that some frame properties are undefinable in the logic of essence and accident, while some are. We propose the suitable bisimulation for this logic, based on which we characterize the expressive power of this logic within modal logic and within first-order logic. We axiomatize this logic over various frame classes, among which the symmetric case is missing, and our method is more suitable than those in the literature. We also find a method to compute certain axioms used to axiomatize this logic over special frames in the literature. As a side effect, we answer some open questions raised in \cite{Marcos:2005}.
Dynamic Analysis can be Improved with Automatic Test Suite Refactoring
Venue: arXiv cs.SE 2015
Year: 2015

Context: Developers design test suites to automatically verify that software meets its expected behaviors. Many dynamic analysis techniques are performed on the exploitation of execution traces from test cases. However, in practice, there is only one trace that results from the execution of one manually-written test case. Objective: In this paper, we propose a new technique of test suite refactoring, called B-Refactoring. The idea behind B-Refactoring is to split a test case into small test fragments, which cover a simpler part of the control flow to provide better support for dynamic analysis. Method: For a given dynamic analysis technique, our test suite refactoring approach monitors the execution of test cases and identifies small test cases without loss of the test ability. We apply B-Refactoring to assist two existing analysis tasks: automatic repair of if-statements bugs and automatic analysis of exception contracts. Results: Experimental results show that test suite refactoring can effectively simplify the execution traces of the test suite. Three real-world bugs that could previously not be fixed with the original test suite are fixed after applying B-Refactoring; meanwhile, exception contracts are better verified via applying B-Refactoring to original test suites. Conclusions: We conclude that applying B-Refactoring can effectively improve the purity of test cases. Existing dynamic analysis tasks can be enhanced by test suite refactoring.
Machine Learning Based Cooperative Relay Selection in Virtual MIMO
Venue: arXiv cs.NI 2015
Year: 2015

In cellular systems, virtual multiple-input multiple-output (V-MIMO) technology promises to achieve performance gains comparable to conventional MIMO. In this paper, we propose cooperative relay selection algorithm based on machine learning techniques. Willingness of user to cooperate in V-MIMO depends on his current battery power, time and day along with incentives offered by service provider. Every user has different criterion to participate in V-MIMO, but allows a specific behavior pattern. Therefore, it is required to predict willing users in the neighborhood of source user (SU), before selecting users as cooperative nodes. Only inactive users belonging to Virtual Antenna Array (VAA) cell of SU are assumed to cooperate. This reduces control overheads in cooperative node discovery. In this paper, we employ prediction algorithm using two machine learning techniques i.e. ANN and SVM to find out inactive willing users within VAA cell. The parameters such as MSE, accuracy, precision and recall are calculated to evaluate performance of ANN and SVM model. Prediction using ANN has MSE of 3% with average accuracy of 97% (variance 0.37), whereas SVM has MSE of 2.58% with average accuracy of 97.56% (variance 0.17). We also observe that proposed prediction method reduces the node discovery time by approximately 29%.
Real scenario and simulations on GLOSA traffic light system for reduced CO2 emissions, waiting time and travel time
Venue: arXiv cs.MA 2015
Year: 2015

Cooperative ITS is enabling vehicles to communicate with the infrastructure to provide improvements in traffic control. A promising approach consists in anticipating the road profile and the upcoming dynamic events like traffic lights. This topic has been addressed in the French public project Co-Drive through functions developed by Valeo named Green Light Optimal Speed Advisor (GLOSA). The system advises the optimal speed to pass the next traffic light without stopping. This paper presents results of its performance in different scenarios through simulations and real driving measurements. A scaling is done in an urban area, with different penetration rates in vehicle and infrastructure equipment for vehicular communication. Our simulation results indicate that GLOSA can reduce CO2 emissions, waiting time and travel time, both in experimental conditions and in real traffic conditions.
Taming Subgraph Isomorphism for RDF Query Processing
Venue: arXiv cs.DB 2015
Year: 2015

RDF data are used to model knowledge in various areas such as life sciences, Semantic Web, bioinformatics, and social graphs. The size of real RDF data reaches billions of triples. This calls for a framework for efficiently processing RDF data. The core function of processing RDF data is subgraph pattern matching. There have been two completely different directions for supporting efficient subgraph pattern matching. One direction is to develop specialized RDF query processing engines exploiting the properties of RDF data for the last decade, while the other direction is to develop efficient subgraph isomorphism algorithms for general, labeled graphs for over 30 years. Although both directions have a similar goal (i.e., finding subgraphs in data graphs for a given query graph), they have been independently researched without clear reason. We argue that a subgraph isomorphism algorithm can be easily modified to handle the graph homomorphism, which is the RDF pattern matching semantics, by just removing the injectivity constraint. In this paper, based on the state-of-the-art subgraph isomorphism algorithm, we propose an in-memory solution, TurboHOM++, which is tamed for the RDF processing, and we compare it with the representative RDF processing engines for several RDF benchmarks in a server machine where billions of triples can be loaded in memory. In order to speed up TurboHOM++, we also provide a simple yet effective transformation and a series of optimization techniques. Extensive experiments using several RDF benchmarks show that TurboHOM++ consistently and significantly outperforms the representative RDF engines. Specifically, TurboHOM++ outperforms its competitors by up to five orders of magnitude.