Pasar al contenido principal

MODELOS Y METODOS COMPUTACIONALES PARA DATOS MASIVOS ESTRUCTURADOS

TIN2013-46181-C2-1-R

•
Nombre agencia financiadora Ministerio de Economía y Competitividad
Acrónimo agencia financiadora MINECO
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos I+D+i Retos de Investigación
Año convocatoria 2013
Plan Estatal 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Unidad de gestión Secretaría de Estado de Educación, Formación Profesional y Universidades
Centro beneficiario UNIVERSITAT POLITECNICA DE CATALUNYA
Identificador persistente http://dx.doi.org/10.13039/501100003329

Resultados relacionados

Resultados totales (Incluyendo duplicados): 22
Encontrada(s) 1 página(s)

UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

The complexity of measuring power in generalized opinion leader decision models

  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Serna Iglesias, María José|||0000-0001-9729-8648
We analyze the computational complexity of the power measure in models of collective decision: the generalized opinion leader-follower model and the oblivious and non-oblivious infuence models. We show that computing the power measure is #P-hard in all these models, and provide two subfamilies in which the power measure can be computed in polynomial time., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Encoding process discovery problems in SMT

  • Sole Simò, Marc
  • Carmona Vargas, Josep|||0000-0001-9656-254X
Information systems, which are responsible for driving many processes in our lives (health care, the web, municipalities, commerce and business, among others), store information in the form of logs which is often left unused. Process mining, a discipline in between data mining and software engineering, proposes tailored algorithms to exploit the information stored in a log, in order to reason about the processes underlying an information system. A key challenge in process mining is discovery: Given a log, derive a formal process model that can be used afterward for a formal analysis. In this paper, we provide a general approach based on satisfiability modulo theories (SMT) as a solution for this challenging problem. By encoding the problem into the logical/arithmetic domains and using modern SMT engines, it is shown how two separate families of process models can be discovered. The theory of this paper is accompanied with a tool, and experimental results witness the significance of this novel view of the process discovery problem., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Dimension and codimension of simple games

  • Kurz, Sascha
  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Olsen, Martin
  • Serna Iglesias, María José|||0000-0001-9729-8648
This paper studies the complexity of computing a representation of a simple game as the intersection (union) of weighted majority games, as well as, the dimension or the codimension. We also present some examples with linear dimension and exponential codimension with respect to the number of players., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Forms of representation for simple games: sizes, conversions and equivalences

  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Riquelme Csori, Fabian Rolando|||0000-0003-4491-0148
  • Serna Iglesias, María José|||0000-0001-9729-8648
Simple games are cooperative games in which the benefit that a coalition may have is always binary, i.e., a coalition may either win or loose. This paper surveys different forms of representation of simple games, and those for some of their subfamilies like regular games and weighted games. We analyze the forms of representations that have been proposed in the literature based on different data structures for sets of sets. We provide bounds on the computational resources needed to transform a game from one form of representation to another one. This includes the study of the problem of enumerating the fundamental families of coalitions of a simple game. In particular we prove that several changes of representation that require exponential time can be solved with polynomial-delay and highlight some open problems., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Firefighting as a strategic game

  • Álvarez Faura, M. del Carme|||0000-0003-2352-0546
  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
  • Molter, Hendrik
The Firefighter Problem was proposed in 1995 as a deterministic discrete-time model for the spread and containment of a fire. The problem is defined on an undirected finite graph G = (V, E), where fire breaks out initially at f nodes. In each subsequent time-step, two actions occur: a certain number b of firefighters are placed on nonburning nodes, permanently protecting them from the fire, then the fire spreads to all nondefended neighbors of the nodes on fire. Because the graph is finite, at some point each node is either on fire or saved, and thus the fire cannot spread further. One of the objectives for the problem is to place the firefighters in such a way that the number of saved nodes is maximized. The applications of the Firefighter Problem reach from real fires to the spreading of diseases and the containment of floods. Furthermore, it can be used to model the spread of computer viruses or viral marketing in communication networks. Most research on the problem considers the case in which the fire starts in a single place (i.e., f = 1), and in which the budget of available firefighters per time-step is one (i.e., b = 1). So does the work in this study. This configuration already leads to hard problems and, even in this case, the problem is known to be NP-hard. In this work, we study the problem from a game-theoretical perspective. We introduce a strategic game model for the Firefighter Problem to tackle its complexity from a different angle. We refer to it as the Firefighter Game. Such a game-based context seems very appropriate when applied to large networks where entities may act and make decisions based on their own interests, without global coordination. At every time-step of the game, a player decides whether to place a new firefighter in a nonburning node of the graph. If so, he must decide where to place it. By placing it, the player is indirectly deciding which nodes to protect at that time-step. We define different utility functions in order to model selfish and nonselfish scenarios, which lead to equivalent games. We show that the Price of Anarchy (PoA) is linear for a particular family of graphs, but it is at most two for trees. We also analyze the quality of the equilibria when coalitions among players are allowed. It turns out that it is possible to compute an equilibrium in polynomial time, even for constant-size coalitions. This yields to a polynomial time approximation algorithm for the problem and its approximation ratio equals the PoA of the corresponding game. We show that for some specific topologies, the PoA is constant when constant-size coalitions are considered., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Quad-kd trees: A general framework for kd trees and quad trees

  • Bereczky, Nikolett
  • Duch Brown, Amalia|||0000-0003-4371-1286
  • Németh, Krisztián
  • Roura Ferret, Salvador|||0000-0003-4394-5939
We introduce the quad-kd tree: a general purpose and hierarchical data structure for the storage of multidimensional points. Quad-kd trees include point quad trees and kd trees as particular cases and therefore they could constitute a general framework for the study of fundamental properties of trees similar to them. Besides, quad-kd trees can be tuned by means of insertion heuristics and bucketing techniques to obtain trade-offs between their costs in time and space. We propose three such heuristics and we show analytically and experimentally their competitive performance. Our analytical results back the experimental outcomes and suggest that the quad-kd tree is a flexible data structure that can be tailored to the resource requirements of a given application., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Centrality measure in social networks based on linear threshold model

  • Riquelme Csori, Fabian Rolando|||0000-0003-4491-0148
  • Gonzalez Cantergiani, Pablo
  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Serna Iglesias, María José|||0000-0001-9729-8648
Centrality and influence spread are two of the most studied concepts in social network analysis. In recent years, centrality measures have attracted the attention of many researchers, generating a large and varied number of new studies about social network analysis and its applications. However, as far as we know, traditional models of influence spread have not yet been exhaustively used to define centrality measures according to the influence criteria. Most of the considered work in this topic is based on the independent cascade model. In this paper we explore the possibilities of the linear threshold model for the definition of centrality measures to be used on weighted and labeled social networks. We propose a new centrality measure to rank the users of the network, the Linear Threshold Rank (LTR), and a centralization measure to determine to what extent the entire network has a centralized structure, the Linear Threshold Centralization (LTC). We appraise the viability of the approach through several case studies. We consider four different social networks to compare our new measures with two centrality measures based on relevance criteria and another centrality measure based on the independent cascade model. Our results show that our measures are useful for ranking actors and networks in a distinguishable way., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Cooperation through social influence

  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Riquelme Csori, Fabian Rolando|||0000-0003-4491-0148
  • Serna Iglesias, María José|||0000-0001-9729-8648
We consider a simple and altruistic multiagent system in which the agents are eager to perform a collective task but where their real engagement depends on the willingness to perform the task of other influential agents. We model this scenario by an influence game, a cooperative simple game in which a team (or coalition) of players succeeds if it is able to convince enough agents to participate in the task (to vote in favor of a decision). We take the linear threshold model as the influence model. We show first the expressiveness of influence games showing that they capture the class of simple games. Then we characterize the computational complexity of various problems on influence games, including measures (length and width), values (Shapley-Shubik and Banzhaf) and properties (of teams and players). Finally, we analyze those problems for some particular extremal cases, with respect to the propagation of influence, showing tighter complexity characterizations., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

The social cost of congestion games by imposing variable delays

  • Díaz Cort, Josep|||0000-0003-4422-0067
  • Giotis, Ioannis
  • Kirousis, Lefteris
  • Mourtos, Ioannis
  • Serna Iglesias, María José|||0000-0001-9729-8648
© <year>. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, In this study, we describe a new coordination mechanism for non-atomic congestion games that leads to a (selfish) social cost which is arbitrarily close to the non-selfish optimal. This mechanism incurs no additional cost, in contrast to tolls that typically differ from the social cost as expressed in terms of delays., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Comparing MapReduce and pipeline implementations for counting triangles

  • Pasarella Sánchez, Ana Edelmira|||0000-0001-8315-4977
  • Vidal, Maria-Esther
  • Zoltan Torres, Ana Cristina
A common method to define a parallel solution for a computational problem consists in finding a way to use the Divide and Conquer paradigm in order to have processors acting on its own data and scheduled in a parallel fashion. MapReduce is a programming model that follows this paradigm, and allows for the definition of efficient solutions by both decomposing a problem into steps on subsets of the input data and combining the results of each step to produce final results. Albeit used for the implementation of a wide variety of computational problems, MapReduce performance can be negatively affected whenever the replication factor grows or the size of the input is larger than the resources available at each processor. In this paper we show an alternative approach to implement the Divide and Conquer paradigm, named dynamic pipeline. The main features of dynamic pipelines are illustrated on a parallel implementation of the well-known problem of counting triangles in a graph. This problem is especially interesting either when the input graph does not fit in memory or is dynamically generated. To evaluate the properties of pipeline, a dynamic pipeline of processes and an ad-hoc version of MapReduce are implemented in the language Go, exploiting its ability to deal with channels and spawned processes. An empirical evaluation is conducted on graphs of different topologies, sizes, and densities. Observed results suggest that dynamic pipelines allows for an efficient implementation of the problem of counting triangles in a graph, particularly, in dense and large graphs, drastically reducing the execution time with respect to the MapReduce implementation., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

RTL synthesis: From logic synthesis to automatic pipelining

  • Cortadella, Jordi|||0000-0001-8114-250X
  • Galcerán Oms, Marc
  • Kishinevsky, Mike
  • Sapatnekar, Sachin S.
Design automation has been one of the main propellers of the semiconductor industry with logic synthesis being one of the core technologies in this field. This article reviews the evolution of logic synthesis until the advent of techniques for automatic pipelining based on elastic timing, either synchronous or asynchronous. The emergence of these techniques can enable a productive interaction with tools that can do microarchitectural exploration of complex designs., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Comparing MapReduce and pipeline implementations for counting triangles

  • Pasarella Sánchez, Ana Edelmira
  • Vidal, Maria-Esther
  • Zoltan Torres, Ana Cristina
A common method to define a parallel solution for a computational problem consists in finding a way to use the Divide and Conquer paradigm in order to have processors acting on its own data and scheduled in a parallel fashion. MapReduce is a programming model that follows this paradigm, and allows for the definition of efficient solutions by both decomposing a problem into steps on subsets of the input data and combining the results of each step to produce final results. Albeit used for the implementation of a wide variety of computational problems, MapReduce performance can be negatively affected whenever the replication factor grows or the size of the input is larger than the resources available at each processor. In this paper we show an alternative approach to implement the Divide and Conquer paradigm, named dynamic pipeline. The main features of dynamic pipelines are illustrated on a parallel implementation of the well-known problem of counting triangles in a graph. This problem is especially interesting either when the input graph does not fit in memory or is dynamically generated. To evaluate the properties of pipeline, a dynamic pipeline of processes and an ad-hoc version of MapReduce are implemented in the language Go, exploiting its ability to deal with channels and spawned processes. An empirical evaluation is conducted on graphs of different topologies, sizes, and densities. Observed results suggest that dynamic pipelines allows for an efficient implementation of the problem of counting triangles in a graph, particularly, in dense and large graphs, drastically reducing the execution time with respect to the MapReduce implementation., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Firefighting as a strategic game

  • Álvarez Faura, M. del Carme
  • Blesa Aguilera, Maria Josep
  • Molter, Hendrik
The Firefighter Problem was proposed in 1995 as a deterministic discrete-time model for the spread and containment of a fire. The problem is defined on an undirected finite graph G = (V, E), where fire breaks out initially at f nodes. In each subsequent time-step, two actions occur: a certain number b of firefighters are placed on nonburning nodes, permanently protecting them from the fire, then the fire spreads to all nondefended neighbors of the nodes on fire. Because the graph is finite, at some point each node is either on fire or saved, and thus the fire cannot spread further. One of the objectives for the problem is to place the firefighters in such a way that the number of saved nodes is maximized. The applications of the Firefighter Problem reach from real fires to the spreading of diseases and the containment of floods. Furthermore, it can be used to model the spread of computer viruses or viral marketing in communication networks. Most research on the problem considers the case in which the fire starts in a single place (i.e., f = 1), and in which the budget of available firefighters per time-step is one (i.e., b = 1). So does the work in this study. This configuration already leads to hard problems and, even in this case, the problem is known to be NP-hard. In this work, we study the problem from a game-theoretical perspective. We introduce a strategic game model for the Firefighter Problem to tackle its complexity from a different angle. We refer to it as the Firefighter Game. Such a game-based context seems very appropriate when applied to large networks where entities may act and make decisions based on their own interests, without global coordination. At every time-step of the game, a player decides whether to place a new firefighter in a nonburning node of the graph. If so, he must decide where to place it. By placing it, the player is indirectly deciding which nodes to protect at that time-step. We define different utility functions in order to model selfish and nonselfish scenarios, which lead to equivalent games. We show that the Price of Anarchy (PoA) is linear for a particular family of graphs, but it is at most two for trees. We also analyze the quality of the equilibria when coalitions among players are allowed. It turns out that it is possible to compute an equilibrium in polynomial time, even for constant-size coalitions. This yields to a polynomial time approximation algorithm for the problem and its approximation ratio equals the PoA of the corresponding game. We show that for some specific topologies, the PoA is constant when constant-size coalitions are considered., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Encoding process discovery problems in SMT

  • Sole Simò, Marc
  • Carmona Vargas, Josep
Information systems, which are responsible for driving many processes in our lives (health care, the web, municipalities, commerce and business, among others), store information in the form of logs which is often left unused. Process mining, a discipline in between data mining and software engineering, proposes tailored algorithms to exploit the information stored in a log, in order to reason about the processes underlying an information system. A key challenge in process mining is discovery: Given a log, derive a formal process model that can be used afterward for a formal analysis. In this paper, we provide a general approach based on satisfiability modulo theories (SMT) as a solution for this challenging problem. By encoding the problem into the logical/arithmetic domains and using modern SMT engines, it is shown how two separate families of process models can be discovered. The theory of this paper is accompanied with a tool, and experimental results witness the significance of this novel view of the process discovery problem., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Forms of representation for simple games: sizes, conversions and equivalences

  • Molinero Albareda, Xavier
  • Riquelme Csori, Fabian Rolando
  • Serna Iglesias, María José
Simple games are cooperative games in which the benefit that a coalition may have is always binary, i.e., a coalition may either win or loose. This paper surveys different forms of representation of simple games, and those for some of their subfamilies like regular games and weighted games. We analyze the forms of representations that have been proposed in the literature based on different data structures for sets of sets. We provide bounds on the computational resources needed to transform a game from one form of representation to another one. This includes the study of the problem of enumerating the fundamental families of coalitions of a simple game. In particular we prove that several changes of representation that require exponential time can be solved with polynomial-delay and highlight some open problems., Peer Reviewed, Postprint (author’s final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Dimension and codimension of simple games

  • Kurz, Sascha
  • Molinero Albareda, Xavier
  • Olsen, Martin
  • Serna Iglesias, María José
This paper studies the complexity of computing a representation of a simple game as the intersection (union) of weighted majority games, as well as, the dimension or the codimension. We also present some examples with linear dimension and exponential codimension with respect to the number of players., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Centrality measure in social networks based on linear threshold model

  • Riquelme Csori, Fabian Rolando
  • Gonzalez Cantergiani, Pablo
  • Molinero Albareda, Xavier
  • Serna Iglesias, María José
Centrality and influence spread are two of the most studied concepts in social network analysis. In recent years, centrality measures have attracted the attention of many researchers, generating a large and varied number of new studies about social network analysis and its applications. However, as far as we know, traditional models of influence spread have not yet been exhaustively used to define centrality measures according to the influence criteria. Most of the considered work in this topic is based on the independent cascade model. In this paper we explore the possibilities of the linear threshold model for the definition of centrality measures to be used on weighted and labeled social networks. We propose a new centrality measure to rank the users of the network, the Linear Threshold Rank (LTR), and a centralization measure to determine to what extent the entire network has a centralized structure, the Linear Threshold Centralization (LTC). We appraise the viability of the approach through several case studies. We consider four different social networks to compare our new measures with two centrality measures based on relevance criteria and another centrality measure based on the independent cascade model. Our results show that our measures are useful for ranking actors and networks in a distinguishable way., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Cooperation through social influence

  • Molinero Albareda, Xavier
  • Riquelme Csori, Fabian Rolando
  • Serna Iglesias, María José
We consider a simple and altruistic multiagent system in which the agents are eager to perform a collective task but where their real engagement depends on the willingness to perform the task of other influential agents. We model this scenario by an influence game, a cooperative simple game in which a team (or coalition) of players succeeds if it is able to convince enough agents to participate in the task (to vote in favor of a decision). We take the linear threshold model as the influence model. We show first the expressiveness of influence games showing that they capture the class of simple games. Then we characterize the computational complexity of various problems on influence games, including measures (length and width), values (Shapley-Shubik and Banzhaf) and properties (of teams and players). Finally, we analyze those problems for some particular extremal cases, with respect to the propagation of influence, showing tighter complexity characterizations., Peer Reviewed, Postprint (author’s final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

RTL synthesis: From logic synthesis to automatic pipelining

  • Cortadella, Jordi
  • Galcerán Oms, Marc
  • Kishinevsky, Mike
  • Sapatnekar, Sachin S.
Design automation has been one of the main propellers of the semiconductor industry with logic synthesis being one of the core technologies in this field. This article reviews the evolution of logic synthesis until the advent of techniques for automatic pipelining based on elastic timing, either synchronous or asynchronous. The emergence of these techniques can enable a productive interaction with tools that can do microarchitectural exploration of complex designs., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Quad-kd trees: A general framework for kd trees and quad trees

  • Bereczky, Nikolett
  • Duch Brown, Amalia
  • Németh, Krisztián
  • Roura Ferret, Salvador
We introduce the quad-kd tree: a general purpose and hierarchical data structure for the storage of multidimensional points. Quad-kd trees include point quad trees and kd trees as particular cases and therefore they could constitute a general framework for the study of fundamental properties of trees similar to them. Besides, quad-kd trees can be tuned by means of insertion heuristics and bucketing techniques to obtain trade-offs between their costs in time and space. We propose three such heuristics and we show analytically and experimentally their competitive performance. Our analytical results back the experimental outcomes and suggest that the quad-kd tree is a flexible data structure that can be tailored to the resource requirements of a given application., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The social cost of congestion games by imposing variable delays

  • Díaz Cort, Josep
  • Giotis, Ioannis
  • Kirousis, Lefteris
  • Mourtos, Ioannis
  • Serna Iglesias, María José
© <year>. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, In this study, we describe a new coordination mechanism for non-atomic congestion games that leads to a (selfish) social cost which is arbitrarily close to the non-selfish optimal. This mechanism incurs no additional cost, in contrast to tolls that typically differ from the social cost as expressed in terms of delays., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The complexity of measuring power in generalized opinion leader decision models

  • Molinero Albareda, Xavier
  • Serna Iglesias, María José
We analyze the computational complexity of the power measure in models of collective decision: the generalized opinion leader-follower model and the oblivious and non-oblivious infuence models. We show that computing the power measure is #P-hard in all these models, and provide two subfamilies in which the power measure can be computed in polynomial time., Peer Reviewed, Postprint (author's final draft)