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): 54
Encontrada(s) 1 página(s)

Repositorio Digital de la UPF
Publicación Contribución de congreso (ConferenceOutput)

A datalog framework for modeling relationship-based access control policies

  • Pasarella Sánchez, Ana Edelmira
  • Lobo, Jorge
Comunicació presentada al SACMAT'17. 22nd ACM Symposium on Access Control Models and Technologies, celebrat els dies 21 a 23 de juny de 2017 a Indianapolis, EUA., Relationships like friendship to limit access to resources have been part of social network applications since their beginnings. Describing access control policies in terms of relationships is not particular to social networks and it arises naturally in many situations. Hence, we have recently seen several proposals formalizing different Relationship-based Access Control (ReBAC) models. In this paper, we introduce a class of Datalog programs suitable for modeling ReBAC and argue that this class of programs, that we called ReBAC Datalog policies, provides a very general framework to specify and implement ReBAC policies. To support our claim, we first formalize the merging of two recent proposals for modeling ReBAC, one based on hybrid logic and the other one based on path regular expressions. We present extensions to handle negative authorizations and temporal policies. We describe mechanism for policy analysis, and then discuss the feasibility of using Datalog-based systems as implementations., Edelmira Pasarella was partially supported by the Spanish Ministry for Economy and Competitiveness (MINECO) and the European Union (FEDER funds) under Grant Ref.: TIN2013-46181-C2-1-R COMMAS. Jorge Lobo was partially supported by the Secretaria d’Universitats i Recerca de la Generalitat de Catalunya, the Maria de Maeztu Units of Excellence Programme and the Spanish Ministry for Economy and Competitiveness (MINECO) under Grant Ref.: TIN2016-81032-P.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Análisis de la evolución de un curso: productividad y desigualdad

  • Blesa, Maria J.
  • Duch, Amalia
  • Gabarro, Joaquim
  • Petit, Jordi
  • Serna, Maria
Este trabajo analiza cuantitativamente las diferentes medidas adoptadas en la evaluación continua del curso de Programación-1 de la Facultat d’Informàtica de Barcelona de la Universitat Politècnica de Catalunya desde 2010, año en que comienza la impartición del nuevo grado en Ingeniería Informática. Se analiza el efecto de dichas medidas sobre las categorías de calificaciones obtenidas por los estudiantes en relación al incremento de carga docente del profesorado. El estudio de la evolución de estos dos valores a lo largo del tiempo usa una aproximación de coste-beneficio marginal, clásica en ámbitos de economía. Usando herramientas provenientes de las ciencias sociales, este estudio se complementa con un análisis preliminar de desigualdad. Ambos enfoques pretenden introducir nuevas técnicas para el análisis objetivo del impacto de medidas docentes.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

De Menos a Distinto: Estudio de la Implantación de R en las Asignaturas del Grado de Estadística

  • Baixeries, Jaume
  • Fairén, Marta
  • Gabarro, Joaquim
  • Pasarella, Edelmira
  • Alcañiz, Manuela
Los cursos de informática en las titulaciones que no son informáticas siempre pecan de falta de motivación y buenos resultados de los estudiantes. El argumento del estudiante acostumbra a ser: ¿A mí para que me servirá todo esto?, y esto se acusa aun más cuando al estudiante le cuestan este tipo de asignaturas. En este artículo analizamos los primeros cursos de informática en el Grado de Estadística de la Universitat de Barcelona (UB) y la Universitat Politècnica de Catalunya (UPC), grado conjunto de las dos universidades. En estos cursos se intentó inicialmente reducir la complejidad de los contenidos para promover mejores resultados pero no funcionó como se esperaba, así que cambiamos de táctica y decidimos modificar las herramientas para adaptarlas a aquellas que los estudiantes entienden que están más cerca de sus intereses. En este caso concreto se decidió usar el lenguaje de programación R, un lenguaje ampliamente utilizado por los estadísticos, para explicarles los conceptos básicos de la programación. Así pues, modificamos nuestra estrategia pasando de menos (contenidos más simples) a distinto (contenidos más elaborados y no triviales adaptados a sus expectativas).
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

The alignment of formal, structured and unstructured process descriptions

  • Carmona Vargas, Josep|||0000-0001-9656-254X
Nowadays organizations are experimenting a drift on the way processes are managed. On the one hand, formal notations like Petri nets or Business Process Model and Notation (BPMN) enable the unambiguous reasoning and automation of designed processes. This way of eliciting processes by manual design, which stemmed decades ago, will still be an important actor in the future. On the other hand, regulations require organizations to store their process executions in structured representations, so that they are known and can be analyzed. Finally, due to the different nature of stakeholders within an organization (ranging from the most technical members, e.g., developers, to less technical), textual descriptions of processes are also maintained to enable that everyone in the organization understands their processes. In this paper I will describe techniques for facilitating the interconnection between these three process representations. This requires interdisciplinary research to connect several fields: business process management, formal methods, natural language processing and process mining., Peer Reviewed
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 Contribución de congreso (ConferenceOutput)

A hierarchical mathematical model for automatic pipelining and allocation using elastic systems

  • Cortadella, Jordi|||0000-0001-8114-250X
  • Petit Silvestre, Jordi|||0000-0001-8331-8126
The advent of FPGA-based accelerators has encouraged the use of high-level synthesis (HLS) for rapid prototyping and design space exploration. In this context, design optimization at behavioral level becomes a critical task for the delivery of high-quality solutions. Time elasticity opens a new avenue of optimizations that can be applied after HLS and before logic synthesis, proposing new sequential transformations that expand beyond classical retiming and enlarge the register-transfer level (RTL) exploration space. This paper proposes a mathematical model for RTL transformations that exploit elasticity to select the best implementation for each functional unit and add pipeline registers to increase performance. Two simple examples are used to validate the effectiveness and potential benefits of the model., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

MapReduce vs. pipelining counting triangles

  • Pasarella Sánchez, Ana Edelmira|||0000-0001-8315-4977
  • Vidal Serodio, Maria Esther
  • Zoltan Torres, Ana Cristina
In this paper we follow an alternative approach named pipeline, to implement 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 be concrete, we implement a dynamic pipeline of processes and an ad-hoc MapReduce version using the language Go. We explote the ability of Go language to deal with channels and spawned processes. An empirical evaluation is conducted on graphs of different size and density. Observed results suggest that pipeline allows for the implementation of an efficient solution 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 Contribución de congreso (ConferenceOutput)

A datalog framework for modeling relationship-based access control policies

  • Pasarella Sánchez, Ana Edelmira|||0000-0001-8315-4977
  • Lobo, Jorge
SACMAT'17 Best paper, Relationships like friendship to limit access to resources have been part of social network applications since their beginnings. Describing access control policies in terms of relationships is not particular to social networks and it arises naturally in many situations. Hence, we have recently seen several proposals formalizing different Relationship-based Access Control (ReBAC) models. In this paper, we introduce a class of Datalog programs suitable for modeling ReBAC and argue that this class of programs, that we called ReBAC Datalog policies, provides a very general framework to specify and implement ReBAC policies. To support our claim, we first formalize the merging of two recent proposals for modeling ReBAC, one based on hybrid logic and the other one based on path regular expressions. We present extensions to handle negative authorizations and temporal policies. We describe mechanism for policy analysis, and then discuss the feasibility of using Datalog-based systems as implementations., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Comparing MapReduce and pipeline implementations for counting triangles

  • Pasarella Sánchez, Ana Edelmira|||0000-0001-8315-4977
  • Vidal Serodio, Maria Esther
  • Zoltan, Cristina
A generalized method to define the Divide & 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 & Conquer paradigm, named pipeline. The main features of pipeline 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 sizes and densities. Observed results suggest that pipeline allows for the implementation of an efficient solution 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 Contribución de congreso (ConferenceOutput)

Communication requirements for team automata

  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Beek, Maurice ter
  • Hennicker, Rolf
  • Kleijn, Jetty
Compatibility of components is an important issue in the quest for systems of systems that guarantee successful communications, free from message loss and indefinite waiting for inputs. In this paper, we investigate compatibility in the context of systems consisting of reactive components which may communicate through the synchronised execution of common actions. We model such systems in the team automata framework, which does not impose any a priori restrictions on the synchronisation policy followed to combine the components. We identify a family of representative synchronisation types based on the number of sending and receiving components participating in synchronisations. Then, we provide a generic procedure to derive, for each synchronisation type, requirements for receptiveness and for responsiveness of team automata that prevent that outputs are not accepted and inputs are not provided, respectively. Due to the genericity of our approach w.r.t. synchronisation policies, we can capture compatibility notions for various multi-component system models known from the literature., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Estudio, informe, memoria (Report)

Measuring satisfaction in societies with opinion leaders and mediators

  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Riquelme Csori, Fabian Rolando|||0000-0003-4491-0148
  • Serna Iglesias, María José|||0000-0001-9729-8648
An opinion leader-follower model (OLF) is a two-action collective decision-making model for societies, in which three kinds of actors are considered:
UPCommons. Portal del coneixement obert de la UPC
Publicación Estudio, informe, memoria (Report)

A graph semantics for a variant of the ambient calculus more adequate for modeling SOC

  • Mylonakis Pascual, Nicolás|||0000-0002-2535-8573
In this paper we present a graph semantics of a variant of the well known ambient calculus. The main change of our variant is to extract the mobility commands of the original calculus from the ambient topology. Similar to a previous work of ours, we prove that our encoding have good properties. We strongly believe that this variant would allow us to integrate our graph semantics of our mobile calculus with previous work of us in service oriented computing (SOC). Basically, our work on SOC develops a new graph transformation system which we call temporal symbolic graphs. This new graph formalism is used to give semantics to a design language for SOC developed in an european project, but it could also be used in connection with other approaches for modeling or specifying service systems.
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 Contribución de congreso (ConferenceOutput)

Alignment-based trace clustering

  • Chatain, Thomas
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Dongen, Boudewijn F. van
A novel method to cluster event log traces is presented in this paper. In contrast to the approaches in the literature, the clustering approach of this paper assumes an additional input: a process model that describes the current process. The core idea of the algorithm is to use model traces as centroids of the clusters detected, computed from a generalization of the notion of alignment. This way, model explanations of observed behavior are the driving force to compute the clusters, instead of current model agnostic approaches, e.g., which group log traces merely on their vector-space similarity. We believe alignment-based trace clustering provides results more useful for stakeholders. Moreover, in case of log incompleteness, noisy logs or concept drift, they can be more robust for dealing with highly deviating traces. The technique of this paper can be combined with any clustering technique to provide model explanations to the clusters computed. The proposed technique relies on encoding the individual alignment problems into the (pseudo-)Boolean domain, and has been implemented in our tool DarkSider that uses an open-source solver., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Partial match queries in relaxed K-dt trees

  • Duch Brown, Amalia|||0000-0003-4371-1286
  • Lau Laynes-Lozada, Gustavo Salvador
The study of partial match queries on random hierarchical multidimensional data structures dates back to Ph. Flajolet and C. Puech’s 1986 seminal paper on partial match retrieval. It was not until recently that fixed (as opposed to random) partial match queries were studied for random relaxed K-d trees, random standard K-d trees, and random 2-dimensional quad trees. Based on those results it seemed natural to classify the general form of the cost of fixed partial match queries into two families: that of either random hierarchical structures or perfectly balanced structures, as conjectured by Duch, Lau and Martínez (On the Cost of Fixed Partial Queries in K-d trees Algorithmica, 75(4):684–723, 2016). Here we show that the conjecture just mentioned does not hold by introducing relaxed K-dt trees and providing the average-case analysis for random partial match queries as well as some advances on the average-case analysis for fixed partial match queries on them. In fact this cost –for fixed partial match queries– does not follow the conjectured forms., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

A framework for online conformance checking

  • Burattin, Andrea
  • Carmona Vargas, Josep|||0000-0001-9656-254X
Conformance checking – a branch of process mining – focuses on establishing to what extent actual executions of a process are in line with the expected behavior of a reference model. Current conformance checking techniques only allow for a-posteriori analysis: the amount of (non-)conformant behavior is quantified after the completion of the process instance. In this paper we propose a framework for online conformance checking: not only do we quantify (non-)conformant behavior as the execution is running, we also restrict the computation to constant time complexity per event analyzed, thus enabling the online analysis of a stream of events. The framework is instantiated with ideas coming from the theory of regions, and state similarity. An implementation is available in ProM and promising results have been obtained., 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 Contribución de congreso (ConferenceOutput)

Análisis de la evolución de un curso: productividad y desigualdad

  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
  • Duch Brown, Amalia|||0000-0003-4371-1286
  • Gabarró Vallès, Joaquim|||0000-0003-3771-2813
  • Petit Silvestre, Jordi|||0000-0001-8331-8126
  • Serna Iglesias, María José|||0000-0001-9729-8648
Este trabajo analiza cuantitativamente las diferentes medidas adoptadas en la evaluación contínua del curso de Programación-1 de la Facultat d’Informàtica de Barcelona de la Universitat Politècnica de Catalunya desde 2010, año en que comienza la impartición del nuevo grado en Ingeniería Informática. Se analiza el efecto de dichas medidas sobre las categorías de calificaciones obtenidas por los estudiantes en relación al incremento de carga docente del profesorado. El estudio de la evolución de estos dos valores a lo largo del tiempo usa una aproximación de coste-beneficio marginal, clásica en ámbitos de economía. Usando herramientas provenientes de las ciencias sociales, este estudio se complementa con un análisis preliminar de desigualdad. Ambos enfoques pretenden introducir nuevas técnicas para el análisis objetivo del impacto de medidas docentes., This paper analyzes quantitatively the different measures taken in the continuous assessment of the CS1 course at the Facultat d’Informàtica de Barcelona of the Universitat Politècnica de Catalunya since 2010, when the new degree in Informatics Engineering began. The effect of those measures on the marks obtained by the students is analyzed with respect to the increment of the course load for the faculty members. These two values are compared along time through a classical marginal cost-benefit approach. Using tools commonly accepted in the social sciences, this study is complemented with a preliminary analysis of inequality. Both approaches aim at introducing new techniques for an objective analysis on the impact of teaching measures.
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 Contribución de congreso (ConferenceOutput)

Reducing event variability in logs by clustering of word embeddings

  • Sánchez Charles, David
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Muntés Mulero, Victor
  • Solé Simó, Marc|||0000-0001-7056-4600
Several business-to-business and business-to-consumer services are provided as a human-to-human conversation in which the provider representative guides the conversation towards its resolution based on her experience, following internal guidelines. Several attempts to automatize these services are becoming popular, but they are currently limited to procedures and objectives set during design step. Process discovery techniques could provide the necessary mechanisms to monitor event logs derived from textual conversations and expand the capabilities of conversational bots. Still, variability of textual messages hinders the utility of process discovery techniques by producing non-understandable unstructured process models. In this paper, we propose the usage of word embedding for combining events that have a semantically similar name., 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
UPCommons. Portal del coneixement obert de la UPC
Publicación Estudio, informe, memoria (Report)

Stars and celebrities: A network creation game

  • Álvarez Faura, M. del Carme|||0000-0003-2352-0546
  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
  • Duch Brown, Amalia|||0000-0003-4371-1286
  • Messegué Buisan, Arnau|||0000-0002-7425-7592
  • Serna Iglesias, María José|||0000-0001-9729-8648
CoRR, Celebrity games, a new model of network creation games is introduced. The specific features of this model are that players have different celebrity weights and that a critical distance is taken into consideration. The aim of any player is to be close (at distance less than critical) to the others, mainly to those with high celebrity weights. The cost of each player depends on the cost of establishing direct links to other players and on the sum of the weights of those players at a distance greater than the critical distance. We show that celebrity games always have pure Nash equilibria and we characterize the family of subgames having connected Nash equilibria, the so called star celebrity games. Exact bounds for the PoA of non star celebrity games and a bound of O(n/ß+ß) for star celebrity games are provided. The upper bound on the PoA can be tightened when restricted to particular classes of Nash equilibria graphs. We show that the upper bound is O(n/ß) in the case of 2-edge-connected graphs and 2 in the case of trees.
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 Contribución de congreso (ConferenceOutput)

Análisis de la evolución de un curso: productividad y desigualdad

  • Blesa Aguilera, Maria Josep
  • Duch Brown, Amalia
  • Gabarró Vallès, Joaquim
  • Petit Silvestre, Jordi
  • Serna Iglesias, María José
Este trabajo analiza cuantitativamente las diferentes medidas adoptadas en la evaluación contínua del curso de Programación-1 de la Facultat d’Informàtica de Barcelona de la Universitat Politècnica de Catalunya desde 2010, año en que comienza la impartición del nuevo grado en Ingeniería Informática. Se analiza el efecto de dichas medidas sobre las categorías de calificaciones obtenidas por los estudiantes en relación al incremento de carga docente del profesorado. El estudio de la evolución de estos dos valores a lo largo del tiempo usa una aproximación de coste-beneficio marginal, clásica en ámbitos de economía. Usando herramientas provenientes de las ciencias sociales, este estudio se complementa con un análisis preliminar de desigualdad. Ambos enfoques pretenden introducir nuevas técnicas para el análisis objetivo del impacto de medidas docentes., This paper analyzes quantitatively the different measures taken in the continuous assessment of the CS1 course at the Facultat d’Informàtica de Barcelona of the Universitat Politècnica de Catalunya since 2010, when the new degree in Informatics Engineering began. The effect of those measures on the marks obtained by the students is analyzed with respect to the increment of the course load for the faculty members. These two values are compared along time through a classical marginal cost-benefit approach. Using tools commonly accepted in the social sciences, this study is complemented with a preliminary analysis of inequality. Both approaches aim at introducing new techniques for an objective analysis on the impact of teaching measures.
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 Contribución de congreso (ConferenceOutput)

A hierarchical mathematical model for automatic pipelining and allocation using elastic systems

  • Cortadella, Jordi
  • Petit Silvestre, Jordi
The advent of FPGA-based accelerators has encouraged the use of high-level synthesis (HLS) for rapid prototyping and design space exploration. In this context, design optimization at behavioral level becomes a critical task for the delivery of high-quality solutions. Time elasticity opens a new avenue of optimizations that can be applied after HLS and before logic synthesis, proposing new sequential transformations that expand beyond classical retiming and enlarge the register-transfer level (RTL) exploration space. This paper proposes a mathematical model for RTL transformations that exploit elasticity to select the best implementation for each functional unit and add pipeline registers to increase performance. Two simple examples are used to validate the effectiveness and potential benefits of the model., 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 Contribución de congreso (ConferenceOutput)

A datalog framework for modeling relationship-based access control policies

  • Pasarella Sánchez, Ana Edelmira
  • Lobo, Jorge
Comunicació presentada al SACMAT'17. 22nd ACM Symposium on Access Control Models and Technologies, celebrat els dies 21 a 23 de juny de 2017 a Indianapolis, EUA., Relationships like friendship to limit access to resources have been part of social network applications since their beginnings. Describing access control policies in terms of relationships is not particular to social networks and it arises naturally in many situations. Hence, we have recently seen several proposals formalizing different Relationship-based Access Control (ReBAC) models. In this paper, we introduce a class of Datalog programs suitable for modeling ReBAC and argue that this class of programs, that we called ReBAC Datalog policies, provides a very general framework to specify and implement ReBAC policies. To support our claim, we first formalize the merging of two recent proposals for modeling ReBAC, one based on hybrid logic and the other one based on path regular expressions. We present extensions to handle negative authorizations and temporal policies. We describe mechanism for policy analysis, and then discuss the feasibility of using Datalog-based systems as implementations., Edelmira Pasarella was partially supported by the Spanish Ministry for Economy and Competitiveness (MINECO) and the European Union (FEDER funds) under Grant Ref.: TIN2013-46181-C2-1-R COMMAS. Jorge Lobo was partially supported by the Secretaria d’Universitats i Recerca de la Generalitat de Catalunya, the Maria de Maeztu Units of Excellence Programme and the Spanish Ministry for Economy and Competitiveness (MINECO) under Grant Ref.: TIN2016-81032-P.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Alignment-based trace clustering

  • Chatain, Thomas
  • Carmona Vargas, Josep
  • Dongen, Boudewijn F. van
A novel method to cluster event log traces is presented in this paper. In contrast to the approaches in the literature, the clustering approach of this paper assumes an additional input: a process model that describes the current process. The core idea of the algorithm is to use model traces as centroids of the clusters detected, computed from a generalization of the notion of alignment. This way, model explanations of observed behavior are the driving force to compute the clusters, instead of current model agnostic approaches, e.g., which group log traces merely on their vector-space similarity. We believe alignment-based trace clustering provides results more useful for stakeholders. Moreover, in case of log incompleteness, noisy logs or concept drift, they can be more robust for dealing with highly deviating traces. The technique of this paper can be combined with any clustering technique to provide model explanations to the clusters computed. The proposed technique relies on encoding the individual alignment problems into the (pseudo-)Boolean domain, and has been implemented in our tool DarkSider that uses an open-source solver., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Reducing event variability in logs by clustering of word embeddings

  • Sánchez Charles, David
  • Carmona Vargas, Josep
  • Muntés Mulero, Victor
  • Solé Simó, Marc
Several business-to-business and business-to-consumer services are provided as a human-to-human conversation in which the provider representative guides the conversation towards its resolution based on her experience, following internal guidelines. Several attempts to automatize these services are becoming popular, but they are currently limited to procedures and objectives set during design step. Process discovery techniques could provide the necessary mechanisms to monitor event logs derived from textual conversations and expand the capabilities of conversational bots. Still, variability of textual messages hinders the utility of process discovery techniques by producing non-understandable unstructured process models. In this paper, we propose the usage of word embedding for combining events that have a semantically similar name., 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 Contribución de congreso (ConferenceOutput)

MapReduce vs. pipelining counting triangles

  • Pasarella Sánchez, Ana Edelmira
  • Vidal Serodio, Maria Esther
  • Zoltan Torres, Ana Cristina
In this paper we follow an alternative approach named pipeline, to implement 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 be concrete, we implement a dynamic pipeline of processes and an ad-hoc MapReduce version using the language Go. We explote the ability of Go language to deal with channels and spawned processes. An empirical evaluation is conducted on graphs of different size and density. Observed results suggest that pipeline allows for the implementation of an efficient solution 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

Stars and celebrities: A network creation game

  • Álvarez Faura, M. del Carme
  • Blesa Aguilera, Maria Josep
  • Duch Brown, Amalia
  • Messegué Buisan, Arnau
  • Serna Iglesias, María José
CoRR, Celebrity games, a new model of network creation games is introduced. The specific features of this model are that players have different celebrity weights and that a critical distance is taken into consideration. The aim of any player is to be close (at distance less than critical) to the others, mainly to those with high celebrity weights. The cost of each player depends on the cost of establishing direct links to other players and on the sum of the weights of those players at a distance greater than the critical distance. We show that celebrity games always have pure Nash equilibria and we characterize the family of subgames having connected Nash equilibria, the so called star celebrity games. Exact bounds for the PoA of non star celebrity games and a bound of O(n/ß+ß) for star celebrity games are provided. The upper bound on the PoA can be tightened when restricted to particular classes of Nash equilibria graphs. We show that the upper bound is O(n/ß) in the case of 2-edge-connected graphs and 2 in the case of trees., Preprint
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Partial match queries in relaxed K-dt trees

  • Duch Brown, Amalia
  • Lau Laynes-Lozada, Gustavo Salvador
The study of partial match queries on random hierarchical multidimensional data structures dates back to Ph. Flajolet and C. Puech’s 1986 seminal paper on partial match retrieval. It was not until recently that fixed (as opposed to random) partial match queries were studied for random relaxed K-d trees, random standard K-d trees, and random 2-dimensional quad trees. Based on those results it seemed natural to classify the general form of the cost of fixed partial match queries into two families: that of either random hierarchical structures or perfectly balanced structures, as conjectured by Duch, Lau and Martínez (On the Cost of Fixed Partial Queries in K-d trees Algorithmica, 75(4):684–723, 2016). Here we show that the conjecture just mentioned does not hold by introducing relaxed K-dt trees and providing the average-case analysis for random partial match queries as well as some advances on the average-case analysis for fixed partial match queries on them. In fact this cost –for fixed partial match queries– does not follow the conjectured forms., 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 Contribución de congreso (ConferenceOutput)

A datalog framework for modeling relationship-based access control policies

  • Pasarella Sánchez, Ana Edelmira
  • Lobo, Jorge
SACMAT'17 Best paper, Relationships like friendship to limit access to resources have been part of social network applications since their beginnings. Describing access control policies in terms of relationships is not particular to social networks and it arises naturally in many situations. Hence, we have recently seen several proposals formalizing different Relationship-based Access Control (ReBAC) models. In this paper, we introduce a class of Datalog programs suitable for modeling ReBAC and argue that this class of programs, that we called ReBAC Datalog policies, provides a very general framework to specify and implement ReBAC policies. To support our claim, we first formalize the merging of two recent proposals for modeling ReBAC, one based on hybrid logic and the other one based on path regular expressions. We present extensions to handle negative authorizations and temporal policies. We describe mechanism for policy analysis, and then discuss the feasibility of using Datalog-based systems as implementations., 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 Contribución de congreso (ConferenceOutput)

The alignment of formal, structured and unstructured process descriptions

  • Carmona Vargas, Josep
Nowadays organizations are experimenting a drift on the way processes are managed. On the one hand, formal notations like Petri nets or Business Process Model and Notation (BPMN) enable the unambiguous reasoning and automation of designed processes. This way of eliciting processes by manual design, which stemmed decades ago, will still be an important actor in the future. On the other hand, regulations require organizations to store their process executions in structured representations, so that they are known and can be analyzed. Finally, due to the different nature of stakeholders within an organization (ranging from the most technical members, e.g., developers, to less technical), textual descriptions of processes are also maintained to enable that everyone in the organization understands their processes. In this paper I will describe techniques for facilitating the interconnection between these three process representations. This requires interdisciplinary research to connect several fields: business process management, formal methods, natural language processing and process mining., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

A framework for online conformance checking

  • Burattin, Andrea
  • Carmona Vargas, Josep
Conformance checking – a branch of process mining – focuses on establishing to what extent actual executions of a process are in line with the expected behavior of a reference model. Current conformance checking techniques only allow for a-posteriori analysis: the amount of (non-)conformant behavior is quantified after the completion of the process instance. In this paper we propose a framework for online conformance checking: not only do we quantify (non-)conformant behavior as the execution is running, we also restrict the computation to constant time complexity per event analyzed, thus enabling the online analysis of a stream of events. The framework is instantiated with ideas coming from the theory of regions, and state similarity. An implementation is available in ProM and promising results have been obtained., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Communication requirements for team automata

  • Carmona Vargas, Josep
  • Beek, Maurice ter
  • Hennicker, Rolf
  • Kleijn, Jetty
Compatibility of components is an important issue in the quest for systems of systems that guarantee successful communications, free from message loss and indefinite waiting for inputs. In this paper, we investigate compatibility in the context of systems consisting of reactive components which may communicate through the synchronised execution of common actions. We model such systems in the team automata framework, which does not impose any a priori restrictions on the synchronisation policy followed to combine the components. We identify a family of representative synchronisation types based on the number of sending and receiving components participating in synchronisations. Then, we provide a generic procedure to derive, for each synchronisation type, requirements for receptiveness and for responsiveness of team automata that prevent that outputs are not accepted and inputs are not provided, respectively. Due to the genericity of our approach w.r.t. synchronisation policies, we can capture compatibility notions for various multi-component system models known from the literature., 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 Contribución de congreso (ConferenceOutput)

Comparing MapReduce and pipeline implementations for counting triangles

  • Pasarella Sánchez, Ana Edelmira
  • Vidal Serodio, Maria Esther
  • Zoltan, Cristina
A generalized method to define the Divide & 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 & Conquer paradigm, named pipeline. The main features of pipeline 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 sizes and densities. Observed results suggest that pipeline allows for the implementation of an efficient solution 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

A graph semantics for a variant of the ambient calculus more adequate for modeling SOC

  • Mylonakis Pascual, Nicolás
In this paper we present a graph semantics of a variant of the well known ambient calculus. The main change of our variant is to extract the mobility commands of the original calculus from the ambient topology. Similar to a previous work of ours, we prove that our encoding have good properties. We strongly believe that this variant would allow us to integrate our graph semantics of our mobile calculus with previous work of us in service oriented computing (SOC). Basically, our work on SOC develops a new graph transformation system which we call temporal symbolic graphs. This new graph formalism is used to give semantics to a design language for SOC developed in an european project, but it could also be used in connection with other approaches for modeling or specifying service systems., Postprint (published version)
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)
Recercat. Dipósit de la Recerca de Catalunya
Publicación

Measuring satisfaction in societies with opinion leaders and mediators

  • Molinero Albareda, Xavier
  • Riquelme Csori, Fabian Rolando
  • Serna Iglesias, María José
An opinion leader-follower model (OLF) is a two-action collective decision-making model for societies, in which three kinds of actors are considered:, Preprint