Pasar al contenido principal

MODELOS Y TECNICAS PARA EL PROCESAMIENTO DE INFORMACION A GRAN ESCALA -- BARCELONA

PID2020-112581GB-C21

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2020
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

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

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Capítulo o parte de un libro (BookPart)

Take the Challenge: Compute the CO2e emissions of your Programming Course

  • Gabarró, Joaquim
  • Blesa, Maria Josep
  • Duch, Amalia
  • Serna, Maria
[EN] Sustainability constraints ask for quick and drastic changes in the ways to teach at university. Here we study the amount of carbon emissions of lecturing a first course in programming. In addition to fix costs estimations, our study relies on a pool on student mobility patterns at our university. We estimate, per campus and level of presentiality, the amount of CO2e emissions of the course. Our results show that the main contributed cost of the course is not always due to transportation. Indeed, the difference in emissions between virtual and face-to-face is not huge and in some cases face-to-face is even better. This offers a discussion about the convenience of replacing face-to-face by virtual teaching through minimizing transportation emissions. We claim that the former can be made CO2e competitive by disseminating the lectures across the city avoiding the use of costly traveling means., This work was partially supported by the Spanish Agencia Estatal de Investigación, under grant PID2020-112581GB-C21 (MOTION).
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Otros (Other)

Tight Bounds for an Accelerated k-means++ Algorithm

  • Rodríguez-Corominas, Guillem
  • Blesa Aguilera, María Jesús
  • Blum, Christian
21st IFIP WG 12.5 International Conference, AIAI 2025, Limassol, Cyprus, June 26–29, 2025, Proceedings, Part I, Conference proceedings. IFIP (International Federation for Information Processing)., In this paper, we improve a recently introduced accelerated k-means++ algorithm by proposing a dynamic method for calculating bounds during its execution. This approach produces high-quality bounds without requiring a full iteration over the dataset, using the Triangle Inequality and the norm of the points for efficient computation. We propose three evaluation metrics to assess the quality of the calculated bounds and analyze their behavior across a diverse dataset. Results show that this dynamic method outperforms the traditional approach of initializing bounds at the end of the process, before the execution of the -means algorithm., The research presented in this paper was supported by grant 2022 FI_B 00903 funded by the AGAUR; grant PID-2020-112581GB-C21 (MOTION) funded by the AEI; grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033; and project MMT24-IIIA-02 funded by Red.es, Peer reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Capítulo o parte de un libro (BookPart)

DP_Kruskal: A concurrent algorithm to maintain dynamically minimum spanning trees

  • Benedí García, Daniel
  • Duch Brown, Amalia|||0000-0003-4371-1286
  • Pasarella Sánchez, Ana Edelmira|||0000-0001-8315-4977
  • Zoltan Torres, Ana Cristina
We provide a working implementation of DP_Kruskal; a parallel, distributed and concurrent adaptation of Kruskal algorithm that keeps the input graph distributed along a pipeline and computes online its minimum spanning tree (or forest) in the Go programming language. We show experimentally that DP_Kruskal is competitive and scales well to a large number of processes. Our experimental study is done for a large class of dynamic random graphs –including several densities and sizes– and some real dynamic graphs., This work has been funded by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C2., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Capítulo o parte de un libro (BookPart)

Advanced process discovery techniques

  • Augusto, Adriano
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Verbeek, Eric
Given the challenges associated to the process discovery task, more than a hundred research studies addressed the problem over the past two decades. Despite the richness of proposals, many state-of-the-art automated process discovery techniques, especially the oldest ones, struggle to systematically discover accurate and simple process models. In general, when the behavior recorded in the input event log is simple (e.g., exhibiting little parallelism, repetitions, or inclusive choices) or noise free, some basic algorithms such as the alpha miner can output accurate and simple process models. However, as the complexity of the input data increases, the quality of the discovered process models can worsen quickly. Given that oftentimes real-life event logs record very complex and unstructured process behavior containing many repetitions, infrequent traces, and incomplete data, some state-of-the-art techniques turn unreliable and not purposeful. Specifically, they tend to discover process models that either have limited accuracy (i.e., low fitness and/or precision) or are syntactically incorrect. While currently there exists no perfect automated process discovery technique, some are better than others when discovering a process model from event logs recording complex process behavior. In this chapter, we introduce four of such techniques, discussing their underlying approach and algorithmic ideas, reporting their benefits and limitation, and comparing their performance with the algorithms introduced in the previous chapter., This work has been supported by MCIN/AEI funds under grant PID2020-112581GB-C21., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Capítulo o parte de un libro (BookPart)

A probabilistic model revealing shortcomings in Lua’s hybrid tables

  • Martínez Parra, Conrado|||0000-0003-1302-9067
  • Nicaud, Cyril
  • Rotondo, Pablo
Lua (Ierusalimschy et al., 1996) is a well-known scripting language, popular among many programmers, most notably in the gaming industry. Remarkably, the only data-structuring mechanism in Lua, is an associative array called a table. With Lua 5.0, the reference implementation of Lua introduced hybrid tables to implement tables using both a hash table and a dynamically growing array combined together: the values associated with integer keys are stored in the array part, when suitable. All this is transparent to the user, which has a unique simple interface to handle tables. In this paper we carry out a theoretical analysis of the performance of Lua ’s tables, by considering various worst-case and probabilistic scenarios. In particular, we uncover some problematic situations for the simple probabilistic model where we add a new key with some fixed probability p>1/2 and delete a key with probability 1−p: the cost of performing T such operations is proved to be Ω(TlogT) with high probability, instead of linear in T., The work of the first author has been supported by funds from project MOTION (Project PID2020-112581GB-C21) of the Spanish Ministry of Science & Innovation MCIN/AEI/10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Capítulo o parte de un libro (BookPart)

LotterySampling: A randomized algorithm for the Heavy Hitters and Top-k problems in data streams

  • Martínez Parra, Conrado|||0000-0003-1302-9067
  • Solera Pardo, Gonzalo
We propose a new randomized count-based algorithm to solve the Heavy Hitters and Top-k problems in data streams. This algorithm, called LotterySampling, uses the intuitive concept of “lottery tickets”, to decide which elements to sample. We prove that LotterySampling is inside the (δ,ϵ)-deficient framework for the Heavy Hitters problem and that it has a similar performance to the well known StickySampling algorithm, although they are very different in nature. More importantly, we define a similar (δ,ϵ)-deficient framework for the harder Top-k problem and we prove that LotterySampling is inside it. Hence, LotterySampling can be used, without any previous assumption of the data distribution, as a probabilistic approximation scheme to find the k most frequent elements and to approximate the frequencies of the reported elements by a factor of 1−ϵ . To the best of our knowledge, this is the first algorithm that gives theoretical guarantees for the Top-k problem for unknown and arbitrary streams, which is the most important contribution of this paper. Its memory usage is adaptive to the distribution of the stream, and it will increase or decrease depending on whether the stream becomes less or more skewed. More precisely, the sample size depends, at any given moment, on the unknown kth highest frequency but it is independent of the length of the stream and of the number of distinct elements. The user just needs to provide two parameters that determine the quality of the answers, independently of the stream. We compare LotterySampling with other existing probabilistic and deterministic algorithms showing its strengths and weaknesses., This work has been supported by funds from the MOTION Project (Project PID2020-112581GB-C21) of the Spanish Ministry of Science & Innovation MCIN/AEI/10.13039/501100011033, while the second author was a postgraduate student at Universitat Politècnica de Catalunya., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Capítulo o parte de un libro (BookPart)

Conformance checking: foundations, milestones and challenges

  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Dongen, Boudewijn F. van
  • Weidlich, Matthias
By relating observed and modelled behaviour, conformance checking unleashes the full power of process mining. Techniques from this discipline enable the analysis of the quality of a process model discovered from event data, the identification of potential deviations, and the projection of real traces onto process models. This way, the insights gained from the available event data can be transferred to a richer conceptual level, amenable for a human interpretation. The aforementioned functionalities are grounded on the use of conformance checking artefacts that explicit the relation between observed and modelled behaviour. This chapter describes these artefacts, and builds upon them to gain evidence-based insights on the processes of an organization. Moreover, we overview the applications of conformance checking and propose a general framework that incorporates these applications. Finally, milestones and challenges of the field are outlined., This work has been supported by MCIN/AEI funds under grant PID2020-112581GB-C21., Peer Reviewed