39 citations · 154 across the 10 of their papers we have counts for
11 papers
Alice and the Caterpillar: A more descriptive null model for assessing data mining results
Giulia Preti, Gianmarco De Francisci Morales, Matteo Riondato
We introduce novel null models for assessing the results obtained from observed binary transactional and sequence datasets, using statistical hypothesis testing. Our null models ma…
An impossibility result for Markov Chain Monte Carlo sampling from micro-canonical bipartite graph ensembles
Giulia Preti, Gianmarco De Francisci Morales, Matteo Riondato
Markov Chain Monte Carlo (MCMC) algorithms are commonly used to sample from graph ensembles. Two graphs are neighbors in the state space if one can be obtained from the other with…
RePBubLik: Reducing the Polarized Bubble Radius with Link Insertions
Shahrzad Haddadan, Cristina Menghini, Matteo Riondato +1
The topology of the hyperlink graph among pages expressing different opinions may influence the exposure of readers to diverse content. Structural bias may trap a reader in a polar…
MCRapper: Monte-Carlo Rademacher Averages for Poset Families and Approximate Pattern Mining
Leonardo Pellegrina, Cyrus Cousins, Fabio Vandin +1
We present MCRapper, an algorithm for efficient computation of Monte-Carlo Empirical Rademacher Averages (MCERA) for families of functions exhibiting poset (e.g., lattice) structur…
ABRA: Approximating Betweenness Centrality in Static and Dynamic Graphs with Rademacher Averages
Matteo Riondato, Eli Upfal
We present ABRA, a suite of algorithms that compute and maintain probabilistically-guaranteed, high-quality, approximations of the betweenness centrality of all nodes (or edges) on…
TRIÈST: Counting Local and Global Triangles in Fully-dynamic Streams with Fixed Memory Size
Lorenzo De Stefani, Alessandro Epasto, Matteo Riondato +1
We present TRIÈST, a suite of one-pass streaming algorithms to compute unbiased, low-variance, high-quality approximations of the global and local (i.e., incident to each vertex) n…
Finding the True Frequent Itemsets
Matteo Riondato, Fabio Vandin
Frequent Itemsets (FIs) mining is a fundamental primitive in data mining. It requires to identify all itemsets appearing in at least a fraction of a transactional dataset $\mat…
Space-Round Tradeoffs for MapReduce Computations
Andrea Pietracaprina, Geppino Pucci, Matteo Riondato +2
This work explores fundamental modeling and algorithmic issues arising in the well-established MapReduce framework. First, we formally specify a computational model for MapReduce w…
Efficient Discovery of Association Rules and Frequent Itemsets through Sampling with Tight Performance Guarantees
Matteo Riondato, Eli Upfal
The tasks of extracting (top-) Frequent Itemsets (FI's) and Association Rules (AR's) are fundamental primitives in data mining and database applications. Exact algorithms for th…
The VC-Dimension of Queries and Selectivity Estimation Through Sampling
Matteo Riondato, Mert Akdere, Ugur Cetintemel +2
We develop a novel method, based on the statistical concept of the Vapnik-Chervonenkis dimension, to evaluate the selectivity (output cardinality) of SQL queries - a crucial step i…
Mining Top-K Frequent Itemsets Through Progressive Sampling
Andrea Pietracaprina, Matteo Riondato, Eli Upfal +1
We study the use of sampling for efficiently mining the top-K frequent itemsets of cardinality at most w. To this purpose, we define an approximation to the top-K frequent itemsets…