Files in this item



application/pdfECE499-Su2014-chajed.pdf (2MB)Restricted to U of Illinois
(no description provided)PDF


Title:Characterizing Accuracy and Performance Tradeoffs in Graph Sampling for Graph Property Computations
Author(s):Chajed, Tej
Contributor(s):Gupta, Indranil
Subject(s):graph analytics
graph sampling
Abstract:In this thesis, we present a systematic way to characterize the tradeoffs between accuracy and cost in graph sampling. This characterization is heavily dependent on graph structure. Here we focus on vector graph properties, which consist of a value per node in the graph (e.g., PageRank, degree). We present a new technique for assessing the accuracy of a property based on the algorithm used to computer it. Next, we describe how to interpret several features of accuracy-performance tradeoff curves. Finally, we present our analysis of actual accuracy-cost curves for both real-world and synthetic graphs. Conclusions from the analysis include that the structure of the graph is more important than its scale for the purposes of sampling, and that different structures require different sampling approaches.
Issue Date:2014-08
Date Available in IDEALS:2014-12-19

This item appears in the following Collection(s)

Item Statistics