Services for data provisioning can be extremely valuable. Organizations wrestle with deciding whether to “expose or not to expose” their data through Web APIs and, depending on the nature of their business, mull over potential benefits and drawbacks. This is because data can be exploited and misused in unanticipated ways. Rate restriction techniques are frequently used to manage data access and protect back-end computing resources. The best choice for the maximum rate at which information can be “safely” provided to clients will determine its effectiveness. An important situation involves formal service-level agreements that govern the quality of services provided by public governments and private businesses. These firms might need to decide on a rate cap for their Web APIs that prevents unauthorized clients from accurately calculating service levels while still enabling the development of valuable value-added services. In this paper, we propose a statistical model for this problem and a technique, based on sampling tools, following brute-force, binary search, and heuristic search methods, to select an appropriate rate limit, and demonstrate its validity through a case study involving a large Italian bus company.

Lorenzo Balzotti, Donatella Firmani, Jerin George Mathew, Riccardo Torlone, Sihem Amer-Yahia. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2025.

The increasing adoption of Large Language Models (LLMs) has significantly lowered technical barriers across various domains, enabling tasks such as code generation, database querying, and service composition. This work explores the potential of LLMs to facilitate human access to heterogeneous data in Cyber-Physical Systems (CPS). The proposed system interprets natural language queries and, by leveraging in-context learning, dynamically synthesizes data integration pipelines that compose data services, thus enabling access to information from multiple sources. The execution of a pipeline generates a table that fulfills the input query, effectively integrating and structuring the retrieved data. This paper presents the design and implementation of the proposed solution and its evaluation using a real-world case study and the BIRD benchmark dataset. The results demonstrate its effectiveness in improving data retrieval, data service design, and execution in CPS.

The problem of estimating the size of a query result has a long history in data management. When the query performs entity resolution (aka record linkage or deduplication), the problem is that of estimating the number of distinct entities, referred to as the entity count. This problem has received attention from the statistics community but it has been largely overlooked in the data management literature. In this work, we formally define the entity count problem from a data management perspective and decompose it into a framework of fundamental steps. We explore approaches from both statistics and data management, systematically identifying a design space for different pipelines that address this problem. Finally, we provide extensive experiments to highlight the strengths and weaknesses of these approaches on real-world benchmarks.

Entity resolution (ER) aims at matching records that refer to the same real-world entity. Although widely studied for the last 50 years, ER still represents a challenging data management problem, and several recent works have started to investigate the opportunity of applying deep learning (DL) techniques to solve this problem. In this paper, we study the fundamental problem of explainability of the DL solution for ER. Understanding the matching predictions of an ER solution is indeed crucial to assess the trustworthiness of the DL model and to discover its biases. We treat the DL model as a black box classifier and - while previous approaches to provide explanations for DL predictions are agnostic to the classification task - we propose the CERTA approach that is aware of the semantics of the ER problem. Our approach produces both saliency explanations, which associate each attribute with a saliency score, and counterfactual explanations, which provide examples of values that can flip the prediction. CERTA builds on a probabilistic framework that aims at computing the explanations evaluating the outcomes produced by using perturbed copies of the input records. We experimentally evaluate CERTA'S explanations of state-of-the-art ER solutions based on DL models using publicly available datasets, and demonstrate the effectiveness of CERTA over recently proposed methods for this problem.

Knowledge assessment in online platforms is widely based on multiple-choice questions (MCQs). In this paper we describe our proposal for a NLP-based system designed to support the management of large repositories of MCQs. Indeed, within large repositories of MCQs, it is common to have similar if not almost duplicated questions, and coping with them is a time consuming and error prone task. We propose an approach, based on Natural Language Processing (NLP), that i) computes the similarity between the items and ii) checks the similarity between the questions and, if available, the areas of the syllabus. The results of the analysis are also displayed in a graph (i.e. network) based view, providing a clear picture to the user.

Link Prediction (LP) aims at tackling Knowledge Graph incompleteness by inferring new, missing facts from the already known ones. The rise of novel Machine Learning techniques has led researchers to develop LP models that represent Knowledge Graph elements as vectors in an embedding space. These models can outperform traditional approaches and they can be employed in multiple downstream tasks; nonetheless, they tend to be opaque, and are mostly regarded as black boxes. Their lack of interpretability limits our understanding of their inner mechanisms, and undermines the trust that users can place in them. In this paper, we propose the novel Kelpie explainability framework. Kelpie can be applied to any embedding-based LP models independently from their architecture, and it explains predictions by identifying the combinations of training facts that have enabled them. Kelpie can extract two complementary types of explanations, that we dub necessary and sufficient. We describe in detail both the structure and the implementation details of Kelpie, and thoroughly analyze its performance through extensive experiments. Our results show that Kelpie significantly outperforms baselines across almost all scenarios.

Recent advances in AI techniques, as well as enabling hardware and infrastructure, has led to the integration of AI in wide-ranging domains and tasks. In particular, AI has been used to handle various types of data (including numerical, textual and graphical data) and has been adopted in large-scale distributed systems. From a data management perspective, this calls for the harnessing of state-of- the-art AI solutions for data management tasks and systems. aiDM is a full-day workshop that offers a stage for innovative interdisciplinary research that studies the interaction between AI and data management and develops new AI technologies for data-related tasks. This year, aiDM'22 particularly focuses on the transparent exploitation of AI techniques in existing enterprise-level data management workloads.

In many applications, entity references (i.e., records) and entities need to be organized to capture diverse relationships like type-subtype, is-A (mapping entities to types), and duplicate (mapping records to entities) relationships. However, automatic identification of such relationships is often inaccurate due to noise and heterogeneous representation of records across sources. Similarly, manual maintenance of these relationships is infeasible and does not scale to large datasets. In this work, we circumvent these challenges by considering weak supervision in the form of an oracle to formulate a novel hierarchical ER task. In this setting, records are clustered in a tree-like structure containing records at leaf-level and capturing record-entity (duplicate), entity-type (is-A) and subtype-supertype relationships. For effective use of supervision, we leverage triplet comparison oracle queries that take three records as input and output the most similar pair(s). We develop HierER, a querying strategy that uses record pair similarities to minimize the number of oracle queries while maximizing the identified hierarchical structure. We show theoretically and empirically that HierER is effective under different similarity noise models and demonstrate empirically that HierER can scale up to million-size datasets.

The latest generations of Link Prediction (LP) models rely on embeddings to tackle incompleteness in Knowledge Graphs, achieving great performance at the cost of interpretability. Their opaqueness limits the trust that users can place in them, hindering their adoption in real-world applications. We have recently introduced Kelpie, an explainability framework tailored specifically for embedding-based LP models. Kelpie can be applied to any embedding-based LP model, and supports two explanation scenarios that we have called necessary and sufficient. In this demonstration we showcase Kelpie's capability to explain the predictions of models based on vastly different architectures on the 5 major datasets in literature.

Entity resolution (ER) aims at identifying record pairs that refer to the same real-world entity. Recent works have focused on deep learning (DL) techniques, to solve this problem. While such works have brought tremendous enhancements in terms of effectiveness in solving the ER problem, understanding their matching predictions is still a challenge, because of the intrinsic opaqueness of DL based solutions. Interpreting and trusting the predictions made by ER systems is crucial for humans in order to employ such methods in decision making pipelines. We demonstrate CERTEM an explanation system for ER based on CERTA, a recently introduced explainability framework for ER, that is able to provide both saliency explanations, which associate each attribute with a saliency score, and counterfactual explanations, which provide examples of values that can flip a prediction. In this demonstration we will showcase how CERTEM can be effectively employed to better understand and debug the behavior of state-of-the-art DL based ER systems on data from publicly available ER benchmarks.

Blocking is a key component of Entity Resolution (ER) that aims to improve efficiency by quickly pruning out non-matching record pairs. However, depending on the noise in the dataset and the distribution of entity cluster sizes, existing techniques can be either (a) too aggressive, such that they help scale but can adversely affect the ER effectiveness, or (b) too permissive, potentially harming ER efficiency. We propose a new methodology of progressive blocking that enables both efficient and effective ER and works across different entity cluster size distributions without manual fine tuning. In this paper, we demonstrate BEER (Blocking for Effective Entity Resolution), the first end-to-end system that leverages intermediate ER output in a feedback loop to refine the blocking result in a data-driven fashion, thereby enabling effective entity resolution. BEER allows the user to explore the different components of the ER pipeline, analyze the effectiveness of alternative blocking techniques and understand the interaction between blocking and ER. BEER supports visualization of the different entities present in a block, explains the change in blocking output with every round of feedback and allows the end-user to interactively compare different techniques. BEER has been developed as open-source software; the code and the demonstration video are available at beer-system.github.io.

Abstract We focus on the automatic detection of communities in large networks, a challenging problem in many disciplines (such as sociology, biology, and computer science). Humans tend to associate to form families, villages, and nations. Similarly, the elements of real-world networks naturally tend to form highly connected groups. A popular model to represent such structures is the clique, that is, a set of fully interconnected nodes. However, it has been observed that cliques are too strict to represent communities in practice. The k-plex relaxes the notion of clique, by allowing each node to miss up to k connections. Although k-plexes are more flexible than cliques, finding them is more challenging as their number is greater. In addition, most of them are small and not significant. In this paper we tackle the problem of finding only large k-plexes (i.e., comparable in size to the largest clique) and design a meta-algorithm that can be used on top of known enumeration algorithms to return only significant k-plexes in a fraction of the time. Our approach relies on: (1) methods for strongly reducing the search space and (2) decomposition techniques based on the efficient computation of maximal cliques. We demonstrate experimentally that known enumeration algorithms equipped with our approach can run orders of magnitude faster than full enumeration.

Knowledge Graphs (KGs) have found many applications in industrial and in academic settings, which in turn, have motivated considerable research efforts towards large-scale information extraction from a variety of sources. Despite such efforts, it is well known that even the largest KGs suffer from incompleteness; Link Prediction (LP) techniques address this issue by identifying missing facts among entities already in the KG. Among the recent LP techniques, those based on KG embeddings have achieved very promising performance in some benchmarks. Despite the fast-growing literature on the subject, insufficient attention has been paid to the effect of the design choices in those methods. Moreover, the standard practice in this area is to report accuracy by aggregating over a large number of test facts in which some entities are vastly more represented than others; this allows LP methods to exhibit good results by just attending to structural properties that include such entities, while ignoring the remaining majority of the KG. This analysis provides a comprehensive comparison of embedding-based LP methods, extending the dimensions of analysis beyond what is commonly available in the literature. We experimentally compare the effectiveness and efficiency of 18 state-of-the-art methods, consider a rule-based baseline, and report detailed analysis over the most popular benchmarks in the literature.

We present a novel approach for the detection of 2-plexes, a popular relaxation of cliques used for modeling network communities. Specifically, with the purpose of identifying theoretically sound methods for community detection on a large scale, we introduce the first shared-nothing distributed algorithm for this problem. This result opens a new research direction for scalable community detection. Our proposal has three main ingredients: (i) we reduce the problem of finding 2-plexes to that of finding cliques; (ii) we leverage known algorithms for fast computation of cliques; (iii) we exploit a decomposition technique for a distributed shared-nothing computation. Preliminary experiments on a 10-nodes cluster running Spark confirm the effectiveness of our approach.

The technological foundation of smart manufacturing consists of cyber-physical systems and the Internet-of-Things (IoT). Each IoT device in a smart factory can be coupled with a digital twin, that is, a dynamic virtual representation of the physical system across its life-cycle using real-time sensor data. Currently, the manufacturing process itself, the involved devices, and how they interact, is designed by human experts in a traditional way. We envision an architecture where humans can instead specify a goal and take advantage of technologies such as digital twins to automatically compose the corresponding physical processes, sharing some analogies with the notion of Web service composition.

Data-provisioning services can provide high value. Since data can be used and misused in unpredictable ways, organizations deal with the dilemma "to expose or not to expose" their data through Web APIs and - depending on the nature of their business - ponder possible opportunities and pitfalls. Rate limiting strategies are widely employed to control access to data and to safeguard back-end computational resources. However, their effectiveness depends on a good choice of the maximum allowed rate at which information can be "safely" released to users. A relevant scenario is represented by public administrations and private companies providing services whose quality is regulated by formal business agreements on the service levels. These organizations may need to choose a rate limit for their Web APIs that prevent unauthorized users to compute service levels with an high confidence while still allowing the creation of useful value-added services. In this paper, we propose a general statistical model for this problem and a technique, based on uniform sampling tools, to select an appropriate rate limit, and we demonstrate its validity through a case study involving a large bus company.

In Codice Ratio is a research project to study tools and techniques for analyzing the contents of historical documents conserved in the Vatican Secret Archives (VSA). In this paper, we present our efforts to develop a system to support the transcription of medieval manuscripts. The goal is to provide paleographers with a tool to reduce their efforts in transcribing large volumes, as those stored in the VSA, producing good transcriptions for significant portions of the manuscripts. We propose an original approach based on character segmentation. Our solution is able to deal with the dirty segmentation that inevitably occurs in handwritten documents. We use a convolutional neural network to recognize characters, and statistical language models to compose word transcriptions. Our approach requires minimal training effort, making the transcription process more scalable, as the production of training sets requires a few pages and can be easily crowdsourced. We have conducted experiments on manuscripts from the Vatican Registers, an unreleased corpus containing the correspondence of the popes. With training data produced by 120 high school students, our system has been able to produce good transcriptions that can be used by paleographers as a solid basis to speedup the transcription process at a large scale.

Entity resolution (ER) seeks to identify which records in a data set refer to the same real-world entity. Given the diversity of ways in which entities can be represented, matched and distinguished, ER is known to be a challenging task for automated strategies, but relatively easier for expert humans. In our work, we abstract the knowledge of experts with the notion of a binary oracle. Our oracle can answer questions of the form "do records u and v refer to the same entity?" under a flexible error model, allowing for some questions to be more difficult to answer correctly than others.

K-plexes are a formal yet flexible way of defining communities in networks. They generalize the notion of cliques and are more appropriate in most real cases: while a node of a clique C is connected to all other nodes of C, a node of a k-plex may miss up to k connections. Unfortunately, computing all maximal k-plexes is a gruesome task and state-of-the-art algorithms can only process small-size networks. In this paper we propose a new approach for enumerating large k-plexes in networks that speeds up the search by several orders of magnitude, leveraging on (i) methods for strongly reducing the search space and (ii) efficient techniques for the computation of maximal cliques. Several experiments show that our strategy is effective and is able to increase the size of the networks for which the computation of large k-plexes is feasible from a few hundred to several hundred thousand nodes.

In this paper, we discuss the application of concept of data quality to big data by highlighting how much complex is to define it in a general way. Already data quality is a multidimensional concept, difficult to characterize in precise definitions even in the case of well-structured data. Big data add two further dimensions of complexity: (i) being “ very ” source specific , and for this we adopt the interesting UNECE classification, and (ii) being highly unstructured and schema-less , often without golden standards to refer to or very difficult to access. After providing a tutorial on data quality in traditional contexts, we analyze big data by providing insights into the UNECE classification, and then, for each type of data source, we choose a specific instance of such a type (notably deep Web data, sensor-generated data, and Twitters/short texts) and discuss how quality dimensions can be defined in these cases. The overall aim of the paper is therefore to identify further research directions in the area of big data quality, by providing at the same time an up-to-date state of the art on data quality.

Entity resolution (ER) is the task of identifying all records in a database that refer to the same underlying entity. This is an expensive task, and can take a significant amount of money and time; the end-user may want to take decisions during the process, rather than waiting for the task to be completed. We formalize an online version of the entity resolution task, and use an oracle which correctly labels matching and non-matching pairs through queries. In this setting, we design algorithms that seek to maximize progressive recall, and develop a novel analysis framework for prior proposals on entity resolution with an oracle, beyond their worst case guarantees. Finally, we provide both theoretical and experimental analysis of the proposed algorithms.

The problem of building an ℓ0-sampler is to sample near-uniformly from the support set of a dynamic multiset. This problem has a variety of applications within data analysis, computational geometry and graph algorithms. In this paper, we abstract a set of steps for building an ℓ0-sampler, based on sampling, recovery and selection. We analyze the implementation of an ℓ0-sampler within this framework, and show how prior constructions of ℓ0-samplers can all be expressed in terms of these steps. Our experimental contribution is to provide a first detailed study of the accuracy and computational cost of ℓ0-samplers.

Current route planning algorithms for public transport networks are mostly based on timetable information only, i.e., they compute shortest routes under the assumption that all transit vehicles (e.g., buses, subway trains) will incur in no delays throughout their trips. Unfortunately, unavoidable and unexpected delays often prevent transit vehicles to respect their originally planned schedule. In this paper, we try to measure empirically the quality of the solutions offered by timetabling routing in a real public transport network, where unpredictable delays may happen with a certain frequency, such as the public transport network of the metropolitan area of Rome. To accomplish this task, we take the time estimates required for trips provided by a timetabling-based route planner (such as Google Transit) and compare them against the times taken by the trips according to the actual tracking of transit vehicles in the transport network, measured through the GPS data made available by the transit agency. In our experiments, the movement of transit vehicles was only mildly correlated to the timetable, giving strong evidence that in such a case timetabled routing may fail to deliver optimal or even high-quality solutions.

The betweenness centrality of a node is a measure related to the number of shortest path the node is involved with. It is, indeed, a measure of the importance of the node in the network, and in the recent years has been used intensively for network analysis. The major drawback of this measure is its high computational cost, and thus in the literature several works appeared providing ways of approximating it, thus presenting a trade off between accuracy and speed. The articulation points of a connected network are the nodes whose removal disconnects the network, and the critical nodes are the articulation points of the network core, i.e. the subset of the network obtained by repeatedly pruning the nodes of low (fixed) degree. In [1] Ausiello et al. showed that, in ten years of samples of the Autonomous System (AS) Network, the removal of a single critical node from the network was able to affect hundreds of nodes, that were no longer connected to the main part of the AS Network.

The articulation points and bridges of a connected network are, respectively, the vertices and the edges whose removal disconnects the network. However, not all the articulation points (resp. bridges) are equal: from the graph theoretic perspective, there is no difference whether the removal of a vertex (resp. bridge) disconnects only one vertex from the rest of the network, or it cuts the network in two pieces. But in the monitoring of a huge network, it makes a difference. We present a real-time algorithm, analyzed in the (semi-)streaming model of computation, that is able to identify a core subset of the articulation points (resp. bridges), i.e. the ones whose removal has a big impact on the network: these are the critical nodes (resp. edges) of the network. We complement our work with an experimental evaluation of the algorithm against ten years of samples of the Autonomous System network, that confirms the effectiveness of our approach.

Calling context trees are one of the most fundamental data structures for representing the interprocedural control flow of a program, providing valuable information for program understanding and optimization. Nodes of a calling context tree associate performance metrics to whole distinct paths in the call graph starting from the root function. However, no explicit information is provided for detecting short hot sequences of activations, which may be a better optimization target in large modular programs where groups of related functions are reused in many different parts of the code. Furthermore, calling context trees can grow prohibitively large in some scenarios. Another classical approach, called edge profiling, collects performance metrics for caller-callee pairs in the call graph, allowing it to detect hot paths of fixed length one. We study a generalization of edge and context-sensitive profiles by introducing a novel data structure called k-calling context forest (k-CCF). Nodes in a k-CCF associate performance metrics to paths of length at most k that lead to each distinct routine of the program, providing edge profiles for k=1, full context-sensitive profiles for k equal to infinity, as well as any other intermediate point in the spectrum. We study the properties of the k-CCF both theoretically and experimentally on a large suite of prominent Linux applications, showing how to construct it efficiently and discussing its relationships with the calling context tree. Our experiments show that the k-CCF can provide effective space-accuracy tradeoffs for interprocedural contextual profiling, yielding useful clues to the hot spots of a program that may be hidden in a calling context tree and using less space for small values of k, which appear to be the most interesting in practice.

Abstract In this article, we present the first algorithm in the streaming model to characterize completely the biconnectivity properties of undirected networks: articulation points, bridges, and connected and biconnected components. The motivation of our work was the development of a real‐time algorithm to monitor the connectivity of the autonomous systems (AS) network, but the solution provided is general enough to be applied to any network. The network structure is represented by a graph, and the algorithm is analyzed in the datastream framework. Here, as in the on‐line model, the input graph is revealed one item (i.e., graph edge) after the other, in an on‐line fashion; but, if compared to traditional on‐line computation, there are stricter requirements for both memory occupation and per item processing time. Our algorithm works by properly updating a forest over the graph nodes. All the graph (bi)connectivity properties are stored in this forest. We prove the correctness of the algorithm, together with its space (O(nlog n), with n being the number of nodes in the graph) and time bounds. We also present the results of a brief experimental evaluation against real‐world graphs, including many samples of the AS network, ranging from medium to massive size. These preliminary experimental results confirm the effectiveness of our approach. © 2012 Wiley Periodicals, Inc. NETWORKS, Vol. 2012

The structural analysis is the very basic tool for understanding the properties of a network. In this paper we present a (customizable) tool, able to compute in real-time the most important connectivity properties of a network, modeled as an undirected graph: connected and biconnected components, articulation points and bridges. The algorithm underlying the tool has been theoretically analyzed in the (semi-)streaming model, and has been tested with graphs up to hundreds of millions nodes and billions edges. The tool, therefore, can be employed to monitor traffic flows in medium and large networks, at real-time, and detect possible anomalies. As an application, we provide results about the structural properties of ten years of samples of the Autonomous System network, obtained from the Univ. of Oregon Route Views project, that (once again) shows the ubiquitous presence of power-law distribution.