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

UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Coinductive techniques for checking satisfiability of generalized nested conditions

  • Stoltenow, Lara
  • König, Barbara
  • Schneider, Sven
  • Corradini, Andrea
  • Lambers, Leen
  • Orejas Valdés, Fernando|||0000-0002-3023-4006
We study nested conditions, a generalization of first-order logic to a categorical setting, and provide a tableau-based (semi-decision) procedure for checking (un)satisfiability and finite model generation. This generalizes earlier results on graph conditions. Furthermore we introduce a notion of witnesses, allowing the detection of infinite models in some cases. To ensure completeness, paths in a tableau must be fair, where fairness requires that all parts of a condition are processed eventually. Since the correctness arguments are non-trivial, we rely on coinductive proof methods and up-to techniques that structure the arguments. We distinguish between two types of categories: categories where all sections are isomorphisms, allowing for a simpler tableau calculus that includes finite model generation; in categories where this requirement does not hold, model generation does not work, but we still obtain a sound and complete calculus., Andrea Corradini: Research partially supported by the Italian MUR under the PRIN 20228KXFN2 “STENDHAL” and by the University of Pisa under the PRA 2022_99 “FM4HD”. Fernando Orejas: Research partially supported by MCIN/ AEI /10.13039/501100011033 under grant PID2020-112581GB-C21., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Thresholds as mechanisms for weighting influence in the linear threshold rank

  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
  • Dominguez Besserer, Alejandro
  • Serna Iglesias, María José|||0000-0001-9729-8648
Social networks are the natural space for the spreading of information and influence and have become a media themselves. Several models capturing that diffusion process have been proposed, most of them based on the Independent Cascade (IC) model or on the Linear Threshold (LT) model. The IC model is probabilistic while the LT model relies on the knowledge of an actor to be convinced, reflected in an associated individual threshold. Although the LT-based models contemplate an individual threshold for each actor in the network, the existing studies so far have always considered a threshold of 0.5 equal in all actors (i.e., a simple majority activation criterion). Our main objective in this work is to start the study on how the dissemination of information on networks behaves when we consider other options for setting those thresholds and how many network actors end up being influenced by this dissemination. For doing so, we consider a recently introduced centrality measure based on the LT model, the Forward Linear Threshold Rank (FwLTR), which is the natural interpretation of the Linear Threshold Rank on directed networks. We experimentally analyze the ranking properties for several networks in which the influence resistance threshold follows different schemes. Here we consider three different schemes: (1) uniform, in which all players have the same value; (2) random, where each player is assigned a threshold u.a.r. in a prescribed interval; and (3) determined by the value of another centrality measure on the actor. Our results show that the selection has a clear impact on the ranking, even quite significant and abrupt in some cases. We conclude that the social networks ranks that provide the best assignments for the individual thresholds are FwLTR and the well-known PageRank., Supported by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

The semantics of GQL-like path queries

  • Orejas Valdés, Fernando|||0000-0002-3023-4006
  • Pino Blanco, Elvira|||0000-0003-3376-5096
The success of graph databases (GDBs) has caused the development of several dozens of GDB products by companies like Neo4j, Oracle, Amazon, IBM or SAP. In parallel, several graph query languages have been designed for querying these GDBs, like Cypher for Neo4j, PGQL for Oracle, or GSQL for TigerGraph, which actually are quite similar. This situation has led to propose the creation of a unifying standard for graph query languages. This standard is currently under development, and is called GQL. In a previous paper we defined a logical and an operational semantics for a core language similar to Cypher, showing that the operational semantics is sound and complete with respect to the logical one. However, GQL has gone beyond the expressive power of the above mentioned languages in several senses. Therefore, in the current work, our aim is to redefine the semantics that we gave for Cypher-like languages to a core subset of GQL., This work is partially supported by MCIN/ AEI /10.13039/501100011033 under grant PID2020-112581GB-C21., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Relating real and synthetic social networks through centrality measures

  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
  • Popa, Mihail Eduard
  • Serna Iglesias, María José|||0000-0001-9729-8648
We perform here a comparative study on the behaviour of real and synthetic social networks with respect to a selection of nine centrality measures. Some of them are topology based (degree, closeness, betweenness), while others consider the relevance of the actors within the network (Katz, PageRank) or their ability to spread influence through it (Independent Cascade rank, Linear Threshold Rank). We run different experiments on synthetic social networks, with 1K, 10K, and 100K nodes, generated according to the Gaussian Random partition model, the stochastic block model, the LFR benchmark graph model and hyperbolic geometric graphs model. Some real social networks are also considered, with the aim of discovering how do they relate to the synthetic models in terms of centrality. Apart from usual statistical measures, we perform a correlation analysis between all the nine measures. Our results indicate that, in general, the correlation matrices of the different models scale nicely with size. Moreover, the correlation plots distinguish four categories that classify most of the real networks studied here. Those categories have a clear correspondence with particular configurations of the models for synthetic networks., M. Blesa and M. Serna acknowledge support by MICIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION). M.E. Popa was funded by the Ministry of Education and Vocational Training (MEFP) with a student grant (Beca de colaboración, call 2020-2021), Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Negative learning ant colony optimization for network alignment

  • Rodríguez Corominas, Guillem
  • Blum, Christian
  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
The Network Alignment problem is a hard Combinatorial Optimization problem with a wide range of applications, especially in computational biology. Given two (or more) networks, the goal is to find a mapping between their respective nodes that preserves the topological and functional structure of the networks. In this work we extend a novel ant colony optimization approach for network alignment by adding a recently proposed Negative Learning mechanism. In particular, information for Negative Learning is obtained by solving sub-instances of the tackled problem instances at each iteration by means of an Integer Linear Programming solver. The results show that the proposed algorithm not only outperforms the standard ant colony optimization approach but also current state-of-the-art methods from the literature., M. Blesa acknowledges support by AGAUR (GENCAT) under grant 2017-SGR-786 (ALBCOM). Moreover, the authors acknowledge support by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION) and grant PID2019-104156GB-I00 (CISUSTAIN)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Tight bounds for an accelerated k-means++ algorithm

  • Rodríguez i Corominas, Guillem
  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
  • Blum, Christian
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 k-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 Contribución de congreso (ConferenceOutput)

A proposal for an Educational Well-Being Index (EWI) for undergraduate course design

  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
  • Duch Brown, Amalia|||0000-0003-4371-1286
  • Gabarró Vallès, Joaquim|||0000-0003-3771-2813
  • Serna Iglesias, María José|||0000-0001-9729-8648
Every day it is more common to hear around us about the publication of studies, surveys or statistical results about the well-being of people, workers, women in a given country. Indeed, as university professors, our work cannot be independent of the level of well-being of our students. So, in this work, we propose a methodology to asses the students well-being inside a course implementation by what we call the educational well-being index (EWI). We start with a survey that gathers those factors that computing courses’ students at our university –of two different levels and majors– consider most important. Our second step is the evaluation –by a group of teachers– of the presence of those factors in different educational models of implementation of the courses. We use principal component analysis to extract, from the student data, the valuations that they expressed in the survey: the principal component of their own measurements on well-being. We work only with the coefficients of the first dimension of the principal component. The third step is a (subjective) valuation of the topics addressed in the survey when considering a particular educational model. Finally, we gather everything together to obtain a well-being index of an educational model that allows their comparison. Besides the methodology, we present and analyze the values obtained from our case study., Supported by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Forward and backward linear threshold ranks

  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
  • García Rodríguez, Pau
  • Serna Iglesias, María José|||0000-0001-9729-8648
We propose the FwLTR and BwLTR, two new centrality measures based on the Linear Threshold model. In contrast to the Linear Threshold rank (LTR), these measures differentiate between the incoming and the outgoing neighborhoods of the activation set that initiates the spreading process. Their rankings are distinguishable from the rest of the centrality measures considered traditionally. However, LTR and BwLTR behave quite similarly, while FwLTR is clearly different., Supported by AEI under grant PID-2020-112581GB-C21 (MOTION) and AGAUR under grant 2017-SGR-786 (ALBCOM)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

How can graph databases and reasoning be combined and integrated?

  • Pasarella Sánchez, Ana Edelmira|||0000-0001-8315-4977
Nowadays the graph data model has been accepted as one of the most suitable data models to formalize relationships among entities of many domains. Deductive databases based on the Datalog language have been used to deduce new information from large amounts of data. Most of the attempts to combine logic and graph databases are based on translating knowledge in graph databases into Datalog and then use its inference engine. We aim to open the discussion about combining graph databases and a graph-oriented logic to define «native» deductive graph databases. This is, graph databases equipped with an inference mechanism based on graph based logic. To be concrete, we plan to use the recently introduced graph navigational logic., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Rainbow connectivity of multilayered random geometric graphs

  • Díaz Cort, Josep|||0000-0003-4422-0067
  • Diner, Oznur Y.
  • Serra Albó, Oriol|||0000-0001-8561-4631
  • Serna Iglesias, María José|||0000-0001-9729-8648
An edge-colored multigraph G is rainbow connected if every pair of vertices is joined by at least one rainbow path, i.e., a path where no two edges are of the same color. In the context of multilayered networks, we introduce the notion of multilayered random geometric graphs, from h = 2 independent random geometric graphs G(n,r) on the unit square. We define an edge-coloring by coloring the edges according to the copy of G(n,r) they belong to and study the rainbow connectivity of the resulting edge-colored multigraph. We show that r(n) = lnn nh-1 1/2h , is a threshold of the radius for the property of being rainbow connected. This complements the known analogous results for the multilayered graphs defined on the Erdos–Rényi random model., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

A stream processing-based algorithm for maintaining minimum spanning forests of evolving graphs

  • Benedí García, Daniel
  • Duch Brown, Amalia|||0000-0003-4371-1286
  • Pasarella Sánchez, Ana Edelmira|||0000-0001-8315-4977
In this work we introduce a concurrent/parallel adaptation of Kruskal algorithm based on the dynamic pipeline approach. This is, the input (undirected) graph is given by a stream of weighted edges and it is dynamically created and maintained in a distributed way along a pipeline of stateful stages. To be concrete, firstly an initial graph is created and then, whenever the graph evolves because of edges are added, removed or updated, the minimum spanning tree (forest) according to the current graph can be computed and output immediately. Moreover, we provide a working implementation in the Go programming language. Go is suitable to dynamic pipelines’ implementations thanks to its communication channels and co-routines. We show experimentally that our algorithm scales well to a large number of processes and that it is competitive against the classic sequential Kruskal algorithm and a well known parallelized version of the Kruskal algorithm. 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-C21., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Partial match queries in quad-K-d trees

  • Duch Brown, Amalia|||0000-0003-4371-1286
  • Martínez Parra, Conrado|||0000-0003-1302-9067
Quad-K-d trees [Bereckzy et al., 2014] are a generalization of several well-known hierarchical Kdimensional data structures. They were introduced to provide a unified framework for the analysis of associative queries and to investigate the trade-offs between the cost of different operations and the memory needs (each node of a quad-K-d tree has arity 2 m for some m, 1 ≤ m ≤ K). Indeed, we consider here partial match – one of the fundamental associative queries – for several families of quad-K-d trees including, among others, relaxed K-d trees and quadtrees. In particular, we prove that the expected cost of a random partial match Pˆn that has s out of K specified coordinates in a random quad-K-d tree of size n is Pˆn ∼ β · n α where α and β are constants given in terms of K and s as well as additional parameters that characterize the specific family of quad-K-d trees under consideration. Additionally, we derive a precise asymptotic estimate for the main order term of Pn,q – the expected cost of a fixed partial match in a random quad-K-d tree of size n. The techniques and procedures used to derive the mentioned costs extend those already successfully applied to derive analogous results in quadtrees and relaxed K-d trees; our results show that the previous results are just particular cases, and states the validity of the conjecture made in [Duch et al., 2016] to a wider variety of multidimensional data structures., This work has been supported by funds from the MOTION Project (Project PID2020-112581GB-C21) of the Spanish Ministery of Science and Innovation MCIN/AEI/10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Improved reconstruction of random geometric graphs

  • Dani, Varsha
  • Díaz Cort, Josep|||0000-0003-4422-0067
  • Hayes, Thomas P.
  • Moore, Cristopher
Embedding graphs in a geographical or latent space, i.e. inferring locations for vertices in Euclidean space or on a smooth manifold or submanifold, is a common task in network analysis, statistical inference, and graph visualization. We consider the classic model of random geometric graphs where n points are scattered uniformly in a square of area n, and two points have an edge between them if and only if their Euclidean distance is less than r. The reconstruction problem then consists of T A inferring the vertex positions, up to the symmetries of the square, given only the adjacency matrix of the resulting graph. We give an algorithm that, if r = nα for α > 0, with high probability reconstructs the vertex positions with a maximum error of O(nβ) where β = 1/2 − (4/3)α, until α ≥3/8 where β =0 and the error becomes O(√ log n). This improves over earlier results, which E were unable to reconstruct with error less than r. Our method estimates Euclidean distances using a hybrid of graph distances and short-range estimates based on the number of common neighbors. We extend our results to the surface of the sphere in R3 and to hypercubes in any constant dimension., Josep Díaz: Partially supported by PID-2020-112581GB-C21 (MOTION). Thomas P. Hayes: Partially supported by NSF grant CCF-1150281. Cristopher Moore: Partially supported by NSF grant IIS-1838251., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Small language models for less-resourced languages in a real-world scenario: The case for Catalan

  • Saurí Colomer, Roser
  • Sànchez-Ferreres, Josep|||0000-0002-7204-4307
  • Padró, Lluís|||0000-0003-4738-5019
  • Carmona Vargas, Josep|||0000-0001-9656-254X
Small Language Models (SLMs), typically ranging from a few million to 10–15 billion parameters, offer a promising solution towards constraints imposed by platform size–particularly mobile and IoT devices–and by the requirements of many organizations such as SMEs, which need solutions that ensure data privacy while remaining cost-effective. Their compactness and efficiency provide digital sovereignty and flexibility, though with more limited general-purpose capabilities. This makes them especially sensitive when working with underrepresented languages, such as Catalan, due to interference from majority languages that can increase bias risk. This paper evaluates state-of-the-art SLMs in a real-world Catalan use case: an AI assistant for older adults, assessing both user interactions and structured function call generation. Our work, which contributes to the FREC initiative for deploying a connected SLM-based infrastructure under the Model Context Protocol, demonstrates that some SLMs are able to deliver high-quality performance even in resource-constrained, linguistically minority environments., This piece of work has been supported by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION). Also, by the European Union – NextGenerationEU, Spain’s Recovery, Transformation and Resilience Plan (RRP), in collaboration with the Catalan government (Generalitat de Catalunya), under grant SDC007/25/000055., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Theoretical and empirical analysis of cost-function merging for implicit hitting set WCSP solving

  • Larrosa Bondia, Francisco Javier|||0000-0002-8322-0505
  • Martínez Parra, Conrado|||0000-0003-1302-9067
  • Rollón Rico, Emma|||0000-0001-8021-9464
The Implicit Hitting Set (HS) approach has shown very effective for MaxSAT solving. However, only preliminary promising results have been obtained for the very similar Weighted CSP framework. In this paper we contribute towards both a better theoretical understanding of the HS approach and a more effective HS-based solvers for WCSP. First, we bound the minimum number of iterations of HS thanks to what we call distinguished cores. Then, we show a source of inefficiency by introducing two simple problems where HS is unfeasible. Next, we propose two reformulation methods that merge cost-functions to overcome the problem. We provide a theoretical analysis that quantifies the magnitude of the improvement of each method with respect to the number of iterations of the algorithm. In particular, we show that the reformulations can bring an exponential number of iterations down to a constant number in our working examples. Finally, we complement our theoretical analysis with two sets of experiments. First, we show that our results are aligned with real executions. Second, and most importantly, we conduct experiments on typical benchmark problems and show that cost-function merging may be heuristically applied and it may accelerate HS algorithms by several orders of magnitude. In some cases, it even outperforms state-of-the-art solvers., The work of Javier Larrosa and Emma Rollon was supported by grant PID2021-122830OB-C43, funded by MCIN/AEI/ 10.13039/501100011033 and by “ERDF: A way of making Europe”. The work of Conrado Martínez was supported by grant PID2020-112581GB-C21 (MOTION Project), funded by MCIN/AEI/10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Resource-guided FPGA floorplanning via quad-tree-based NLP optimization

  • Chen, Ze|||0000-0003-4111-6715
  • Cortadella, Jordi|||0000-0001-8114-250X
Field-programmable gate arrays (FPGAs) are widely adopted as accelerators for compute-intensive applications. In modern FPGA flows, floorplanning provides coarse-grained region constraints, but commercial tools offer no automatic support, requiring designers to manually define partition regions that substantially impact placement and routing. This paper presents a fully automatic framework that generates resource-guided floorplanning constraints to improve the clock frequency of FPGA designs. The framework employs a divide-and-conquer strategy with nonlinear optimization for resource-aware region assignment, exploiting FPGA heterogeneity in a device-agnostic manner and producing constraints that integrate into commercial toolflows. The framework has been integrated into Vivado and tested with nine benchmarks and two platforms, improving the maximum clock frequency by 11.4% and 5.8%, respectively, and yielding an additional 4.1% gain with timing-optimization strategies without significant congestion overhead., This work has been supported by funds from the Spanish Agencia Estatal de Investigación under grant PID2020-112581GB-C21 (MOTION), and by the China Scholarship Council (CSC)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Affirmative sampling: theory and applications

  • Lumbroso, Jérémie
  • Martínez Parra, Conrado|||0000-0003-1302-9067
Affirmative Sampling is a practical and efficient novel algorithm to obtain random samples of distinct elements from a data stream. Its most salient feature is that the size S of the sample will, on expectation, grow with the (unknown) number n of distinct elements in the data stream. As any distinct element has the same probability to be sampled, and the sample size is greater when the “diversity” (the number of distinct elements) is greater, the samples that Affirmative Sampling delivers are more representative than those produced by any scheme where the sample size is fixed a priori - hence its name. Our algorithm is straightforward to implement, and several implementations already exist., 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, and by Princeton University, and its Department of Computer Science., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Take the challenge: compute the CO2e emissions of your programming course

  • Gabarró Vallès, Joaquim|||0000-0003-3771-2813
  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
  • Duch Brown, Amalia|||0000-0003-4371-1286
  • Serna Iglesias, María José|||0000-0001-9729-8648
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)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Continuous query engine to detect anomalous ATM transactions

  • Martín Canfrán, Fernando
  • Benedí García, Daniel
  • Duch Brown, Amalia|||0000-0003-4371-1286
  • Pasarella Sánchez, Ana Edelmira|||0000-0001-8315-4977
Nowadays data are in motion, change continuously and are –possibly– unbounded implying data sources that are also constantly evolving. From the data persistence point of view this reality breaks the usual paradigm of having dynamic but stable data sources. This, together with the increasing number applications based on data streams for taking critical decisions in real time, raises the need for re-thinking both the data and the query models to fit these new requirements. Therefore, under these circumstances, it seems reasonable that a suitable data model is a continuously evolving data graph. In this work we tackled the problem of querying continuously evolving data graphs in the context of ATM transactions, in particular anomalous ones. Under this context, evaluating continuous queries corresponds to recognize patterns usually associated with anomalous behaviors in the volatile subgraph of ATM transactions. We propose an evaluation process based on the dynamic pipeline computational model, a stream processing technique allowing the emission of alerts as soon as anomalous patterns are identified. Stream based Bank applications that monitor ATM transactions are direct beneficiaries of our proposal since they can continuously query data graphs to get “fresh” data as are produced, avoiding the computational overhead of having to discard non-valid data., This work has been supported by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Unbiased similarity estimators using samples

  • Martínez Parra, Conrado|||0000-0003-1302-9067
  • Viola Deambrosis, Alfredo
  • Wang, Jun
Computing a similarity measure (or a distance) between two complex objects is a fundamental building block for a huge number of applications in a wide variety of domains. Since many tasks involve computing such similarities among many pairs of objects, many algorithmic techniques and data structures have been devised in the past to reduce the number of similarity computations and to reduce the complexity of computing the similarity (e.g., dimension-reduction techniques). In this paper, we focus on computing the similarity of two sets and show that computing the similarity of two random samples drawn from the respective sets leads to an (asymptotically) unbiased estimator of the true similarity, with relative standard error going to zero as the size of the involved sets grows, and of course at a much lower computational cost as we compute the similarity of the significantly smaller samples. While this result has been known for a long time since Broder’s seminal paper (Broder, 1997) for the Jaccard similarity index, we show here that the result also holds for many other similarity measures, such as the well-known cosine similarity, Sørensen-Dice, the first and second Kulczynski coefficients, etc., 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., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Small language models for less-resourced languages in a real-world scenario: The case for Catalan

  • Saurí Colomer, Roser
  • Sànchez-Ferreres, Josep
  • Padró, Lluís
  • Carmona Vargas, Josep
Small Language Models (SLMs), typically ranging from a few million to 10–15 billion parameters, offer a promising solution towards constraints imposed by platform size–particularly mobile and IoT devices–and by the requirements of many organizations such as SMEs, which need solutions that ensure data privacy while remaining cost-effective. Their compactness and efficiency provide digital sovereignty and flexibility, though with more limited general-purpose capabilities. This makes them especially sensitive when working with underrepresented languages, such as Catalan, due to interference from majority languages that can increase bias risk. This paper evaluates state-of-the-art SLMs in a real-world Catalan use case: an AI assistant for older adults, assessing both user interactions and structured function call generation. Our work, which contributes to the FREC initiative for deploying a connected SLM-based infrastructure under the Model Context Protocol, demonstrates that some SLMs are able to deliver high-quality performance even in resource-constrained, linguistically minority environments., This piece of work has been supported by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION). Also, by the European Union – NextGenerationEU, Spain’s Recovery, Transformation and Resilience Plan (RRP), in collaboration with the Catalan government (Generalitat de Catalunya), under grant SDC007/25/000055., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Forward and backward linear threshold ranks

  • Blesa Aguilera, Maria Josep
  • García Rodríguez, Pau
  • Serna Iglesias, María José
We propose the FwLTR and BwLTR, two new centrality measures based on the Linear Threshold model. In contrast to the Linear Threshold rank (LTR), these measures differentiate between the incoming and the outgoing neighborhoods of the activation set that initiates the spreading process. Their rankings are distinguishable from the rest of the centrality measures considered traditionally. However, LTR and BwLTR behave quite similarly, while FwLTR is clearly different., Supported by AEI under grant PID-2020-112581GB-C21 (MOTION) and AGAUR under grant 2017-SGR-786 (ALBCOM)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Partial match queries in quad-K-d trees

  • Duch Brown, Amalia
  • Martínez Parra, Conrado
Quad-K-d trees [Bereckzy et al., 2014] are a generalization of several well-known hierarchical Kdimensional data structures. They were introduced to provide a unified framework for the analysis of associative queries and to investigate the trade-offs between the cost of different operations and the memory needs (each node of a quad-K-d tree has arity 2 m for some m, 1 ≤ m ≤ K). Indeed, we consider here partial match – one of the fundamental associative queries – for several families of quad-K-d trees including, among others, relaxed K-d trees and quadtrees. In particular, we prove that the expected cost of a random partial match Pˆn that has s out of K specified coordinates in a random quad-K-d tree of size n is Pˆn ∼ β · n α where α and β are constants given in terms of K and s as well as additional parameters that characterize the specific family of quad-K-d trees under consideration. Additionally, we derive a precise asymptotic estimate for the main order term of Pn,q – the expected cost of a fixed partial match in a random quad-K-d tree of size n. The techniques and procedures used to derive the mentioned costs extend those already successfully applied to derive analogous results in quadtrees and relaxed K-d trees; our results show that the previous results are just particular cases, and states the validity of the conjecture made in [Duch et al., 2016] to a wider variety of multidimensional data structures., This work has been supported by funds from the MOTION Project (Project PID2020-112581GB-C21) of the Spanish Ministery of Science and Innovation MCIN/AEI/10.13039/501100011033., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

A stream processing-based algorithm for maintaining minimum spanning forests of evolving graphs

  • Benedí García, Daniel
  • Duch Brown, Amalia
  • Pasarella Sánchez, Ana Edelmira
In this work we introduce a concurrent/parallel adaptation of Kruskal algorithm based on the dynamic pipeline approach. This is, the input (undirected) graph is given by a stream of weighted edges and it is dynamically created and maintained in a distributed way along a pipeline of stateful stages. To be concrete, firstly an initial graph is created and then, whenever the graph evolves because of edges are added, removed or updated, the minimum spanning tree (forest) according to the current graph can be computed and output immediately. Moreover, we provide a working implementation in the Go programming language. Go is suitable to dynamic pipelines’ implementations thanks to its communication channels and co-routines. We show experimentally that our algorithm scales well to a large number of processes and that it is competitive against the classic sequential Kruskal algorithm and a well known parallelized version of the Kruskal algorithm. 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-C21., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

How can graph databases and reasoning be combined and integrated?

  • Pasarella Sánchez, Ana Edelmira
Nowadays the graph data model has been accepted as one of the most suitable data models to formalize relationships among entities of many domains. Deductive databases based on the Datalog language have been used to deduce new information from large amounts of data. Most of the attempts to combine logic and graph databases are based on translating knowledge in graph databases into Datalog and then use its inference engine. We aim to open the discussion about combining graph databases and a graph-oriented logic to define «native» deductive graph databases. This is, graph databases equipped with an inference mechanism based on graph based logic. To be concrete, we plan to use the recently introduced graph navigational logic., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Unbiased similarity estimators using samples

  • Martínez Parra, Conrado
  • Viola Deambrosis, Alfredo
  • Wang,Jun
Computing a similarity measure (or a distance) between two complex objects is a fundamental building block for a huge number of applications in a wide variety of domains. Since many tasks involve computing such similarities among many pairs of objects, many algorithmic techniques and data structures have been devised in the past to reduce the number of similarity computations and to reduce the complexity of computing the similarity (e.g., dimension-reduction techniques). In this paper, we focus on computing the similarity of two sets and show that computing the similarity of two random samples drawn from the respective sets leads to an (asymptotically) unbiased estimator of the true similarity, with relative standard error going to zero as the size of the involved sets grows, and of course at a much lower computational cost as we compute the similarity of the significantly smaller samples. While this result has been known for a long time since Broder’s seminal paper (Broder, 1997) for the Jaccard similarity index, we show here that the result also holds for many other similarity measures, such as the well-known cosine similarity, Sørensen-Dice, the first and second Kulczynski coefficients, etc., 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., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Theoretical and empirical analysis of cost-function merging for implicit hitting set WCSP solving

  • Larrosa Bondia, Francisco Javier
  • Martínez Parra, Conrado
  • Rollón Rico, Emma
The Implicit Hitting Set (HS) approach has shown very effective for MaxSAT solving. However, only preliminary promising results have been obtained for the very similar Weighted CSP framework. In this paper we contribute towards both a better theoretical understanding of the HS approach and a more effective HS-based solvers for WCSP. First, we bound the minimum number of iterations of HS thanks to what we call distinguished cores. Then, we show a source of inefficiency by introducing two simple problems where HS is unfeasible. Next, we propose two reformulation methods that merge cost-functions to overcome the problem. We provide a theoretical analysis that quantifies the magnitude of the improvement of each method with respect to the number of iterations of the algorithm. In particular, we show that the reformulations can bring an exponential number of iterations down to a constant number in our working examples. Finally, we complement our theoretical analysis with two sets of experiments. First, we show that our results are aligned with real executions. Second, and most importantly, we conduct experiments on typical benchmark problems and show that cost-function merging may be heuristically applied and it may accelerate HS algorithms by several orders of magnitude. In some cases, it even outperforms state-of-the-art solvers., The work of Javier Larrosa and Emma Rollon was supported by grant PID2021-122830OB-C43, funded by MCIN/AEI/ 10.13039/501100011033 and by “ERDF: A way of making Europe”. The work of Conrado Martínez was supported by grant PID2020-112581GB-C21 (MOTION Project), funded by MCIN/AEI/10.13039/501100011033., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Coinductive techniques for checking satisfiability of generalized nested conditions

  • Stoltenow, Lara
  • König, Barbara
  • Schneider, Sven
  • Corradini, Andrea
  • Lambers, Leen
  • Orejas Valdés, Fernando
We study nested conditions, a generalization of first-order logic to a categorical setting, and provide a tableau-based (semi-decision) procedure for checking (un)satisfiability and finite model generation. This generalizes earlier results on graph conditions. Furthermore we introduce a notion of witnesses, allowing the detection of infinite models in some cases. To ensure completeness, paths in a tableau must be fair, where fairness requires that all parts of a condition are processed eventually. Since the correctness arguments are non-trivial, we rely on coinductive proof methods and up-to techniques that structure the arguments. We distinguish between two types of categories: categories where all sections are isomorphisms, allowing for a simpler tableau calculus that includes finite model generation; in categories where this requirement does not hold, model generation does not work, but we still obtain a sound and complete calculus., Andrea Corradini: Research partially supported by the Italian MUR under the PRIN 20228KXFN2 “STENDHAL” and by the University of Pisa under the PRA 2022_99 “FM4HD”. Fernando Orejas: Research partially supported by MCIN/ AEI /10.13039/501100011033 under grant PID2020-112581GB-C21., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Improved reconstruction of random geometric graphs

  • Dani, Varsha
  • Díaz Cort, Josep
  • Hayes, Thomas P.
  • Moore, Cristopher
Embedding graphs in a geographical or latent space, i.e. inferring locations for vertices in Euclidean space or on a smooth manifold or submanifold, is a common task in network analysis, statistical inference, and graph visualization. We consider the classic model of random geometric graphs where n points are scattered uniformly in a square of area n, and two points have an edge between them if and only if their Euclidean distance is less than r. The reconstruction problem then consists of T A inferring the vertex positions, up to the symmetries of the square, given only the adjacency matrix of the resulting graph. We give an algorithm that, if r = nα for α > 0, with high probability reconstructs the vertex positions with a maximum error of O(nβ) where β = 1/2 − (4/3)α, until α ≥3/8 where β =0 and the error becomes O(√ log n). This improves over earlier results, which E were unable to reconstruct with error less than r. Our method estimates Euclidean distances using a hybrid of graph distances and short-range estimates based on the number of common neighbors. We extend our results to the surface of the sphere in R3 and to hypercubes in any constant dimension., Josep Díaz: Partially supported by PID-2020-112581GB-C21 (MOTION). Thomas P. Hayes: Partially supported by NSF grant CCF-1150281. Cristopher Moore: Partially supported by NSF grant IIS-1838251., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

The semantics of GQL-like path queries

  • Orejas Valdés, Fernando
  • Pino Blanco, Elvira
The success of graph databases (GDBs) has caused the development of several dozens of GDB products by companies like Neo4j, Oracle, Amazon, IBM or SAP. In parallel, several graph query languages have been designed for querying these GDBs, like Cypher for Neo4j, PGQL for Oracle, or GSQL for TigerGraph, which actually are quite similar. This situation has led to propose the creation of a unifying standard for graph query languages. This standard is currently under development, and is called GQL. In a previous paper we defined a logical and an operational semantics for a core language similar to Cypher, showing that the operational semantics is sound and complete with respect to the logical one. However, GQL has gone beyond the expressive power of the above mentioned languages in several senses. Therefore, in the current work, our aim is to redefine the semantics that we gave for Cypher-like languages to a core subset of GQL., This work is partially supported by MCIN/ AEI /10.13039/501100011033 under grant PID2020-112581GB-C21., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

A proposal for an Educational Well-Being Index (EWI) for undergraduate course design

  • Blesa Aguilera, Maria Josep
  • Duch Brown, Amalia
  • Gabarró Vallès, Joaquim
  • Serna Iglesias, María José
Every day it is more common to hear around us about the publication of studies, surveys or statistical results about the well-being of people, workers, women in a given country. Indeed, as university professors, our work cannot be independent of the level of well-being of our students. So, in this work, we propose a methodology to asses the students well-being inside a course implementation by what we call the educational well-being index (EWI). We start with a survey that gathers those factors that computing courses’ students at our university –of two different levels and majors– consider most important. Our second step is the evaluation –by a group of teachers– of the presence of those factors in different educational models of implementation of the courses. We use principal component analysis to extract, from the student data, the valuations that they expressed in the survey: the principal component of their own measurements on well-being. We work only with the coefficients of the first dimension of the principal component. The third step is a (subjective) valuation of the topics addressed in the survey when considering a particular educational model. Finally, we gather everything together to obtain a well-being index of an educational model that allows their comparison. Besides the methodology, we present and analyze the values obtained from our case study., Supported by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION)., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Tight bounds for an accelerated k-means++ algorithm

  • Rodríguez i Corominas, Guillem
  • Blesa Aguilera, Maria Josep
  • Blum, Christian
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 k-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, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Rainbow connectivity of multilayered random geometric graphs

  • Díaz Cort, Josep
  • Diner, Oznur Y.
  • Serra Albó, Oriol
  • Serna Iglesias, María José
An edge-colored multigraph G is rainbow connected if every pair of vertices is joined by at least one rainbow path, i.e., a path where no two edges are of the same color. In the context of multilayered networks, we introduce the notion of multilayered random geometric graphs, from h = 2 independent random geometric graphs G(n,r) on the unit square. We define an edge-coloring by coloring the edges according to the copy of G(n,r) they belong to and study the rainbow connectivity of the resulting edge-colored multigraph. We show that r(n) = lnn nh-1 1/2h , is a threshold of the radius for the property of being rainbow connected. This complements the known analogous results for the multilayered graphs defined on the Erdos–Rényi random model., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Negative learning ant colony optimization for network alignment

  • Rodríguez Corominas, Guillem
  • Blum, Christian
  • Blesa Aguilera, Maria Josep
The Network Alignment problem is a hard Combinatorial Optimization problem with a wide range of applications, especially in computational biology. Given two (or more) networks, the goal is to find a mapping between their respective nodes that preserves the topological and functional structure of the networks. In this work we extend a novel ant colony optimization approach for network alignment by adding a recently proposed Negative Learning mechanism. In particular, information for Negative Learning is obtained by solving sub-instances of the tackled problem instances at each iteration by means of an Integer Linear Programming solver. The results show that the proposed algorithm not only outperforms the standard ant colony optimization approach but also current state-of-the-art methods from the literature., M. Blesa acknowledges support by AGAUR (GENCAT) under grant 2017-SGR-786 (ALBCOM). Moreover, the authors acknowledge support by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION) and grant PID2019-104156GB-I00 (CISUSTAIN)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Affirmative sampling: theory and applications

  • Lumbroso, Jérémie
  • Martínez Parra, Conrado
Affirmative Sampling is a practical and efficient novel algorithm to obtain random samples of distinct elements from a data stream. Its most salient feature is that the size S of the sample will, on expectation, grow with the (unknown) number n of distinct elements in the data stream. As any distinct element has the same probability to be sampled, and the sample size is greater when the “diversity” (the number of distinct elements) is greater, the samples that Affirmative Sampling delivers are more representative than those produced by any scheme where the sample size is fixed a priori - hence its name. Our algorithm is straightforward to implement, and several implementations already exist., 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, and by Princeton University, and its Department of Computer Science., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Take the challenge: compute the CO2e emissions of your programming course

  • Gabarró Vallès, Joaquim
  • Blesa Aguilera, Maria Josep
  • Duch Brown, Amalia
  • Serna Iglesias, María José
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)., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Thresholds as mechanisms for weighting influence in the linear threshold rank

  • Blesa Aguilera, Maria Josep
  • Dominguez Besserer, Alejandro
  • Serna Iglesias, María José
Social networks are the natural space for the spreading of information and influence and have become a media themselves. Several models capturing that diffusion process have been proposed, most of them based on the Independent Cascade (IC) model or on the Linear Threshold (LT) model. The IC model is probabilistic while the LT model relies on the knowledge of an actor to be convinced, reflected in an associated individual threshold. Although the LT-based models contemplate an individual threshold for each actor in the network, the existing studies so far have always considered a threshold of 0.5 equal in all actors (i.e., a simple majority activation criterion). Our main objective in this work is to start the study on how the dissemination of information on networks behaves when we consider other options for setting those thresholds and how many network actors end up being influenced by this dissemination. For doing so, we consider a recently introduced centrality measure based on the LT model, the Forward Linear Threshold Rank (FwLTR), which is the natural interpretation of the Linear Threshold Rank on directed networks. We experimentally analyze the ranking properties for several networks in which the influence resistance threshold follows different schemes. Here we consider three different schemes: (1) uniform, in which all players have the same value; (2) random, where each player is assigned a threshold u.a.r. in a prescribed interval; and (3) determined by the value of another centrality measure on the actor. Our results show that the selection has a clear impact on the ranking, even quite significant and abrupt in some cases. We conclude that the social networks ranks that provide the best assignments for the individual thresholds are FwLTR and the well-known PageRank., Supported by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Relating real and synthetic social networks through centrality measures

  • Blesa Aguilera, Maria Josep
  • Popa, Mihail Eduard
  • Serna Iglesias, María José
We perform here a comparative study on the behaviour of real and synthetic social networks with respect to a selection of nine centrality measures. Some of them are topology based (degree, closeness, betweenness), while others consider the relevance of the actors within the network (Katz, PageRank) or their ability to spread influence through it (Independent Cascade rank, Linear Threshold Rank). We run different experiments on synthetic social networks, with 1K, 10K, and 100K nodes, generated according to the Gaussian Random partition model, the stochastic block model, the LFR benchmark graph model and hyperbolic geometric graphs model. Some real social networks are also considered, with the aim of discovering how do they relate to the synthetic models in terms of centrality. Apart from usual statistical measures, we perform a correlation analysis between all the nine measures. Our results indicate that, in general, the correlation matrices of the different models scale nicely with size. Moreover, the correlation plots distinguish four categories that classify most of the real networks studied here. Those categories have a clear correspondence with particular configurations of the models for synthetic networks., M. Blesa and M. Serna acknowledge support by MICIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21 (MOTION). M.E. Popa was funded by the Ministry of Education and Vocational Training (MEFP) with a student grant (Beca de colaboración, call 2020-2021), Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Continuous query engine to detect anomalous ATM transactions

  • Martín Canfrán, Fernando
  • Benedí García, Daniel
  • Duch Brown, Amalia
  • Pasarella Sánchez, Ana Edelmira
Nowadays data are in motion, change continuously and are –possibly– unbounded implying data sources that are also constantly evolving. From the data persistence point of view this reality breaks the usual paradigm of having dynamic but stable data sources. This, together with the increasing number applications based on data streams for taking critical decisions in real time, raises the need for re-thinking both the data and the query models to fit these new requirements. Therefore, under these circumstances, it seems reasonable that a suitable data model is a continuously evolving data graph. In this work we tackled the problem of querying continuously evolving data graphs in the context of ATM transactions, in particular anomalous ones. Under this context, evaluating continuous queries corresponds to recognize patterns usually associated with anomalous behaviors in the volatile subgraph of ATM transactions. We propose an evaluation process based on the dynamic pipeline computational model, a stream processing technique allowing the emission of alerts as soon as anomalous patterns are identified. Stream based Bank applications that monitor ATM transactions are direct beneficiaries of our proposal since they can continuously query data graphs to get “fresh” data as are produced, avoiding the computational overhead of having to discard non-valid data., This work has been supported by MCIN/AEI/10.13039/501100011033 under grant PID2020-112581GB-C21., Peer Reviewed, Postprint (published version)