Back to search

University of South Florida

Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs

Abstract

dc:description

In recent years, the popularity of graph databases has grown rapidly. This paper focuses on 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. In this paper, we propose a novel framework for constructing support measures that brings together existing minimum-image-based and overlap-graph-based support measures. Our framework is built on the concept of occurrence / instance hypergraphs. Based on that, we present two new support measures: minimum instance (MI) measure and minimum vertex cover (MVC) measure, that combine the advantages of existing measures. In particular, we show that the existing minimum-image-based support measure is an upper bound of the MI measure, which is also linear-time computable and results in counts that are close to number of instances of a pattern. Although the MVC measure is NP-hard, it can be approximated to a constant factor in polynomial time. We also provide polynomial-time relaxations for both measures and bounding theorems for all presented support measures in the hypergraph setting. We further show that the hypergraph-based framework can unify all support measures studied in this paper. This framework is also flexible in that more variants of support measures can be defined and profiled in it.

Degree

thesis:*
Name thesis:degree_name
Master of Science (M.S.)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Engineering
Grantor
University of South Florida
Year dc:date
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Meng, Jinghan
Contributors dc:contributor
  • Yicheng Tu, Ph.D.
  • Yao Liu, Ph.D.
  • Paul Rosen, Ph.D.

Subjects

dc:subject × 6

Identifiers

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

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. Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs. Thesis thesis, University of South Florida, 2017. https://digitalcommons.usf.edu/etd/6900