5_capitolo.tex

\chapter{Conclusion and future works}
    
We presented randomized algorithms and data structures for approximate a subgraph similarity measure, which takes into account both the internal structure of subgraphs and their interface to the rest of the network. \medskip

The proposed algorithms, $\textsc{f-samp}$ and $\textsc{f-count}$, guarantee a good efficiency and approximation (as unbiased estimators) of the Bray-Curtis index and the Frequency Jaccard index, and show good practical performance compared to a less refined baseline sampler $\textsc{base}$. In particular the steady running time of $\textsc{f-samp}$ on networks with hundreds of millions of edges suggests its usefulness as an estimator on very large networks.\medskip

A great advantage of the proposed algorithms is that they are highly parallelizable, which makes them suitable for analyzing massive datasets using today's datacenter with thousands of CPU cores running simultaneously.\medskip

As a future work, we note that the assumption that the graph is undirected with one label per node can be removed, and it would be interesting to study further similarity indexes that can be approximated with our algorithms.

\noindent

\clearpage