2024
Journal article
Open Access
Fulgor: a fast and compact k-mer index for large-scale matching and color queries
Fan J., Khan J., Pratap Singh N., Pibiri G. E., Patro R.
The problem of sequence identification or matching--determining the subset of reference sequences from a given collection that are likely to contain a short, queried nucleotide sequence--is relevant for many important tasks in Computational Biology, such as metagenomics and pangenome analysis. Due to the complex nature of such analyses and the large scale of the reference collections a resource-efficient solution to this problem is of utmost importance. This poses the threefold challenge of representing the reference collection with a data structure that is efficient to query, has light memory usage, and scales well to large collections. To solve this problem, we describe an efficient colored de Bruijn graph index, arising as the combination of a k-mer dictionary with a compressed inverted index. The proposed index takes full advantage of the fact that unitigs in the colored compacted de Bruijn graph are monochromatic (i.e., all k-mers in a unitig have the same set of references of origin, or color). Specifically, the unitigs are kept in the dictionary in color order, thereby allowing for the encoding of the map from k-mers to their colors in as little as 1 + o(1) bits per unitig. Hence, one color per unitig is stored in the index with almost no space/time overhead. By combining this property with simple but effective compression methods for integer lists, the index achieves very small space. We implement these methods in a tool called Fulgor, and conduct an extensive experimental analysis to demonstrate the improvement of our tool over previous solutions. For example, compared to Themisto--the strongest competitor in terms of index space vs. query time trade-off--Fulgor requires significantly less space (up to 43% less space for a collection of 150,000 Salmonella enterica genomes), is at least twice as fast for color queries, and is 2-6× faster to construct.Source: Algorithms for molecular biology 19 (2024). doi:10.1186/s13015-024-00251-9
DOI: 10.1186/s13015-024-00251-9
Metrics:
Fan J., Khan J., Pratap Singh N., Pibiri G. E., Patro R.
The problem of sequence identification or matching--determining the subset of reference sequences from a given collection that are likely to contain a short, queried nucleotide sequence--is relevant for many important tasks in Computational Biology, such as metagenomics and pangenome analysis. Due to the complex nature of such analyses and the large scale of the reference collections a resource-efficient solution to this problem is of utmost importance. This poses the threefold challenge of representing the reference collection with a data structure that is efficient to query, has light memory usage, and scales well to large collections. To solve this problem, we describe an efficient colored de Bruijn graph index, arising as the combination of a k-mer dictionary with a compressed inverted index. The proposed index takes full advantage of the fact that unitigs in the colored compacted de Bruijn graph are monochromatic (i.e., all k-mers in a unitig have the same set of references of origin, or color). Specifically, the unitigs are kept in the dictionary in color order, thereby allowing for the encoding of the map from k-mers to their colors in as little as 1 + o(1) bits per unitig. Hence, one color per unitig is stored in the index with almost no space/time overhead. By combining this property with simple but effective compression methods for integer lists, the index achieves very small space. We implement these methods in a tool called Fulgor, and conduct an extensive experimental analysis to demonstrate the improvement of our tool over previous solutions. For example, compared to Themisto--the strongest competitor in terms of index space vs. query time trade-off--Fulgor requires significantly less space (up to 43% less space for a collection of 150,000 Salmonella enterica genomes), is at least twice as fast for color queries, and is 2-6× faster to construct.Source: Algorithms for molecular biology 19 (2024). doi:10.1186/s13015-024-00251-9
DOI: 10.1186/s13015-024-00251-9
Metrics:
See at:
almob.biomedcentral.com 
| ISTI Repository | CNR ExploRA
2023
Conference article
Open Access
GAM Forest explanation
Lucchese C., Orlando S., Perego R., Veneri A.
Most accurate machine learning models unfortunately produce black-box predictions, for which it is impossible to grasp the internal logic that leads to a specific decision. Unfolding the logic of such black-box models is of increasing importance, especially when they are used in sensitive decision-making processes. In thisworkwe focus on forests of decision trees, which may include hundreds to thousands of decision trees to produce accurate predictions. Such complexity raises the need of developing explanations for the predictions generated by large forests.We propose a post hoc explanation method of large forests, named GAM-based Explanation of Forests (GEF), which builds a Generalized Additive Model (GAM) able to explain, both locally and globally, the impact on the predictions of a limited set of features and feature interactions.We evaluate GEF over both synthetic and real-world datasets and show that GEF can create a GAM model with high fidelity by analyzing the given forest only and without using any further information, not even the initial training dataset.Source: EDBT 2022 - 26th International Conference on Extending Database Technology, pp. 171–182, Ioannina, Greece, 28-31/03/2023
DOI: 10.48786/edbt.2023.14
Metrics:
Lucchese C., Orlando S., Perego R., Veneri A.
Most accurate machine learning models unfortunately produce black-box predictions, for which it is impossible to grasp the internal logic that leads to a specific decision. Unfolding the logic of such black-box models is of increasing importance, especially when they are used in sensitive decision-making processes. In thisworkwe focus on forests of decision trees, which may include hundreds to thousands of decision trees to produce accurate predictions. Such complexity raises the need of developing explanations for the predictions generated by large forests.We propose a post hoc explanation method of large forests, named GAM-based Explanation of Forests (GEF), which builds a Generalized Additive Model (GAM) able to explain, both locally and globally, the impact on the predictions of a limited set of features and feature interactions.We evaluate GEF over both synthetic and real-world datasets and show that GEF can create a GAM model with high fidelity by analyzing the given forest only and without using any further information, not even the initial training dataset.Source: EDBT 2022 - 26th International Conference on Extending Database Technology, pp. 171–182, Ioannina, Greece, 28-31/03/2023
DOI: 10.48786/edbt.2023.14
Metrics:
See at:
ISTI Repository | openproceedings.org | CNR ExploRA
2023
Conference article
Open Access
Spectrum preserving tilings enable sparse and modular reference indexing
Fan J., Khan J., Pibiri G. E., Patro R.
The reference indexing problem for -mers is to pre-process a collection of reference genomic sequences so that the position of all occurrences of any queried -mer can be rapidly identified. An efficient and scalable solution to this problem is fundamental for many tasks in bioinformatics. In this work, we introduce the spectrum preserving tiling (SPT), a general representation of that specifies how a set of tiles repeatedly occur to spell out the constituent reference sequences in. By encoding the order and positions where tiles occur, SPTs enable the implementation and analysis of a general class of modular indexes. An index over an SPT decomposes the reference indexing problem for -mers into: (1) a -mer-to-tile mapping; and (2) a tile-to-occurrence mapping. Recently introduced work to construct and compactly index -mer sets can be used to efficiently implement the -mer-to-tile mapping. However, implementing the tile-to-occurrence mapping remains prohibitively costly in terms of space. As reference collections become large, the space requirements of the tile-to-occurrence mapping dominates that of the -mer-to-tile mapping since the former depends on the amount of total sequence while the latter depends on the number of unique -mers in. To address this, we introduce a class of sampling schemes for SPTs that trade off speed to reduce the size of the tile-to-reference mapping. We implement a practical index with these sampling schemes in the tool pufferfish2. When indexing over 30,000 bacterial genomes, pufferfish2 reduces the size of the tile-to-occurrence mapping from 86.3 GB to 34.6 GB while incurring only a 3.6 slowdown when querying -mers from a sequenced readset. Availability: pufferfish2 is implemented in Rust and available at https://github.com/COMBINE-lab/pufferfish2.Source: RECOMB 2023 - 27th International Conference on Research in Computational Molecular Biology, pp. 21–40, Istanbul, Turkey, 16-19/04/2023
DOI: 10.1007/978-3-031-29119-7_2
Project(s): MobiDataLab
Metrics:
Fan J., Khan J., Pibiri G. E., Patro R.
The reference indexing problem for -mers is to pre-process a collection of reference genomic sequences so that the position of all occurrences of any queried -mer can be rapidly identified. An efficient and scalable solution to this problem is fundamental for many tasks in bioinformatics. In this work, we introduce the spectrum preserving tiling (SPT), a general representation of that specifies how a set of tiles repeatedly occur to spell out the constituent reference sequences in. By encoding the order and positions where tiles occur, SPTs enable the implementation and analysis of a general class of modular indexes. An index over an SPT decomposes the reference indexing problem for -mers into: (1) a -mer-to-tile mapping; and (2) a tile-to-occurrence mapping. Recently introduced work to construct and compactly index -mer sets can be used to efficiently implement the -mer-to-tile mapping. However, implementing the tile-to-occurrence mapping remains prohibitively costly in terms of space. As reference collections become large, the space requirements of the tile-to-occurrence mapping dominates that of the -mer-to-tile mapping since the former depends on the amount of total sequence while the latter depends on the number of unique -mers in. To address this, we introduce a class of sampling schemes for SPTs that trade off speed to reduce the size of the tile-to-reference mapping. We implement a practical index with these sampling schemes in the tool pufferfish2. When indexing over 30,000 bacterial genomes, pufferfish2 reduces the size of the tile-to-occurrence mapping from 86.3 GB to 34.6 GB while incurring only a 3.6 slowdown when querying -mers from a sequenced readset. Availability: pufferfish2 is implemented in Rust and available at https://github.com/COMBINE-lab/pufferfish2.Source: RECOMB 2023 - 27th International Conference on Research in Computational Molecular Biology, pp. 21–40, Istanbul, Turkey, 16-19/04/2023
DOI: 10.1007/978-3-031-29119-7_2
Project(s): MobiDataLab
Metrics:
See at:
link.springer.com | ISTI Repository | CNR ExploRA
2023
Journal article
Open Access
Roads, rails, and checkpoints: assessing the permeability of nation-state borders worldwide
Deutschmann E., Gabrielli L., Recchi E.
The permeability of nation-state borders determines the flow of people and commodities between countries and therefore greatly influences many aspects of human development from trade and economic inequality to migration and the ethnic composition of societies worldwide. While past research on the topic has focused on border fortification (walls, fences, etc.) or the legal dimension of border controls, we take a different approach by arguing that transport infrastructure (paths, roads, railroads, ferries) together with political checkpoints can be used as valuable indicators for the permeability of borders worldwide. More and better transport infrastructure increases permeability, whereas checkpoints create the political capacity for reducing entries. Using automatized computational methods combined with extensive manual checks, we parse data from OpenStreetMap and the World Food Programme to detect cross-border transport infrastructure and checkpoints. Based on this information, we define an index of border permeability for 312 land borders globally. Subsequent analyses show that regardless of the degree of closure enforcement at checkpoints, Europe and Africa have the most, and the Americas the least, permeable borders worldwide. Regression models reveal that border permeability is higher in densely populated areas and that economic development, by far the most relevant explanatory factor, has a curvilinear relationship with border permeability: Borders of very rich and very poor countries are highly permeable, whereas those of moderately prosperous nation-states are significantly harder to cross. Implications of this remarkably clear pattern are discussed.Source: World development 164 (2023). doi:10.1016/j.worlddev.2022.106175
DOI: 10.1016/j.worlddev.2022.106175
Metrics:
Deutschmann E., Gabrielli L., Recchi E.
The permeability of nation-state borders determines the flow of people and commodities between countries and therefore greatly influences many aspects of human development from trade and economic inequality to migration and the ethnic composition of societies worldwide. While past research on the topic has focused on border fortification (walls, fences, etc.) or the legal dimension of border controls, we take a different approach by arguing that transport infrastructure (paths, roads, railroads, ferries) together with political checkpoints can be used as valuable indicators for the permeability of borders worldwide. More and better transport infrastructure increases permeability, whereas checkpoints create the political capacity for reducing entries. Using automatized computational methods combined with extensive manual checks, we parse data from OpenStreetMap and the World Food Programme to detect cross-border transport infrastructure and checkpoints. Based on this information, we define an index of border permeability for 312 land borders globally. Subsequent analyses show that regardless of the degree of closure enforcement at checkpoints, Europe and Africa have the most, and the Americas the least, permeable borders worldwide. Regression models reveal that border permeability is higher in densely populated areas and that economic development, by far the most relevant explanatory factor, has a curvilinear relationship with border permeability: Borders of very rich and very poor countries are highly permeable, whereas those of moderately prosperous nation-states are significantly harder to cross. Implications of this remarkably clear pattern are discussed.Source: World development 164 (2023). doi:10.1016/j.worlddev.2022.106175
DOI: 10.1016/j.worlddev.2022.106175
Metrics:
See at:
World Development | ISTI Repository | www.sciencedirect.com | CNR ExploRA
2023
Contribution to conference
Open Access
Preface to the Proceedings of the 1st International Workshop on Computational Intelligence for Process Mining (CI4PM 2022) and 1st International Workshop on Pervasive Artificial Intelligence (PAI 2022)
Pegoraro M., Bacciu D., Burattin A., Carta A., Dazzi P., De Leoni M., Eirinaki M., Varlamis I.
This CEUR-WS volume contains the joint proceedings of two workshops on the domain of computational intelligence: the first International Workshop on Computational Intelligence for Process Mining (CI4PM 2022) and the first International Workshop on Pervasive Artificial Intelligence (PAI 2022). Both events were co-located with the fortieth IEEE International Joint Conference on Neural Networks (IJCNN 2022), organized within the twelfth IEEE World Congress on Computational Intelligence (WCCI 2022). The University of Padua (Università degli Studi di Padova) served as the hosting institution for WCCI 2022, which took place between the 18?? and the 23?? of July 2022 in Padua, Italy. The accepted papers of CI4PM were presented on the 18?? of July, while accepted papers of PAI were presented on the 19?? of July. Additional information on the individual events, accepted papers, and the respective committees can be found on the following pages.
Pegoraro M., Bacciu D., Burattin A., Carta A., Dazzi P., De Leoni M., Eirinaki M., Varlamis I.
This CEUR-WS volume contains the joint proceedings of two workshops on the domain of computational intelligence: the first International Workshop on Computational Intelligence for Process Mining (CI4PM 2022) and the first International Workshop on Pervasive Artificial Intelligence (PAI 2022). Both events were co-located with the fortieth IEEE International Joint Conference on Neural Networks (IJCNN 2022), organized within the twelfth IEEE World Congress on Computational Intelligence (WCCI 2022). The University of Padua (Università degli Studi di Padova) served as the hosting institution for WCCI 2022, which took place between the 18?? and the 23?? of July 2022 in Padua, Italy. The accepted papers of CI4PM were presented on the 18?? of July, while accepted papers of PAI were presented on the 19?? of July. Additional information on the individual events, accepted papers, and the respective committees can be found on the following pages.
See at:
ceur-ws.org | ISTI Repository | CNR ExploRA
2023
Journal article
Open Access
Data-aware declarative application management in the cloud-IoT continuum
Massa J., Forti S., Dazzi P., Brogi A.
Nowadays billions of devices are connected to the Internet of Things and can reach computing facilities along the Cloud-IoT continuum to process the data they produce, leading to a dramatic increase in the number of deployed applications as well as in the amount of data they need to crunch. Following a continuous reasoning approach to speed up the decision-making process, our research proposes a declarative and data-aware solution to determine service-based application placements over the Cloud-IoT continuum while meeting functional and non-functional application requirements.Source: ERCIM news (2023): 35–36.
Massa J., Forti S., Dazzi P., Brogi A.
Nowadays billions of devices are connected to the Internet of Things and can reach computing facilities along the Cloud-IoT continuum to process the data they produce, leading to a dramatic increase in the number of deployed applications as well as in the amount of data they need to crunch. Following a continuous reasoning approach to speed up the decision-making process, our research proposes a declarative and data-aware solution to determine service-based application placements over the Cloud-IoT continuum while meeting functional and non-functional application requirements.Source: ERCIM news (2023): 35–36.
See at:
ercim-news.ercim.eu | ISTI Repository | CNR ExploRA
2023
Conference article
Open Access
A general methodology for building multiple aspect trajectories
Lettich F., Pugliese C., Renso C., Pinelli F.
The massive use of personal location devices, the Internet of Mobile Things, and Location Based Social Networks, enables the collection of vast amounts of movement data. Such data can be enriched with several semantic dimensions (or aspects), i.e., contextual and heterogeneous information captured in the surrounding environment, leading to the creation of multiple aspect trajectories (MATs). In this work, we present how the MAT-Builder system can be used for the semantic enrichment processing of movement data while being agnostic to aspects and external semantic data sources. This is achieved by integrating MAT-Builder into a methodology which encompasses three design principles and a uniform representation formalism for enriched data based on the Resource Description Framework (RDF) format. An example scenario involving the generation and querying of a dataset of MATs gives a glimpse of the possibilities that our methodology can open up.Source: SAC 2023 - 38th ACM/SIGAPP Symposium on Applied Computing, pp. 515–517, Tallinn, Estonia, 27-31/03/2023
DOI: 10.1145/3555776.3577832
Project(s): MobiDataLab, MASTER , SoBigData-PlusPlus
Metrics:
Lettich F., Pugliese C., Renso C., Pinelli F.
The massive use of personal location devices, the Internet of Mobile Things, and Location Based Social Networks, enables the collection of vast amounts of movement data. Such data can be enriched with several semantic dimensions (or aspects), i.e., contextual and heterogeneous information captured in the surrounding environment, leading to the creation of multiple aspect trajectories (MATs). In this work, we present how the MAT-Builder system can be used for the semantic enrichment processing of movement data while being agnostic to aspects and external semantic data sources. This is achieved by integrating MAT-Builder into a methodology which encompasses three design principles and a uniform representation formalism for enriched data based on the Resource Description Framework (RDF) format. An example scenario involving the generation and querying of a dataset of MATs gives a glimpse of the possibilities that our methodology can open up.Source: SAC 2023 - 38th ACM/SIGAPP Symposium on Applied Computing, pp. 515–517, Tallinn, Estonia, 27-31/03/2023
DOI: 10.1145/3555776.3577832
Project(s): MobiDataLab
, MASTER , SoBigData-PlusPlus Metrics:
See at:
ISTI Repository | dl.acm.org 
| CNR ExploRA
2023
Journal article
Open Access
On weighted k-mer dictionaries
Pibiri G. E.
We consider the problem of representing a set of k-mers and their abundance counts, or weights, in compressed space so that assessing membership and retrieving the weight of a k-mer is efficient. The representation is called a weighted dictionary of k-mers and finds application in numerous tasks in Bioinformatics that usually count k-mers as a pre-processing step. In fact, k-mer counting tools produce very large outputs that may result in a severe bottleneck for subsequent processing. In this work we extend the recently introduced SSHash dictionary (Pibiri in Bioinformatics 38:185-194, 2022) to also store compactly the weights of the k-mers. From a technical perspective, we exploit the order of the k-mers represented in SSHash to encode runs of weights, hence allowing much better compression than the empirical entropy of the weights. We study the problem of reducing the number of runs in the weights to improve compression even further and give an optimal algorithm for this problem. Lastly, we corroborate our findings with experiments on real-world datasets and comparison with competitive alternatives. Up to date, SSHash is the only k-mer dictionary that is exact, weighted, associative, fast, and small.Source: Algorithms for molecular biology 18 (2023). doi:10.1186/s13015-023-00226-2
DOI: 10.1186/s13015-023-00226-2
Metrics:
Pibiri G. E.
We consider the problem of representing a set of k-mers and their abundance counts, or weights, in compressed space so that assessing membership and retrieving the weight of a k-mer is efficient. The representation is called a weighted dictionary of k-mers and finds application in numerous tasks in Bioinformatics that usually count k-mers as a pre-processing step. In fact, k-mer counting tools produce very large outputs that may result in a severe bottleneck for subsequent processing. In this work we extend the recently introduced SSHash dictionary (Pibiri in Bioinformatics 38:185-194, 2022) to also store compactly the weights of the k-mers. From a technical perspective, we exploit the order of the k-mers represented in SSHash to encode runs of weights, hence allowing much better compression than the empirical entropy of the weights. We study the problem of reducing the number of runs in the weights to improve compression even further and give an optimal algorithm for this problem. Lastly, we corroborate our findings with experiments on real-world datasets and comparison with competitive alternatives. Up to date, SSHash is the only k-mer dictionary that is exact, weighted, associative, fast, and small.Source: Algorithms for molecular biology 18 (2023). doi:10.1186/s13015-023-00226-2
DOI: 10.1186/s13015-023-00226-2
Metrics:
See at:
almob.biomedcentral.com | ISTI Repository | CNR ExploRA
2023
Journal article
Open Access
Matchtigs: minimum plain text representation of k-mer sets
Schmidt S., Khan S., Alanko J. N., Pibiri G. E., Tomescu A. I.
We propose a polynomial algorithm computing a minimum plain-text representation of k-mer sets, as well as an efficient near-minimum greedy heuristic. When compressing read sets of large model organisms or bacterial pangenomes, with only a minor runtime increase, we shrink the representation by up to 59% over unitigs and 26% over previous work. Additionally, the number of strings is decreased by up to 97% over unitigs and 90% over previous work. Finally, a small representation has advantages in downstream applications, as it speeds up SSHash-Lite queries by up to 4.26× over unitigs and 2.10× over previous work.Source: Genome biology (Online) 24 (2023). doi:10.1186/s13059-023-02968-z
DOI: 10.1186/s13059-023-02968-z
Project(s): MobiDataLab, SAFEBIO
Metrics:
Schmidt S., Khan S., Alanko J. N., Pibiri G. E., Tomescu A. I.
We propose a polynomial algorithm computing a minimum plain-text representation of k-mer sets, as well as an efficient near-minimum greedy heuristic. When compressing read sets of large model organisms or bacterial pangenomes, with only a minor runtime increase, we shrink the representation by up to 59% over unitigs and 26% over previous work. Additionally, the number of strings is decreased by up to 97% over unitigs and 90% over previous work. Finally, a small representation has advantages in downstream applications, as it speeds up SSHash-Lite queries by up to 4.26× over unitigs and 2.10× over previous work.Source: Genome biology (Online) 24 (2023). doi:10.1186/s13059-023-02968-z
DOI: 10.1186/s13059-023-02968-z
Project(s): MobiDataLab
, SAFEBIO Metrics:
See at:
genomebiology.biomedcentral.com | ISTI Repository | CNR ExploRA
2023
Journal article
Open Access
Locality-preserving minimal perfect hashing of k-mers
Pibiri G. E., Shibuya Y., Limasset A.
Motivation: Minimal perfect hashing is the problem of mapping a static set of n distinct keys into the address space {1, ... , n} bijectively. It is well-known that n log2(e) bits are necessary to specify a minimal perfect hash function (MPHF) f, when no additional knowledge of the input keys is to be used. However, it is often the case in practice that the input keys have intrinsic relationships that we can exploit to lower the bit complexity of f. For example, consider a string and the set of all its distinct k-mers as input keys: since two consecutive k-mers share an overlap of k - 1 symbols, it seems possible to beat the classic log2(e) bits/key barrier in this case. Moreover, we would like f to map consecutive k-mers to consecutive addresses, as to also preserve as much as possible their relationship in the codomain. This is a useful feature in practice as it guarantees a certain degree of locality of reference for f, resulting in a better evaluation time when querying consecutive k-mers.Results: Motivated by these premises, we initiate the study of a new type of locality-preserving MPHF designed for k-mers extracted consecutively from a collection of strings. We design a construction whose space usage decreases for growing k and discuss experiments with a practical implementation of the method: in practice, the functions built with our method can be several times smaller and even faster to query than the most efficient MPHFs in the literature.Code Availability: https://github.com/jermp/lphashData Availability: https://zenodo.org/record/7239205Source: Bioinformatics (Oxf., Online) 39 (2023): i534–i543. doi:10.1093/bioinformatics/btad219
DOI: 10.1093/bioinformatics/btad219
Metrics:
Pibiri G. E., Shibuya Y., Limasset A.
Motivation: Minimal perfect hashing is the problem of mapping a static set of n distinct keys into the address space {1, ... , n} bijectively. It is well-known that n log2(e) bits are necessary to specify a minimal perfect hash function (MPHF) f, when no additional knowledge of the input keys is to be used. However, it is often the case in practice that the input keys have intrinsic relationships that we can exploit to lower the bit complexity of f. For example, consider a string and the set of all its distinct k-mers as input keys: since two consecutive k-mers share an overlap of k - 1 symbols, it seems possible to beat the classic log2(e) bits/key barrier in this case. Moreover, we would like f to map consecutive k-mers to consecutive addresses, as to also preserve as much as possible their relationship in the codomain. This is a useful feature in practice as it guarantees a certain degree of locality of reference for f, resulting in a better evaluation time when querying consecutive k-mers.Results: Motivated by these premises, we initiate the study of a new type of locality-preserving MPHF designed for k-mers extracted consecutively from a collection of strings. We design a construction whose space usage decreases for growing k and discuss experiments with a practical implementation of the method: in practice, the functions built with our method can be several times smaller and even faster to query than the most efficient MPHFs in the literature.Code Availability: https://github.com/jermp/lphashData Availability: https://zenodo.org/record/7239205Source: Bioinformatics (Oxf., Online) 39 (2023): i534–i543. doi:10.1093/bioinformatics/btad219
DOI: 10.1093/bioinformatics/btad219
Metrics:
See at:
academic.oup.com | ISTI Repository | ISTI Repository | CNR ExploRA
2023
Conference article
Restricted
A geometric framework for query performance prediction in conversational search
Faggioli G., Ferro N., Muntean C. I., Perego R., Tonellotto N.
Thanks to recent advances in IR and NLP, the way users interact with search engines is evolving rapidly, with multi-turn conversations replacing traditional one-shot textual queries. Given its interactive nature, Conversational Search (CS) is one of the scenarios that can benefit the most from Query Performance Prediction (QPP) techniques. QPP for the CS domain is a relatively new field and lacks proper framing. In this study, we address this gap by proposing a framework for the application of QPP in the CS domain and use it to evaluate the performance of predictors. We characterize what it means to predict the performance in the CS scenario, where information needs are not independent queries but a series of closely related utterances. We identify three main ways to use QPP models in the CS domain: as a diagnostic tool, as a way to adjust the system's behaviour during a conversation, or as a way to predict the system's performance on the next utterance. Due to the lack of established evaluation procedures for QPP in the CS domain, we propose a protocol to evaluate QPPs for each of the use cases. Additionally, we introduce a set of spatial-based QPP models designed to work the best in the conversational search domain, where dense neural retrieval models are the most common approaches and query cutoffs are typically small. We show how the proposed QPP approaches improve significantly the predictive performance over the state-of-the-art in different scenarios and collections.Source: SIGIR '23 - 46th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 1355–1365, Taipei, Taiwan, 23-27/07/2023
DOI: 10.1145/3539618.3591625
Project(s): SoBigData-PlusPlus
Metrics:
Faggioli G., Ferro N., Muntean C. I., Perego R., Tonellotto N.
Thanks to recent advances in IR and NLP, the way users interact with search engines is evolving rapidly, with multi-turn conversations replacing traditional one-shot textual queries. Given its interactive nature, Conversational Search (CS) is one of the scenarios that can benefit the most from Query Performance Prediction (QPP) techniques. QPP for the CS domain is a relatively new field and lacks proper framing. In this study, we address this gap by proposing a framework for the application of QPP in the CS domain and use it to evaluate the performance of predictors. We characterize what it means to predict the performance in the CS scenario, where information needs are not independent queries but a series of closely related utterances. We identify three main ways to use QPP models in the CS domain: as a diagnostic tool, as a way to adjust the system's behaviour during a conversation, or as a way to predict the system's performance on the next utterance. Due to the lack of established evaluation procedures for QPP in the CS domain, we propose a protocol to evaluate QPPs for each of the use cases. Additionally, we introduce a set of spatial-based QPP models designed to work the best in the conversational search domain, where dense neural retrieval models are the most common approaches and query cutoffs are typically small. We show how the proposed QPP approaches improve significantly the predictive performance over the state-of-the-art in different scenarios and collections.Source: SIGIR '23 - 46th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 1355–1365, Taipei, Taiwan, 23-27/07/2023
DOI: 10.1145/3539618.3591625
Project(s): SoBigData-PlusPlus
Metrics:
See at:
dl.acm.org | CNR ExploRA
2023
Journal article
Open Access
Parallel and external-memory construction of minimal perfect hash functions with PTHash
Pibiri G. E., Trani R.
A function is a minimal perfect hash function for a set of size , if bijectively maps into the first n natural numbers. These functions are important for many practical applications in computing, such as search engines, computer networks, and databases. Several algorithms have been proposed to build minimal perfect hash functions that: scale well to large sets, retain fast evaluation time, and take very little space, e.g., 2 - 3 bits/key. PTHash is one such algorithm, achieving very fast evaluation in compressed space, typically many times faster than other techniques. In this work, we propose a new construction algorithm for PTHash enabling: (1) , to either build functions more quickly or more space-efficiently, and (2) , to scale to inputs much larger than the available internal memory. Only few other algorithms in the literature share these features, despite of their practical impact. We conduct an extensive experimental assessment on large real-world string collections and show that, with respect to other techniques, PTHash is competitive in construction time and space consumption, but retains 2 - 6× better lookup time.Source: IEEE transactions on knowledge and data engineering (Online) (2023). doi:10.1109/TKDE.2023.3303341
DOI: 10.1109/tkde.2023.3303341
Metrics:
Pibiri G. E., Trani R.
A function is a minimal perfect hash function for a set of size , if bijectively maps into the first n natural numbers. These functions are important for many practical applications in computing, such as search engines, computer networks, and databases. Several algorithms have been proposed to build minimal perfect hash functions that: scale well to large sets, retain fast evaluation time, and take very little space, e.g., 2 - 3 bits/key. PTHash is one such algorithm, achieving very fast evaluation in compressed space, typically many times faster than other techniques. In this work, we propose a new construction algorithm for PTHash enabling: (1) , to either build functions more quickly or more space-efficiently, and (2) , to scale to inputs much larger than the available internal memory. Only few other algorithms in the literature share these features, despite of their practical impact. We conduct an extensive experimental assessment on large real-world string collections and show that, with respect to other techniques, PTHash is competitive in construction time and space consumption, but retains 2 - 6× better lookup time.Source: IEEE transactions on knowledge and data engineering (Online) (2023). doi:10.1109/TKDE.2023.3303341
DOI: 10.1109/tkde.2023.3303341
Metrics:
See at:
ISTI Repository | ieeexplore.ieee.org | CNR ExploRA
2023
Journal article
Open Access
Semantic enrichment of mobility data: a comprehensive methodology and the MAT-BUILDER system
Lettich F., Pugliese C., Renso C., Pinelli F.
The widespread adoption of personal location devices, the Internet of Mobile Things, and Location Based Social Networks, enables the collection of vast amounts of movement data. This data often needs to be enriched with a variety of semantic dimensions, or aspects, that provide contextual and heterogeneous information about the surrounding environment, resulting in the creation of multiple aspect trajectories (MATs). Common examples of aspects can be points of interest, user photos, transportation means, weather conditions, social media posts, and many more. However, the literature does not currently provide a consensus on how to semantically enrich mobility data with aspects, particularly in dynamic scenarios where semantic information is extracted from numerous and heterogeneous external data sources. In this work, we aim to address this issue by presenting a comprehensive methodology to facilitate end users in instantiating their semantic enrichment processes of movement data. The methodology is agnostic to semantic aspects and external semantic data sources. The vision behind our methodology rests on three pillars: (1) three design principles which we argue are necessary for designing systems capable of instantiating arbitrary semantic enrichment processes; (2) the MAT-Builder system, which embodies these principles; (3) the use of an RDF knowledge graph-based representation to store MATs datasets, thereby enabling uniform querying and analysis of enriched movement data. We qualitatively evaluate the methodology in two complementary example scenarios, where we show both the potential in generating interesting and useful semantically enriched mobility datasets, and the expressive power in querying the resulting RDF trajectories with SPARQL.Source: IEEE access 11 (2023): 90857–90875. doi:10.1109/ACCESS.2023.3307824
DOI: 10.1109/access.2023.3307824
Project(s): MobiDataLab, MASTER , SoBigData-PlusPlus
Metrics:
Lettich F., Pugliese C., Renso C., Pinelli F.
The widespread adoption of personal location devices, the Internet of Mobile Things, and Location Based Social Networks, enables the collection of vast amounts of movement data. This data often needs to be enriched with a variety of semantic dimensions, or aspects, that provide contextual and heterogeneous information about the surrounding environment, resulting in the creation of multiple aspect trajectories (MATs). Common examples of aspects can be points of interest, user photos, transportation means, weather conditions, social media posts, and many more. However, the literature does not currently provide a consensus on how to semantically enrich mobility data with aspects, particularly in dynamic scenarios where semantic information is extracted from numerous and heterogeneous external data sources. In this work, we aim to address this issue by presenting a comprehensive methodology to facilitate end users in instantiating their semantic enrichment processes of movement data. The methodology is agnostic to semantic aspects and external semantic data sources. The vision behind our methodology rests on three pillars: (1) three design principles which we argue are necessary for designing systems capable of instantiating arbitrary semantic enrichment processes; (2) the MAT-Builder system, which embodies these principles; (3) the use of an RDF knowledge graph-based representation to store MATs datasets, thereby enabling uniform querying and analysis of enriched movement data. We qualitatively evaluate the methodology in two complementary example scenarios, where we show both the potential in generating interesting and useful semantically enriched mobility datasets, and the expressive power in querying the resulting RDF trajectories with SPARQL.Source: IEEE access 11 (2023): 90857–90875. doi:10.1109/ACCESS.2023.3307824
DOI: 10.1109/access.2023.3307824
Project(s): MobiDataLab
, MASTER , SoBigData-PlusPlus Metrics:
See at:
ieeexplore.ieee.org | ISTI Repository | CNR ExploRA
2023
Conference article
Open Access
Predicting EV parking behaviour in shared premises
Monteiro De Lira V., Pallonetto F., Gabrielli L., Renso C.
The global electric car sales continued to exceed the expectations climbing to over 3 millions and reaching a market share of over 4%. However, uncertainty of generation caused by higher penetration of renewable energies and the advent of Electrical Vehicles (EV) with their additional electricity demand could cause strains to the power system, both at distribution and transmission levels. The present work fits this context in supporting charging optimization for EV in parking premises assuming a incumbent high penetration of EVs in the system. We propose a methodology to predict an estimation of the parking duration in shared parking premises. The final objective is estimating the energy requirement of a specific parking lot, evaluate optimal EVs charging schedule and integrate the scheduling into a smart controller. We formalize the prediction problem as a supervised machine learning task to predict the duration of the parking event before the car leaves the slot. We test the proposed approach in a combination of datasets from 2 different campus facilities in Italy and Brazil. The overall results of the models shows an higher accuracy compared to a statistical analysis based on frequency, indicating a viable route for the development of accurate predictors for sharing parking premises energy management systems.Source: BMDA 2023 - 5th International Workshop on Big Mobility Data Analytics co-located with EDBT/ICDT 2023 Joint Conference, Ioannina, Greece, 28/03/2023
Project(s): ERANet SmartGridPlus
Monteiro De Lira V., Pallonetto F., Gabrielli L., Renso C.
The global electric car sales continued to exceed the expectations climbing to over 3 millions and reaching a market share of over 4%. However, uncertainty of generation caused by higher penetration of renewable energies and the advent of Electrical Vehicles (EV) with their additional electricity demand could cause strains to the power system, both at distribution and transmission levels. The present work fits this context in supporting charging optimization for EV in parking premises assuming a incumbent high penetration of EVs in the system. We propose a methodology to predict an estimation of the parking duration in shared parking premises. The final objective is estimating the energy requirement of a specific parking lot, evaluate optimal EVs charging schedule and integrate the scheduling into a smart controller. We formalize the prediction problem as a supervised machine learning task to predict the duration of the parking event before the car leaves the slot. We test the proposed approach in a combination of datasets from 2 different campus facilities in Italy and Brazil. The overall results of the models shows an higher accuracy compared to a statistical analysis based on frequency, indicating a viable route for the development of accurate predictors for sharing parking premises energy management systems.Source: BMDA 2023 - 5th International Workshop on Big Mobility Data Analytics co-located with EDBT/ICDT 2023 Joint Conference, Ioannina, Greece, 28/03/2023
Project(s): ERANet SmartGridPlus
See at:
ceur-ws.org | ISTI Repository | CNR ExploRA
2023
Journal article
Open Access
A research infrastructure where artificial intelligence meets persons and society
Trasarti R., Genovali K., Rapisarda B.
In our complex society, the ethical use and storage of data are essential for the scientific community and institutions to build trust in citizens. SoBigData is a pan-European and cross-disciplinary Research Infrastructure on social mining and data analytics, which bases its research activities on ethics and fairness. SoBigData doesn't apply science only to the most challenging societal issues; in fact, it provides data and facilities to researchers and services to firms and public administrations to develop innovative tools and respond to societal needs. Above all, it works to create an ecosystem for data research that respects the founding principles of Europe for the benefit of the whole community.Source: ERCIM news online edition 133 (2023): 30–31.
Trasarti R., Genovali K., Rapisarda B.
In our complex society, the ethical use and storage of data are essential for the scientific community and institutions to build trust in citizens. SoBigData is a pan-European and cross-disciplinary Research Infrastructure on social mining and data analytics, which bases its research activities on ethics and fairness. SoBigData doesn't apply science only to the most challenging societal issues; in fact, it provides data and facilities to researchers and services to firms and public administrations to develop innovative tools and respond to societal needs. Above all, it works to create an ecosystem for data research that respects the founding principles of Europe for the benefit of the whole community.Source: ERCIM news online edition 133 (2023): 30–31.
See at:
ercim-news.ercim.eu | ISTI Repository | CNR ExploRA
2023
Journal article
Open Access
Social search: retrieving information in online social platforms - a survey
Amendola M., Passarella A., Perego R.
Social Search research studies methodologies exploiting social information to better satisfy user information needs in Online Social Media while simplifying the search effort and consequently reducing the time spent and the computational resources utilized. Starting from previous studies, in this work, we analyze the current state of the art of the Social Search area, proposing a new taxonomy and highlighting current limitations and open research directions. We divide the Social Search area into three subcategories, where the social aspect plays a pivotal role: Social Question&Answering, Social Content Search, and Social Collaborative Search. For each subcategory, we present the key concepts and selected representative approaches in the literature in greater detail. We found that, up to now, a large body of studies model users' preferences and their relations by simply combining social features made available by social platforms. It paves the way for significant research to exploit more structured information about users' social profiles and behaviours (as they can be inferred from data available on social platforms) to optimize their information needs further.Source: Online social networks and media 36 (2023). doi:10.1016/j.osnem.2023.100254
DOI: 10.1016/j.osnem.2023.100254
DOI: 10.48550/arxiv.2209.14369
Project(s): SoBigData-PlusPlus
Metrics:
Amendola M., Passarella A., Perego R.
Social Search research studies methodologies exploiting social information to better satisfy user information needs in Online Social Media while simplifying the search effort and consequently reducing the time spent and the computational resources utilized. Starting from previous studies, in this work, we analyze the current state of the art of the Social Search area, proposing a new taxonomy and highlighting current limitations and open research directions. We divide the Social Search area into three subcategories, where the social aspect plays a pivotal role: Social Question&Answering, Social Content Search, and Social Collaborative Search. For each subcategory, we present the key concepts and selected representative approaches in the literature in greater detail. We found that, up to now, a large body of studies model users' preferences and their relations by simply combining social features made available by social platforms. It paves the way for significant research to exploit more structured information about users' social profiles and behaviours (as they can be inferred from data available on social platforms) to optimize their information needs further.Source: Online social networks and media 36 (2023). doi:10.1016/j.osnem.2023.100254
DOI: 10.1016/j.osnem.2023.100254
DOI: 10.48550/arxiv.2209.14369
Project(s): SoBigData-PlusPlus
Metrics:
See at:
arXiv.org e-Print Archive | Online Social Networks and Media | ISTI Repository | ISTI Repository | www.sciencedirect.com | doi.org | CNR ExploRA
2023
Conference article
Open Access
A proposal for a continuum-aware programming model: from workflows to services autonomously interacting in the compute continuum
Aldinucci M., Birke R., Brogi A., Carlini E., Coppola M., Danelutto M., Dazzi P., Ferrucci L., Forti S., Kavalionak H., Mencagli G., Mordacchini M., Pasin M., Paganelli F., Torquati M.
This paper proposes a continuum-aware programming model enabling the execution of application workflows across the compute continuum: cloud, fog and edge resources. It simplifies the management of heterogeneous nodes while alleviating the burden of programmers and unleashing innovation. This model optimizes the continuum through advanced development experiences by transforming workflows into autonomous service collaborations. It reduces complexity in positioning/interconnecting services across the continuum. A metamodel introduces high-level workflow descriptions as service networks with defined contracts and quality of service, thus enabling the deployment/management of workflows as first-class entities. It also provides automation based on policies, monitoring and heuristics. Tailored mechanisms orchestrate/manage services across the continuum, optimizing performance, cost, data protection and sustainability while managing risks. This model facilitates incremental development with visibility of design impacts and seamless evolution of applications and infrastructures. In this work, we explore this new computing paradigm showing how it can trigger the development of a new generation of tools to support the compute continuum progress.Source: COMPSAC 2023 - 2023 IEEE 47th Annual Computers, Software, and Applications Conference, pp. 1852–1857, Torino, Italy, 23-30/06/2023
DOI: 10.1109/compsac57700.2023.00287
Metrics:
Aldinucci M., Birke R., Brogi A., Carlini E., Coppola M., Danelutto M., Dazzi P., Ferrucci L., Forti S., Kavalionak H., Mencagli G., Mordacchini M., Pasin M., Paganelli F., Torquati M.
This paper proposes a continuum-aware programming model enabling the execution of application workflows across the compute continuum: cloud, fog and edge resources. It simplifies the management of heterogeneous nodes while alleviating the burden of programmers and unleashing innovation. This model optimizes the continuum through advanced development experiences by transforming workflows into autonomous service collaborations. It reduces complexity in positioning/interconnecting services across the continuum. A metamodel introduces high-level workflow descriptions as service networks with defined contracts and quality of service, thus enabling the deployment/management of workflows as first-class entities. It also provides automation based on policies, monitoring and heuristics. Tailored mechanisms orchestrate/manage services across the continuum, optimizing performance, cost, data protection and sustainability while managing risks. This model facilitates incremental development with visibility of design impacts and seamless evolution of applications and infrastructures. In this work, we explore this new computing paradigm showing how it can trigger the development of a new generation of tools to support the compute continuum progress.Source: COMPSAC 2023 - 2023 IEEE 47th Annual Computers, Software, and Applications Conference, pp. 1852–1857, Torino, Italy, 23-30/06/2023
DOI: 10.1109/compsac57700.2023.00287
Metrics:
See at:
ISTI Repository | ieeexplore.ieee.org | CNR ExploRA
2023
Conference article
Open Access
GNOSIS: proactive pmage placement using graph neural networks & deep reinforcement learning
Theodoropoulos T., Makris A., Psomakelis E., Carlini E., Mordacchini M., Dazzi P., Tserpes K.
The transition from Cloud Computing to a Cloud-Edge continuum brings many new exciting possibilities for interactive and data-intensive Next Generation applications, but as many challenges. Approaches and solutions that successfully worked in the Cloud space now need to be rethought for the Edge's distributed, heterogeneous and dynamic ecosystem. The placement of application images needs to be proactively devised to reduce as much as possible the image transfer time and comply with the dynamic nature and strict requirements of the applications. To this end, this paper proposes an approach based on the combination of Graph Neural Networks and actor-critic Reinforcement Learning. The approach is analyzed empirically and compared with a state-of-the-art solution. The results show that the proposed approach exhibits a larger execution times but generally better results in terms of application image placement.Source: CLOUD 2023 - IEEE 16th International Conference on Cloud Computing, pp. 120–128, Chicago, Illinois, USA, 2-8/7/2023
DOI: 10.1109/cloud60044.2023.00022
Project(s): ACCORDION, CHARITY
Metrics:
Theodoropoulos T., Makris A., Psomakelis E., Carlini E., Mordacchini M., Dazzi P., Tserpes K.
The transition from Cloud Computing to a Cloud-Edge continuum brings many new exciting possibilities for interactive and data-intensive Next Generation applications, but as many challenges. Approaches and solutions that successfully worked in the Cloud space now need to be rethought for the Edge's distributed, heterogeneous and dynamic ecosystem. The placement of application images needs to be proactively devised to reduce as much as possible the image transfer time and comply with the dynamic nature and strict requirements of the applications. To this end, this paper proposes an approach based on the combination of Graph Neural Networks and actor-critic Reinforcement Learning. The approach is analyzed empirically and compared with a state-of-the-art solution. The results show that the proposed approach exhibits a larger execution times but generally better results in terms of application image placement.Source: CLOUD 2023 - IEEE 16th International Conference on Cloud Computing, pp. 120–128, Chicago, Illinois, USA, 2-8/7/2023
DOI: 10.1109/cloud60044.2023.00022
Project(s): ACCORDION
, CHARITY Metrics:
See at:
ISTI Repository | ieeexplore.ieee.org | CNR ExploRA
2023
Conference article
Open Access
Innovation potential of the ACCORDION platform
Carlini E., Dazzi P., Tserpes K., Blasi L., Di Girolamo M., Dober D.
The seamless utilization of resources in the cloud-edge spectrum is a key driver for innovation in the ICT sector, as it supports economic growth and strengthens the industry's competitiveness while making next-application services possible with minimal investments and disruption. In this context, the EU project ACCORDION provides an innovative three-layered architecture designed as a comprehensive solution dedicated to latency-aware applications. This paper summarizes the key technological innovations of ACCORDION, highlighting their alignment with the European agenda of the ICT sector.Source: FRAME '23 - 3rd Workshop on Flexible Resource and Application Management on the EdgeAugust 2023 - colocated with HPDC '23 - 32nd International Symposium on High-Performance Parallel and Distributed Computing, pp. 33–35, Orlando, Florida, USA, 20/06/2023
DOI: 10.1145/3589010.3594887
Project(s): ACCORDION
Metrics:
Carlini E., Dazzi P., Tserpes K., Blasi L., Di Girolamo M., Dober D.
The seamless utilization of resources in the cloud-edge spectrum is a key driver for innovation in the ICT sector, as it supports economic growth and strengthens the industry's competitiveness while making next-application services possible with minimal investments and disruption. In this context, the EU project ACCORDION provides an innovative three-layered architecture designed as a comprehensive solution dedicated to latency-aware applications. This paper summarizes the key technological innovations of ACCORDION, highlighting their alignment with the European agenda of the ICT sector.Source: FRAME '23 - 3rd Workshop on Flexible Resource and Application Management on the EdgeAugust 2023 - colocated with HPDC '23 - 32nd International Symposium on High-Performance Parallel and Distributed Computing, pp. 33–35, Orlando, Florida, USA, 20/06/2023
DOI: 10.1145/3589010.3594887
Project(s): ACCORDION
Metrics:
See at:
dl.acm.org | ISTI Repository | CNR ExploRA
2023
Conference article
Open Access
DATA7: a dataset for assessing resource and application management solutions at the edge
Carlini E., Coppola M., Dazzi P., Ferrucci L., Kavalionak H., Mordacchini M.
This paper presents a dataset on edge devices and mobility patterns to comprehensively understand user behaviour and devices workload in Edge computing environments. The dataset is built on top of a publicly available dataset of cellular tower locations to simulate Edge devices, and on user mobility trajectories generated by a state-of-the-art simulator based on real location maps in the area of the city of Pisa, Italy. The resulting dataset reports the amount of vehicles in the range of about 200 Edge devices for each step of the simulation. The dataset can be used for various applications in edge computing and mobility, most notably for assessing results on resource and application management solutions at the edge in a realistic environment.Source: FRAME '23 - 3rd Workshop on Flexible Resource and Application Management on the EdgeAugust 2023 - colocated with HPDC '23 - 32nd International Symposium on High-Performance Parallel and Distributed Computing, pp. 3–6, Orlando, Florida, USA, 20/06/2023
DOI: 10.1145/3589010.3595652
Project(s): ACCORDION
Metrics:
Carlini E., Coppola M., Dazzi P., Ferrucci L., Kavalionak H., Mordacchini M.
This paper presents a dataset on edge devices and mobility patterns to comprehensively understand user behaviour and devices workload in Edge computing environments. The dataset is built on top of a publicly available dataset of cellular tower locations to simulate Edge devices, and on user mobility trajectories generated by a state-of-the-art simulator based on real location maps in the area of the city of Pisa, Italy. The resulting dataset reports the amount of vehicles in the range of about 200 Edge devices for each step of the simulation. The dataset can be used for various applications in edge computing and mobility, most notably for assessing results on resource and application management solutions at the edge in a realistic environment.Source: FRAME '23 - 3rd Workshop on Flexible Resource and Application Management on the EdgeAugust 2023 - colocated with HPDC '23 - 32nd International Symposium on High-Performance Parallel and Distributed Computing, pp. 3–6, Orlando, Florida, USA, 20/06/2023
DOI: 10.1145/3589010.3595652
Project(s): ACCORDION
Metrics:
See at:
ISTI Repository | dl.acm.org | CNR ExploRA