University of Illinois Urbana-Champaign

Characterizing Accuracy and Performance Tradeoffs in Graph Sampling for Graph Property Computations

Chajed, Tej

This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.

Permalink

https://hdl.handle.net/2142/72635

Description

Title
Characterizing Accuracy and Performance Tradeoffs in Graph Sampling for Graph Property Computations
Author(s)
Chajed, Tej
Contributor(s)
Gupta, Indranil
Issue Date
2014-08
Keyword(s)
  • graph analytics
  • graph sampling
  • measurement
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.
Type of Resource
text
Language
en
Permalink
http://hdl.handle.net/2142/72635

Owning Collections

Senior Theses - Electrical and Computer Engineering PRIMARY
The best of ECE undergraduate research