Manuela MONTANGERO - personale UniMoRe

Nuova ricerca

Manuela MONTANGERO

Professore Associato
Dipartimento di Scienze Fisiche, Informatiche e Matematiche sede ex-Matematica

Pubblicazioni

2024 - Exploiting Traffic Light Coordination and Auctions for Intersection and Emergency Vehicle Management in a Smart City Mixed Scenario [Articolo su rivista]
Muzzini, Filippo; Montangero, Manuela
abstract

2024 - Learn to Bet: Using Reinforcement Learning to Improve Vehicle Bids in Auction-Based Smart Intersections [Articolo su rivista]
Cabri, G.; Lugli, M.; Montangero, M.; Muzzini, F.
abstract

With the advent of IoT, cities will soon be populated by autonomous vehicles and managed by intelligent systems capable of actively interacting with city infrastructures and vehicles. In this work, we propose a model based on reinforcement learning that teaches to autonomous connected vehicles how to save resources while navigating in such an environment. In particular, we focus on budget savings in the context of auction-based intersection management systems. We trained several models with Deep Q-learning by varying traffic conditions to find the most performance-effective variant in terms of the trade-off between saved currency and trip times. Afterward, we compared the performance of our model with previously proposed and random strategies, even under adverse traffic conditions. Our model appears to be robust and manages to save a considerable amount of currency without significantly increasing the waiting time in traffic. For example, the learner bidder saves at least 20% of its budget with heavy traffic conditions and up to 74% in lighter traffic with respect to a standard bidder, and around three times the saving of a random bidder. The results and discussion suggest practical adoption of the proposal in a foreseen future real-life scenario.

2023 - Coordinated traffic lights and auction intersection management in a mixed scenario [Relazione in Atti di Convegno]
Muzzini, F.; Capodieci, N.; Montangero, M.
abstract

IoT (Internet-of-Things) powered devices can be exploited to connect vehicles to a smart city infrastructure and thus allow vehicles to share their intentions while retrieving contextual information about diverse aspects of urban viability. Such a complex system is aimed at improving our way of living in the city by mitigating the effect of traffic congestion, and consequently stress and pollution. We place ourselves in a transient scenario in which next generation vehicles that are able to communicate with the surrounding infrastructure coexist with traditional vehicles with limited or absent IoT-capabilities. In this work we focus on intersection management and, in particular, on reusing existing traffic lights empowered by a new management systems. We propose an auction based system in which traffic lights are able to exchange contextual information with vehicles and the nearby traffic lights with the aim of reducing average waiting times at intersections and consequently, overall trip times. We evaluate our proposal using the well known MATSim transport simulator, by using a synthetic Manhattan map and a new map we build on an urban area located in our town, in Norther Italy. In such an area, instrumentation through IoT devices has been set up as part of an European research project. Results show that the proposal is better performing than the classical Fixed Time Control system currently adopted for traffic lights, and then auction strategies that do not exploit coordination among nearby traffic lights.

2023 - Improving urban viability through smart parking [Articolo su rivista]
Muzzini, F.; Capodieci, N.; Montangero, M.
abstract

In Smart Cities, vehicles can share intentions and retrieve information through IoT (Internet-of-Things) devices. This work proposes a reservation system that exploits communication between vehicles and city infrastructure to reduce the time a road user needs to find parking. The system is designed to manage the coexistence of next-generation vehicles, that communicate with city infrastructure and traditional vehicles that don't. We reconstructed an IoT-instrumented urban area using the MATSim simulator to evaluate the system. The proposed system reduces the parking search time of next-generation vehicles without disadvantaging traditional vehicles, making it a candidate for scenarios where both vehicle types coexist.

2023 - Smart Parking for All: Equipped and Non-equipped Vehicles in Smart Cities [Relazione in Atti di Convegno]
Muzzini, F.; Montangero, M.; Capodieci, N.
abstract

The current trend in designing cities is to think them as smart environments that are constantly connected with road users. For this purpose, a smart city is implemented as a collection of IoT (Internet-of-Things) powered devices set up in order to connect vehicles to their surrounding infrastructure. In this way, road users share their intentions while retrieving useful information from the smart city itself. This complex and distributed system must be then tailored to improve viability performance metrics such as reducing traffic congestion, optimizing accident response and everything else related to transportation in urban areas. In this work we focus on parking management in a scenario in which next generation vehicles will be able to communicate with the surrounding infrastructure and will coexist with traditional vehicles with limited or absent IoT-capabilities. We propose a reservation mechanism able to exploit communication at infrastructure level, with the goal of reducing the time needed to find a free parking spot close to destination. We evaluate our proposed mechanisms using the well known MATSim transport simulator.

2023 - Twitter as Passive Sensor to Understand How COVID-19 Pandemic Affected Human Mobility [Relazione in Atti di Convegno]
Furini, M.; Montangero, M.
abstract

During the COVID-19 pandemic, countries all over the world have tried to prevent the spread of the virus with measures like social distancing, movement limitation, closure of premises and shops, voluntary isolation, lockdown, and curfew. Likely, these limitations have influenced the way people moved within urban spaces. In this study, we use Twitter as a passive sensor to understand how these measures affected human mobility. We focus on the city of Milan, one of the most international and active cities in Italy, but also one of the cities most affected by the spread of the virus. We analyzed more than one million of GPS geo-tagged tweets, posted from 2019 to 2022, and results show that the pandemic has affected human mobility (in 2022, less mobility during work hours and more mobility during the evening hours), and show that social and fashion-related activities are the main reasons people move within the city. This study shows the benefits of using Twitter as a passive sensor to measure human mobility: real-time analysis (not possible with interviews and/or questionnaire) and insights of the reasons behind human mobility (not possible to get with the sole use of telephone operators data).

2023 - Understanding users music listening habits for time and activity sensitive customized playlists [Relazione in Atti di Convegno]
Furini, M.; Montangero, M.
abstract

Music playlists have rapidly become one of the top services of streaming platforms: users do not need to spend time into deciding what to listen to, they just have to select the proper pre-compiled playlists composed by some music they know and some new songs close to their taste. However, users will continue to listen to playlists only if these conform to their musical tastes. Indeed, users listening habits might differ according to the activity they are performing while listening to music, and suggested playlists should reflect that. As there still are not in literature standard methods to produce customized playlists automatically, in this work in progress paper we focus on how to exploit users past music hearings to define genre listening habits in specific days of the week and hours of the day. We present our first investigation toward this direction by proposing a simple and computationally inexpensive method and by testing it using the Spotify listening history of volunteer users. We show that the method is promising and discuss several future working directions to improve the method and make it more effective.

2022 - A Predictive Method to Improve the Effectiveness of Twitter Communication in a Cultural Heritage Scenario [Articolo su rivista]
Furini, Marco; Mandreoli, Federica; Martoglia, Riccardo; Montangero, Manuela
abstract

Museums are embracing social technologies in an attempt to broaden their audience and to engage people. Although social communication seems an easy task, media managers know how hard it is to reach millions of people with a simple message. Indeed, millions of posts are competing every day to get visibility in terms of likes and shares and very little research focused on museums communication to identify best practices. In this article, we focus on Twitter and we propose a novel method that exploits interpretable machine learning techniques to: (a) predict whether a tweet will likely be appreciated by Twitter users or not; (b) present simple suggestions that will help to enhance the message and increase the probability of its success. Using a real-world dataset of around 40,000 tweets written by 23 world famous museums, we show that our proposed method allows identifying tweet features that are more likely to influence the tweet success.

2022 - About Challenges in Data Analytics and Machine Learning for Social Good [Articolo su rivista]
Martoglia, Riccardo; Montangero, Manuela
abstract

The large number of new services and applications and, in general, all our everyday activities resolve in data mass production: all these data can become a golden source of information that might be used to improve our lives, wellness and working days. (Interpretable) Machine Learning approaches, the use of which is increasingly ubiquitous in various settings, are definitely one of the most effective tools for retrieving and obtaining essential information from data. However, many challenges arise in order to effectively exploit them. In this paper, we analyze key scenarios in which large amounts of data and machine learning techniques can be used for social good: social network analytics for enhancing cultural heritage dissemination; game analytics to foster Computational Thinking in education; medical analytics to improve the quality of life of the elderly and reduce health care expenses; exploration of work datafication potential in improving the management of human resources (HRM). For the first two of the previously mentioned scenarios, we present new results related to previously published research, framing these results in a more general discussion over challenges arising when adopting machine learning techniques for social good.

2022 - Automatic and Personalized Sequencing of Music Playlists [Relazione in Atti di Convegno]
Furini, M.; Montangero, M.
abstract

Music playlists are appreciated by users, music artists and service providers for various reasons (i.e., no need to waste time choosing what to listen to, showcase to increase popularity, engage users to the provided services). However, despite their ever-increasing centrality, in literature there is no precise definition on how to produce them. Often, playlists are produced by music recommendation algorithms that focus on the songs selection process and don't give enough importance to songs sequencing. Indeed, until a few years ago the listening order was not considered important. In this paper, we address the songs sequencing problem in a novel way. Through dynamic programming, we transform a set of non-ordered songs into a user-tailored sequence of songs that meets the user's musical preferences. To the best of our knowledge, this approach has never been used in the literature.

2022 - Digital Twins and Artificial Intelligence as Pillars of Personalized Learning Models [Articolo su rivista]
Furini, Marco; Gaggi, Ombretta; Mirri, Silvia; Montangero, Manuela; Pelle, Elvira; Poggi, Francesco; Prandi, Catia
abstract

Modern educational systems have not really evolved enough to meet the needs of modern students.21 No wonder, the percentage of dropouts from university studies is quite high (40% in the U.S. and 10% in Europe7,9). The university student profile has changed over the years. While yesterday's students were mainly full-time, today's students face challenges such as work commitments, family obligations, financial constraints, physical impairments, and learning models that do not adequately engage students or help them understand core concepts.11 One might think that this issue concerns only those who fail to complete their studies, but this is view is shortsighted. Today's educational system deficiencies will affect the welfare of tomorrow's society.

2022 - On Designing a Time Sensitive Interaction Graph to Identify Twitter Opinion Leaders [Relazione in Atti di Convegno]
Furini, M.; Mariotti, L.; Martoglia, R.; Montangero, M.
abstract

What happened on social media during the recent pandemic? Who was the opinion leader of the conversations? Who influenced whom? Were they medical doctors, ordinary people, scientific experts? Did health institutions play an important role in informing and updating citizens? Identifying opinion leaders within social platforms is of particular importance and, in this paper, we introduce the idea of a time sensitive interaction graph to identify opinion leaders within Twitter conversations. To evaluate our proposal, we focused on all the tweets posted on Twitter in the period 2020-21 and we considered just the ones that were Italian-written and were related to COVID-19. After mapping these tweets into the graph, we applied the PageRank algorithm to extract the opinion leaders of these conversations. Results show that our approach is effective in identifying opinion leaders and therefore it might be used to monitor the role that specific accounts (i.e., health authorities, politicians, city administrators) have within specific conversations.

2022 - Traffic Flow Modelling When Autonomous Vehicles Coexist with Human Driven Vehicles: Perspectives and Challenges [Relazione in Atti di Convegno]
Cabri, G.; Crisci, S.; Montangero, M.
abstract

The problem of mathematically modeling traffic flows has been tackled, with different approaches, since the first decades of the last century. The classic framework that accounts only for human-driven cars is bound to change due to the rise of autonomous driving technologies, which will deeply transform mobility, as well as general driving rules and infrastructures. It is therefore urgent to design novel approaches for modeling the transition phase, where autonomous vehicles and human-driven vehicles will have to coexist, and to devise appropriate solutions for their coordination. In this paper, we provide a brief overview of the most recent studies on the transition scenario, and outline the main challenges and perspectives that are likely to appear in the near future for this case.

2021 - About auction strategies for intersection management when human-driven and autonomous vehicles coexist [Articolo su rivista]
Cabri, Giacomo; Gherardini, Luca; Montangero, Manuela; Muzzini, Filippo
abstract

Autonomous vehicles are appearing in our streets, and will soon populate our transportation infrastructures, which must be equipped with appropriate sensors and actuators in order to manage vehicles in a fruitful way. Besides the infrastructures, appropriate algorithms must be defined in order to coordinate the vehicles and to enable them to exploit the resources in a fair yet effective way. In the immediate future, autonomous vehicles must coexist human-driven vehicles, and this transitory scenario poses several challenges in coordinating both kinds to exploit street resources. One of these resources, whose management is quite challenging, is represented by intersections: vehicles come and aim at passing the intersection, often as soon as possible, but they must compete with other vehicles having the same aim. A possible approach that has been used in literature to this problem uses auction based mechanisms. In this paper, we place ourselves in the above-mentioned transitory scenario in which both human-driven and autonomous vehicles will compete to cross intersections, and we investigate the effectiveness of auction-based mechanism to coordinate vehicles at intersections. We devise some simple auction policies, and assume vehicle coordination strategies that are suitable also for human drivers. Our results lead us to believe that, under these assumptions, simple auction mechanisms do not introduce advantages for what concern traveling times as they do in the case of exclusively autonomous vehicles.

2021 - On using conversational interfaces to improve the accessibility of a university campus [Relazione in Atti di Convegno]
Furini, M.; Mirrit, S.; Montangero, M.; Pecorelli, M.; Prandi, C.
abstract

Moving around a university campus may seem an activity of little importance: students are young, they walk and run without problems, with a simple glance they know where they are and where to go, they understand where a lesson is held, when a teacher is available or where to go when they are hungry. Activities that millions of students do every day. But what about students with some form of physical impairments? For them, moving around a university campus is a daily challenge. Can conversational interfaces improve the accessibility of a University campus? is the research question we address in this study. We involved students (with and without disabilities) in the development and evaluation of a skill for the Amazon Alexa platform. Results show that conversational interfaces are highly appreciated by most of the participants and confirm that such interfaces might improve the daily experience of users within a university campus.

2020 - An Intelligent Dashboard for Assisted Tweet Composition in the Cultural Heritage Area (Work-in-progress) [Relazione in Atti di Convegno]
Martoglia, R.; Montangero, M.
abstract

Cultural Heritage institutions are nowadays using social media to communicate with citizens and tourists. However, providing actual effective communication is not an easy task, as every day millions of messages are posted through social media. Thus, getting visibility is not trivial. In this paper we present the architecture of a dashboard, accessible by mobile Android devices, to support museum social media managers in composing effective tweets by providing suggestions to improve message drafts. At this aim, the application exploits machine learning techniques over data related to tweets posted by museums in the past.

2020 - Can IoT Wearable Devices Feed Frugal Innovation? [Relazione in Atti di Convegno]
Furini, M.; Mirri, S.; Montangero, M.; Prandi, C.
abstract

Recently, there has been a lot of talk about Frugal services, that is, services that use existing technologies for a purpose other than the one for which they were designed. In this paper, we study whether the IoT wearable environment can be a fertile ground for the production of Frugal services. Through a real-world study, we investigate whether these devices are widespread, if there are obstacles that limit their diffusion, if the sensors they are equipped with are deemed reliable and, finally, if people who own them have an altruistic propensity or not. The results, from the frugal point of view, are encouraging: the IoT wearable environment seems to be pervasive enough and ubiquitous, without great obstacles for their adoption. The provided sensors seem to be generally reliable, whereas the altruistic propensity might be questioned: in general, people are not inclined to share, but if the goal is clear (in our case we hypothesized a fight against Covid-19), altruistic propensity grows a lot.

2020 - Conversational Interfaces for a Smart Campus: A Case Study [Relazione in Atti di Convegno]
Bortoli, M.; Furini, M.; Mirri, S.; Montangero, M.; Prandi, C.
abstract

The spoken language is the most natural interface for a human being and, thanks to the scientific-technological advances made in recent decades, nowadays we have voice assistance devices to interact with a machine through the use of natural language. Vocal user interfaces (VUI) are now included in many technological devices, such as desktop and laptop computers, smartphones and tablets, navigators, and home speakers, being welcomed by the market. The use of voice assistants can also be interesting and strategic in educational contexts and in public environments. This paper presents a case study based on the design, development, and assessment of a prototype devoted to assist students' during their daily activities in a smart campus context.

2020 - Distributed balanced color assignment on arbitrary networks [Articolo su rivista]
De Marco, G.; Leoncini, M.; Montangero, M.
abstract

Consider a scenario in which a set of n agents hold items, where each item can be of one out of m possible types (colors). The agents are connected by an arbitrary network and have to distributively find a repartition of the colors such that the amount of colors for each agent is as balanced as possible: in the particular case where m is a multiple of n, each agent must have exactly m/n colors. More formally, the goal is to let the agents agree on an assignment of colors to agents such that the following two conditions hold: (i) each color is assigned to exactly one agent; (ii) each agent has at least ⌊m/n⌋ and at most ⌈m/n⌉ colors. Among all possible such repartitions, we seek for the one that minimizes the number of “changes” (measured in terms of misplaced items) with respect to the initial configuration. In other words, our aim is to design a distributed algorithm that finds a balanced coloring of minimum cost, where the cost of a coloring is the number of items that need to be relocated. This kind of questions, usually modeled as generalized bipartite matching problems, have been studied in the distributed setting only on clusters of commodity nodes with the aim of copying with real-world massive instances, which may involve millions of agents and colors. Here we propose the first distributed algorithm designed to run on an arbitrary network with the agents as nodes. Our algorithm turns out to be efficient in terms of both time and message complexity for a large class of graphs. Our results can be outlined as follows. We prove a lower bound Ω(m/n⋅D2) on message complexity, where D is the diameter of the graph, that holds for any approximation algorithm whose solution has cost at most 2(α−2)/α times the cost of any optimal solution, for every constant α>2. We give a distributed deterministic algorithm with time complexity O(max⁡n2,Dlog⁡q) and message complexity?>O(nlog⁡n⋅(log⁡q+mlog⁡m)), where q is the maximum number of items of a given color held by any agent. We show that the cost of our solution for arbitrary graphs is at most (2+δ) times the optimal cost, for any δ>0. We finally observe that, for large diameter graphs (i.e., D=Ω(nϵ), ϵ>0), we get matching lower and upper bounds on message complexity for the vast majority of instances of potential interest, that is, instances with polynomial number of colors and (up to) super-exponential number of items.

2020 - Do Conversational Interfaces Kill Web Accessibility? [Relazione in Atti di Convegno]
Furini, M.; Mirri, S.; Montangero, M.; Prandi, C.
abstract

Conversational interfaces are making web accessibility studies obsolete. Long-time has passed since the introduction of graphical interfaces. They revolutionized the way people used the computer. The desktop metaphor popularized and made easy access to the software but did not consider the specific needs of people with some form of sight and/or motion impairments. Accessibility, at that time, was a minor issue. The web changed everything and empathized the need to include people. Researchers from around the world began working on accessibility, which is still an issue on the agenda of many scientific labs. Despite this, we observe that today, with the diffusion of conversational interfaces, there is less need to bother about colors, fonts, size and many other visual features. Indeed, people might access to web contents through voice interaction. No need to see the graphic interface or to use input devices requiring the use of hands. The voice is everything you need, and accessibility has never been easier. Conversational interfaces are about to revolutionize accessibility and in this provocative paper, we show benefits, problems, and open issues that happen when these interfaces meet accessibility requirements.

2020 - Exploiting Traffic Lights to Manage Auction-Based Crossings [Relazione in Atti di Convegno]
Muzzini, F.; Capodieci, N.; Montangero, M.
abstract

Auction-based crossing management approaches are used to design coordination policies for autonomous vehicles and improve smart intersections by providing differentiated latencies. In this paper, we propose and exploit an auction based mechanism for managing the urban traffic light infrastructure in which participant vehicles are either equipped or non-equipped. The difference between these two categories of vehicles is that only the equipped ones can actively participate to auctions through in-vehicle IoT-devices, i.e. they are able to communicate with the surrounding urban infrastructure. In this way, we aim to study the transitional period that will occur before the complete adoption of autonomous or strongly connected vehicles. Through extensive experiments and simulations, by comparing our mechanism to the traditional traffic light fixed-time-control approach, we studied the benefits and limitations, in term of waiting and trip times, when varying the subset of equipped vehicles and the available budget that can be used to participate to auctions.

2020 - Managing Human-driven and Autonomous Vehicles at Smart Intersections [Relazione in Atti di Convegno]
Cabri, G.; Montangero, M.; Muzzini, F.; Valente, P.
abstract

Auction-based crossing management approaches are used to design coordination policies for autonomous vehicles and improve smart intersections by providing for differentiated latencies. In this paper we exploit auction-based mechanisms to design a management intersections system re-using traffic lights and coordinating human driven and autonomous vehicles. We first describe in detail this system that uses already present traffic lights and the bidding policy of our auction mechanisms. We then describe our experimental scenario and the research issue that will be addressed by means of future simulations.

2020 - On the Usage of Smart Speakers during the Covid-19 Coronavirus Lockdown [Relazione in Atti di Convegno]
Furini, M.; Mirri, S.; Montangero, M.; Prandi, C.
abstract

The COVID-19 pandemic has dramatically changed every aspect of our professional and private life. It forced us to stay at home and it gave unprecedented power to technology. In this paper we focus on the emerging technology of smart speakers (e.g., Amazon Echo Plus, Google Home, etc.) and, through a developed questionnaire, we investigate how people use these devices. In particular, we analyze whether the human behavior has been affected by availability of these smart speaker. Results showed that the usage of these devices did not increase during lockdown, but it highlighted the presence of some privacy issues that might represent a burden to the diffusion of this type of technology.

2020 - Privacy Perception when Using Smartphone Applications [Articolo su rivista]
Furini, M.; Mirri, S.; Montangero, M.; Prandi, C.
abstract

Our smartphone is full of applications and data that analytically organize, facilitate and describe our lives. We install applications for the most varied reasons, to inform us, to have fun and for work, but, unfortunately, we often install them without reading the terms and conditions of use. The result is that our privacy is increasingly at risk. Considering this scenario, in this paper, we analyze the user’s perception towards privacy while using smartphone applications. In particular, we formulate two different hypotheses: 1) the perception of privacy is influenced by the knowledge of the data used by the installed applications; 2) applications access to much more data than they need. The study is based on two questionnaires (within-subject experiments with 200 volunteers) and on the lists of installed apps (30 volunteers). Results show a widespread abuse of data related to location, personal contacts, camera, Wi-Fi network list, running apps list, and vibration. An in-depth analysis shows that some features are more relevant to certain groups of users (e.g., adults are mainly worried about contacts and Wi-Fi connection lists; iOS users are sensitive to smartphone vibration; female participants are worried about possible misuse of the smartphone camera).

2020 - Untangling between fake-news and truth in social media to understand the Covid-19 Coronavirus [Relazione in Atti di Convegno]
Furini, M.; Mirri, S.; Montangero, M.; Prandi, C.
abstract

"Covid-19 is a virus developed to rule the world"is just one of the many fake-news published on the Web. In this pandemic period, the Web is flooded with real news, allegedly true or blatantly false. To understand how fake news is affecting the Covid-19 perception, we selected 40 news (either true or fake) related to the origin, diffusion, treatment and effects of Covid-19 and we asked 293 volunteers to express their opinion on the truthfulness of the news. Then, we propose an Awareness index to compute knowledge degree of the volunteers. The results highlight a large ignorance on medical news, ignorance that goes beyond educational background. The study highlights the need for Health Institution to enter social media platforms in order to clearly explain what is true and what is false on Covid-19.

2019 - A Parallel Branch-and-Bound Algorithm to Compute a Tighter Tardiness Bound for Preemptive Global EDF [Articolo su rivista]
Leoncini, Mauro; Montangero, Manuela; Valente, Paolo
abstract

In this paper we present a parallel exact algorithm to compute an upper bound to tardiness of preemptive Global EDF (G-EDF) schedulers, named harmonic bound, which has been proved to be up to 30% tighter than previously proposed bounds. Tightness is a crucial property of tardiness bounds: a too loose bound may cause a feasible soft real-time application to be mistakenly deemed unfeasible. Unfortunately, no polynomial-time algorithm is known to date to compute the harmonic bound. Although there is no proof of hardness of any sort either, the complex formula of the bound apparently provides no hints to devise algorithms with sub-exponential worst-case cost. In this paper we address this issue by proposing a parallel, exact, branch-andbound algorithm to compute the harmonic bound, called harm-BB, which proves to be extremely fast in a large number of experiments. More specifically, we compare its execution times with those of existing polynomial-time algorithms for other known tardiness bounds on 630000 random task sets. harm-BB outperforms, or is comparable to, the competitor algorithms in all scenarios but the ones with the highest number of processors (7 and 8) and tasks (50). In the latter scenarios harm-BB is indeed slower than the other algorithms; yet, it was still feasible, as it takes only about 2:8 s to compute the bound on a commodity Dual-Core CPU. Even better, we show that harm-BB has a high parallel efficiency, thus its execution time may be largely cut down on highly-parallel platforms.

2019 - A distributed message-optimal assignment on rings [Articolo su rivista]
De Marco, G.; Leoncini, M.; Montangero, M.
abstract

Consider a set of items and a set of m colors, where each item is associated to one color. Consider also n computational agents connected by a ring. Each agent holds a subset of the items and items of the same color can be held by different agents. We analyze the problem of distributively assigning colors to agents in such a way that (a) each color is assigned to one agent only and (b) the number of different colors assigned to each agent is minimum. Since any color assignment requires the items be distributed according to it (e.g. all items of the same color are to be held by only one agent), we define the cost of a color assignment as the amount of items that need to be moved, given an initial allocation. We first show that any distributed algorithm for this problem requires a message complexity of Ω(n⋅m) and then we exhibit an optimal message complexity algorithm for synchronous and asynchronous rings that in polynomial time determines a color assignment with cost at most three times the optimal. We show that the approximation is tight and how to get a better cost solution at the expenses of either the message or the time complexity. Finally, we present some experiments showing that, in practice, our algorithm performs much better than the theatrical worst case scenario.

2019 - Auction-based crossings management [Relazione in Atti di Convegno]
Cabri, G.; Gherardini, L.; Montangero, M.
abstract

Autonomous vehicles will ``invade'' our street in a not so far future. They must be coordinated in order to exploit the resources in a fair yet effective way. One of these resources, whose management is quite challenging, is represented by crossings: vehicles come and aim at passing the intersection, often as soon as possible, but they must compete with other vehicles. In this paper we propose an auction-based mechanism to coordinate the vehicles at a crossing, considering the presence of both human-driven and autonomous vehicles; moreover, we introduce an enhancement mechanism to take into consideration also the presence of vehicles in the lanes behind the first one. We analyze different strategies and, by means of simulation experiments, we compare them and show how waiting times change depending on the strategies. The results show that the cooperative strategy presents average waiting times lower for all vehicles than a competitive strategy.

2019 - Automated Generation of User-Tailored and Time-Sensitive Music Playlists [Relazione in Atti di Convegno]
Furini, Marco; Martini, Jessica; Montangero, Manuela
abstract

Streaming music platforms have changed the way people listen to music. Today, we can access to millions of songs with a simple internet-connected device. The drawback is that the selection of what to listen is a long, tedious, ant time-consuming process. This is why, nowadays, we choose playlists instead of songs. Unfortunately, since there are thousands of playlists, the selection process can once again be long, tedious, and time-consuming. In this paper, we design a system to facilitate the listening and discovering of new music. The system automatically generates user-tailored and time-sensitive music playlists and proposes a single playlist to play when the user accesses to a music platform. The system understands the user's listening habits by analyzing the low-level features of songs recently played by the user and by using two different clustering algorithms. A novel designed method uses these data to produce a playlist that expands the user's musical knowledge keeping in mind that a good playlist must contain a mix of new and known music and artists. An implementation based on the Spotify API proved the effectiveness of the approach and showed that the proposal might provide benefits to both users (no time wasted to select what to play) and to music platforms (playing of music that otherwise would remain unknown to users).

2019 - Crowd-sensing Images to Understand Citizens' Emotions, Issues and Interests [Relazione in Atti di Convegno]
De Michele, R.; Furini, M.; Montangero, M.
abstract

Many studies are beginning to gather data with a crowd-sensing approach in order to understand citizens' opinions and thoughts, because these data are more and more crucial for the smart management of a city. So far, the focus is mainly on textual data, but recent approaches revealed the wealth of information that can be found in multimedia contents. In this paper, we propose a crowd-sensing approach that exploits the popularity and the pervasiveness of the Instagram application to understand citizens emotions, issues and interests. The idea is to map the colors of the images into a psychological emotional model and to measure the significance of the words used in the caption of the images. Results showed that the use of the visual contents might be misleading, due to the large use of image filters that alter the real contents of the images, but also disclosed that captions might give insights about citizens that can be very useful to smartly manage a city.

2019 - Dealing With Data Heterogeneity in a Data Fusion Perspective: Models, Methodologies, and Algorithms [Capitolo/Saggio]
Mandreoli, F.; Montangero, M.
abstract

Dealing with multiple manifestations of the same real-world entity across several data sources is a very common challenge for many modern applications, including life science applications. This challenge is referenced as data heterogeneity in the data management research field where the final aim is often to get a unified or integrated view of the real-world entities represented in the data sources. Data heterogeneity is a long-standing challenge that has attracted much interest in different computer science disciplines. The main aim of the chapter is to show how data heterogeneity problems that are typical of life science application contexts can be afforded by adopting systematic solutions stemming from the computer science field. To this end, it focusses on the main sources of heterogeneity in the life science context, presents the main problems that arise when dealing with heterogeneity, and provides a review of the solutions proposed in the computer science literature.

2019 - Diabetes: What are Italian twitter users talking about? [Relazione in Atti di Convegno]
Ferretti, S.; Furini, M.; Montangero, M.
abstract

Social media are nowadays used by people to talk about any kind of topic, either private or not, and among others health problems. Concerning health, on social media one can find large communities discussing about chronic diseases. Here people look for advise, information, support, and so on. In this paper we take into consideration the Italian Twitter community interested in diabetes, a chronic blood disease. Our aim is to understand which are the main conversation topics in this community. Thus, we analyzed about 9K tweets written in Italian that contained the world diabete (diabetes) and performed both a hashtag analysis and a lexicon analysis, the latter by means of ad-hoc dictionaries. Results show that this is a calm community interested into several distinct topics (e.g., disease related information gathering, recipes for diabetes patients, fundraising campaigns), none of which is really predominant over the others.

2019 - Gamification and Accessibility [Relazione in Atti di Convegno]
Furini, Marco; Mirri, Silvia; Montangero, Manuela
abstract

Many different environments are looking at gamification to improve education, business, tourism, smart-cities management, etc. Despite its popularity, and despite the availability of many studies that propose approaches to transform a non-game activity into a game, a gamification strategy guideline is missing. Usually, the proposed methods are too general to be effective (e.g., simple rules, incentive mechanisms such as scores or vague prizes). In a society where algorithms personalize everything, and where people with different impairments (either technological or physical) are present, it is important to also understand peoples preferences in terms of games. In this paper, through a questionnaire filled by 22 people, we show that the game preferences (rules, mechanics, focus, motivations, and gaming environment) are assistive-technology dependent. These preferences can be used to customize the gamification process and therefore the study might be helpful to develop effective gamification strategies.

2019 - On predicting the success of political tweets using psycho-linguistic categories [Relazione in Atti di Convegno]
Furini, M.; Montangero, M.
abstract

Politics is increasingly influenced by Twitter communications and more and more politicians are using this platform to keep in touch with their electorate or to make proselytes. However, an effective communication is not easy to obtain and many studies are trying to identify strategies able to produce successful tweets. Day and time of publication, presence or absence of hashtags and images are some metrics used to define a communication strategy, but in this paper we propose a novel approach. Our idea is to describe tweets through novel psycho-linguistic categories (e.g. immigrants, security, kindness, etc.) and to use these categories as features to predict the success of political tweets. Through the observation of tweets posted over the last year by an Italian politician, very active and popular in the social scenario, we analyze two different machine learning approaches (i.e., Decision Tree and K-Neighbors) to predict the success of a tweet. The results obtained show that it is possible to achieve a prediction accuracy of 76%, thus showing the importance of the proposed psycho-linguistic categories to characterize tweets in the political context.

2019 - Privacy perception and user behavior in the mobile ecosystem [Relazione in Atti di Convegno]
Furini, M.; Mirri, S.; Montangero, M.; Prandi, C.
abstract

Smartphones contain a myriad of personal information and, due to their ubiquity and the possibility to access the Internet through wireless networks, our privacy might be constantly at risk. In this study, we formulate two hypotheses: (H1) users ignore the relationship between authorization requests and privacy and this lack of knowledge affects their perception towards privacy; (H2) users install applications that access sensitive data that are not necessary for their correct functioning. To investigate H1, we developed a questionnaire and we submitted it to 150 volunteers using a within subject approach where the controlled variable is the knowledge about possible abuses of smartphone data. Results show that ignorance influences the privacy perception. To investigate H2, we analyzed more than 800 apps installed on the smartphone of 30 volunteers and we found a widespread abuse of data related to location, contacts, camera, Wi-Fi network list, running apps list, and vibration. The outcome reveals that some features are more relevant to groups of users with specific characteristics, e.g., adults are mainly worried about contacts and Wi-Fi, iOS users are sensitive to the smartphone vibration, female participants are worried about possible misuse of the smartphone camera, to list a few. By identifying such features, our study might be considered the first step towards a more secure smartphone usage, as such features might work as expedients to attract users’ attention on privacy issues.

2018 - 5 steps to make art museums tweet influentially [Relazione in Atti di Convegno]
Furini, Marco; Mandreoli, Federica; Martoglia, Riccardo; Montangero, Manuela
abstract

A growing number of museums has started using social networks as different forms of engagement that can act outside museum architectural bounds. Specifically, museum leaders are praising Twitter as a necessary tool to any online programming or presence in museums today. Nevertheless, using Twitter in a satisfactory way so to increase museums' influence is not an easy task and there has been a gap between its usage and the possibilities it represents. In this paper, we propose an easily understandable framework to analyze the key content factors in museum conversations, including novel formulas for the evaluation of tweets and Twitter accounts influence. We apply the framework to a dataset of 100,000 messages related to 26 museum accounts to understand which museum is more influential in writing tweets, and which features have more impact on the influence of a tweet. Finally, we propose 5 key steps that museums can perform in order to write more influential tweets.

2018 - Entertainment for Serious Purposes: Customization of the Gamification Process [Relazione in Atti di Convegno]
Furini, Marco; Mirri, Silvia; Montangero, Manuela
abstract

The gamification process is gaining increasing interest in many different environments such as education, business, tourism, smart-cities management. In literature, many studies proposed approaches to transform a non- game activity into a game, but these methods are often too general to be effective (e.g., simple rules, incentive mechanisms such as scores or vague prizes). In a society where algorithms personalize everything, from search en- gine results, to news on social networks, it is anachronistic to think of a single gamification strategy suited to different categories of people (e.g., what might be motivating for digital natives, might not be for digital immigrants, and vice versa). In this paper, through a questionnaire filled by 226 people, we show that the game preferences (rules, mechanics, focus, motivations, and gaming environment) are age-dependent. These preferences can be used to customize the gamification process and therefore the study might be helpful to develop effective gamification strategies.

2018 - Sentiment analysis and Twitter: a game proposal, [Articolo su rivista]
Furini, Marco; Montangero, Manuela
abstract

Pervasive sensing of people's opinions is becoming critical in strategic decision processes, as it may be helpful in identifying problems and strengthening strategies. A recent research trend is to understand users' opinions through a sentiment analysis of contents published in the Twitter platform. This approach involves two challenges: the large volume of available data and the large variety of used languages combined with the brevity of texts. The former makes manual analysis unreasonable, whereas the latter complicates any type of automatic analysis. Since sentiment analysis is a difficult process for computers, but it is quite simple for humans, in this article we transform the sentiment analysis process into a game. Indeed, we consider the game with a purpose approach and we propose a game that involves users in classifying the polarity (e.g., positive, negative, neutral) and the sentiment (e.g., joy, surprise, sadness, etc.) of tweets. To evaluate the proposal, we used a dataset of 52,877 tweets, we developed a Web-based game, we invited people to play the game, and we validated the results through a ground-truth approach. The experimental assessment showed that the game approach is effective in measuring people' sentiments and also highlighted that participants liked to play the game.

2018 - Standards, Security and Business Models: Key Challenges for the IoT Scenario [Articolo su rivista]
Bujari, Armir; Furini, Marco; Mandreoli, Federica; Martoglia, Riccardo; Montangero, Manuela; Ronzani, Daniele
abstract

The number of physical objects connected to the Internet constantly grows and a common thought says the IoT scenario will change the way we live and work. Since IoT technologies have the potential to be pervasive in almost every aspect of a human life, in this paper, we deeply analyze the IoT scenario. First, we describe IoT in simple terms and then we investigate what current technologies can achieve. Our analysis shows four major issues that may limit the use of IoT (i.e., interoperability, security, privacy, and business models) and it highlights possible solutions to solve these problems. Finally, we provide a simulation analysis that emphasizes issues and suggests practical research directions.

2018 - Topic-based playlist to improve video lecture accessibility [Relazione in Atti di Convegno]
Furini, Marco; Mirri, Silvia; Montangero, Manuela
abstract

Learning is considered one of the most important activities for the human being, and many educational institutes are trying to improve the engagement with students through the availability of video lectures. However, the access to video material is not easy as one may think. For millions of people with some form of disabilities the simple act of browsing a video lecture archive represents an insuperable burden. Motivated by the need to improve accessibility to video lecture materials, in this paper we present VLP, which stands for Video Lecture Playlist. The idea is to use low-level audio/video features, video segmentation and OCR analysis to 'understand' the content of the video lectures. In this way, students can search for specific topic through keywords and the system browses the entire video lecture archive to find all the pieces of video lectures that cover the searched topic. These pieces are then provided through a playlist, so that a single search and a single playout return a complete view of how the searched topic is covered within the entire archive. A developed prototype shows the feasibility of the approach and results obtained from a survey highlight that students would like to browse video lecture archives with keywords and playlists.

2018 - Towards tweet content suggestions for museum media managers [Relazione in Atti di Convegno]
Furini, Marco; Martoglia, Riccardo; Mandreoli, Federica; Montangero, Manuela
abstract

Cultural Heritage institutions are embracing social technologies in the attempt to provide an effective communication towards citizens. Although it seems easy to reach millions of people with a simple message posted on social media platforms, media managers know that practice is different from theory. Millions of posts are competing every day to get visibility in terms of likes and retweets. The way text, images, hashtags and links are combined together is critical for the visibility of a post. In this paper, we propose to exploit machine learning techniques in order to predict whether a tweet will likely be appreciated by Twitter users or not. Through an experimental assessment, we show that it is possible to provide insights about the tweet features that will likely influence its reception/recommendation among readers. The preliminary tests, performed on a real-world dataset of 19,527 museum tweets, show promising accuracy results.

2017 - A branch-and-bound algorithm to compute a tighter bound to tardiness for preemptive global EDF scheduler [Relazione in Atti di Convegno]
Leoncini, Mauro; Montangero, Manuela; Valente, Paolo
abstract

Tightness is a crucial property of tardiness bounds; in fact, a too loose bound may cause a feasible soft real-time application to be mistakenly deemed unfeasible. Recently, a new tardiness bound for preemptive global EDF (G-EDF), named harmonic bound, has been proposed and proved to be up to 30% tighter than previous bounds. Unfortunately, no polynomial-time algorithm is known to date to compute the harmonic bound. Although there is no proof of hardness of any sort either, the complex formula of the bound apparently provides no hints to devise algorithms with sub-exponential worst-case cost. In this paper we address this issue by proposing an exact branch-and-bound algorithm, called harm-BB, which proved to be extremely fast in a large number of experiments. More specifically, we compared its execution times with those of existing polynomial-time algorithms for other known similar bounds on 630000 random task sets. harm-BB outperformed the competitor algorithms in all scenarios but the ones with the highest number of processors and tasks (8 and â ¼50, respectively). However, even in the latter cases, harm-BB was at most 1.5 slower than the other algorithms, and, in absolute terms, took only about 4.4 ms to compute the bound on commodity hardware.

2017 - Distributed Beta-Assignment on graphs [Relazione in Atti di Convegno]
DE MARCO, Gianluca; Leoncini, Mauro; Mazzali, Lucia; Montangero, Manuela
abstract

Consider a set of items and a set of m colors, where each item is associated to one color. Consider also n computational agents connected by an arbitrary graph. Each agent initially holds a subset of the items. We analyze the problem of distributively assigning colors to agents in such a way that (a) each color is assigned to one agent only and (b) the number of different colors assigned to each agent is minimum (c) the number of items initially assigned to agents that are not consistent with the assignment of colors is minimum. This problem, known in the centralized setting as a matching problem, has been introduced in the distributed setting in [3] for the simple ring topology. Here, we generalize the problem to arbitrary graphs, by solving it with a distributed algorithm which is eficient both in terms of time complexity and message complexity for a large class of graphs. Namely, our results can be outlined as follows. We prove a lower bound on the message complexity ofÏ (m/n D2), where D is the diameter of the graph. We give a distributed deterministic algorithm with time complexity O(maxn2;Dlog qg) and message complexity O (n/log n) (log q+mlogm) , where q is the maximum number of items of a given color held by an agent. It can be noticed that for a large class of instances of practical interest, namely for m O(nc), for some constant c, and q â¬ O(mm), our algorithm exhibits a message complexity of O(m n), which turns out to be optimal, in view of our lower bound, for graphs with diameter linear in the number of nodes. We finally show that the cost of our solution for arbitrary graphs is at most three times the optimal cost (found by a centralized algorithm).

2017 - IoT: Science Fiction or real revolution? [Relazione in Atti di Convegno]
Furini, Marco; Mandreoli, Federica; Martoglia, Riccardo; Montangero, Manuela
abstract

It's been many years since media began talking about the wonders of the IoT scenario, where a smart fridge checks the milk ex- piration date and automatically compiles the shopping list, but in the real life how many people have this smart fridge in the kitchen? Yet the interest around the IoT scenario is growing every day, so in this paper we try to figure out if IoT is science fiction or a real revolution. In particu- lar, we describe in simple terms the IoT scenario, what can be done with current technologies, what are the main obstacles that limit the success and the wide use of IoT and we highlight directions that can make IoT a true reality.

2017 - TagLecture: The gamification of video lecture indexing through quality-based tags [Relazione in Atti di Convegno]
Furini, Marco; Mirri, Silvia; Montangero, Manuela
abstract

The wide availability of video lectures within digital archives is causing significant problems to video providers. Indeed, students search for very specific contents and the few minutes of video lecture that cover the required topic have to be found in an archive composed of thousands of hours of videos. Therefore, the indexing of video material is becoming a critical process. Unfortunately, most of the systems return a list of full-length video lectures, and force students to use VCR-like functions in order to find what they are looking for. This approach is not adequate. Furthermore, the indexing process never considers the quality of the lecture (e.g., 'interesting', 'meaningless', etc.). A recent approach proposed to improve the indexing process by using social tagging. To be effective, this approach requires having a considerable number of tags. In this paper, we propose TagLecture, a Game With A Purpose that introduces game elements into the indexing process in order to involve students in the indexing process of video lectures. Through an experimental investigation we highlight that the gamification of the video indexing process is well accepted by students: more than 80% of participants liked the idea of using quality-based tags to classify video lectures, and more than half of them liked the idea of a game where students challenge each other to tag pieces of video lectures.

2017 - The Use of Hashtags in the Promotion of Art Exhibitions [Relazione in Atti di Convegno]
Furini, Marco; Mandreoli, Federica; Martoglia, Riccardo; Montangero, Manuela
abstract

Hashtags are increasingly used to promote, foster and group conversations around specific topics. For example, the entertainment industry widely uses hashtags to increase interest around their products. In this paper, we analyze whether hashtags are effective in a niche scenario like the art exhibitions. The obtained results show very different behaviors and confused strategies: from museums that do not consider hashtags at all, to museums that create official hastags, but hardly mention them; from museums that create multiple hashtags for the same exhibition, to those that are very confused about hashtag usage. Furthermore, we discovered an interesting case, where a smart usage of hashtags stimulated the interest around art. Finally, we highlight few practical guidelines with behaviors to follow and to avoid; the guidelines might help promoting art exhibitions.

2016 - TSentiment: On gamifying Twitter sentiment analysis [Relazione in Atti di Convegno]
Furini, Marco; Montangero, Manuela
abstract

Social media platforms contain interesting information that can be used to directly measure people' feelings and, thanks to the use of communication technologies, also to geographically locate these feelings. Unfortunately, the understanding is not as easy as one may think. Indeed, the large volume of data makes the manual approach impractical and the diversity of language combined with the brevity of the texts makes the automatic approach quite complicated. In this paper, we consider the gamification approach to sentimentally classify tweets and we propose TSentiment, a game with a purpose that uses human beings to classify the polarity of tweets (e.g., positive, negative, neutral) and their sentiment (e.g., joy, surprise, sadness, etc.). We created a dataset of more than 65,000 tweets, we developed a Web-based game and we asked students to play the game. Obtained results showed that the game approach was well accepted and thus it can be useful in scenarios where the identification of people' feelings may bring benefits to decision making processes.

2015 - CMStalker: a combinatorial tool for composite motif discovery [Articolo su rivista]
Leoncini, Mauro; Montangero, Manuela; PANUCIA TILLAN, Karina; Pellegrini, Marco
abstract

Controlling the differential expression of many thousands different genes at any given time is a fundamental task of metazoan organisms and this complex orchestration is controlled by the so-called regulatory genome encoding complex regulatory networks: several Transcription Factors bind to precise DNA regions, so to perform in a cooperative manner a specific regulation task for nearby genes. The in silico prediction of these binding sites is still an open problem, notwithstanding continuous progress and activity in the last two decades. In this paper we describe a new efficient combinatorial approach to the problem of detecting sets of cooperating binding sites in promoter sequences, given in input a database of Transcription Factor Binding Sites encoded as Position Weight Matrices. We present CMStalker, a software tool for composite motif discovery which embodies a new approach that combines a constraint satisfaction formulation with a parameter relaxation technique to explore efficiently the space of possible solutions. Extensive experiments with twelve data sets and eleven state-of-the-art tools are reported, showing an average value of the correlation coefficient of 0.54 (against a value 0.41 of the closest competitor). This improvements in output quality due to CMStalker is statistically significant.

2015 - Investigating Power and Limitations of Ensemble Motif Finders Using Metapredictor CE3 [Articolo su rivista]
Leoncini, Mauro; Montangero, Manuela; Panucia Tillan, Karina
abstract

Ensemble methods represent a relatively new approach to motif discovery that combines the results returned by "third-party" finders with the aim of achieving a better accuracy than that obtained by the single tools. Besides the choice of the external finders, another crucial element for the success of an ensemble method is the particular strategy adopted to combine the finders' results, a.k.a. learning function. Results appeared in the literature seem to suggest that ensemble methods can provide noticeable improvements over the quality of the most popular tools available for motif discovery. With the goal of better understanding potentials and limitations of ensemble methods, we developed a general software architecture whose major feature is the flexibility with respect to the crucial aspects of ensemble methods mentioned above. The architecture provides facilities for the easy addition of virtually any third-party tool for motif discovery whose code is publicly available, and for the definition of new learning functions. We present a prototype implementation of our architecture, called CE3 (Customizable and Easily Extensible Ensemble). Using CE3, and available ensemble methods, we performed experiments with three well-known datasets. The results presented here are varied. On the one hand, they confirm that ensemble methods cannot be just considered as the universal remedy for "in-silico" motif discovery. On the other hand, we found some encouraging regularities that may help to find a general set up for CE3 (and other ensemble methods as well) able to guarantee substantial improvements over single finders in a systematic way.

2015 - TRank: Ranking Twitter Users According to Specific Topics [Relazione in Atti di Convegno]
Furini, Marco; Montangero, Manuela
abstract

Twitter is the most popular real-time micro-blogging service and it is a platform where users provide and obtain information at rapid pace. In this scenario, one of the biggest challenge is to find a way to automatically identify the most influential users of a given topic. Currently, there are several approaches that try to address this challenge using different Twitter signals (e.g., number of followers, lists, metadata), but results are not clear and sometimes conflicting. In this paper, we propose TRank, a novel method designed to address the problem of identifying the most influential Twitter users on specific topics identified with hashtags. The novelty of our approach is that it combines different Twitter signals (that represent both the user and the user's tweets) to provide three different indicators that are intended to capture different aspects of being influent. The computation of these indicators is not based on the magnitude of the Twitter signals alone, but they are computed taking into consideration also human factors, as for example the fact that a user with many active followings might have a very noisy time lime and, thus, miss to read many tweets. The experimental assessment confirms that our approach provides results that are more reasonable than the one obtained by mechanisms based on the sole magnitude of data.

2013 - CE^3: Customizable and Easily Extensible Ensemble Tool for Motif Discovery [Relazione in Atti di Convegno]
PANUCIA TILLAN, Karina; Leoncini, Mauro; Montangero, Manuela
abstract

Ensemble methods (or simply ensembles) for motif discovery represent a relatively new approach to improve the accuracy of standalone motif finders. In particular, the accuracy of an ensemble is determined by the included finders and the strategy (learning rule) used to combine the results returned by the latter, making these choices crucial for the ensemble success. In this research we propose a general architecture for ensembles, called CE3, which is meant to be extensible and customizable for what concerns external tools inclusion and learning rule. Using CE3 the user will be able to “simulate” existing ensembles and possibly incorporate newly proposed tools (and learning functions) with the aim at improving the ensemble’s prediction accuracy. Preliminary experiments performed with a prototype implementation of CE3 led to interesting insights and a critical analysis of the potentials and limitations of currently available ensembles.

2013 - CMF: a Combinatorial Tool to Find Composite Motifs [Relazione in Atti di Convegno]
Leoncini, Mauro; Montangero, Manuela; M., Pellegrini; PANUCIA TILLAN, Karina
abstract

Controlling the differential expression of many thousands genes at any given time is a fundamental task of metazoan organisms and this complex orchestration is controlled by the so-called regulatory genome encoding complex regulatory networks. Cis-Regulatory Modules are fundamental units of such networks. To detect Cis-Regulatory Modules “in-silico” a key step is the discovery of recurrent clusters of DNA binding sites for sets of cooperating Transcription Factors. Composite motif is the term often adopted to refer to these clusters of sites. In this paper we describe CMF, a new efficient combinatorial method for the problem of detecting composite motifs, given in input a description of the binding affinities for a set of transcription factors. Testing with known benchmark data, we attain statistically significant better performance against nine state-of-the-art competing methods.

2012 - Direct vs 2-stage approaches to structured motif finding [Articolo su rivista]
Federico, Maria; Leoncini, Mauro; Montangero, Manuela; Valente, Paolo
abstract

Background The notion of DNA motif is a mathematical abstraction used to model regions of the DNA (known as Transcription Factor Binding Sites, or TFBSs) that are bound by a given Transcription Factor to regulate gene expression or repression. In turn, DNA structured motifs are a mathematical counterpart that models sets of TFBSs that work in concert in the gene regulations processes of higher eukaryotic organisms. Typically, a structured motif is composed of an ordered set of isolated (or simple) motifs, separated by a variable, but somewhat constrained number of "irrelevant" base-pairs. Discovering structured motifs in a set of DNA sequences is a computationally hard problem that has been addressed by a number of authors using either a direct approach, or via the preliminary identication and successive combination of simple motifs. Results We describe a computational tool, named SISMA, for the de-novo discovery of structured motifs in a set of DNA sequences. SISMA is an exact, enumerative algorithm, meaning that it nds all the motifs conforming to the specications. It does so in two stages: rst it discovers all the possible component simple motifs, then combines them in a way that respects the given constraints. We developed SISMA mainly with the aim of understanding the potential benets of such a 2-stage approach w.r.t. direct methods. In fact, no 2-stage software was available for the general problem of structured motif discovery, but only a few tools that solved restricted versions of the problem. We evaluated SISMA against other published tools on a comprehensive benchmark made of both synthetic and real biological datasets. In a signicant number of cases, SISMA outperformed the competitors, exhibiting a good performance also in most of the cases in which it was inferior. Conclusions A reection on the results obtained lead us to conclude that a 2-stage approach can be implemented with many advantages over direct approaches. Some of these have to do with greater modularity, ease of parallelization, and the possibility to perform adaptive searches of structured motifs. As another consideration, we noted that most hard instances for SISMA were easy to detect in advance. In these cases one may initially opt for a direct method; or, as a viable alternative in most laboratories, one could run both direct and 2-stage tools in parallel, halting the computations when the first halts.

2012 - Optimal Decision Trees for Local Image Processing Algorithms [Articolo su rivista]
Grana, Costantino; Montangero, Manuela; Borghesani, Daniele
abstract

In this paper we present a novel algorithm to synthesize an optimal decision tree from OR-decision tables, an extension of standard decision tables, complete with the formal proof of optimality and computational cost analysis. As many problems which require to recognize particular patterns can be modeled with this formalism, we select two common binary image processing algorithms, namely connected components labeling and thinning, to show how these can be represented with decision tables, and the benets of their implementation as optimal decision trees in terms of reduced memory accesses. Experiments are reported, to show the computational time improvements over state of the art implementations.

2011 - A High Performing Tool for Residue Solvent Accessibility Prediction [Relazione in Atti di Convegno]
Palmieri, Lorenzo; Federico, Maria; Leoncini, Mauro; Montangero, Manuela
abstract

Many efforts were spent in the last years in bridging the gap between the huge number of sequenced proteins and the relatively few solved structures. Relative Solvent Accessibility (RSA) prediction of residues in protein complexes is a key step towards secondary structure and protein-protein interaction sites prediction. With very different approaches, a number of software tools for RSA prediction have been produced throughout the last twenty years. Here, we present a binary classifier which implements a new method mainly based on sequence homology and implemented by means of look-up tables. The tool exploits residue similarity in solvent exposure pattern of neighboring context in similar protein chains, using BLAST search and DSSP structure. A two-state classification with 89.5% accuracy and 0.79 correlation coefficient against the real data is achieved on a widely used dataset.

2011 - Optimal Decision Trees Generation from OR-Decision Tables [Relazione in Atti di Convegno]
Grana, Costantino; Montangero, Manuela; Borghesani, Daniele; Cucchiara, Rita
abstract

In this paper we present a novel dynamic programming algorithm to synthesize an optimal decision tree from OR-decision tables,an extension of standard decision tables,which allow to choose between several alternative actions in the same rule. Experiments are reported,showing the computational time improvements over state of the art implementations of connected components labeling,using this modelling technique.

2010 - STIMO: STIll and MOving Video Storyboard\\ for the Web Scenario [Articolo su rivista]
Furini, Marco; Geraci, Filippo; Montangero, Manuela; Pellegrini, Marco
abstract

In the current Web scenario a video browsing tool that produces on-the-fly storyboards is more and more a need. Video summary techniques can be helpful but, due to their long processing time, they are usually unsuitable for on-the-fly usage. Therefore, it is common to produce storyboards in advance, penalizing users customization. The lack of customization is more and more critical, as the number of videos is increasing day after day, users have different demands and might access the Web with several different networking and device technologies. In this paper we propose STIMO, a summarization technique designed to produce on-the-fly video storyboards. STIMO produces still and moving storyboards and allows advanced users customization (e.g., users can select the storyboard length and the maximum time they are willing to wait to get the storyboard). STIMO is based on a fast clustering algorithm that selects the most representative video contents using HSV frame color distribution. Experimental results show that STIMO produces storyboards with good quality and in a time that makes on-the-fly usage possible.

2009 - An Efficient Algorithm for Planted Composit Motif Extraction [Relazione in Atti di Convegno]
Federico, M.; Valente, Paolo; Leoncini, Mauro; Montangero, Manuela; Cavicchioli, R.
abstract

In this paper we present an algorithm for the problem of planted structured motif extraction from a set of sequences. This problem is strictly related to the structured motif extraction problem, which has many important applications in molecular biology. We propose an algorithm that uses a simple two-stage approach: first it extracts simple motifs, then the simple motifs are combined in order to extract structured motifs. We compare our algorithm with existing algorithms whose code is available, and which are based on more complex approaches. Our experiments show that, even if in general the problem is NP-hard, our algorithm is able to handle complex instances of the problem in a reasonable amount of time.

2009 - Incentive Mechanisms in Mobile Music Distribution [Capitolo/Saggio]
Furini, Marco; Montangero, Manuela
abstract

In this paper we analyze the current mobile music market anf then we outline a possible multi-channel distribution strategy along with an incentive mechanism that stimulates cooperation in a mobile environment. We evalutate the multi-channel strategy and we give an overview of related works in the area of content distribution.

2009 - K-Boost: a Scalable Algorithm for High-Quality Clustering of Microarray Gene Expression Data [Articolo su rivista]
Geraci, F; Leoncini, Mauro; Montangero, Manuela; Pellegrini, M; Renda, M. E.
abstract

In this paper we propose K-Boost, a novel clustering algorithm basedon a combination of the Furthest-Point-First (FPF) heuristic for solving themetric k-center problem, a {\em stability-based} method for determining thenumber of clusters, and a k-means-like cluster refinement. Experiments showthat \textit{K-Boost} exhibits a good quality/running time tradeoff that makesit ideal for large data sets, with quality measured by several internal andexternal criteria.

2008 - On Using Clustering Algorithms to Produce Video Abstracts for the Web Scenario [Relazione in Atti di Convegno]
Furini, Marco; F., Geraci; Montangero, Manuela; M., Pellegrini
abstract

A tool to provide an idea of the content of a given video is becoming a need in the current Web scenario, where the presence of videos is increasing day after day. Dynamic summarization techniques can be used to this aim as they set up a video abstract, by selecting and sequencing short video clips extracted from the original video. Needless to say, the selection process is critical. In this paper we focus our attention on clustering algorithms to provide such selection and we investigate the effects of their employment in the web scenario. Clustering algorithms are very effecting in producing static video summary, but few works consider them for video abstract production. For this reason, we set up an experimental scenario where we investigate their performance considering different categories of video, different abstract lengths and different low-level video analysis. Results show that clustering techniques can be useful only for some categories of videos and only if the selection process is based on video scene characteristics. Furthermore, the investigation also shows that to provide a customized service (user can freely decide the abstract time length), only fast clustering algorithm should be used.

2008 - The Impact of Incentive Mechanisms in Multi-Channel Mobile Music Distribution [Articolo su rivista]
Furini, Marco; Montangero, Manuela
abstract

Record labels and telecoms are using the pervasiveness of mobile technologies to create a mobile music market, where customers can have their preferred music at any time and in any place. The idea is to replicate the successful strategy of the Internet-based music market into the mobile scenario. In this paper we first analyze the current mobile music market and we show that this strategy leads to several problems (e.g., excessive download time, cost and protection). As a second contribution, we propose and analyze a multi-channel distribution strategy, where customers can cooperate to music distribution. The approach is based on the cellphone network, the free-of-charge communication technologies provided by cellphones, and on an incentive mechanism that financially compensates users for their cooperation in music distribution. The approach evaluation shows that the employment of an effective incentive mechanism can mitigate the problems of the current mobile music scenario, as it provides benefits to customers, cellphone network providers and music stores.

2007 - FPF-SB: A SCALABLE ALGORITHM FOR MICROARRAY GENE EXPRESSION DATA CLUSTERING [Relazione in Atti di Convegno]
Geraci, F; Leoncini, Mauro; Montangero, Manuela; Pellegrini, M; Renda, M. E.
abstract

Efficient and effective analysis of large datasets from microarraygene expression data is one of the keys to time-critical personalizedmedicine. The issue we address here is the scalability of the dataprocessing software for clustering gene expression data into groupswith homogeneous expression profile. In this paper we propose FPFSB,a novel clustering algorithm based on a combination of theFurthest-Point-First (FPF) heuristic for solving the k-center problemand a stability-based method for determining the number of clustersk. Our algorithm improves the state of the art: it is scalable to largedatasets without sacrificing output quality.

2007 - VISTO: VIsual STOryboard for Web Video Browsing [Relazione in Atti di Convegno]
Furini, Marco; F., Geraci; Montangero, Manuela; M., Pellegrini
abstract

Web video browsing is rapidly becoming a very popular activity in the Web scenario, causing the production of a concise video content representation a real need. Currently, static video summary techniques can be used to this aim. Unfortunately, they require long processing time and hence all the summaries are produced in advance without any users customization. With an increasing number of videos and with the large users heterogeneousness, this is a burden. In this paper we propose VISTO, a summarization technique that produces customized on-the-fly video storyboards. The mechanism uses a fast clustering algorithm that selects the most representative frames using their HSV color distribution and allows users to select the storyboard length and the processing time. An objective and subjective evaluation shows that the storyboards are produced with good quality and in a time that allows on-the-fly usage.

2006 - Distributed Algorithm for a Color Assignment on Asynchronous Rings [Relazione in Atti di Convegno]
G., DE MARCO; Leoncini, Mauro; Montangero, Manuela
abstract

We study a version of the beta-assignment problem (Chang and Lee, 1988) on asynchronous rings: consider a set of items and a set of m colors, where each item is associated to one color. Consider also n computational agents connected by an asynchronous ring. Each agent holds a subset of the items, where initially different agents might hold items associated to the same color. We analyze the problem of distributively assigning colors to agents in such a way that (a) each color is assigned to one agent and (b) the number of different colors assigned to each agent is minimum. Since any color assignment requires that the items be distributed according to it (e.g. all items of the same color are to be held by only one agent), we define the cost of a color assignment as the amount of items that need to be moved, given an initial allocation. We first show that any distributed algorithm for this problem on the ring requires a communication complexity of Omega(n middot m) and then we exhibit a polynomial time distributed algorithm with message complexity matching the bound, that determines a color assignment with cost at most (2 + eps) times the optimal cost, for any 0 < eps < 1.

2006 - Efficient automatic simulation of parallel computation on networks of workstations [Articolo su rivista]
C., Kaklamanis; D., Krizanc; Montangero, Manuela; P., Persiano
abstract

Andrews et al. [Automatic method for hiding latency in high bandwidth networks, in: Proceedings of the ACM Symposium on Theory of Computing, 1996, pp. 257-265; Improved methods for hiding latency in high bandwidth networks, in: Proceedings of the Eighth Annual ACM Symposium on Parallel Algorithms and Architectures, 1996, pp. 52-61] introduced a number of techniques for automatically hiding latency when performing simulations of networks with unit delay links on networks with arbitrary unequal delay links. In their work, they assume that processors of the host network are identical in computational power to those of the guest network being simulated. They further assume that the links of the host are able to pipeline messages, i.e., they are able to deliver P packets in time O(P + d) where d is the delay on the link. In this paper we examine the effect of eliminating one or both of these assumptions. In particular, we provide an efficient simulation of a linear array of homogeneous processors connected by unit-delay links on a linear array of heterogeneous processors connected by links with arbitrary delay. We show that the slowdown achieved by our simulation is optimal. We then consider the case of simulating cliques by cliques; i.e., a clique of heterogeneous processors with arbitrary delay links is used to simulate a clique of homogeneous processors with unit delay links. We reduce the slowdown from the obvious bound of the maximum delay link to the average of the link delays. In the case of the linear array we consider both links with and without pipelining. For the clique simulation the links are not assumed to support pipelining. The main motivation of our results (as was the case with Andrews et al.) is to mitigate the degradation of performance when executing parallel programs designed for different architectures on a network of workstations (NOW). In such a setting it is unlikely that the links provided by the NOW will support pipelining and it is quite probable the processors will be heterogeneous. Combining our result on clique simulation with well-known techniques for simulating shared memory PRAMs on distributed memory machines provides an effective automatic compilation of a PRAM algorithm on a NOW.

2006 - The Use of Incentive Mechanisms in Multi-Channel Mobile Music Distribution [Relazione in Atti di Convegno]
Furini, Marco; Montangero, Manuela
abstract

The music industry is planning to perform a significant shift toward the digital world by partnering cellphone network operators to build a mobile music market. In this paper we analyze the mobile music distribution strategy focusing on: the communication infrastructure, the pricing strategy and the copyright protection. Results of our analysis show that the strategy may be questioned and hence we propose a multi-channel distribution approach that makes use of both the cellphone network and the free-of-charge communication technologies provided in cellphones. Our multi-channel distribution strategy is coupled with an incentive mechanism that stimulates customers cooperation in the mobile scenario. An evaluation of our approach shows that all the entities involved in the mobile music distribution (customers, cellphone network providers and music stores) can benefit from using a multi-channel distribution approach.

2005 - Station Placement in Networks [Articolo su rivista]
C., Galdi; C., Kaklamanis; Montangero, Manuela; P., Persiano
abstract

In this paper we study the Station Placement problem on directed graphs, a problem that has applications to efficient multicasting in circuit-switched networks. We first argue that the problem on general directed graphs can be efficiently reduced to computing bounded depth Steiner tree on complete weighted directed graphs. Then, we concentrate on the case in which the graph is a directed tree and we give polynomial time algorithms to solve the problem and a natural variant of the problem.

2005 - The plurality problem with three colors and more [Articolo su rivista]
M., Aigner; G., DE MARCO; Montangero, Manuela
abstract

The plurality problem is a game between two participants: Paul and Carole. We are given n balls, each of them is colored with one out of c colors. At any step of the game, Paul chooses two balls and asks whether they are of the same color, whereupon Carole answers yes or no. The game ends when Paul either produces a ball a of the plurality color (meaning that the number of balls colored like a exceeds those of the other colors), or when Paul states that there is no plurality. How many questions L, (n) does Paul have to ask in the worst case? For c = 2, the problem is equivalent to the well-known majority problem which has already been solved (Combinatorica 11 (1991) 383-387). In this paper we show that 3 [n/2]-2 <= L-3 (n) <= [5n/3]-2. Moreover, for any c <= n, we show that surprisingly the naive algorithm for the plurality problem is asymptotically optimal.

2004 - Approximation algorithms for a hierarchically structured bin packing problem [Articolo su rivista]
B., Codenotti; G., DE MARCO; Leoncini, Mauro; Montangero, Manuela; M., Santini
abstract

In this paper we study a variant of the bin packing problem in which the items to be packed are structured as the leaves of a tree. The problem is motivated by document organization and retrieval. We show that the problem is NP-hard and we give approximation algorithms for the general case and for the particular case in which all the items have the same size.

2004 - The Plurality Problem with Three Colors [Relazione in Atti di Convegno]
M., Aigner; G., De Marco; Montangero, Manuela
abstract

The plurality problem with three colors is a game between twoparticipants: Paul and Carol. Suppose we are given $n$ balls colored with three colors. At any step of the game, Paul chooses two balls and asks whether they are of the same color, whereupon Carol answers yes or no. The game ends when Paul either produces a ball $a$ of the plurality color (meaning that the number of balls colored like $a$ exceeds those of the other colors), or when Paul states that there is no plurality. How many questions L(n) does Paul have to ask in the worst case? We show that 3 \lfloor n/2 \rfloor - 2 <= L(n) <= \lfloor 5n/3 \rfloor-2.

2002 - Distributed algorithms for certain assignment problems [Articolo su rivista]
B., Codenotti; G., DE MARCO; Leoncini, Mauro; Montangero, Manuela
abstract

In the last two decades several approaches toindexing problems have appeared in the literature.Such interest on indexing was deeply renovatedby the emergence of WEB technologies and by thesubsequent need of algorithmic tools for indexing,clustering, and/or classifying a very large amountof data. In this paper we consider the problemof classifying a set of documents against a set ofcolors (e.g., keywords or predened categories),and we develop distributed algorithms for its so-lution. In particular, seek efficient algorithmsfor the problem of assigning documents to a setof agents (connected according to, e.g., a ringtopology) in such a way that each agent achievesthe maximum possible specialization, i.e., it holdsdocuments associated with the minimum numberof dierent colors.

2001 - Distributed Algorithms for Certain Assigment Problems [Relazione in Atti di Convegno]
B., Codenotti; G., De Marco; Leoncini, Mauro; Montangero, Manuela
abstract

In the last two decades several approaches to indexing problems have appeared in the literature. Such interest on indexing was deeply renovated by the emergence of WEB technologies and by the subsequent need of algorithmic tools for indexing, clustering, and/or classifying a very large amount of data. In this paper we consider the problem of classifying a set of documents against a set of colors (e.g., keywords or predefined categories), and we develop distributedalgorithms for its solution. In particular, seek efficient algorithms for the problem of assigning documents to a set of agents (connected according to, e.g., a ring topology) in such a way that eachagent achieves the maximum possible specialization, i.e., it holds documents associated with the minimum number of different colors.

2001 - Optimal and Approxiamte Station Placement in Networks (with Application to Multicasting and Space Efficient Traversals) [Relazione in Atti di Convegno]
C., Galdi; C., Kaklamanis; Montangero, Manuela; P., Persiano
abstract

In this paper we study the k-station placement problem (k-SP problem for short) on graphs. This problem has application toefficient multicasting in circuit-switched networks and to spaceefficient traversals. We show that the problem is NP-complete evenfor 3-stage graphs and give an approximation algorithm with logarithmic approximation ratio. Moreover we show that the problem can be solved in polynomial time for trees.We also present algorithms for a generalized version and variants of the k-SP problem.

2000 - Efficient Automatic Simulation of Parallel Algorithms on Network of Workstations [Relazione in Atti di Convegno]
C., Kaklamanis; D., Krizanc; Montangero, Manuela; P., Persiano
abstract

Andrews introduced a number of techniques for automaticallyhiding latency when performing simulations of networks with unit delay links on networks with arbitrary unequal delay links. In their work, they assume that processors of the host network are identicalin computational power to those of the guest network being simulated.They further assume that the links of the host are able to pipelinemessages, i.e., they are able to deliver P packets in time O(P+ d) where d is the delay on the link. In this paper we examine the effect of eliminating one or both of theseassumptions. In particular, we provide an efficient simulation of a linear array of homogenous processors with unit delay links on a linear array of hetrogenous processors with arbitrary delay links and we show that the slowdown achieved by our simulation is optimal. We also consider the case of simulating a clique of homogenous processors with unit delay links on a clique of hetrogenous processors with arbitrary delay reducing the slowdown from the obvious bound of the maximum delay link to the average of the link delays. For the case of the linear array we consider both links with and without pipelining. For the clique simulation the links are not assumed to support pipelining.The main motivation of our results is to mitigate the degradation of performance when executing parallel programs designed for different architectures on a Network of Workstations (NOW). In such a setting is unlikely that the links provided by the NOW will support pipelining and it is quite probable the processors will be heterogenous. Combining our result on clique simulation with well-known techniques for simulating shared memory PRAMs on distributed memory machines provides an effective automatic compilation of a PRAM algorithm on a NOW.

1998 - On updating suffix tree labels [Articolo su rivista]
P., Ferragina; R., Grossi; Montangero, Manuela
abstract

We investigate the problem of maintaining the arc labels in the suffixtree data structure when it undergoes string insertions and deletions. In current literature, this problem is solved either by a simple accounting strategy to obtain amortized bounds or by a periodical suffix tree reconstruction to obtain worst-case bounds (according to the global rebuilding technique). Unfortunately, the former approach is simple and space-efficient at the cost of attaining amortized bounds for the single update; the latter is space-consuming in practice because it needs to keep two extra suffix tree copies. In this paper, we obtain a simple real-time algorithm that achieves worst-case bounds and only requires small additional space (i.e., a bi-directional pointer per suffix tree label). We analyze it by introducing a combinatorial coloring problem on the suffix tree arcs.

1997 - A Note on Updating Suffix Tree Labels [Relazione in Atti di Convegno]
P., Ferragina; R., Grossi; Montangero, Manuela
abstract

We investigate the problem of maintaining the arc labels in the suffixtree data structure when it undergoes string insertions and deletions. In current literature, this problem is solved either by a simple accounting strategy to obtain amortized bounds or by a periodical suffix tree reconstruction to obtain worst-case bounds (according to a global rebuilding technique). Unfortunately, the former approach is simple and space-efficient at the cost of attaining amortized bounds for the single update; the latter is space-consuming in practice because it needs to keep two extra suffix tree copies. In this paper, we obtain a simple real-time algorithm that achieves worst-case bounds and only requires small additional space (i.e., a bi-directional pointer per suffix tree label). We analyze it by introducing a combinatorial coloring problem on the suffix tree arcs.

Università degli studi di Modena e Reggio Emilia

Pubblicazioni