Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


case1269979693.pdf (887.14 KB)

ETD Abstract Container

Abstract Header

A FRAMEWORK FOR SAMPLING PATTERN OCCURRENCES IN A HUGE GRAPH

Li, Shirong
http://rave.ohiolink.edu/etdc/view?acc_num=case1269979693

Abstract Details

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)
Computer Science
Graph; subgraph matching; occurrence estimation; occurrence sampling

Recommended Citations

Citations

  • Li, S. (2010). A FRAMEWORK FOR SAMPLING PATTERN OCCURRENCES IN A HUGE GRAPH [Master's thesis, Case Western Reserve University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=case1269979693

    APA Style (7th edition)

  • Li, Shirong. A FRAMEWORK FOR SAMPLING PATTERN OCCURRENCES IN A HUGE GRAPH. 2010. Case Western Reserve University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=case1269979693.

    MLA Style (8th edition)

  • Li, Shirong. "A FRAMEWORK FOR SAMPLING PATTERN OCCURRENCES IN A HUGE GRAPH." Master's thesis, Case Western Reserve University, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=case1269979693

    Chicago Manual of Style (17th edition)

case1269979693
419
© 2010, all rights reserved.
This open access ETD is published by Case Western Reserve University School of Graduate Studies and OhioLINK.