The input/output complexity of triangle enumeration
R Pagh, F Silvestri - Proceedings of the 33rd ACM SIGMOD-SIGACT …, 2014 - dl.acm.org
Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART symposium on Principles of …, 2014•dl.acm.org
We consider the well-known problem of enumerating all triangles of an undirected graph.
Our focus is on determining the input/output (I/O) complexity of this problem. Let E be the
number of edges, M< E the size of internal memory, and B the block size. The best results
obtained previously are sort E 3/2) I/Os (Dementiev, PhD thesis 2006) and O (E 2/MB) I/Os
(Hu et al., SIGMOD 2013), where sort (n) denotes the number of I/Os for sorting n items. We
improve the I/O complexity to O (E 3/2/(√ MB) expected I/Os, which improves the previous …
Our focus is on determining the input/output (I/O) complexity of this problem. Let E be the
number of edges, M< E the size of internal memory, and B the block size. The best results
obtained previously are sort E 3/2) I/Os (Dementiev, PhD thesis 2006) and O (E 2/MB) I/Os
(Hu et al., SIGMOD 2013), where sort (n) denotes the number of I/Os for sorting n items. We
improve the I/O complexity to O (E 3/2/(√ MB) expected I/Os, which improves the previous …
We consider the well-known problem of enumerating all triangles of an undirected graph. Our focus is on determining the input/output (I/O) complexity of this problem. Let E be the number of edges, M<E the size of internal memory, and B the block size. The best results obtained previously are sortE3/2) I/Os (Dementiev, PhD thesis 2006) and O(E2/MB) I/Os (Hu et al., SIGMOD 2013), where sort(n) denotes the number of I/Os for sorting n items. We improve the I/O complexity to O(E3/2/(√MB) expected I/Os, which improves the previous bounds by a factor min(√E/M),√M). Our algorithm is cache-oblivious and also I/O optimal: We show that any algorithm enumerating t distinct triangles must always use Ω(√MB) I/Os, and there are graphs for which t=Ω(E3/2). Finally, we give a deterministic cache-aware algorithm using O(E3/2/√MB) I/Os assuming M > Ec for a constant c > 0. Our results are based on a new color coding technique, which may be of independent interest.