Publications

2017

• Finding dense subgraphs and events in social media
  
  • Balalau Oana
  , 2017. Event detection in social media is the task of finding mentions of real-world events in collections of posts. The motivation behind our work is two-folded: first, finding events that are not covered by mainstream media and second, studying the interest that users show for certain types of events. In order to solve our problem, we start from a graph based characterization of the data in which nodes represent words and edges count word co-occurrences. Density is a very good measure of importance and cohesiveness in graphs. Taking into account the special properties of real-word networks, we can develop algorithms that efficiently solve hard problems. The contributions of this thesis are: devising efficient algorithms for computing different types of dense subgraphs in real-world graphs, presenting a novel dense subgraph definition and providing an efficient graph-based algorithm for event detection.
• Multi-View Design for Cyber-Physical Systems
  
  • Zhao Hui
  • Apvrille Ludovic
  • Mallet Frédéric
  , 2017, pp.22-28. Cyber-Physical Systems are complex systems made of various and heterogeneous subsystems; they have different aspects and each aspect has its own requirements and properties to be satisfied. Model-Driven Engineering (MDE) is a promising approach used to design and analyze complex systems on different levels and diverse views. CPS designers take many factors into account due to the complexity and diversity of current CPS systems. The designers have their own individual experience and specific viewpoint; they may use different models and languages to describe various domains, different models and languages lead to a complex coherency management. Therefore, how to promote the coherency of a whole system and ensure all subsystems can work together is an important concrete issue. To resolve this issue, we introduce a unified modeling methodology which can coordinate different models and languages with a multi-view approach. Indeed, we expect multi-view approaches to help handling system coherency. Hence, we focus on providing a high-level modeling methodology with multi-view that (i) Coordinates different languages of models and diverse tools. (ii) Ensures engineering-wide collaboration by sharing the same reference architecture. (iii) Handles the complexity of systems and architectures, using unified viewpoints to model the whole systems with top-down refinement. (iv) Supports different formal methods to verify critical elements. (v) Backtraces verification results to models.
• Wireless Node Cooperation with Resource Availability Constraints
  
  • Alvarez-Corrales Luis David
  • Giovanidis Anastasios
  • Martins Philippe
  • Decreusefond Laurent
  , 2017. —Base station cooperation is a promising scheme to improve network performance for next generation cellular networks. Up to this point research has focused on station grouping criteria based solely on geographic proximity. However, for the cooperation to be meaningful, each station participating in a group should have sufficient available resources to share with others. In this work we consider an alternative grouping criterion based on a distance that considers both geographic proximity and available resources of the stations. When the network is modelled by a Poisson Point Process, we derive analytical formulas on the proportion of cooperative pairs or single stations, and the expected sum interference from each of the groups. The results illustrate that cooperation gains strongly depend on the distribution of available resources over the network. (10.23919/WIOPT.2017.7959946)
  DOI : 10.23919/WIOPT.2017.7959946
• Distributed Deblurring of Large Images of Wide Field-of-View
  
  • Mourya Rahul
  • Ferrari André
  • Flamary Rémi
  • Bianchi Pascal
  • Richard Cédric
  , 2017. Image deblurring is an economic way to reduce certain degradations (blur and noise) in acquired images. Thus, it has become essential tool in high resolution imaging in many applications, e.g., astronomy, microscopy or computational photography. In applications such as astronomy and satellite imaging, the size of acquired images can be extremely large (up to gigapixels) covering wide field-of-view suffering from shift-variant blur. Most of the existing image deblurring techniques are designed and implemented to work efficiently on centralized computing system having multiple processors and a shared memory. Thus, the largest image that can be handle is limited by the size of the physical memory available on the system. In this paper, we propose a distributed nonblind image deblurring algorithm inwhich several connected processing nodes (with reasonable computational resources) process simultaneously different portions of a large image while maintaining certain coherency among them to finally obtain a single crisp image. Unlike the existing centralized techniques, image deblurring in distributed fashion raises several issues. To tackle these issues, we consider certain approximations that trade-offs between the quality of deblurred image and the computational resources required to achieve it. The experimental results show that our algorithm produces the similar quality of images as the existing centralized techniques while allowing distribution, and thus being cost effective for extremely large images.
• Proceedings of the 15th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt) 2017
  
  • Coupechoux Marceau
  • Giovanidis Anastasios
  • Walrand Jean
  • Bonald Thomas
  • Debbah Mérouane
  • Huang Jianwei
  • Médard Muriel
  , 2017.
• Conjunctive Queries on Probabilistic Graphs: Combined Complexity
  
  • Amarilli Antoine
  • Monet Mikaël
  • Senellart Pierre
  , 2017. Query evaluation over probabilistic databases is known to be intractable in many cases, even in data complexity, i.e., when the query is fixed. Although some restrictions of the queries [20] and instances [4] have been proposed to lower the complexity, these known tractable cases usually do not apply to combined complexity, i.e., when the query is not fixed. This leaves open the question of which query and instance languages ensure the tractability of probabilistic query evaluation in combined complexity. This paper proposes the first general study of the combined complexity of conjunctive query evaluation on probabilistic instances over binary signatures, which we can alternatively phrase as a probabilistic version of the graph homomor-phism problem, or of a constraint satisfaction problem (CSP) variant. We study the complexity of this problem depending on whether instances and queries can use features such as edge labels, disconnectedness, branching, and edges in both directions. We show that the complexity landscape is surprisingly rich, using a variety of technical tools: automata-based compilation to d-DNNF lineages as in [4], β-acyclic lin-eages using [11], the X-property for tractable CSP from [25], graded DAGs [28] and various coding techniques for hardness proofs. (10.1145/3034786.3056121)
  DOI : 10.1145/3034786.3056121
• Side-channel analysis and machine learning: A practical perspective
  
  • Picek Stjepan
  • Heuser Annelie
  • Jovic Alan
  • Ludwig Simone
  • Guilley Sylvain
  • Jakobović Domagoj
  • Mentens Nele
  , 2017.
• Incremental learning with the minimum description length principle
  
  • Murena Pierre Alexandre
  • Cornuéjols Antoine
  • Dessalles Jean-Louis
  , 2017, pp.np. Whereas a large number of machine learning methods focus on offline learning over a single batch of data called training data set, the increasing number of automatically generated data leads to the emergence of new issues that offline learning cannot cope with. Incremental learning designates online learning of a model from streaming data. In non-stationary environments, the process generating these data may change over time, hence the learned concept becomes invalid. Adaptation to this non-stationary nature, called concept drift, is an intensively studied topic and can be reached algorithmically by two opposite approaches: active or passive approaches. We propose a formal framework to deal with concept drift, both in active and passive ways. Our framework is derived from the Minimum Description Length principle and exploits the algorithmic theory of information to quantify the model adaptation. We show that this approach is consistent with state of the art techniques and has a valid probabilistic counterpart. We propose two simple algorithms to use our framework in practice and tested both of them on real and simulated data.
• Mesure dynamique de déformation par rétrodiffusion Brillouin spontanée B-OTDR
  
  • Maraval Damien
  , 2017. Aujourd’hui, trois technologies distinctes et complémentaires sont disponibles pour réaliser des mesures réparties de température, de déformation ou de vibration grâce à l’analyses des rétrodiffusion Raman, Brillouin et Rayleigh. Les besoins industriels actuels se portent sur la mesure répartie de déformation pour des infrastructures avec de longs linéaires, comme les canalisations, pour lesquelles une cartographie linéaire et en temps réel de leur état est demandée. Nous nous focalisons alors sur la conception d’un système de mesure Brillouin capable de mesurer de manière répartie et dynamique les déformations subies par une fibre optique. La méthode employée sera celle du flanc de frange ; elle a déjà été développée et expérimentée sur une architecture opto-électronique de type analyseur Brillouin (Brillouin-OTDA), nécessitant l’accès aux deux extrémités de la fibre optique. Dans notre cas, elle est implémentée sur une architecture fonctionnant en réflectométrie. Les résultats expérimentaux obtenus seront caractérisés et validés par la simulation des mesures de la déformation et du déplacement d’une canalisation supportée entre deux appuis simples ; un modèle mécanique, adapté à cette configuration et transposable sur des projets réels, est développé. Par le biais de partenaire industriels de Cementys, ce modèle est utilisé dans deux projets de surveillance de canalisation d’hydrocarbures dont les moyens d’installation et la finalité sont différents.
• Phase reference sharing schemes for continuous-variable quantum cryptography
  
  • Alleaume Romain
  , 2017.
• Q-Learning for Policy Based SON Management in wireless Access Networks
  
  • Daher Tony
  • Jemaa Sana Ben
  • Decreusefond Laurent
  , 2017, pp.1091-1096. Self organized networks has been one of the first concrete implementations of autonomic network management concept. Currently, several Self-Organizing-Network (SON) functions are developed by Radio Access Network (RAN) vendors and already deployed in many networks all around the world. These functions have been designed independently to replace different operational tasks. The concern of making these functions work together in a coherent manner has been studied later in particular in SEMAFOUR project where a Policy Based SON Management (PBSM) framework has been proposed to holistically manage a SON enabled network, namely a network with several individual SON functions. Enriching this PBSM framework with cognition capability is the next step towards the realization of the initial promise of SON concept: a unique self-managed network that responds autonomously and efficiently to the operator high level requirements and objectives. This paper proposes a cognitive PBSM system that enhances the SON management decisions by learning from past experience using Q-learning approach. Our approach is evaluated by simulation on a SON enabled Long-Term Evolution Advanced (LTE-A) network with several SON functions. The paper shows that the decisions are enhanced during the learning process and discusses the implementation options of this solution. (10.23919/INM.2017.7987442)
  DOI : 10.23919/INM.2017.7987442
• Malleable User Interface Toolkits for Cross-Surface Interaction
  
  • Eagan James R
  , 2017. Existing user interface toolkits are based on a single user interacting with a single machine with a relatively fixed set of input devices. Today's interactive systems, however, can involve multiple users interacting with a heterogeneous set of input, computational, and output capabilities across a dynamic set of different devices. The abstractions that help programmers create interactive software for one kind of system do not necessarily scale to these new kinds of environments. New toolkits designed around these environments, however, need to be able to bridge existing software and libraries or recreate them from scratch. In this position paper, we examine these new constraints and needs. We look at three strategies for software toolkits that help to bridge existing toolkit models to these new interaction paradigms.
• VersaPen: An Adaptable, Modular and Multimodal I/O Pen
  
  • Teyssier Marc
  • Bailly Gilles
  • Lecolinet Éric
  , 2017, pp.2155 - 2163. While software often allows user customization, most physical devices remain mainly static. We introduce VersaPen, an adaptable, multimodal, hot-pluggable pen for expanding input capabilities. Users can create their own pens by stacking different input/output modules that define both the look and feel of the customized device. VersaPen offers multiple advantages. Allowing in-place interaction, it reduces hand movements and avoids cluttering the interface with menus and palettes. It also enriches interaction by providing multimodal capabilities, as well as a mean to encapsulate virtual data into physical modules which can be shared by users to foster collaboration. We present various applications to demonstrate how VersaPen enables new interaction techniques. (10.1145/3027063.3053159)
  DOI : 10.1145/3027063.3053159
• VersaPen: Exploring Multimodal Interactions with a Programmable Modular Pen
  
  • Teyssier Marc
  • Bailly Gilles
  • Lecolinet Éric
  , 2017, pp.377 - 380. We introduce and demonstrate VersaPen, a modular pen for expanding input capabilities. Users can create their own digital pens by stacking different input/output modules that define both the look and feel of the customized device. Ver-saPen investigate the benefits of adaptable devices and enriches interaction by providing multimodal capabilities, allows in-place interaction, it reduces hand movements and avoids cluttering the interface with menus and palettes. The device integrates seamlessly thanks to a visual programming interface, allowing end users to connect input and output sources in other existing software. We present various applications to demonstrate the power of VersaPen and how it enables new interaction techniques. (10.1145/3027063.3052964)
  DOI : 10.1145/3027063.3052964
• IconHK: Using Toolbar Button Icons to Communicate Keyboard Shortcuts
  
  • Giannisakis Emmanouil
  • Bailly Gilles
  • Malacria Sylvain
  • Chevalier Fanny
  , 2017, pp.12. We propose a novel perspective on the design of toolbar buttons that aims to increase keyboard shortcut accessibility. IconHK implements this perspective by blending visual cues that convey keyboard shortcut information into toolbar buttons without denaturing the pictorial representation of their command. We introduce three design strategies to embed the hotkey, a visual encoding to convey the modifiers, and a magnification factor that determines the blending ratio between the pictogram of the button and the visual representation of the keyboard shortcut. Two studies examine the benefits of IconHK for end-users and provide insights from professional designers on the practicality of our approach for creating iconsets. Building on these insights, we develop a tool to assist designers in applying the IconHK design principle. (10.1145/3025453.3025595)
  DOI : 10.1145/3025453.3025595
• Effects of Frequency Distribution on Linear Menu Performance
  
  • Liu Wanyu
  • Bailly Gilles
  • Howes Andrew
  , 2017, 1 (1), pp.1307-1312. While it is well known that menu usage follows a Zipfian distribution, there has been little interest in the impact of menu item frequency distribution on user's behavior. In this note, we explore the effects of frequency distribution on average menu performance as well as individual item performance. We compare three frequency distributions of menu item usage: Uniform; Zipfian with s=1 and Zipfian with s=2. The results show that (1) user's behavior is sensitive to different frequency distributions at both menu and item level; (2) individual item selection time depends on, not only its frequency, but also the frequency of other items in the menu. Finally, we discuss how these findings might have impacts on menu design, empirical studies and menu modelling. (10.1145/3025453.3025707)
  DOI : 10.1145/3025453.3025707
• CoReach: Cooperative Gestures for Data Manipulation on Wall-sized Displays
  
  • Liu Can
  • Chapuis Olivier
  • Beaudouin-Lafon Michel
  • Lecolinet Eric
  , 2017. Multi-touch wall-sized displays afford collaborative exploration of large datasets and reorganization of digital content. However, standard touch interactions, such as dragging to move content, do not scale well to large surfaces and were not designed to support collaboration, such as passing an object around. This paper introduces CoReach, a set of collabora-tive gestures that combine input from multiple users in order to manipulate content, facilitate data exchange and support communication. We conducted an observational study to inform the design of CoReach, and a controlled study showing that it reduced physical fatigue and facilitated collaboration when compared with traditional multi-touch gestures. A final study assessed the value of also allowing input through a handheld tablet to manipulate content from a distance. (10.1145/3025453.3025594)
  DOI : 10.1145/3025453.3025594
• BIGnav: Bayesian Information Gain for Guiding Multiscale Navigation
  
  • Liu Wanyu
  • Lucas d'Oliveira Rafael
  • Beaudouin-Lafon Michel
  • Rioul Olivier
  , 2017, pp.5869-5880. This paper introduces BIGnav, a new multiscale navigation technique based on Bayesian Experimental Design where the criterion is to maximize the information-theoretic concept of mutual information, also known as information gain. Rather than simply executing user navigation commands, BIGnav interprets user input to update its knowledge about the user's intended target. Then it navigates to a new view that maximizes the information gain provided by the user's expected subsequent input. We conducted a controlled experiment demonstrating that BIGnav is significantly faster than conventional pan and zoom and requires fewer commands for distant targets, especially in non-uniform information spaces. We also applied BIGnav to a realistic application and showed that users can navigate to highly probable points of interest on a map with only a few steps. We then discuss the tradeoffs of BIGnav—including efficiency vs. increased cognitive load—and its application to other interaction tasks. (10.1145/3025453.3025524)
  DOI : 10.1145/3025453.3025524
• MarkPad: Augmenting Touchpads for Command Selection
  
  • Fruchard Bruno
  • Lecolinet Eric
  • Chapuis Olivier
  , 2017. We present MarkPad, a novel interaction technique taking advantage of the touchpad. MarkPad allows creating a large number of size-dependent gestural shortcuts that can be spatially organized as desired by the user. It relies on the idea of using visual or tactile marks on the touchpad or a combination of them. Gestures start from a mark on the border and end on another mark anywhere. MarkPad does not conflict with standard interactions and provides a novice mode that acts as a rehearsal of the expert mode. A first study showed that an accuracy of 95% could be achieved for a dense configuration of tactile and/or visual marks allowing many gestures. Performance was 5% lower in a second study where the marks were only on the borders. A last study showed that borders are rarely used, even when the users are unaware of the technique. Finally, we present a working prototype and briefly report on how it was used by two users for a few months. (10.1145/3025453.3025486)
  DOI : 10.1145/3025453.3025486
• How Data Workers Cope with Uncertainty
  
  • Boukhelifa Nadia
  • Perrin Marc-Emmanuel
  • Huron Samuel
  • Eagan James
  , 2017. Uncertainty plays an important and complex role in data analysis , where the goal is to find pertinent patterns, build robust models, and support decision making. While these endeavours are often associated with professional data scientists, many domain experts engage in such activities with varying skill levels. To understand how these domain experts (or "data workers") analyse uncertain data we conducted a qualitative user study with 12 participants from a variety of domains. In this paper, we describe their various coping strategies to understand, min-imise, exploit or even ignore this uncertainty. The choice of the coping strategy is influenced by accepted domain practices, but appears to depend on the types and sources of uncertainty and whether participants have access to support tools. Based on these findings, we propose a new process model of how data workers analyse various types of uncertain data and conclude with design considerations for uncertainty-aware data analytics. (10.1145/3025453.3025738)
  DOI : 10.1145/3025453.3025738
• To Miss is Human Information-Theoretic Rationale for Target Misses in Fitts’ Law
  
  • Gori Julien
  • Rioul Olivier
  • Guiard Yves
  , 2017. In usual Fitts' law experiments the outcome of a pointing act can be either measured as an error, i.e., a distance from end-point to target center, or categorized in an all-or-none way as a hit versus a miss. Information theory offers a useful distinction between transmission errors (the received symbol is wrong) and erasures (the received symbol is empty). Although Fitts' law research has been very much inspired by the information theoretic rationale, the error/erasure distinction has escaped attention so far: Target misses have always been treated as normally-distributed errors, through the effective index of difficulty ID e. The paper introduces a new index of difficulty based on the simple observation that a target miss conveys zero bit of information, i.e., it is an erasure. Not only is the new index more consistent with the fundamentals of information theory, it is much simpler to derive than the ISO-recommended ID e . (10.1145/3025453.3025660)
  DOI : 10.1145/3025453.3025660
• À la racine du parallélisme
  
  • Bonald Thomas
  • Comte Céline
  • Mathieu Fabien
  , 2017. Nous considérons un cluster de serveurs traitant des requêtes en parallèle. Si les clients ont en général intérêt à ce que leurs requêtes soient traitées par le plus grand nombre de serveurs, l’impact du parallélisme sur les serveurs est moins clair : trop faible, il ne permet pas d’utiliser pleinement les ressources disponibles ; trop fort, il risque d’encombrer inutilement les serveurs de requêtes en attente. Nous étudions ce phénomène à l’aide d’un modèle de files d’attente où les requêtes arrivent selon un processus de Poisson et requièrent des traitements dont le volume suit une loi exponentielle. Chaque nouvelle requête est affectée à un certain nombre de serveurs, choisis de manière aléatoire, uniforme, et indépendante de l’état du système. Chaque serveur traite ses requêtes dans leur ordre d’arrivée. Nous montrons qu’il existe un degré de parallélisme qui minimise le nombre moyen de requêtes présentes dans chaque serveur. Ce degré optimal est de l’ordre de la racine carrée du nombre de serveurs pour une charge faible à modérée, et décroît jusqu’à deux à très forte charge.
• Narrow Linewidth Quantum Dot distributed Feedback Lasers
  
  • Duan Jianan
  • Huang Heming
  • Schires Kevin
  • Lu Zhaoyang
  • Poole Philip
  • Grillot Frédéric
  , 2017.
• Bernoulli Rank-1 Bandits for Click Feedback
  
  • Szepesvari Csaba
  • Kveton Bratislav
  • Katariya Sumeet
  • Vernade Claire
  , 2017.
• Quantum protocols within Spekkens' toy model
  
  • Disilvestro Leonardo
  • Markham Damian
  Physical Review A : Atomic, molecular, and optical physics [1990-2015], American Physical Society, 2017, 95 (5). Quantum mechanics is known to provide significant improvements in information processing tasks when compared to classical models. These advantages range from computational speeds-up to security improvements. A key question is where these advantages come from. The toy model developed by Spekkens [R. W. Spekkens PRA 75, 032110 (2012)] mimics many of the features of quantum mechanics, such as entanglement and no-cloning, regarded as being important in this regard, despite being a local hidden variable theory. In this work we study several protocols within Spekkens' toy model where we see it can also mimic the advantages and limitations shown in the quantum case. We first provide explicit proofs for the impossibility of toy bit-commitment and the existence of a toy error correction protocol and consequent $k-$threshold secret sharing. Then, defining a toy computational model based on the quantum one-way computer we prove the existence of blind and verified protocols. Importantly, these two last quantum protocols are known to achieve a better-than-classical security. Our results suggest that such quantum improvements need not arise from any Bell-type non locality or contextuality, but rather as a consequence of steering correlations. (10.1103/PhysRevA.95.052324)
  DOI : 10.1103/PhysRevA.95.052324