DegreeSketch: Distributed Cardinality Sketches on Massive Graphs with Applications

We present DegreeSketch, a semi-streaming distributed sketch data structure and demonstrate its utility for estimating local neighborhood sizes and local triangle count heavy hitters on massive graphs. DegreeSketch consists of vertex-centric cardinality sketches distributed across a set of processor...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-04
Main Author: Priest, Benjamin W
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Data structures
Distributed memory
Estimation
Graph theory
Graphs
Intersections
Neighborhoods
Sketches
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present DegreeSketch, a semi-streaming distributed sketch data structure and demonstrate its utility for estimating local neighborhood sizes and local triangle count heavy hitters on massive graphs. DegreeSketch consists of vertex-centric cardinality sketches distributed across a set of processors that are accumulated in a single pass, and then behaves as a persistent query engine capable of approximately answering graph queries pertaining to the sizes of adjacency set unions and intersections. The \(t\)th local neighborhood of a vertex is the number of vertices reachable in \(G\) from \(v\) by traversing at most \(t\) edges, whereas the local triangle count is the number of 3-cycles in which it is included. Both metrics are useful in graph analysis applications, but exact computations scale poorly as graph sizes grow. We present efficient algorithms for estimating both local neighborhood sizes and local triangle count heavy hitters using DegreeSketch. In our experiments we implement DegreeSketch using the celebrated hyperloglog cardinality sketch and utilize the distributed communication tool YGM to achieve state-of-the-art performance in distributed memory.
ISSN:2331-8422