Degree Type

Thesis

Date of Award

2017

Degree Name

Master of Science

Department

Computer Science

Major

Computer Science

First Advisor

PavanKumar Aduri

Abstract

Some of the well known streaming algorithms to estimate number of triangles in a graph stream work as follows: Sample a single triangle with high enough probability and repeat this basic step to obtain a global triangle count. For example, one such algorithm uniformly at random picks a single vertex v and a single edge e and checks whether the two cross edges that connect v to e appear in the stream. In this algorithm, the basic sampling step is repeated multiple times to obtain an estimate for the global triangle count in the input graph stream. This work, proposes a multi-sampling variant of this algorithm: Instead of randomly choosing a single vertex and edge, randomly sample multiple vertices and multiple edges and collect cross edges that connect sampled vertices to the sampled edges. We provide a theoretical analysis of this algorithm and prove that this simple modification improves upon the known space and accuracy bounds. We experimentally show that the proposed algorithm out performs several well known triangle counting streaming algorithms.

Copyright Owner

Neeraj Kavassery Parakkat

Language

en

File Format

application/pdf

File Size

39 pages

Share

COinS