Search ETDs:
A FRAMEWORK FOR SAMPLING PATTERN OCCURRENCES IN A HUGE GRAPH
Li, Shirong

2010, Master of Sciences, Case Western Reserve University, EECS - Computer and Information Sciences.
In many applications, e.g., computational biology, software engineering, social networks, etc., a large amount of data can be represented as huge graphs. Discovery of occurrences of small patterns in these graphs is an important task. The number of pattern occurrences can be very large, which leads to two potential problems: 1) the execution time required to find all occurrences may be very long; 2) it may be very time consuming for end users to process the discovered occurrences. In addition, many applications do not require the discovery of all occurrences; a random sample is sufficient. In this paper, we propose the SALTY framework which can find random samples according to four different definitions of "randomness". It can not only reduce the execution time significantly, but it also produces results closely representing the distribution of all occurrences. Lastly, real and synthetical data sets are utilized to demonstrate the effectiveness and efficiency of the SALTY framework.
Jiong Yang (Committee Chair)
Andy Podgurski (Committee Member)
Soumya Ray (Committee Member)

Recommended Citations

Hide/Show APA Citation

Li, S. (2010). A FRAMEWORK FOR SAMPLING PATTERN OCCURRENCES IN A HUGE GRAPH. (Electronic Thesis or Dissertation). Retrieved from https://etd.ohiolink.edu/

Hide/Show MLA Citation

Li, Shirong. "A FRAMEWORK FOR SAMPLING PATTERN OCCURRENCES IN A HUGE GRAPH." Electronic Thesis or Dissertation. Case Western Reserve University, 2010. OhioLINK Electronic Theses and Dissertations Center. 28 Apr 2015.

Hide/Show Chicago Citation

Li, Shirong "A FRAMEWORK FOR SAMPLING PATTERN OCCURRENCES IN A HUGE GRAPH." Electronic Thesis or Dissertation. Case Western Reserve University, 2010. https://etd.ohiolink.edu/

Files

case1269979693.pdf (887.14 KB) View|Download