Back to search

University of South Florida

Design of Support Measures for Counting Frequent Patterns in Graphs

Abstract

dc:description

In recent years, the popularity of graph datasets has grown rapidly. Frequent subgraph mining (FSM) from graphs becomes an important subject in computer science research. In this dissertation, we study single-graph as an effective model to represent information and its related graph mining techniques. In frequent pattern mining in a single-graph setting, there are two main problems: support measure and search scheme. We study the development of support measures, which are basically functions that map a pattern to its frequency count in a database. Our work is based on the hypergraph framework using the concept of occurrence/instance hypergraphs. We present improved hardness and approximation theorems among the major support measures and a general form for minimum-image-based measures. For the purpose of guiding the development of new support measures, we present general sufficient conditions for designing new support measures in hypergraph framework, which can be applied to MNI and other support measures that are not included in the overlap graph framework. We utilize the sufficient conditions to generalize MNI and minimum instance measure (MI) for designing user-defined linear-time measures. From the sufficient conditions, we develop a new efficient polynomial-time support measure named maximum independent subedge set (MISS) measure which combines the advantages of existing measures. We also show that MISS can ll the gap between MIS and MI in computation complexity and support count. Last but not least, we present and review the experimental evaluations of the major support measures.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (Ph.D.)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Computer Science and Engineering
Grantor
University of South Florida
Year dc:date
2020

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Meng, Jinghan
Contributors dc:contributor
  • Yicheng Tu, Ph.D.
  • John Licato, Ph.D.
  • John Murray-Bruce, Ph.D.
  • Ankit Shah, Ph.D.
  • Feng Cheng, Ph.D.

Subjects

dc:subject × 4

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.usf.edu/etd/9015

Chain of custody

source
Harvested from
University of South Florida
Base URL
digitalcommons.usf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Meng, Jinghan. Design of Support Measures for Counting Frequent Patterns in Graphs. Dissertation thesis, University of South Florida, 2020. https://digitalcommons.usf.edu/etd/9015