HyperHeadTail v. 1.0

Abstract

HyperHeadTail is a streaming algorithm for estimating the degree distribution of a graph from a stream of edges using very small storage space. Our algorithm builds upon the HeadTail algorithm of Simpson, Comandur, and McGregor [14], but extends it to handle repeat edges and variable-length sliding time windows, making it suitable for application to real-world streams such as those generated by network traffic or other communication networks.