University of Twente Student Theses


Estimating graph properties with HyperLogLog-type algorithms

Huizinga, J.J. (2019) Estimating graph properties with HyperLogLog-type algorithms.

[img] PDF
Abstract:When one is dealing with algorithms in very large networks, the main memory often becomes too small. Therefore, other techniques are necessary to analyse these graphs. Boldi and Vigna showed that vertex ball cardinality can be estimated well using HyperBall, which is based on HyperLogLog probabilistic counters. In this paper HyperEdgeball, similar to HyperBall, is created to estimate edgeball cardinality. Both algorithms are used in HyperSurplus to estimate the number of surplus edges locally, which gives good first practical results. Theory is deduced to count triangles and 4-cycles in a similar fashion, this yielded not yet in a properly performing algorithm.
Item Type:Essay (Bachelor)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics
Programme:Applied Mathematics BSc (56965)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page