On Asymptotic Cost of Triangle Listing in Random Graphs Conference Paper uri icon

abstract

  • 2017 ACM. Triangle listing has been a long-standing problem, with many heuristics, bounds, and experimental results, but not much asymptotically accurate complexity analysis. To address this issue, we introduce a novel stochastic framework, based on Glivenko-Cantelli results for functions of order statistics, that allows modeling cost of in-memory triangle enumeration in families of random graphs. Unlike prior work that usually studies the O(.) notation, we derive the exact limits of CPU complexity of all vertex/edge iterators under arbitrary acyclic orientations as graph size n . These results are obtained in simple closed form as functions of the degree distribution. This allows us to establish optimal orientations for all studied algorithms, compare them to each other, and discover the best technique within each class.

name of conference

  • Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

published proceedings

  • PODS'17: PROCEEDINGS OF THE 36TH ACM SIGMOD-SIGACT-SIGAI SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS

author list (cited authors)

  • Xiao, D. i., Cui, Y. i., Cline, D., & Loguinov, D.

citation count

  • 10

complete list of authors

  • Xiao, Di||Cui, Yi||Cline, Daren BH||Loguinov, Dmitri

editor list (cited editors)

  • Sallinger, E., Bussche, J., & Geerts, F.

publication date

  • January 2017