39 citations · 154 across the 10 of their papers we have counts for
5 papers · 1 filter
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…
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…
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…